Oktaviaとは何か？

OktaviaはJavaScriptで書かれた全文検索エンジンです。ブラウザとnode.js上で動作します。

プロジェクトのゴールは、 Sphinx のHTML出力用の、代替の検索エンジンを作ることです。

SphinxはPythonで書かれた素晴らしいドキュメントツールです。このツールはシンプルなフォーマット(reStructuredText)のテキストを読み込み、HTMLやPDFなどのさまざまなフォーマットに変換します。このツールはプログラミング言語のリファレンスマニュアルやソフトウェアの使用方法の説明、ライブラリやAPIのドキュメントなどでよく使われています。

SphinxのHTMLジェネレータにはシンプルな組み込みの検索エンジンが搭載されています。Sphinxで作成されたHTMLドキュメントには検索窓がついており、ドキュメント全体を検索できるようになっています。これはJavaScriptで書かれており、インデックスファイルをダウンロードしてクライアントのブラウザ上で検索を行います。ドキュメントを公開する人は検索エンジンをサーバにインストールする必要はありません。 html フォルダを公開するだけで検索機能が利用できます。

現在では、数多くのHTMLのホスティングサービスが存在します。PyPI, Google Drive などがあります。また、HTML5はアプリケーションキャッシュを提供します。(Sphinxのアウトプットのような)サーバ上の検索エンジンを持たない静的なHTMLドキュメントはますます増えています。今はブラウザ上で動作する検索エンジンを作る絶好の機会です。この検索エンジンは、これらのコンテンツのユーザによりよい体験を提供します。

FM-index

このエンジンは FM-index をアルゴリズムとして使用しています。FM-indexはPaolo FerraginaとGiovanni Manziniの発明者の名前をとって名付けられました。転置インデックス方式と比べると、FM-indexには次のような長所があります:

  • 検索前に単語を分割する必要がない

    いくつかの東アジア言語は単語の境界としてスペースを使用していません。単語を分割する場合は、その言語の情報(辞書)が必要です。例えば、日本語の分かち書きツールとして有名なMeCabは大きなサイズの辞書(10MB以上)を必要とします。中国語と韓国語については専門家ではないのでよくわかりませんが、その言語の固有の知識が必要となります。転置インデックスで東アジアの言語をサポートするのは困難です。

  • インデックスファイルからオリジナルのドキュメントを復元できる

    転置インデックスはドキュメント内の単語の位置のみを記憶します。ドキュメントの一部を検索結果ページに表示させるには、インデックスファイル以外にオリジナルのファイルが必要となります。FM-indexの場合は、インデックスファイルさえあれば、単語の検索とドキュメントサンプルの表示の両方が行えます。Sphinxはこの目的のために、ドキュメントのソースを使います。ですが、Sphinxの翻訳機能を使うとソースファイルと言語が別物になります。また、ソースをエクスポートするオプションを有効にしなければなりません。

  • 圧縮インデックスファイルを使った検索アルゴリズムの中で最速

    書籍「高速文字列解析の世界」の中でこのように言われています。13年前はFM-indexはそれほど速くはなかったようですが、この13年間で高速化され続けてきました。

これらの理由により、ブラウザ上で動作する検索アルゴリズムとしてはFM-indexがベストであると考えました。より詳細の情報については ../inside_oktavia を参照してください。

検索エンジンの実装は、 @echizen_tm さんによって書かれた、C++のFM-indexライブラリの Shellinford を参照しています。このライブラリはとてもシンプルで、FM-indexを理解するにはとても良いサンプルです。