Namazuの索引を理解する

検索システムを作る上で、既存のシステムを理解する必要があると思い、代表的な検索システムであるNamazu *1を勉強することにした。Namazuが前処理で作成する一連のファイルをどのように検索で利用するかをメモしておく。

まずファイルの中心となる内容を…

例として『珈琲』を検索するようすをシミュレートしてみる。

NMZ.wiを利用して、NMZ.wをバイナリサーチする。
見つかったときのNMZ.wiの位置を４分の１（NMZ.wiは4バイトで位置を保持するから）すると単語IDになる（NMZ.wでいうと行番号になる）。例として単語IDを10とする。
NMZ.iiの40バイト目（10×4）の値を読み、それをもとにNMZ.iにアクセス。
NMZ.iで『珈琲』が含まれるFIDを取得

細かい点を言えばこの後でNMZ.tを利用してそのファイルが存在するかをチェックしたりもするが、ここでは省略。さらに上記内容はソースを読んだわけではなく、データ構造から想像したことなので、全然違うかもしれない（大まかには合ってるはず）。

Namazuで参考になったこと。

FIDが出来る限り小さくなるように、『FIDをBER圧縮』して、さらに『差分のみ保持』するようにしている。BER圧縮はここでは省略するが、差分のみ保持というのは

{1, 3, 20, 23}  =>  {1, 2, 17, 3}

とすることだ。これにより、索引を小さくできるようにしている。