SSG向け日本語対応の全文検索エンジンを作りました(3) - 打ち間違いしても検索したい！
- 第一回 日本語で検索したい！
- 第二回 英語でももちろん検索したい！
- 第三回 打ち間違いしても検索したい！(今回)
- 第四回 WebGPUで検索したい！
- 第五回 使いやすい検索にしたい！
前回のおさらい！英語で文字n-gramのベンチマークをしたところ、誤ヒットの多い検索結果になり、とても使えるものではありませんでした。そこで、日本語と英語で違ったインデックスを作成することにしました。Unicodeの正規化などを併用しつつ、word単位のインデックスとbigramインデックスを使い分けることで、英語の検索性能は線形探索の1000倍の性能を達成することができました。
ぼくが実際に作成した全文検索エンジンは以下で紹介してあります。みんな、どしどし使ってくれよな！
最適化する前に測定せよ
前回までの作業で、Unicodeで表せる全ての言語で、転置インデックスを使った高速検索が可能になりました。よかったよかった。了。
……と、何も気付かず終われば良かったのですが、よくよくベンチマークをみると嫌なことに気付きました。ベンチマークを再掲します。検索実行回数は1,719回です。
| 手法 | 作成時間 | サイズ | gzipサイズ | 検索時間 | 一致 | 擬陽性 | 偽陰性 |
|---|---|---|---|---|---|---|---|
| 線形探索 - 英語 | 24ms | 3,745kbyte | 1,322kbyte | 4,391ms | |||
| 英語word (2) | 290ms | 3,170kbyte | 500kbyte | 4.9ms | 53,481 | 0 | 5,483 |
線形探索、1719回の検索で4391msの検索時間です。割り算すると、1回の検索あたり2.5ms程度です。
充分速いですね。UIスレッドで使っても固まることなく、ユーザーに気付かれることもなさそうです。英語の場合、gzipしたインデックスはちいさいので利点はあるんですが、日本語の場合はその利点はあまりありません。
なので、転置インデックスを使う理由は無さそうです。線形探索でおしまい！がはは！
あいまい検索、最初から実装したかったんだよね
さて、ぼくが最初から実装したかった(ホントですよ、まじで、ほんとほんと)検索機能があります。あいまい検索です。技術的に面白そうなので実装することにしました。
が、ほとんど実用性に関係ないんじゃないか、単なるカタログスペックではないか、と思わないでもないです。あいまい検索の実装を終えてリリースした今でも、デフォルトの検索スキームとして本当に有用なのか迷っています。むしろ偽陽性が増えて鬱陶しくなった気がします。偽陽性が増えすぎるのを嫌って、1文字の間違いまでしか許容しない設定にしましたが、1文字だけ打ち間違えることなんて本当にあるのか？なんて思ったりもしています。難しいね。
ともかく、技術的には面白いので記事として記録は残しておこうと思います。
あいまい検索にはいくつか定義があるとは思いますが、この記事ではスペルミスをした単語も検索可能にする、という意味としておきます。例えばぼくはrとlがどっちかわかんなくなって間違えて入力することがあります。そういうのも検索できるといいかもなぁ、くらいの感覚です。
あいまい度を定義しよう
あいまい検索を実装する前に抑えておく必要があります。あいまいとは、具体的に数字としてあらわすことができる概念なんでしょうか？これから、あいまいという概念をプログラムで扱うので、具体的に数値で表すことができる概念へ翻訳する必要があります。
直観的には、何文字スペルミスするか、という概念がもっとも納得できるのではないでしょうか。例えば、HelloとHalloは1文字間違っていますね。また、HelloとHeloも1文字間違っていますね。間違ってる文字数が多ければ多いほど、よりあいまいな単語である、と言えそうです。
何文字スペルミスするか、という考え方をもう少しプログラムでも扱えるように定義します。あいまいとは、「ふたつの単語間の編集距離とその大小」として本記事では定義します。編集距離とは、距離の一種で、ひとつの単語から文字の挿入・削除・置換のいずれかの文字編集を1回適用するのを距離1として、その文字編集の繰り返し回数と定義されます。これは単なる一つの定義で、ほかのあいまいの定義をしても大丈夫なのですが、この定義下でのアルゴリズムが古くから多く存在するので、ぼくもそれを倣うことにします。
このように編集距離を定義すると、あいまい検索は「編集距離がn以下の文字列が検索対象内に存在するかを確認する」ことで実現できます。具体的には以下の操作でできそうです。
- 「編集距離がn以下かもしれない文字列T0」を仮に定める。最初は検索対象の先頭からの文字列にする
- 文字列T0と検索文字列の本当の編集距離を求める
- 本当の編集距離が実際にn以下ならば「存在する」で終了
- 違ったら、文字の先頭を1文字進めてT1を定め、T1と検索文字列の編集距離を求める
- Tm(m=行末)まで2-3を繰り返し、「存在する」に該当がなかったら「存在しない」になる
これは、大枠は単純な線形探索アルゴリズムと一緒です。2と3において編集距離を使っているところだけが違っています。
ふたつの文字列同士の編集距離を求める方法
これまでの説明で、ふたつの文字列間の編集距離が計算できれば、あいまい検索ができそうなことがわかりました。次に、実際に編集距離を求めるアルゴリズムを説明します。
ふたつの単語間の編集距離を求めるアルゴリズムとして、動的計画法を用いた編集距離を計算するアルゴリズムが存在します。てきとうなウソ説明をすると、短い単語同士の距離から計算をはじめ、それより1文字増やした単語間の距離は簡単に定めることができるので、検索文字列になるまでそれを再帰的に適用します。""(空文字、長さ0の文)からある単語への編集距離は、その単語の長さに等しいので、初期状態も簡単に定められます。
検索文字列を横軸に、検索対象を縦軸にした表をつくります。この表の各セルには、原点から当該する縦軸と横軸までの単語同士の距離を表します。この表にまず初期状態を記入し、そこからルールに従って距離を埋めていきます。数独的なパズルをやる感覚で、「こことここの値が定まっているから、ここの編集距離はこれに違いない」みたいな推測を続けて表を埋めていくのです。詳しくは前述のWikipediaの説明をご覧ください。マジで天才のアルゴリズムなので必見です。
もう少し効率的なアルゴリズムがあります
前述の検索アルゴリズムはいかにも重いですね。特に、T0, T1...と、検索対象を1文字ずつ進めるたびに表を初期化してふたたび検索を始める必要があり、そこが非効率に感じます。実は、既存の文字列検索アルゴリズムを修正することで、途中の表の初期化をすることなく、編集距離n以下の文字列が存在するかを判定できるアルゴリズムがあります。
それはbitapアルゴリズムと呼ばれるものです。bitapアルゴリズムは完全一致検索を効率的に処理するアルゴリズムとして提案されました。それを改修することであいまい検索に使えることがそののち発見されました。
bitapアルゴリズムは、文字のマッチ状態を表す値を簡単に更新できるアルゴリズムです。文字のマッチ状態は簡単な一本道の状態遷移図で表すことができ、しかも、ひとつ先に遷移するパスしかなく自分自身へ遷移するパスがありません。そのため、状態Snを変数のn bit目に割り当てることにより、1bit shift演算とand, or演算を使うだけで簡単に状態が遷移できます。遷移の結果、m bit目（mは検索文字列長）が1になれば「存在する」で検索終了です。
これはあいまい検索に拡張できます。完全一致のstate machineをE0、編集距離1のstate machineをE1、という風に、編集距離ごとに別にstate machineを作り、それぞれ元の完全一致bitapアルゴリズムに従い状態を更新します。これに加え、E0からE1への遷移、E1からE2への遷移...と、編集距離間の遷移を追加で加えます。これにより、任意の距離の一致が検出できます。検出は完全一致の時と同じく、各編集距離のm bit目が1になったときに、その距離で一致が検出されたことになります。
このアルゴリズムも詳しくは前述のWikipediaをご覧ください。とてもシンプルで美しいアルゴリズムです。
bitapアルゴリズムの実装と評価
とりあえず、なにがしかあいまい検索ができる関数を作らないと何も評価できないため、素直にそのままbitapを実装しました。
アルゴリズムが合っているかどうかは、僅かな単体検証以外は検索結果を目視で確認しました。デバッグは念力です。しかも今ですら雑なテストしかしていません。まじで良くないですこれ。でもテストデータ作るの面倒なんだよな……
さすがに何もテストしてなさすぎなので、記事から抜粋したキーワードに編集距離1の変更を加え、あいまい検索を正しく行えているかの評価はすることにしました。抜粋したキーワードをそのまま使って線形検索を行った結果と、編集距離1に修正したキーワードを使ったbitap検索の比較です。データセットは以前と一緒で、検索時間の単位は[ms/query]です。今回から、検索時間は1検索あたりの時間を表示するようにしました。また、これ以前のテストベンチはサンプル実装でベンチマークを測定していましたが、今回からは実際のstaticseekを使って測定しています。そのため、クエリ解析や結果集計の時間もこのベンチマークに含まれます。新たに作成したベンチマークスクリプトでベンチマークを取得しました。
| 手法 | 作成時間 | サイズ | gzipサイズ | 検索時間 | 一致 | 擬陽性 | 偽陰性 |
|---|---|---|---|---|---|---|---|
| 英語(線形) | 314ms | 3,748kbyte | 1,324kbyte | 2.79ms | |||
| 英語(bitap) | 309ms | 3,748kbyte | 1,324kbyte | 81.10ms | 58964 | 17924 | 0 |
| 日本語(線形) | 137ms | 3,020bkyte | 1,053kbyte | 0.30ms | |||
| 日本語(bitap) | 135ms | 3,020kbyte | 1,053kbyte | 18.32ms | 15437 | 10062 | 0 |
編集距離1のキーワードに対して偽陰性が0のため、英語・日本語ともに正しくあいまい検索ができていることがわかります。擬陽性はかなり増えますね。日本語6割・英語3割くらい増えます。また、検索時間は、String.prototype.indexOf()に比べて、英語で29倍、日本語で61倍時間がかかっています。かなり遅いですね。V8すごい...81msはUIスレッドで動かす処理としては許容するのは厳しそうな気がします。あとやっぱ日本語に比べ英語は1桁遅いな...なんでだろう...
正直、擬陽性が増えすぎてこのまま実装してもいまいち使い物にならないのでは、という気がしないでもないです。その上、特に英語のbitapが遅いですね。ベンチマーク環境（いうの忘れてました。Core i5 13400FにChromeです）より低い性能の環境でも動かすことを考えると、より高速な実装が必要になります。
英語はトライの探索に手を入れてあいまい検索対応に
英語のあいまい検索の高速化については目途があるので、こちらを先に対応します。前回、英語はword転置インデックスを使うことで完全一致・前方一致検索の高速化が達成できました。転置インデックスの実際のデータ構造はソート済みの配列を使いました。しかし、このデータ構造をそのまま使うと、あいまい検索は時間がかかることがわかりました。あいまい検索に対応するには、ソート済み配列中の全てのタームに対してbitapを実行する必要があるからです。コードの改変のため今のレポジトリにベンチマークをとれるスクリプトがありません、すまぬ。
この問題を解決するため、トライを導入しました。これは木の一種で、タームの先頭文字から順番に1文字ずつ木のノードとし、隣接した文字同士をエッジで接続します。タームの最後尾の文字はリーフに向かって伸びますが、必ずしもリーフとはならず、タームの最後尾の文字が中間ノードである場合もあります。先頭文字が同じタームは同じノードを共有します。先頭文字から複数の文字が同じターム同士も、同じくノードとエッジを共有します。
下図はトライの例です。teaとtedとtenは、同じtとeのノードを共有します。inとinnも同じiとnのノードを共有します。ルートからあるノードへのパス上にあるノードの文字を連結してタームとします。そのため、各ノードはひとつのタームを表すことができます。このノードにポスティングリストを対応させることで、転置インデックスとすることができます。
トライの構築と完全一致探索
トライの構築と検索はどちらも似たようなアルゴリズムです。次はトライの構築アルゴリズムです。古い実装であまり綺麗ではありませんが、ごく簡単な実装例もあわせてご覧ください。
- 文字の割り当たっていないノードをルートノードとして作成する
- ルートノードを暫定のベースノードとする
- タームの先頭の文字を取り出す
- ベースノードから直接伸びるエッジの先に、該当する文字のノードがある場合は、ベースノードをそのノードとして割り当てる
- ノードがない場合、新たに該当する文字のノードを作り、ベースノードからエッジを伸ばす。ベースノードを作成したノードとして割り当てる
- タームの残り文字がない場合は、そのノードにポスティングリストを作り、タームが属するドキュメントidを登録する
- タームの残り文字がある場合は、3に戻る
完全一致するタームを探索するアルゴリズムは以下になります。実際には探索というよりは、ノードをたどるだけになります。実装も非常に単純です
- ルートノードを暫定のベースノードとする
- タームの先頭の文字を取り出す
- ベースノードから直接伸びるエッジの先に、該当する文字のノードがある場合は、ベースノードをそのノードとして割り当てる
- ノードがない場合、転置インデックスに該当タームなしでreturnする
- タームの残り文字がない場合は、そのノードのポスティングリストを返す。ノードにポスティングリストが対応していない場合は、転置インデックスに該当タームなしでreturnする
- タームの残り文字がある場合は、3に戻る
前方一致の実装もそれほど難しくありません。タームの最後尾の文字に該当するノードからリーフに向かってたどり着くことのできるノードのポスティングリストを全て返せばよいだけです。
トライのあいまい探索
このように、トライはそのままでは完全一致と前方一致に対応できます。トライをあいまい検索に対応させるには、トライを探索することになります。
前述の完全一致検索のアルゴリズムでは、検索で用いる状態としてタームの残り文字を使っています。完全一致では辿るエッジがひとつに定まるため、非常に簡単な関数で検索が実装できます。
あいまい検索ではタームの残り文字という状態に加え、残り編集距離という状態を使います。残り編集距離が0でない限り、1文字の編集を許す場合にあり得る状態を生成し、その状態に対応する全てのノードを探索します。探索は非常に単純に実装しており、単なる深さ優先探索です。詳細は探索関数の実装をご覧ください。
トライの実装と評価
下記は、前述のベンチマークにトライを加え実行したものです。
| 手法 | 作成時間 | サイズ | gzipサイズ | 検索時間 | 一致 | 擬陽性 | 偽陰性 |
|---|---|---|---|---|---|---|---|
| 英語(線形) | 314ms | 3,748kbyte | 1,324kbyte | 2.79ms | |||
| 英語(bitap) | 309ms | 3,748kbyte | 1,324kbyte | 81.10ms | 58964 | 17924 | 0 |
| 英語(Trie) | 980ms | 3,748kbyte | 505kbyte | 0.32ms | 57762 | 10295 | 1202 |
インデックス作成時間が3倍に伸びています。その代わり、探索時間はbitapに比べ250倍高速化しました。インデックスサイズはbigramでインデックスを作成した時と同等で、bitapに比べ半部以下のサイズになっています。bitapに比べ擬陽性もかなり減っていますね。しかしまだ焼け石に水です...
擬陽性の問題は残ったままですが、検索性能自体は目標を達成できたため、この実装を採用することにしました。
日本語のbigram転置インデックスであいまい検索はどうやる？
さて、問題の日本語bigram転置インデックスを用いたあいまい検索です。あまり良いアイディアがありませんでした。とりあえず、bigramに分割した全てのタームの一致、という検索条件を緩和することで、仮にあいまい検索ができるようにしました。
一例をあげます。また、「東京都渋谷区」という検索対象文字列を考えます。このbigramは以下のようになるのでした。
["東京", "京都", "都渋", "渋谷", "谷区"]
ここで、検索文字列が1文字間違って「東狂都渋谷区」となったとします。こんな間違いするはずないですが、とりあえず。この文字列を検索するためには、同じくこの文字列をbigramに分割して、それぞれのタームが転置インデックスにあることを確認するのでした。
["東狂", "狂都", "都渋", "渋谷", "谷区"]
上記二つのbigramを見比べてください。本来、完全一致を目指すには、検索文字列の全てのbigramターム(5個)が存在することを確認するのでした。しかし、今回、一文字の間違いで、3個のbigramタームだけが一致しています。
この性質を利用して、n-gramにおいてm文字間違う場合は、n x m個のタームの欠如を許容するように検索アルゴリズムを変更しました。先ほどの置換の例では2個のタームの欠如が発生しましたが、削除と挿入に関しても同じく1-2個のタームの欠如が発生します。確認してみてください。
こちらは特に難しくはないのでそのまま実装しました。下記が、以前と同じデータセットを利用したベンチマークです。
| 手法 | 作成時間 | サイズ | gzipサイズ | 検索時間 | 一致 | 擬陽性 | 偽陰性 |
|---|---|---|---|---|---|---|---|
| 日本語(線形) | 137ms | 3,020bkyte | 1,053kbyte | 0.30ms | |||
| 日本語(bitap) | 135ms | 3,020kbyte | 1,053kbyte | 18.32ms | 15437 | 10062 | 0 |
| 日本語(bigram) | 469ms | 3,020kbyte | 813kyte | 0.93ms | 13375 | 22148 | 2062 |
想像してはいましたが、擬陽性が爆増しています。一致の1.6倍もあります。正直、使い物になるのか疑問です。検索時間自体は高速化し、bitapに比べ20倍の高速化を達成できました。かなり不満が多いのですが、とりあえずこの手法で一段落させます。
おわりに
あいまい検索、やっぱりあんま使いものにならん気がするんだよなぁ。検索ノイズが増えすぎます。英語はIMEのようなものがなく打ち間違えは発生しやすいと思うので、英語の検索では活用できるでしょう。日本語の場合は微妙ですね。
微妙、といいつつ、次回、別のあいまい検索の高速化を模索します。WebGPUを用いたbitapの実装です。単純ですがこれも面白かったので楽しみに待っていてください。
Discussion