Zenn
💨

SSG向け日本語対応の全文検索エンジンを作りました(2) - 英語でももちろん検索したい！

2025/02/25に公開
Next.js
TypeScript
Astro
Nuxt 3
tech

前回のおさらい！SSGを使ってうきうきウェブサイト運営をしていた私は、ついうっかり全文検索エンジンが欲しくなってしまいました。しかし、日本語対応しているエンジンが驚くほどすくなく、自作することにしました。文字n-gram転置インデックスを使うことで、線形探索より10-100倍の性能を達成することができました。

ぼくが実際に作成した全文検索エンジンは以下で紹介してあります。みんな、どしどし使ってくれよな！

https://staticseek.lulliecat.com/

英語での文字2-gramは使い物にならない？

前回作成した文字n-gram転置インデックスの評価は、日本語のデータセットで行いました。今回作成しようとしているライブラリは言語によらず使えることを目指しているので、英語のデータセットでも評価してみることにしました。

手法のカッコ内の数字は、(1)がm-gram(m < n)を全て転置インデックスに加える場合で、(2)がインデックスのタームの先頭1文字を二分探索して一致するポスティングリストを抜粋する場合です。データセットは英語のWikipediaの記事抜粋で、文章総サイズは3,747kbyte、検索実行回数は1,719回です。表の「サイズ」はインデックスサイズを指し、「検索時間」は、1,719回の検索時間の合計です。

手法 作成時間 サイズ gzipサイズ 検索時間 一致 擬陽性 偽陰性
線形探索 23ms 3,745kbyte 1,322kbyte 4,316ms
2-gram(1) 1,630ms 849kbyte 139kbyte 58ms 58,964 95,950 0
3-gram(1) 2,677ms 3,932kbyte 567kbyte 47ms 58,964 38,653 0
4-gram(1) 3,592ms 9,222kbyte 1,212kbyte 20ms 58,964 7,852 0
2-gram(2) 932ms 837kbyte 140kbyte 104ms 58,964 95,950 0
3-gram(2) 1013ms 3,557kbyte 523kbyte 58ms 58,964 38,653 0
4-gram(2) 1052ms 6,811kbyte 972kbyte 36ms 58,964 7,852 0

想定はしていましたが、擬陽性が酷く多いですね。4-gramでようやく使い物になるレベルです。gzipしたインデックスサイズ自体は許容範囲内ですかね。

確認はしていませんが、これだけ擬陽性が多い理由は、そもそも英語は文字が26種類しかないところにあると考えています。bigramの組み合わせは 26 x 26 = 676種類しかありません。一方、日本語の漢字は7万字程度、常用漢字だけでも2,136字あります。組み合わせの桁が違いすぎるため、ほとんどの単語が似たようなbigramに入ってしまうのでしょうか。

この結果わかることは、日本語と英語では別のアルゴリズムで検索する必要がある、ということです。少なくとも文字n-gramのnの値は変える必要があります。

また、英語のベンチマークは日本語のベンチマークより一桁遅くなっています。これは何故なのでしょうか？正直理由が判明しません。一致と擬陽性を加えた総ヒット数は日本語の7倍に達するので、ヒット数の違いかもしれません。

日本語と英語で違った戦略をとろう

言語により違う戦略をとると決めたので、まずは与えられた文を言語ごとに分割して整理する関数を作りました。空白や役物をデリミタとして削除し文を分割した上で、文字コードを確認し、英語と日本語の境目で分割しています。実際には、英語と日本語だけではなく、その他言語もすべてあわせて「分かち書きが難しい言語」と「空白で単語を抽出できる言語」の二種類に分類してあります。分類した文の断片はそれぞれ別のインデックスに格納されます。検索ワードも全く同じ関数により分割され、それぞれの検索を行ったのちに共通部分（インターセクション）を取ることで検索結果とします。

寄り道: グラフェム単位での文字の分割

先ほどの関数では、segmenterと呼ばれるものによって、stringから1文字を抽出しています。ところで、一文字とは何でしょうか？

