検索を作る

2021-11-15

こんにちは

どうも、僕です。
検索エンジンを自作しようとしてうまくは行きましたが、想定していた規模には耐えることができなかったという内容の記事です。
実際、パフォーマンスにこだわると厳しい点が多かったり、検索結果が帰ってこなかったりしてだいぶしんどい実装になってしまいました。
もっとうまくやる方法があったら教えてください。

今回の手法と想定する規模

今回は、転置インデックスを作成して戦います。
転置インデックスについては、 Wikipedia で以下のように説明されています。

全文検索を行う対象となる文書群から単語の位置情報を格納するための索引構造をいう。転置索引、転置ファイル、逆引き索引などとも呼ばれる。

検索対象の文字列を分離し、その出現位置をオブジェクトとして保持します。
文字（文字列）の出現位置に関してですが、色々手法があり、例として以下のような手法があります。
今回は、これの前者の n-gram という手法を使ってやってみました。

n-gram
- 特定のサンプルからのn個の連続したシーケンス
- 今回は2-gramで分割した
- たくりんとん だったら、['たく', 'くり', 'りん', 'んと', 'とん'] みたいになる
形態素解析
- 単語ごとで分ける
- Wikipedia の例ではこっちが使われている

また、想定する規模は、100万レコードくらいを1秒以内にレスポンスを返すようなアプリケーションを作りたいです。（作れませんでした）

今回の実装で、1秒以内にレスポンスを返せる限界値は10000レコードくらいで、100倍強くないと潰れることがわかりました。弱い...。

実装していく

前提は以下のような感じ。

転置インデックスはインメモリで保持する
データは僕のブログの中身を「。」で区切ったものをコピペして arr.length が3000くらいの状態で検証
Express で実装

エンドポイントの作成

まずはエンドポイントを作成します。
/search?q={query} のような形でリクエストを受け取り、検索を行います。
関数の中で例外が吐かれた時に 500 を返すようにしています。

import express from 'express';
import bodyParser from 'body-parser';

const app = express();
app.listen(3001);
app.use(bodyParser.urlencoded({ extended: true }));
app.use(bodyParser.json());

app.get('/search', async (req, res, next) => {
  res.header('Access-Control-Allow-Origin', '*');
  res.header('Access-Control-Allow-Methods', 'GET');
  res.header(
    'Access-Control-Allow-Headers',
    'Content-Type, application/json'
  );

  const { q } = req.query;
  const params = q as string;

  // とりあえずもらったパラメータをそのまま返す
  try {
    res.json({
      res: params,
      status: 200,
    });
  } catch {
    res.json({
      status: 500,
    });
  }
});

転置インデックスを作成する

ここが肝です。これは本来クロールするものです。
今回は、最初のリクエストが来たときだけ、インデックスを作成し、2回目以降のリクエストの際には作成したインデックスを使用してレスポンスを返しています。
検索結果のレスポンスも可能な限りメモリ上に乗せておいて、それを返すみたいな感じにしておいた方が楽な気がしなくもないです。

n-gram の作成

最初に、n-gram（今回だと2-gramに分割）の部分を見てみます。
それはそうみたいなコードになっているのですが、文字を分割して、list に入れていきます。検索で大文字と小文字は区別する必要がないので、今回は小文字にして入れるようにしています。

const ngram = (w, n) => {
  let l = [];
  for (let i = 0; i <= w.length - n; i++) {
    l.push(w.substr(i, n).toLowerCase());
  }
  return l;
}

転置インデックスの作成

次にインデックスを作成していきます。
invertedIndex はインメモリにキャッシュしたいので関数の外で定義します。
先ほど定義した n-gram を作る関数の戻り値を取り出し、処理をします。
postingList は n番目の時のインデックスです。これを invertedIndex に加えて、key-value として持つことでインデックスを生成します。

let invertedIndex = {};
let postingList;

const createIndex = (n, text) => {
  ngram(text, 2).forEach((gram, index) => {
    if (invertedIndex[gram]) postingList = invertedIndex[gram];
    else postingList = {};

    if (postingList[n]) postingList[n].push(index);
    else postingList[n] = [index];

    invertedIndex[gram] = postingList;
  });
}

これは、以下のように呼びます。
（後で出てきますが）テキストのリストが引数として渡されているので、インデックスが存在しなかった時のみそれを1つずつ取り出してインデックスを作ってあげます。

if (JSON.stringify(invertedIndex) === '{}') {
  for (let i = 0; i < text.length; i++) {
    createIndex(i, text[i]);
  };
}

検索をする

次に、先ほど作った転置インデックスを使用して検索を行います。
第一引数の qurey にはリクエスト時にもらったクエリパラメータ、nは n-gram の n（今回は2）が入ります。
この関数の戻り値は、検索結果が格納された JSON になります。そのため、出現位置は出力しますが、実際の戻り値として使うのは文字列のリストになります。

const search = (query, n) => {
  const grams = ngram(query, n);
  let results = [];

  const searchProcess = (p, key) => {
    p.forEach(position => {
      if (query.length <= n) {
        continue;
      } else {
        for (let i = 1; i < grams.length; i++) {
          postingList = invertedIndex[grams[i]];
          if (postingList[key]) {
            if (postingList[key].includes(position + i)) {
              if (i === grams.length - 1) { 
                console.log(`${key} 番目文字列の ${position}番目の文字に発見！`);
                sentenceList.push(text[key]);
              }
          }
        }
      }
    });
  };

  underscore.each(invertedIndex[grams[0]], searchProcess); //underscorejs、繰り返しに使う
  return sentenceList;
}

ここでの手法は以下の順番になっています。

検索するワードを分割
分割されたワードの出現位置を取得
出現したら
- 分割後のリストの1番目が対象の文章に含まれてるかどうか調べる
- あったら0番目を見る
- 2番目以降もこれを繰り返す

といった感じです。

つなぎこむ

これを実行する一連の関数を定義して、最後に result を返してあげれば検索用のエンドポイントの完成です。

export const searchUsingInvertedIndex = (q: string) => {
  const data = getAllBlogPosts();
  const contentList = data.map(({ text }) => text);
  return search(q, 2);
}

あとは呼び出します。

app.get('/search', async (req, res, next) => {
  // 省略

  const sentenceList = searchUsingInvertedIndex(params);

  try {
    res.json({
      res: sentenceList,
      status: 200,
    });
  } catch {
    res.json({
      status: 500,
    });
  }
});

これで検索のエンドポイントが完成しました。
素朴な実装でしたが、インデックスを作成する際にどこを見れば良いか理解していなかったり、対応関係がわからなくなってしまったりして意外と苦労しました。

まとめ

今回、簡単な検索を実装しましたが、10000件くらいのデータなら耐えられるのですが、これがもっと増えるとパンクします。20000件を超えたあたりから怪しくなってきて、50000件くらいいくとレスポンスが来なくなりました。（待ってれば来たかも）

世の中の人間がどのようにして最適化されたものを実装しているのかわかりませんが、ちょっと物足りない気がしているのでもう少しここの部分は踏み込んで開発を続けたいなと思います。
少し古い書籍ですが、検索エンジン自作入門 ~手を動かしながら見渡す検索の舞台裏という本があるようなので、このあたりを読んで理解を深められたらなと思います。おしまい。