DBMを使った検索エンジンの作り方

キーワード検索システムとか全文検索システムとか検索エンジンとか呼ばれる仕組みの肝は転置索引とか転置インデックスとか呼ばれるデータベースである。それは、検索語をキーとして、その検索語に該当する文書のIDのリストを値とする連想配列に他ならない。つまり、検索エンジンの肝はDBMである。この記事では、転置索引の効率的な構築方法について考察する。

基本構造

検索エンジンにおいては、検索対象となる個々の文書は、「文書ID」と「語のリスト」のペアであるとみなせる。また、検索エンジンは複数の文書の集合を扱う。そうすると、文書の集合は、文書IDをキー、単語のリストを値とする、連想配列であるとみなせる。Pythonのコードで表すならこんな感じ。

documents = {
  1001: ["She", "is", "Nancy", ".", "I", "love", "her", "."],
  1002: ["This", "pen", "is", "good", ".", "I", "love", "this", "."],
  1003: ["She", "doesn't", "love", "this", "pen", "."],
}

この文書群の構造をひっくり返して、転置索引を作る。個々の語がキーとなり、それを含む文書のIDのリストが値となる。文字を小文字に正規化したり、アルファベットを含まない語は無視したりもする。

index = {
  "she": [1001, 1003],
  "is": [1001, 1002],
  "nancy": [1001],
  "i": [1001, 1002],
  "love": [1001, 1002, 1003],
  "her": [1001],
  "this": [1002, 1003],
  "pen": [1001, 1002, 1003],
  ...
}

転置索引において、個々のレコードの値として保存される文書IDのリストのことをポスティングリストと呼ぶ。ポスティングリストには文書内の該当語の位置情報やスコア情報などを含めることもあり、その辺りには検索エンジン毎の哲学が色濃く反映される。ここでは単純化のために文書IDのみを扱うこととしよう。検索時には、入力された検索語のポスティングリストを取得して、該当の文書の一覧を出せばよい。複数の検索語が入力された場合には、検索語毎に文書IDの集合を取り出し、それらの積集合か和集合を計算することになる。

転置索引の構築には時間がかかるし、構築した転置索引は複数のプロセスやマシンで共有したい。よって、転置索引のデータは検索機能を保ったままファイルに保存したい。そこでDBMが使われる。上述の連想配列の構造をそのままDBMに保存すればよい。ただし、文書IDのリストは文字列ではないので、何らかのシリアライズ処理が必要になる。文書IDが数値なのであれば、8バイトのビッグエンディアン表現を並べるのが率直だ。個々の文書IDが文字列なのであれば、適当な区切り文字を使って連結するだろう。Protocol BuffersやMessagePackやJSONでシリアライズしてもよい。

スケーラビリティ

転置索引を使った単純な検索エンジンを書くことは難しくない。それをスケールするように設計および実装するには多少の工夫が必要だ。まず、転置索引を構築する際に、全ての文書の全ての語とそのポスティングリストをメモリ上に保持することはできない。よって、作業メモリとしてオンメモリの連想配列を使いつつも、適当なタイミングでデータをファイルに吐き出すミニバッチ的な考え方が必要になる。複数台のマシンを使って分散処理を行う場合、語のハッシュ値を用いてシャーディングをした上で、個々のマシンでミニバッチ処理を行うだろう。複数のミニバッチが完了したら、その結果のファイルを適当なタイミングでマージしていく。ミニバッチで用いるオンメモリの連想配列にもポスティングリストに特化した効率的な実装が求められる。

自然文を含む文書群を対象に検索システムを構築する場合、少数の高頻度語と圧倒的多数の低頻度語を同時に扱わねばならないという問題がある。単語を出現頻度の大きい順に左から並べたなら、L字のグラフができあがる。英語だと「the」「a」「is」などが、日本語だと「は」「が」「を」などがほとんどの文書に現れるので、それらのポスティングリストは長大になる。一方で、「mohorovičić」「モホロビチッチ」みたいな低頻度語のバリエーションは無限に存在するが、その多くは頻度1だ。作業用の連想配列においても、保存用のデータベースにおいても、やたら値のサイズが大きくなる高頻度語と、値のサイズは小さいが数がやたら多い低頻度語の両方を効率的に扱う工夫が求められる。これを私は「L字頻度問題」と呼んでいる。

構築処理の概要

転置索引を構築する処理を疑似コードで俯瞰してみよう。単純化のために、分散処理はここでは考えずに、1台のみでミニバッチ処理を行う。

