お、かなりパフォーマンスが高い！ サイト内検索を作る際にまず思いつくのがサーバサイド内での検索です。また公開情報であればGoogleの検索エンジンを使う手もあります。今回はそのどちらでもない第三の選択肢、JavaScriptによるクライアントサイドの検索エンジンです。 検索の難しさは何と言ってもインデックスの生成部分になるかと思います。良くあるのは分かち書きとn-gramだと思いますが、JavaScriptベースの検索エンジンではどちらも不向きです。そこでOktaviaではFM-Indexと言うアルゴリズムを使ってインデックスを生成しています。 何はともあれまずは体験してみましょう。 JSXのプロジェクトページにて使われています。右上にある検索ボックスに単語を入れてエンターキーを押しましょう。 クライアントサイドだけあって高速にレスポンスが返ってきます。一致した部分がハイライトされているので分かりやすいです。 初回でも十分速いですが、インデックスを一回読んでしまえばその後の検索も高速です。 FM-IndexというアルゴリズムについてですがOktaviaの説明によると、

  • 検索前に単語を分割する必要がない
  • インデックスファイルからオリジナルのドキュメントを復元できる
  • 圧縮インデックスファイルを使った検索アルゴリズムの中で最速

となっています。つまり元文書を圧縮してJavaScriptで検索しているようです。面白いのは検索前のインデックス生成が不要ということで、これによりサーバサイドでの負荷が軽減されそうです。 大量のデータでどれくらいのインデックスサイズ、速度で使えるのが興味深いですね。個人のブログ程度であれば十分な速度で使えると思われます。 Oktaviaはnode/JavaScript製のオープンソース・ソフトウェア（MIT License）です。 via Shibu’s Diary: ブラウザ上で動く検索エンジンOktavia ホーム — Oktavia JSX - a faster, safer, easier JavaScript shibukawa/oktavia