N-gram による検索エンジン

すでに使い古された感のある N-gram で、解説記事もたくさん載っておりますが、他の検索エンジンテクニックとの比較を行うため、あえてここから触れたいと思います。

N-gram とは

文字列を連続する２つ以上の文字 tuple に分解し、その出現位置を転置行列に記録することで検索速度を重視した検索エンジンテクニックです。

一方、索引を作成するのに多少時間がかかります。

転置行列の作り方

転置行列とは

転置行列とは、文字 tuple を入力とし、ドキュメント番号と出現位置を出力とする索引情報を含むファイルです。

tuple 数が 2 の場合（bi-gram）で説明すると、例えば、index.html に「TeqStock.tokyoにようこそ！」という文があったとすると、まず文字列を ('T', 'e'), ('e', 'q'), ('q', 'S'), ('S', 't')... という tuple があったとして、その出現位置を記録します。
この例では、{('T', 'e'):[0], ('e','q'):[1], ('q', 'S'):[2], ('S', 't'):[3], ...}となります。複数出現する tuple (例えば ('t', 'o')) では出現位置も複数記録することに注意してください。

転置行列のフォーマット

転置行列は非常に大きくなるため、検索が簡単にできるように固定フォーマットを用います。一般的には、以下のような最適化を行います。

ドキュメント番号の採用	毎回ドキュメント名が出てくること、ドキュメント名が不定長であることによる実装の煩雑さを避けるため、各ドキュメントに番号を振り、それを転置行列に記録するのが通例です。
ドキュメント番号による昇順ソート	転置行列内の各要素では、ドキュメント番号について昇順にリスト化します。これにより、目的の検索木のカットを実装することが可能となります。
出現位置による昇順ソート	ドキュメント番号による昇順ソートと同じ理由で、出現位置についても昇順にリスト化します。

転置行列は、python 風に書くと、[(c0, c1):[(d0, [a0, a1, ...]), ...],..] という内容を持ったファイルです。サンプルの実装では、LTV フォーマットになって、

[長さ1:4bytes][c0:4bytes][c1:4bytes][長さ2:4bytes][d0:4bytes][a0:4bytes]...

と記述されています。ここで、長さ1は自身を含まないリストのバイト数、c0, c1 は出現した文字(UCS4フォーマット)、、長さ2は自身を含まない出現位置リストのバイト数、d はドキュメント番号、a0 は出現位置となっています。
それぞれのリストの最後は L=0 で表現します。なお、数値表現はリトルエンディアンです。

例えば、先程の例だと index.html のドキュメント番号が 0 ならば

18 00 00 00 54 00 00 00 6f 00 00 00 08 00 00 00 00 00 00 00 00 00 00 00 ...

となっていきます。(詳細は実装例を見てください。)

検索の実行

検索は入力文字を tuple に分解します。ちなみに tuple 以下の文字数が入力された場合は検索できません。例えば 'tokyo' を検索したい場合、('t', 'o'), ('o', 'k'), ... と分解します。

まず ('t', 'o') の転置行列を索引すると、この tuple を含むドキュメントと出現位置の集合が得られます。ない場合はどのドキュメントにも文字列が含まれなかったことを意味するので、検索を終了します。
次に ('o', 'k') の転置行列を索引しますが、このとき、出現位置が ('t', 'o') の出現位置 + 1 であるものを拾い上げていきます。２つの出現位置がこの関係にあるものがない場合は 'tok' という文字列が含まれなかったことを意味するので、検索を終了します。

全ての検索文についてこの操作を行い、残った集合

[(d0', [a0',...]), ...]

が検索結果となります。

N-gram 検索エンジンの実装例

アーカイブの "ngram" フォルダに実装があります。

scrayping.py

https://www.teqstock.tokyo/ の記事を取得し、転置行列を作成します。
作成されるファイルは３つあります。

search_hash.bin	2つの文字からなる tuple から 8 ビットの数値を算出するハッシュテーブルです。計算値は h = (ord(c0) & 255) ^ ((ord(c1) + 11) & 255 となります。
search_classify.bin	転置行列本体で、実態は以下のフォーマットを持つバイナリファイルです。フォーマットはすでに記述しました。ただし、実装ではドキュメント番号ではなく、search_docs.bin ファイルのオフセットを格納しています。
search_docs.bin	全ての HTML ファイル１つにまとめたファイルで、以下のフォーマットを持ちます。 [link長さ(2bytes)][link][title長さ(2bytes)][title][body長さ(2bytes)][body]... ここで link は URI の path 部分、title は title タグの中身、body は body タグの中身からタグを全て取り除いた文字列を指します。

search.php

search_engine.php を使うためのラッパーで、値の設定及び結果の解釈を行います。

search_engine.php

search という関数が検索エンジンの実質的な部分で、文字列を受け取ったら tuple に分解して検索を実行します。結果をハイパーリンク付きの文字列として返します。
UCS4 を使うために若干トリッキーな扱いをしています。