# ミニバッチの作業用の連想配列。
memory_index = InitializeMiniBatchIndex()
num_words_in_minibatch = 0

# 全ての文書を処理する。
for doc in GetDocuments():
  # 文書内の全ての語を処理する。
  for word in doc.words:
    # 作業用の連想配列を更新する。
    memory_index[word].append(doc.id)
    num_words_in_minibatch += 1

  # 一定の語数を処理したら、ミニバッチを終わらせる
  if num_words_in_minibatch >= MAX_WORDS_IN_MINI_BATCH:
    FlushMiniBatchIndex(memory_index)
    memory_index = InitializeMiniBatchIndex()
    num_words_in_minibatch = 0

# 全てのミニバッチが終了したら、結果のファイルをマージする
MergeMinibatchResults()

実際には、個々の文書内で異なり語の数を検出してから、異なり語ごとに処理を行なったりとか、位置情報を付与したりとかもするだろう。しかし、基本的な構造は大抵のシステムで同じだ。LuceneでもHyper EstraierでもGoogle Searchでも、検索語毎のポスティングリストをバッファリングしてからファイルに書き出すという点は同じだ。

作業用のオンメモリ連想配列

ミニバッチの中で読んだ文書群の転置索引をオンメモリの連想配列として保持する。キーは語の正規化された文字列で、値は文書IDのリストだ。これは、Pythonで言うなら collections.defaultdict(list)、C++で言うなら std::map< std::string, std::vector< uint64>> を使うと率直に表現できる。しかし、ここではもっと効率的な実装を模索したい。L字頻度問題にうまく対処するには、以下の要件を満たす必要がある。

低頻度語の多数のレコードを扱うため、個々のレコードのフットプリントを最小化する
高頻度語の巨大なポスティングリストの構築にかかる償却時間計算量をO(N)に抑える

TkrzwのオンメモリDBMがこれらの要件を満たすものだ。それが言いたくてこの記事を書いたようなものだ。ハッシュテーブルを用いたTinyDBMと、B+木を用いたBabyDBMという二つのクラスがある。その両方とも、C++/Java/Python/Rubyの各言語の標準的な連想配列よりも、時間効率と空間効率の点で優れている。

ポスティングリストの要素数が1とか2とかになる低頻度語が全ての連想配列の全てのレコードの半分以上を占める。よって、個々のレコードのフットプリントを最小化したい。TinyDBMでもBabyDBMでも、管理用のメタデータと実データ（キーと値）をシリアライズして詰めて保持することで省メモリを達成している。特にBabyDBMは複数のレコードをページ単位でまとめて扱うので、空間効率が良い。レコード毎のフットプリントの期待値は、mallocの内部データを除けば3バイト未満である。

高頻度語のポスティングリストは恐ろしい勢いで増大する。英語の「the」は40%以上の文で出現するので、ほぼ全ての文書で出現する。つまり「the」のレコードのポスティングリストはほぼ全ての文書のIDを含むことになる。「the」や「a」をストップワードとして無視することもできるだろうが、「of」や「is」はどうする。そうやって上位語を消していったら再現性が落ちてしまう。どこで線引きするにせよ、ある程度の高頻度語は処理できなければならない。

ポスティングリストを更新する処理は、連想配列の値の末尾にデータを追記していく処理に他ならない。ここで前回の記事の議論を思い出していただきたい。std::stringにしてもstd::vectorにしても、確保したメモリ領域のサイズを自前で管理して倍々に増やしていくことで拡張時の償却時間計算量をO(N)にしている。一方でそのサイズのメタデータはmallocの内部実装でも持っている冗長なものであり、レコード毎のフットプリントを8バイトも増大させてしまう。TinyDBMとBabyDBMでは毎回reallocを呼ぶことでそれを回避するとともに、確保するメモリのサイズを冪で調整して償却時間計算量がO(N)に収まるようにしている。

TkrzwのDBMのインターフェイスでは、レコードの値を取り出すGetメソッドと、レコードの値を置き換えるSetメソッドが基本となる。Appendというメソッドが全てのクラスで提供されるが、「Getで値を取り出してからその値と与えられた値を連結した結果をSetする」という処理をアトミックに行うラッパーとして実装されている。しかし、その実装だと、毎回のAppendの時間計算量は値のサイズに対してO(N)であるから、文書数Nのコーパスでの高頻度語のポスティングリストの構築にかかる時間計算量はO(N^2)になってしまう。それでは遅すぎる。よって、TinyDBMとBabyDBMでは、Appendメソッドをオーバーライドして特殊化した実装を提供する。与えられた値を既存の値のメモリ領域の末尾に直接書き込むのだ。予めreallocを呼んでからそれを行うので、末尾に十分な領域があることは保証される。

