自作全文検索エンジン

伝えたいこと

• 検索エンジン自作入門という本でwiserという検索エンジンをCで作成されているので、これを参考にgoで検索エンジンを作成した。
• 自作しているの中で面白かったポイント。

どうして自作したのか

1. 検索システムの仕組みを理解したかった
2. 検索システムの仕組みを理解するためには自分で作ってみるのが一番
3. 他の人が作ったものを使うのは楽だけど、自分で作ることで自分の中に落とし込むことができる
4. 「検索エンジン自作入門」という本があったので
5. 今後のOSS活動の前段として

コード

search-my-wiser
readmeに動作方法を記載しています。

システム構成

wikipediaの日本語の記事を登録してマッチング検索する。

インデクシング

文書と文章から作成した転置インデックスを登録する処理を行う。
登録する文章はwikipediaの日本語記事で、タイトルと記事の内容をドキュメント管理へ登録する。

検索

検索クエリから記事を検索する。検索の対象は記事の内容。

ドキュメント管理

記事の情報とインデックスを管理する。インデックスはトークンごとのポスティングリストを持つ。
今回はドキュメント管理は実装しておらずmysqlにお任せ。

転置インデックス

一般的な転置インデックスの構成はこのようになります。

次に、転置インデックスのコード上の構成を示します。
InverseIndexValueが1つのトークンとポスティングリストの情報を持つ。Postingsはトークンごとの文書内の出現位置と総出現回数の情報を持つ。

実装内容

機能ごとに処理の詳細を説明する。

インデクシング

• 記事のタイトルと内容を登録する

• ドキュメントの文章をn-gramを用いてトークンへ分解する
  n=2の場合の　検索勉強会の場合は　検索|索勉|勉強|強会|会のように分解される。

• ポスティングリストを作成する
  ポスティングリストはドキュメントごとのトークンの出現位置と出現回数を持つ。

• 作成したポスティングリストをミニ転置インデックスにマージする
  ミニ転置インデックスは1つのドキュメントに対するポスティングリストの作成が終わるたびにマージされる。

  例えば、検索楽と検索辛という内容の記事を登録する場合のミニ転置インデックスの様子を示す。

  1.検索楽がトークン分割される

  出現位置	トークン
  1	検索
  2	索楽
  3	楽

  2.ミニ転置インデックスに登録される

  トークン	ドキュメント数	ドキュメントID	ポスティングリスト
  検索	2	1	[1]
  索楽	1	1	[2]
  楽	1	1	[3]

  3.検索辛がトークン分割される

  出現位置	トークン
  1	検索
  2	索楽
  3	辛

  4.ミニ転置インデックスにマージされる

  トークン	ドキュメント数	ドキュメントID	ポスティングリスト
  検索	2	1	[1]
  _	_	2	[1]
  索楽	1	1	[2]
  楽	1	1	[3]
  索辛	1	2	[2]
  辛	1	2	[3]

• ミニ転置インデックスが特定の閾値を超えた場合にストレージへ登録する
  先ほど登録したミニ転置はメモリ上にあるのでストレージ（今回はmysql）へ保存する。
  閾値としてドキュメントの登録回数が一定を超えた場合に登録するようにした。
  I/Oの削減効果がある。

検索

• 検索クエリをn-gramを用いてトークンへ分解する
  インデクシングの時と同様だが、n未満となるトークンを検索では利用しないようにした。

• 対象のトークンに紐づくポスティングリストを取得する
  mysqlからトークンをキーにポスティングリストを取得する。

• 取得したポスティングリストをドキュメント数(トークンを含むドキュメントの数)で昇順にソートしておく
  ソートの理由は検索を効率化するためであり後ほど説明する。

