辞書アプリの改良：部分一致（１）

部分一致

これまでは、辞書のインデックスを前方一致で検索していたが、ここでは辞書アプリの部分一致検索対応を行う。
辞書のインデックスファイルは最初からデータの順序が辞書順になっていることを前提にしてきた。インデックスが辞書順にならんでいるため、前方一致の検索結果も全てインデックスファイル上で連続した位置にあることが保証されていた。
部分一致検索では、検索結果のインデックスがインデックスファイル上のどこにあるか分からなくなる。そこで検索の仕方を考え直す必要がある。

ここでは、各インデックスを文書と見なし、それらの文書に対して全文検索を行うことで部分一致検索を実現する。
部分一致とは、対象の文書内の「部分に完全一致」すること。そのため、全文検索のためのインデックスは形態素解析ではなくN-gramで作成する。

検索エンジンを作る：連載｜gihyo.jp … 技術評論社でN-gram方式の全文検索エンジンの作成方法を解説してくれているので、まずはここを参考にN-gram方式のインデックス作成ツールを作ってみる。

バイグラム

N-gramの簡単な説明は第5回 N-gramのしくみ：検索エンジンを作る｜gihyo.jp … 技術評論社を参照。
ここではN-gramの中でも2文字の並びを見出し語にするバイグラムで辞書インデックスのインデックス（メタインデックス）を作成する。
バイグラムでは文字列を頭から1文字ずつずらしながら2文字切り出して見出し語を作成する。
例えば

あいしてるよ、ちゅっちゅっ

という文字列からは

あい
いし
して
てる
るよ
よ、
、ち
ちゅ
ゅっ
っち
ちゅ
ゅっ

という見出し語が取得できる。

1文字の扱い

検索キーが1文字の場合、どうするべきか？
方法としては

完全一致検索にする
部分一致検索にする
前方一致検索にする

部分一致だと検索キーがひらがなやアルファベットの場合、ヒットする辞書インデックスが多くなりすぎる恐れがある。
前方一致だと検索結果数は妥当な数になるが、2文字以上の場合と検索方法を変えなくてはならないだろう。
完全一致の場合、バイグラムのメタインデックスを少しだけ工夫すれば、2文字以上の検索と同様に扱えそう。
ということで、今回は検索キーが1文字の場合は完全一致検索とする。

これを実現するためには、メタインデックスを次のようにすればよい。

辞書インデックスが1文字の場合: 見出し語は1文字
辞書インデックスが2文字の場合: 見出し語は全て2文字

メタインデックスの形式

N-gramの転置インデックスでは、見出し語の他にその見出し語を持つ文書の文書IDと、その文書の中での見出し語の出現位置(offset)を持つ。
この辞書アプリのメタインデックスでは、文書IDとして辞書インデックスのインデックスファイル上の出現位置（offset）とインデックスの長さ(length)の組を使う。

1つのメタインデックスの形式は以下の通り。

1~12バイト	見出し語
13~16バイト	辞書インデックスoffset
17~20バイト	辞書インデックスlength
21~24バイト	見出し語offset

メタインデックスファイルは、全てのメタインデックスを見出し語、辞書インデックスoffset、見出し語offsetの順でソートし、連結した固定長ファイルとする。

Random Note

辞書アプリの改良：部分一致（１）

関連エントリ

部分一致

バイグラム

1文字の扱い

メタインデックスの形式