説明のために、文字列で文書IDを表してポスティングリストを作ることを考えてみよう。文書IDをタブ区切りで並べて文字列を連想配列の値にするということだ。Pythonだと以下のように書ける。

# 作業用の連想配列を構築する
memory_index = tkrzw.DBM()
memory_index.Open("", True, dbm="BabyDBM")

# 文書内の全ての語を処理する。
for word in doc.words:
  # 作業用の連想配列を更新する。
  memory_index.Append(word, str(doc.id), "\t")

ミニバッチの結果を保持するDBM

メモリには限りがあるので、一定の語数を読み込んだら、ミニバッチの連想配列の内容はファイルに吐き出して、次のミニバッチを始めることになる。複数のミニバッチの結果を後でマージする必要があるので、マージ処理に適した形式でデータを保存したい。それにもDBMが役立つ。

マージとはすなわち、複数のデータベースに存在する同一キーのレコードの値を連結して単一のレコードを作ることだ。その処理を効率的に行うには、マージソートと同じアルゴリズムを用いる。したがって、マージ対象となる複数のデータベースはキーでソート済みのレコード群を保持していることが望ましい。ソート済みのレコードを保持すると言えば、スキップリストのデータベースであり、SkipDBMクラスがそれを実装するものだ。B+木であるTreeDBMでも同じことはできるが、メモリ効率の点でSkipDBMの方が優れている。

SkipDBMのデータベースを構築するに際に、レコードがキーでソートされているならば、内部でのソートを省略することで、効率的に処理を行うことができる。ところで、ミニバッチの作業用データベースにBabyDBMを用いている場合、それはB+木なので、レコードは既にソート済みである。マジ好都合。というか、このためにBabyDBMとSkipDBMを作ったのだ。ミニバッチの連想配列の内容をDBMに書き出す実装は以下のようになる。

# 出力先のDBMを開く。
dbm = tkrzw.DBM()
dbm.Open(
  "minibatch-index-00000.tks", True, dbm="SkipDBM",
  truncate=True, insert_in_order=True).OrDie()

# イテレータを回して全レコードを書き出す。
it = memory_index.MakeIterator()
it.First()
while True:
  record = it.Get()
  if not record: break
  dbm.Set(record[0], record[1]).OrDie()
  it.Next()

# 出力先のDBMを閉じて、作業用の連想配列を初期化する。
dbm.Close().OrDie()
memory_index.Clear()

ミニバッチ結果をマージする

SkipDBMをマージする処理は簡単だ。SkipDBMのSynchronizeメソッドにマージする対象のパスをコロン区切りで指定して渡すだけで良い。その際にreducerを指定することができるが、"ReducerConcatWithTab" を指定すると、同じキーのレコードの値をタブ区切りで連結した文字列を新たな値にする。具体的には以下のようなコードになる。

# マージ対象のパスのリスト
src_paths = [
  "minibatch-index-00000.tks", "minibatch-index-00001.tks",
  "minibatch-index-00002.tks", "minibatch-index-00003.tks"
]

# 出力先のDBMを開く
merged_dbm = tkrzw.DBM()
marged_dbm.Open(
  "merged-index.tks", True, dbm="SkipDBM", truncate=True).OrDie()

# マージ処理を行う。
merge_expr = ':'.join(src_paths)
merged_dbm.Synchronize(False, merge=merge_expr,
  reducer="ReducerConcatWithTab").OrDie()

# 出力先のDBMを閉じる。
merged_dbm.Close().OrDie()

マージする際にreducerを指定しなかった場合、キーが重複した複数のレコードが保存される。DBMの多くの実装はキーが重複した複数レコードの存在を許さないが、SkipDBMは例外的に重複キーを許す。そうして作ったデータベースに自分でイテレータを回して後処理を行っても良い。

SkipDBMによるマージ処理の要点は、全てがシーケンシャルアクセスで行われることである。ランダムアクセスをしないので、ハードディスクの上にデータを置いてもスケールする。ソート済みの分割データをマージするというのはMapReduce的なバッチ処理の常套手段だ。ミニバッチの数が1000個とかを超えてファイルディスクリプタの制限が気になる場合、適当な数（16個とか64個とか）ずつマージする処理を階層的に行えばよい。

