🌊
SSG向け日本語対応の全文検索エンジンを作りました(5) - 使いやすい検索にしたい！

2025/03/02に公開
JavaScript
第一回 日本語で検索したい！
第二回 英語でももちろん検索したい！
第三回 打ち間違いしても検索したい！
第四回 WebGPUで検索したい！
第五回 使いやすい検索にしたい！(今回)
前回のあらすじ！あいまい検索の高性能化を模索していたぼくは、GPUによる検索のオフロードという手法があることを知りました。GPUのアーキテクチャを確認し、WebGPUの長い作法とバッファの扱いの難しさを超え、なんとかWGSLでbitapを実装することができました。プロファイル結果に不明な点はあれど、CPUで実行するbitapに比べ、10倍程度の高速化を達成できました。
以下のサイトで、ぼくが作成した全文検索エンジンのstateicseekを解説しています。みんな、使ってくれよな！

https://staticseek.lulliecat.com/

 ライブラリはインターフェースが命前回までの検討と実装で、検索のコアのロジックは定まりました。しかし、まだAPIが定まっていません。ライブラリの使い勝手はAPIを通じてどのようなインターフェースでライブラリを使わせるかによってかなり違うと考えています。ぶっちゃけ、ユーザーにとっては検索アルゴリズムはどうでもよく、使いやすくてそこそこ性能があればそれで満足できると思っています。そこで、APIについても検討を始めることにしました。
方針としては、できるだけ簡単なインターフェースにすること、デフォルト値を用意して、デフォルト値でもそれなりに動くようにすることを考えました。ブラウザ上で動く程度の検索ライブラリであまり複雑なことをするのはオーバースペックではないかと考えたからです。まず使ってもらえないと意味がないので、極力簡単に使えるようにします。別に手抜きをしたわけではありません。本当です。

 クエリの文法の作成とそのパースstaticseekで使われる頻度の一番高い関数は検索関数search()でしょう。staticseekでは、できるだけ簡単に使えるように、検索関数をひとつだけ提供することにしました。ブラウザで使う以上、クエリは文字列としてinput要素に設定されるはずです。そのため、文字列をそのまま受け入れ検索できるような関数search()にしました。
