検索エンジンチームの宮崎です。
今日は、Solr内部でも使用されている全文検索アルゴリズムの転置インデックスについて話をしようと思います。
転置インデックスの仕組みについてざっくり理解したい人の手助けになれば幸いです。
全文検索アルゴリズム
全文検索の方法として大まかに 「grep型」と「インデックス型」があります。
多くの検索エンジンや全文検索ライブラリでは、インデックス型が使われています。
これはgrep型が都度すべての文書を検索するのに対して、インデックス型はその名の通り索引を用いて効率的に検索を行うことができるためです。
インデックスのアルゴリズムもいくつもありますが、今回は apache/solr・apache/luceneでも使用されている転置インデックスについて、簡単な例を用いて解説しようと思います。
今回は転置インデックスを使用した簡単な例として、「google/codesearch」を使用します。
転置インデックス関連の基礎知識
実際の例を見ながら説明する前に、説明する上で必要な基礎知識について触れておきます。
ポスティングリスト
ポスティングリストとは、辞書の各単語がどの文書に出現するかを保存したものです。
キーを単語、値を文書の配列とした連想配列をイメージするとわかりやすいかと思います。
検索を行う際は検索クエリに含まれる単語ごとにポスティングリストを取得し、その積集合を取ることで検索クエリに含まれる単語を含んだ文書を取得することができます。
以下のようなポスティングリストがあった場合、「search」の単語が含まれているのは「doc1, doc2, doc3」であることがわかります。
「search」「engine」の両方の単語が含まれているのは「doc1, doc2, doc3」と「doc1, doc5」の積集合なので、「doc1」のみとなることがわかります。
このように、単語に対して文書が保存されているものを文書レベルのポスティングリストと呼びます。
search: doc1,doc2,doc3 searcher: doc1,doc2,doc3,doc4 engine: doc1,doc5 ...
ただし、「search engine」のように連続している単語を検索する、フレーズ検索を行う場合はどの文書に出現するかだけではなく、出現する位置も同時に保存する必要があります。
このように出現する位置も保存されているものを単語レベルのポスティングリストと呼びます。
検索を行う際は、検索クエリに含まれる単語ごとにポスティングリストを取得し、その積集合を取り、取得した文書の出現位置が「search engine」のように隣り合っていものだけを取り出すことでフレーズ検索を行うことができます。
実際の転置インデックスの中身
それでは、codesearchのインデックスの中身を実際に追っていきましょう。 Index構造体の中身がほぼそのままインデックスファイルに対応します。ファイルの構造は以下のようになっており、バイナリフォーマットで保存されています。
index format:
"csearch index 1\n" # magic
list of paths
list of names
list of posting lists
name index
posting list index
offset of path list # 4bytes
offset of name # 4bytes
offset of posting lists # 4bytes
offset of name index # 4bytes
offset of posting list index # 4bytes
"\ncsearch trailer\n" # trailer magic
それぞれの項目について説明していきます。
list of paths は、ファイル名もしくはディレクトリ名が、NULL終端(\x00)で保存されています。 空文字で終了します。インデックス作成の際に指定したパスが保存されます。
list of names は、ファイル名がNULL終端(\x00)で保存されています。ファイルにはそれぞれファイルIDが割り当てられており、ファイルID順にソートされています。空文字で終了します。実際のファイル一つ一つの名前が格納されています。
list of posting lists は、ポスティングリストがtrigramとファイルIDの差分のペアで保存されています。ファイルIDは32-bitの整数で表現されていますが、全てをそのままエンコードすると無駄が大きくなるので、ファイルIDの差分であれば大体小さい値になり、効率的にエンコードできることを利用するため、ファイルIDの差分を保存しています。
詳細が気になる方は https://pkg.go.dev/encoding/binary のuvarintについて見てみてください。
name index は、ファイルIDに対応する名前へのオフセットが保存されています。名前は可変長なのでファイルIDに対応する名前を探索する際には線形探索を行う必要があります。しかしオフセットを持つことによって固定長のデータになるため、name index のファイルID*4のオフセットの場所を参照するだけで、名前への参照を取得することができるので探索する必要がありません。
posting list index は、単語に対応するドキュメントの数と実際のポスティングリストへのオフセットが保存されています。ポスティングリストは可変長ですが、このように持つことによってポスティングリストインデックスが固定長となるので、検索時に検索クエリに含まれる単語を2分探索で効率的に取得することができます。
name index や、posting list index で使われた、オフセットを扱って固定長にすることで探索を効率的に行うことはよく行われるようです。
あとはそれぞれの項目に対するオフセットが4バイトずつ保存されています。
実際にはバイナリで保存されていますが、イメージとしては以下のような感じです。L数字 は抽象化して行数を表しています。実際のインデックスにおいては行数ではなく、オフセットが保存されています。 また、実際にはそれぞれに改行は無く、 list of pathsのようなラベルもありません。
L1: csearch index 1
list of paths:
L2: /opt/codesearch
list of names:
L3: /opt/codesearch/AUTHORS
L4: /opt/codesearch/CONTRIBUTORS
...
list of posting lists:
L30: aaa 1,2,3
L31: aab 1
L32: aac 1,2,4,5
L33: aad 1,2,3,5,6,8,9,10,11
...
name index:
L50: 0 # list of namesのオフセット(L3)からのオフセット(=0)が保存されます
L51: 1
...
posting list index:
L77: aaa 3 0 # list of posting listのオフセット(L30)からのオフセット(=0)が保存されます
L78: aab 1 1
L79: aac 4 2
L80: aad 9 3
...
offsets:
L97: L2 # list of paths
L98: L3 # list of names
L99: L30 # list of posting lists
L100: L50 # name index
L101: L77 # posting list index
csearch trailer
検索に必要な処理
転置インデックスの基本的な要素についてはこれまでで話したとおりです。
これから検索に必要な処理について見ていきます。
検索時に必要な処理をまとめると以下の処理になります。
- クエリの構築処理
- インデックスのオープン処理
- 検索処理
- ファイル名の取得
実際の検索クエリを作るために「クエリの構築処理」が必要になります。
バイナリフォーマットのインデックスをパースして、検索時に使用できる形に展開するために「インデックスのオープン処理」が必要になります。
クエリを元に、実際にインデックスから該当のドキュメントを取得するために「検索処理」が必要になります。
検索処理の結果、ファイルIDが取得されるが、実際のアプリケーションで活用できる形にするために、ファイルIDから「ファイル名の取得」ができる必要があります。
それぞれの処理について、codesearchの具体的なコードを見ていきます。
クエリの構築処理
codesearchは正規表現で検索できるように、正規表現から出現しうる文字列を trigram に変換しています。
ここも一つのトピックとして面白いですが、今回話したい転置インデックスの本質とはずれるのでここでは割愛します。
インデックスのオープン処理
インデックスのオープンではインデックスファイルのパースを行い、以降の操作に必要なそれぞれへのオフセットの取得や、オフセットの差分から必要な統計値を計算します。
インデックスのOpen時にはインデックスファイルをmmapし、ファイルの最後の部分からオフセットを順に読み出します。
オフセットはすべて4バイトで保存されているので固定サイズを指定することでオフセットを取得することができます。
検索処理
クエリの構築処理で変換した trigram を元にポスティングリストを取得します。構築したクエリはすべて trigram で表現されているため、3文字より長い文字は AND などを使って結合されています。
Hello を検索する場合は以下のようなクエリになります。
Hel AND ell AND llo
なので、"Hel", "ell", "llo" のポスティングリストを取得し、それらのドキュメントIDを AND の条件に従ってマージします。
ファイル名の取得
ファイル名は、 list of names のセクションに保存されていますがオフセットが直接はわからないので、name indexのオフセット+ファイルID*4バイト目に書かれているオフセットを元にlist of namesからファイル名を取得します。
これで検索は完了です。
おわり
実際のインデックスの中身やインデックスを用いた検索について見てきました。検索エンジンが内部でどのようなことを行っているか、より具体的にイメージできるようになれれば嬉しいです。
次回はインデックスの構築編でお会いしましょう。