マージが完了したら、最後に検索機能の都合に合わせてデータ構造を変換する。O(1)で検索させるためにHashDBMにするのもよいし、曖昧検索などを行うためにキーだけを別ファイルに書き出すのもよいし、並列処理を行うためにファイルを分割するのもよい。

まとめ

DBMを使えば、転置索引の構築処理を簡単に書くことができる。オンメモリのB+木でミニバッチの結果をバッファリングし、それをスキップリストのデータベースに書き出し、最後にマージすればよい。この方法で、マシン一台でもかなり大規模な検索システムを作ることができる。複数のマシンに処理を分散させる場合も考え方はだいたい同じだ。

この記事をここまで読んでくれる粋狂な人がおそらく500人くらいはいるだろう。その中で10%くらいの人は、転置索引を作ってみようと思ってくれるのではないか。その中で10%くらいの人は実際に手を動かしてくれるかもしれない。もしそうなら5個くらいの検索エンジンが誕生することになり、それはライブラリ作者の冥利に尽きることだ。

おまけ：ミニバッチ用オンメモリ連想配列の効率比較

単語毎のポスティングリストを保持するためのバッファ構造としてBabyDBMが良いという主張をしたが、性能テストでそれを裏付けたい。TkrzwのTinyDBMと、TkrzwのBabyDBMと、std::unordered_map< std::string, std::string>と、std::map< std::string, std::string>の時間効率および空間効率を比較する。1000万語を読み込んでポスティングリストを作る処理にかかる時間とメモリ使用量を測定する。語の文字列はランダムに生成するが、L字頻度問題を再現するように努力した。長さを1から8までの一様乱数で決定し、個々の文字は16種類から一様乱数で決定する。結果として、異なり語の数は360万語になる。ポスティングリストには個々の語の出現に際して8バイトの数値を追記する。測定は100万語を読み込む毎に行うことで規模と性能の関係を調べる。プログラムはここに置く。

結果は以下のようになる。時間の単位は秒で、メモリ使用量の単位はMBだ。

	unique words	TinyDBM time	TinyDBM memory	BabyDBM time	BabyDBM memory	unordered_ map time	unordered_ map memory	map time	map memory
1-1000000	48129	0.7273	98.0415	1.5909	29.2931	0.4372	50.6439	1.4545	60.0662
1000001-2000000	888106	0.4805	118.4311	1.7400	53.6461	0.3652	94.5091	1.4702	109.9167
2000001-3000000	1272985	0.4805	137.8632	1.9190	79.8225	0.3651	134.5406	1.6005	155.4871
3000001-4000000	1643232	0.5011	156.7459	2.0246	100.4677	0.3984	177.3872	1.6350	204.0520
4000001-5000000	2000732	0.5114	174.4537	2.1134	123.3139	0.3971	215.9081	1.6711	247.6082
5000001-6000000	2347036	0.5267	193.8400	2.2393	148.9944	0.4057	253.1700	1.6812	290.4091
6000001-7000000	2684032	0.5316	210.9261	2.2786	169.1818	0.4294	294.1589	1.7454	336.4449
7000001-8000000	3011809	0.5485	228.8017	2.2923	188.3163	0.4361	333.1833	1.7518	380.7564
8000001-9000000	3331900	0.5748	248.6916	2.3383	209.7168	0.4478	368.1793	1.9945	420.7878
9000001-10000000	3645008	0.5585	265.0108	2.3632	229.3549	0.4566	402.6718	1.8941	460.0639

BabyDBMを推す最大の理由は、メモリ使用量が最も少ないことである。std::mapに比べると半分で済む。逆に言えば、同じメモリ使用量ならミニバッチのサイズを2倍にでき、結果的に後段のマージ処理が高速化する。一方で時間効率を見ると、この中では最下位だ。しかし、100万語で2.3秒という速度は十分に早く、ボトルネックになるようなものではない。ハッシュテーブルを使ったTinyDBMやstd::unordered_mapの方が高速なのは当然だが、それらはレコードに順序の概念がないので、マージ用のファイルに出力する際にソートする必要があり、その処理に余計に時間とメモリを食ってしまう。よって、総合的に考えてB+木であるBabyDBMが最適なのだ。Tkrzwさえ入れていればJavaやPythonやRubyからも気軽に使えるというのも良いところだ。

豪鬼メモ

一瞬千撃