• マッチング検索を行う
  検索クエリの分割と捜査対象のポスティングリストを取得して、準備が整ったのでマッチング検索の処理を例を交えて説明する。

  下記の4つのインデックスが登録されており、
  ドキュメントID：1

  出現位置	トークン
  1	検索
  2	索楽
  3	楽し
  4	しい
  5	い

  ドキュメントID：2

  出現位置	トークン
  1	索勉
  2	勉強
  3	強辛
  4	辛い
  5	い

  ドキュメントID：3

  出現位置	トークン
  1	索勉
  2	勉強
  3	強楽
  4	楽し
  5	しい
  6	い

  ドキュメントID：4

  出現位置	トークン
  1	検索
  2	索勉
  3	勉強
  4	強楽
  5	楽し
  6	しい
  7	い

  検索クエリに検索勉強を入力した場合検索|索勉|勉強と分解されるので、取得したポスティングリストはこのようになる。

  トークン	ドキュメント数	ドキュメントID
  検索	2	1
  _	_	4
  索勉	3	2
  _	_	3
  _	_	4
  勉強	3	2
  _	_	3
  _	_	4

  このポスティングリストの中で共通のドキュメントIDを持つものが検索結果の候補だが、愚直に捜査していくのは良くなさそう。実際に検索を導入したいケースを考えてみると数件のドキュメントから対象を見つけたいわけではなく、大量のドキュメントの中から捜査することになる。
  そこで、先ほどのドキュメント順にポスティングリストをソートした処理が効いてくる。ドキュメントIDの1を起点に他のトークンにも1のドキュメントがないか確認する。他のドキュメントに存在しないことがわかったので、次の4のドキュメントを調査する。その際他のトークンの操作位置は4以降から始めることができるので、3の確認がスキップされる。つまり、ドキュメント出現数が少ない順番で捜査をすることで、以降のポスティングリストは捜査不要なドキュメントをスキップすることができる。

• フレーズ検索を行う
  先ほどまでの処理では検索結果の候補を見つけている。フレーズとして検索したい場合はポスティングリストの中のドキュメント中のトークンの出現位置の情報を使って、フレーズであるかを判定する必要がある。

  出現位置も含めたポスティングリストを示す。

  トークン	ドキュメント数	ドキュメントID	出現位置
  検索	2	1	[1]
  _	_	4	[1]
  索勉	3	2	[1]
  _	_	3	[1]
  _	_	4	[2]
  勉強	3	2	[2]
  _	_	3	[2]
  _	_	4	[3]

  検索|索勉|勉強を見つけたいので、検索クエリに対する出現順番とトークンの出現位置が相対的に一致しているかを確認する。検索候補のIDは4でありそれぞれのトークンの出現位置は、検索が1、索勉が2、勉強が3となる。これは検索クエリの出現位置と相対的に（例が悪く絶対的に一致していますが）等しいのでフレーズとしてもマッチしていることがわかる。ドキュメントID4の中身が検索の勉強会で索勉の場合は出現位置が検索が1、索勉が8、勉強が4となるのでフレーズあるとは認識されない。

• スコアを計算する
  検索結果の一覧を絞り込むことができたら、どの結果が検索クエリとの適合率が高いかを元に並べ替えを行う必要があります。TF-IDFを用いたシンプルな評価を行なっている。

今回実装しなかったけど気になること

• キャッシュ管理
  何も実装せずにOS任せだったがSolrやElasticsearchでも１種類だけではなく、さまざまな種類のキャッシュを実装している。
• データレイアウト
  mysqlを使っただけだが、一般的な検索エンジンは高速化のために独自のレイアウトを採っているのでその構造や高速化の手法を検証する。
• データ圧縮
  実際にはポスティングリストのデータ量は非常に大きくなるため、圧縮するのが必須の要件になるではないかと思う。OSSでどんなことを行なっているのか調査してみたい。

最後に

手を動かしながら理解を進めたことで、実務で検索エンジンの一部の機能を利用する場合にある程度予想した上で検証し確認できるようになったことです。
今回は本当に基礎的な仕組みの実装しただけで、商用で稼働している検索エンジンはたくさんの機能を有しているので、今後は面白い機能にスポットを当てて解析・解説までできればいいなと思っています。