基本動作は、キーワードの入力をするとあいまい検索を行い、その結果を返します。ただ、もっと複雑な検索もしたいことがあるかも、と考えたため、AND検索やOR検索、NOT検索、フィールド限定検索の機能を追加しました。これらの機能はsearch()の引数を増やすのではなく、キーワードの代わりにクエリ文字列を設定することにより検索できるようにしました。そうすると、ライブラリ利用側は特にUIを変更することなくこれらの機能を使うことができます。
クエリ文字列をどういう文法にするかは、Google検索の文法を参考にしました。これが一番普及してそうな文法だったからです。まず、その文法を参考にBNFを作成しました。
<space>   ::= \u0020\u00A0\u1680\u2000\u2001\u2002\u2003\u2004\u2005\u2006\u2007\u2008\u2009\u200A\u202F\u205F\u3000\u0009\u000A\u000B\u000C\u000D\u0085\u2028\u2029\u200B
<char>    ::= [^<space>"()] | '\'[^<space>"()]
<digit>   ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<number>  ::= <digit>+ | <digit>+ '.' <digit>*
<nstr>    ::= <char>+
<exstr>   ::=  [^\"]+
<eos>     ::= (end of string)

<exact>   ::=  '"' <exstr> ('"' | <eos>)
<fuzzy>   ::= <nstr>
    <fuzzy> does not includes "OR"

<token>   ::= <exact> | <fuzzy>
<term>    ::= <token> | '-' <token>
<group>   ::= <term> | '(' <space>* <expr> <space>* (')' | <eos>)
<adj>     ::= 'from:' <nstr> <space>+ <adj> | group
<and>     ::= <adj> (<space>+ <adj>)*
<expr>    ::= <and> [<space>+ 'OR' <space>+ <and>]*
クエリはプログラミング言語ではないため、パースエラーができるだけ起きないように作りました。ユーザーのクエリ作成中の文字列も入力されるため、ダブルクォーテーションなどが閉じられていなくても何かを返すように文法を作ってあります。
クエリのパースは単純なパーサーコンビネーターとして実装しました。性能は特に必要ないため、本当に単純な、エラー処理もないパーサーをいちから作りました。
パーサーコンビネーターは通常、小さなパーサー（任意の一文字をパースする関数など）からはじめ、それらの関数を組み合わせて大きなパーサー（文字列、空白で区切られた文字列など）を作る手法をとります。大きなパーサーは、高階関数を構築する手法で行います。TypeScript でゼロから作るパーサコンビネータを参考にさせてもらいました。この記事とかなりそのままの作法で作っております。
この手法で作ってみてわかりましたが、見にくい実装になってしまう箇所が二か所あります。map()とcat()です。前者はパースした途中結果に任意の関数を適用する関数、後者は複数のパーサーコンビネーターを順番に適用して途中結果をコンカチネート（concatinate、結合）する関数です。
何がつらいかというと、これらは命令型的な言語風の見た目をさせるのに適しているにもかかわらず、パーサーコンビネーターでは高階関数を利用するので関数型的な記述スタイルを要求されるからです。
一例として、from:...をパースするコードを見てみましょう。
const from = map(cat(str("from:"), nstr, space1, adj), (x) => ({
    type: "from",
    field: x[1].join(""),
    node: x[3],
}));
なれるとそれほどでもないですが、初見ではなかなか厳しい見た目なのではないでしょうか。これは、疑似コードでかくと、以下のようになります
from = do
    str("from:")
    field_name <- nstr()
    space()
    child <- adj()
    return {
        type: "from"
        field: field_name.join("")
        node: child
    }
前よりは見やすいと思います。まずfrom:をパースし、次に文字列をパースした結果をfield_nameに代入し、次にスペースをあけて子ノードをパースしchildに代入します。パース結果はfileld_nameとchildによって構築されます。このように書くと少し見通しがよくありませんか？
上記の、順に実行する、というパースは、パーサーコンビネーターではcat()の引数にずらりと並べることに対応します。この時、一時変数のようなものは使えません。また、パース結果に関数を適用するにはmap()が必要で、関数と引数が分離した見た目になってしまいます。これらの理由のせいでTypeScriptで作るパーサーコンビネーターは見にくい見た目になってしまいました。
疑似コードで書いたパーサーはモナディックパーサーコンビネーター(リンク先pdfです)と呼ばれ、このリンク先ではHaskell(たぶん)でパーサーコンビネーターを作っています。モナドとは、誤解を恐れずに言えば、一時変数への代入もエミュレートする逐次処理を副作用のない関数としてラップする構造で、do記法を共に使うことで、見た目がほとんど命令型プログラミング言語のように見える関数を構築することができます。上記の疑似コードがそれに相当するつもりで書きました。一時変数を名付けしてパース結果を格納し、順次処理を行い、一時変数の値を組み立てて結果を返す、という命令型っぽい構造にも関わらず、そのデシュガー結果はTypeScript版で書いたような高階関数のパーサーコンビネーターになり、それもパーサーを組み立てるパーツとして再利用できるのがポイントです。パーサーコンビネーターを命令型っぽくかけるだけでこれだけ見通しがよくなります。
なので、本当はモナディックパーサーコンビネーターを使ってみたかったのですが、たぶんTypeScriptではなくPureScriptがいりますね...さすがにそこまで深入りはできないので、今回は普通の単純なパーサーコンビネーターで我慢することにしました。

 TF-IDFによるスコアリングstaticseekにあいまい検索を導入したことにより、擬陽性がめちゃめちゃ増えてしまいました。検索結果を見やすくするため、検索結果にスコアを付け、よりスコアの高い（より一致度の高い、より重要な）ドキュメントを上位に表示する必要があります。
検索結果にスコアを付けるために、TF-IDFという数値を導入しました。これは、あるドキュメントに焦点をあて、そのドキュメント内に現れる単語に対してスコアを付ける手法です。staticseekでは、検索クエリをパースして各キーワードごとにTF-IDFスコアを計算し、その合算値が高い順に上位になるように検索結果をソートします。また、編集距離が1のキーワードは1/2に、編集距離が2のキーワードは1/3に、といったように、スコアを編集距離+1で割ってあいまいなキーワードのスコアを減じています。
TF-IDFはTF(Term Frequency)とIDF(Inverse Document Frequency)を乗算した数です。TFは、ヒットした一つの文章をとりあげ、その中にキーワードが何個含まれるかをカウントし算出します。算出値はそのドキュメントの長さで割ります。こうすることで、あるキーワードが密度高く現れるドキュメントのスコアが高くなるようにします。
IDFは、キーワードをひとつとりあげ、そのキーワードが何個のドキュメントに入っているかを計算し、逆数にしたものです。キーワードが含まれる文章が多ければ多いほど、そのキーワード自体があまり情報量の含まれない可能性が高いため、スコアを減じるようになっています。
staticseekでは、LinearIndexとGPULinearIndexにTF-IDFスコア算出ロジックを組み入れています。HybridTrieBigramInvertedIndexでは、文章長の調整のないTFだけを計算しています。ちょっとさぼりすぎですね...そのうち修正予定です。

 インデックスの遅延読み込みウェブサイトを見に行くユーザー視点にたつと、ページのロード時間は短ければ短いほどよいはずです。検索機能は実際はそれほど頻度高く使われないにも関わらずインデックスサイズは大きいので、ページ読み込み時に毎回インデックスも読み込むように作ると、ページがもたついて表示されるように見えてしまいます。
この問題を避けるため、インデックスを別ファイルに分離し、検索が実際に実行された瞬間にインデックスを読みに行くようにした検索関数を実装しました。createSearchFn()として実装してあります。この関数を呼び出すと、search()と同じ使い方の非同期関数を返します。この返された非同期関数を初回に呼ぶときに内部でインデックスのfetch()がはじまります。この関数は非同期のため、そのままですと初回のインデックス読み込み中に二回目のクエリを受け付けてしまいます。インデックスが完全に読み込み終了したのちに順番で検索を実行するために、なんちゃってqueueを実装しました。これで実行をシリアライズできた、つもりなのですが、これもLLMをぶっ叩きながら実装したため、いまいち実装に自信がありません...

 valibotによるインデックスのバリデーションインデックスファイルをjsonにして、それをfetch()する関係上、間違ったjsonファイルをfetchしてしまった時はエラーを返したほうがより安全なような気がしてきました。そのため、Valibotを使ってjsonをパースしてからインデックスにしています。Zodを使っているプロジェクトの方が多そうですが、valibotの方がバンドルサイズが小さくなるようです。staticseekでは+10kbyte程度の増加でした。ちなみに、staticseek全体で50kbyte程度のスクリプトサイズです。

 小技LLMに「こんなことできないかね？」と質問をぶっ叩きながら得た知識がいくつかあります。簡単にですがご紹介します。

 クラス自体を引数として渡すクラスはJavaScriptでは要するにオブジェクトのよう？らしい？ので、引数にクラス自身を渡すことができます。その時、クラスの型は以下のようになります。
export type IndexClass = new (index?: any) => SearchIndex<any>;
コンストラクタの型を設定するようです。戻り値は、生成したクラス自体の型です。anyを使っています、ごめんなさい...

 クラスを動的に生成するクラスはJavaScriptでは要するにオブジェクトのよう？らしい？ので、クラスを生成する関数を作ることができます。
まず、無名のクラスをつくることができます。そして、そのクラスに文字列で任意の名前をつけることができます。
export function Ngram<T>(name: string, index_class: IndexClass): IndexClass {
    return {
        [name]: class implements SearchIndex<T> {
        ...
    }[name];
}
class名とそのクラス自身が対応づいたオブジェクトを作成し、そのオブジェクトの要素を返すことで可能なようです。こんな書き方はじめてみました。

 クラス名の文字列からクラスを生成するリモートからfetchしてきたJsonの中にクラス名が書いてあり、そのクラスを実体化したいと思いました。以下にそのコードを示します。
export type IndexClass = new (index?: any) => SearchIndex<any>;

export const IndexTypes: { [key: string]: IndexClass } = {
    LinearIndex,
    GPULinearIndex,
    HybridTrieBigramInvertedIndex,
};

export function createIndexFromObject<T>(
    index: StaticSeekIndexRoot<T>,
): StaticSeekIndexRoot<SearchIndex<T>> | StaticSeekError {
    return {
        index_entry: new IndexTypes[index.type](index.index_entry),
    };
}
IndexTypesというRecord<string, IndexClass>を作ります。これにはクラス名の文字列とクラス自身（のオブジェクト？）が含まれており、IndexType["index name"](constructor_arg)とすることでコンストラクタを呼べるようです。なるほどねー（これもLLMぶっ叩いて知りました）

 おわりに以上が、staticseekを構築した残りの技術でした。これでみなさんも独自の全文検索エンジンを作ることが可能です！勉強にちょうど良いテーマで、かなりぼくも学習できました。みなさんもお時間があれば是非手を動かしてみてください。
これで、一連の記事を終わります。たぶん。みなさん、よき検索ライフを！
ライブラリはインターフェースが命

クエリの文法の作成とそのパース

TF-IDFによるスコアリング

インデックスの遅延読み込み

valibotによるインデックスのバリデーション

小技

クラス自体を引数として渡す

クラスを動的に生成する

クラス名の文字列からクラスを生成する

おわりに

Discussion
