HTML5アドベントカレンダー向けのエントリーです。ブラウザでできることがどんどん増えています。2013年に一部で熱狂的な話題となった本の高速文字列解析の世界
ブラウザ上の検索エンジンと転置インデックスと東アジアの微妙な関係
全然調べていないので、歴史とかよくわからないのですが、僕が始めてブラウザ上で動く検索エンジンと出会ったのは、Sphinxです。SphinxはPythonで書かれたドキュメントツールです。ドキュメントツールというとJavaDocを始めとして各種あります。大きく、自然言語中心のもの(Texとか)と、APIリファレンスの生成ツール(JavaDocとかDoxygenとか)があります。自然言語中心のものはAPIの変更を手で追従しなければならず、自動生成のリファンレスは人が理解しやすい順序に構成して文章を提供するということができません。Sphinxはマークアップで書かれた中に、ソースコードから抽出したドキュメントを埋め込めるようにして両方のいいとこ取りをしていて、PDFにすると3000ページを超えるというPythonのドキュメントを支えています。Pythonだけでなく、PHP系のコミュニティやさまざまなコミュニティで使われています。
SphinxにはjQueryを使って作成されたブラウザ上で動く検索エンジンがついています。仕組みはシンプルです。Sphinxを使って文章をビルドしたら、ドキュメント中の単語をキーとして、それが含まれるドキュメント番号と段落位置の配列を持った巨大なJSONファイルを生成します。ユーザが検索すると、JSONをダウンロードして、単語から、ドキュメント番号と段落位置の配列を持ってきて、ドキュメント番号からドキュメント名とURLを生成して、リストにして表示します。Sphinxでは変換元のテキストを持っていて、これもロードして、単語周辺の文章として表示します。サーバいらずの検索エンジンです。この単語をキーとした辞書/ハッシュを転置インデックスと言います。検索エンジンのもっとも基本的なパーツです。
このシンプルな検索は東アジア系の言語ではあまり実用的になりません。欧米系の言語は単語間にスペースがあるので簡単な正規表現で単語に分けられますが日本語・中国語・韓国語はそうなってません。日本語の場合は漢字・ひらがながあるので、文字種の境界を取得すれば熟語ベースで分けるとかは可能かもしれませんが、欲しい単語にマッチしにくいだろうということは想像に難くないですよね。
東アジア系の文章を単語に区切る処理は、形態要素解析と呼ばれていて、Chasen、MeCab、kuromojiといったツールを使えばできます。サーバ用の検索エンジンはだいたいこれらのどれかが使えるようになっています。東アジア系の言語はやっかいな言語で、単語の辞書がないと単語に分けることもできません。ブラウザで日本語を快適に検索しようとすると、インデックスとは別に日本語の辞書(MeCabでよく使われるので10MB程度)をダウンロードしなければなりません。
それ以外の方法としては、n-gramという方式があります。スペースとか関係なしに、2文字、3文字ずつ区切って、それを単語と見立てて転置インデックスを作ります。これも実装がシンプルなため、オープンソースなシステムで簡単に日本語検索を可能にするために昔からよく使われている方法（僕が知っていてお世話になったことがあるものだとMojixさん作のZopeの日本語トークナイザーとか、Hyper Estraierとか）ですが、インデックスがもとの文章の倍以上に大きくなる欠点がありブラウザ用の仕組みとして使うには実用的ではありません。新聞記者みたいな揺れのないしっかりとした文章を書く自信があって、単語のリストとかを用意できれば、TinySegmenterMakerを使ってうまくやることもできそうです。これは今後トライしたいところ。
FM-index
今年、高速文字列解析の世界という素敵な本が出版されました。この本で紹介されていたのがFM-indexと呼ばれるアルゴリズムです。BW変換/ブロックソートした文章を元に検索するもので、メモリ効率の良いデータ構造のWavelet木/Wavelet行列と組み合わせて利用されます。
- 圧縮されたインデックスを使った検索では最速
- 単語に区切る必要なし(言語の辞書いらず)
- 変換元の文章がインデックスから復元できる
まさにブラウザの検索エンジンのためのアルゴリズムですよね。ちなみに、数値のオーダーとしては、Pythonのドキュメントからタグとかを抜いた文章量が10MBほど。Pythonの現在のSphinxの転置インデックスが1MBほどです。Sphinxでは表示用に元テキストを持っているので、これが10MB以上(reSTのマークアップが残っている)です。n-gramではインデックスが20MBぐらいになるのかな？あと、表示用のテキストもおそらく必要です。FM-indexを使った検索エンジンを作るにあたって、これよりも小さいサイズを目指しました。
Oktavia
できあがったのがこちらです。論文とかも読みながら実装したのですが、ベースとして利用させてもらったのが、@echizen_tmさんのC++実装のShellinfordです。ありがとうございます。
今のところ、node.js用のインデックス作成ツールと検索クライアント、ブラウザ用の検索クライアントがあります。Python版のインデックス作成ライブラリも作成中です。将来Sphinxに組み込めれば、と思っています。簡単に試すなら、-t cmdでインデックスを作成してください。検索ランタイムとインデックスがセットになったnode.js用のスクリプトが生成されます。
$ dest/oktavia-mkindex-cli -t cmd share/httpstatus.txt -o httpstatus
httpstatus.txtは、HTTPのステータスコードが含まれたテキストファイルです。上記のコマンドで、一時期流行った「HTTPのステータスコードを検索して返すプログラム」がプログラミングレスで作れてしまうわけです。話題になった時にはOktavia実装中だったのでブログエントリー公開が遅れてしまいましたが、今後似たようなムーブメントが起きたときは即座に話題に乗れます。
テスト用のHTMLがsampleフォルダに含まれているので、インデックスを作成してこのフォルダにできたものをコピーしてブラウザで表示してみてください。インデックスファイルにはbase64の文字列になったインデックスと検索ランタイム(minifyされて70kbほど)が含まれています。JSとしてvalidなファイルになっています。
使える場合はWebWorkerとして検索のランタイムとインデックスを読み込みます。検索もバックグラウンドタスクとして行われます。WebWorkerが使えない場合は、scriptタグを生成して読み込みます。XHRを使うとChromeでローカルファイルが読み込めないのですが、これなら大丈夫です。テストしてないですが、WebWorkerと、内部で使っているUint32Arrayは使えない時はレガシーな仕組みで代用するようにしているので、IEの古いバージョンでも動くはず。
また、インデックス作成ツールをちょっと改造すれば、文字にメタ情報を付与できます。例えば、この文字列はクラス名だ、とか、これはリンクされている文字だとかです。検索時にこれらの情報を表示したり、ページランクを実装してスコアを調整したり、いろいろできると思います。
Oktaviaとファイルサイズと検索時間を減らすための工夫
WaveletMatrixでは、文字をビット単位で探しに行って、マッチする文字をまとめて取得します。つまりビット数が多ければ時間がかかりますし、インデックスのサイズも大きくなります。Oktaviaでは使っている文字だけの文字コード表を内部で作って、使う文字数が少ない時はビット数を減らすようにしています。Pythonの英語ドキュメントでは123文字使われていますので、7ビットでドキュメントが格納できます。UTF-16だと16ビットなので、50%以上削減されています。Pythonの日本語翻訳でも1024文字をちょっと超えるぐらいなので11ビットでドキュメントを格納しています30%ほど節約です。あと、ビット列はゼロが多いので、(32ビット単位の配列で)ゼロに特化したランレングス符号化でちょっと小さくなるようにしています。今のところ、できあがるインデックスは6MBぐらい。gzipで転送すると考えると3MBぐらいです。ページが読み込まれた時に一緒にロードしますし、待ち時間を感じることはあまりないと思います。(Sphinxは検索ページに行った時に始めてロードするので初回待ちがある)。
今後はzip対応したいですね。小さくして、インデックスをローカルストレージに入れておくとかできればまた用途の幅が広がると思います。あと、検索結果表示時に、そのドキュメントをすべて復元しちゃっていて、そこが処理として重いので、表示される箇所だけ復元するように検索ランタイムを改善したいです。