Unicodeの全ての抽象文字はコードポイントと呼ばれる数字に結び付いています。一方、JavaScriptで使われるstringは、UTF-16 コード単位という単位で文字列を扱います。しかし、全てのコードポイントが含まれるコードスペースは16bitで扱える範囲より多くなっています。そのため、一部の文字はサロゲートペアと呼ばれる、単一の文字を表す16ビットのコード単位のペアで表されます。UTF-16文字列からコードポイントを取得するには、String.prototype.codePointAt()を使います。

ところが、Unicodeでは、いわゆる私たちが「1文字」と認識する矩形は、複数のコードポイントで構成されることもあります。これをグラフェムクラスターと呼びます。私たちが通常使う一文字は、グラフェムと呼ばれ、この単位でUnicode stringを分割するには、前述のsegmenterを使う必要があるのです。

私が作成したstaticseekはグラフェム単位を1文字として扱い、グラフェムの先頭コードポイントを代表文字として抜粋し、検索を行っています。そのため、全ての言語で安定した検索が行えるようになっています。

寄り道：テキストの前処理

staticseekでは、テキストに対しいくつかの前処理を行っています。グラフェム単位での文字の分割では、ついでに役物（記号とか句読点とかのこと）の削除をしております。これも一種前処理と言ってもいいでしょう。

基本的には、できる限り検索を安定して行えるようにいくつかの正規化を行っています。

ほんとうに簡単なものしかおこなっていませんが、これにより少しは検索を安定にできるようになっていると思います。

ちなみに、ストップワードの除外とステミングは行っていません。言語中立なので...（言い訳）

日本語n-gram・英語word転置インデックスを採用

英語と日本語を分離したインデックスにできたので、せっかくだから英語の方は通常のword単位の転置インデックスで実装することにしました。word転置インデックスはソート済みの配列で実装されます。完全一致検索に加え、前方一致検索を実装するため、転置インデックスを検索する二分探索アルゴリズムに少し手を入れ、前方一致する配列の範囲を返すようにしました。アルゴリズムの詳細は、refine()という関数の実装をご覧ください。前回と同じ、ベンチマーク実行スクリプトでベンチマークをとれます。データセットの内容は、これまで利用してきたデータセットと同一です。

手法 作成時間 サイズ gzipサイズ 検索時間 一致 擬陽性 偽陰性
線形探索 - 英語 24ms 3,745kbyte 1,322kbyte 4,391ms
英語word (2) 290ms 3,170kbyte 500kbyte 4.9ms 53,481 0 5,483
線形探索 - 日本語 12ms 2,988kbyte 1,051kbyte 200ms
日本語bigram (2) 350ms 6,066kbyte 910kbyte 9.6ms 15,125 5,095 313
日本語trigram (2) 560ms 11,568kbyte 1,964kbyte 5.1ms 15,125 125 313

英語は線形探索に比べword転置インデックスでの検索は1000倍も速くなりました。また、英語はword単位でインデックス化したおかげで、gzipインデックスサイズが半減しています。さらに、擬陽性はなくなりました。一方、偽陰性が増えました。これは実は線形探索の方がリファレンスとしては質が低く、単語の途中でマッチする問題があるので、偽陰性が増えたような見た目になっています。実際はword単位の転置インデックスを作ったほうが検索の質は高いように思えています。検索も文字n-gramより10倍高速です。

日本語で擬陽性が増えているのは、役物などを削除したせいでしょうか、ちょっと確認できていません。そのかわり、検索時間が倍に高速化しています。日本語はbigramだと擬陽性が厳しく、trigramだと擬陽性はかなり抑えられますがインデックスサイズが倍増します。悩ましいですね。

おわりに

日本語対応の検索エンジンを考えていましたが、無事に英語と日本語を両方同時に取り扱えそうな手段を得ることができました。が、次回、非常に残念なことが発覚します。今回のデータをみてもそれがわかります。さて、なんでしょうか？次回、おたのしみに！（悲鳴

Discussion