こんにちは、 @kz_morita です。

今回は，情報検索システムのクエリのスペルミスの修正について概要をまとめます．

スペルミス修正とは

Webの検索システムにおいて，ユーザーが入力したクエリがスペルミスしている可能性もあり，スペルミスの修正を行う場合もあります．

Google 検索などでも，「もしかして○○」といったものが表示され，スペルミスを検知していることがわかります．

編集距離

スペル修正を行う場合以下のような実装を行う必要があるかと思います．

１. 誤ったスペルのクエリに対して，もっとも近いものを選択する
２. 正しいスペルのクエリが複数ある場合には，より一般的なものを選択する

ここで，もっとも近い というワードが出てきましたが，検索クエリと辞書内にある用語の距離を図る必要があります．つまり文字列と文字列の距離を判定するロジックが必要になります．

そこで 編集距離 (レーベンシュタイン距離) という考え方があります．

文字列 s1 から s2 に変換するために以下のような編集走査を何回行う必要があるか？その最小値を編集距離と呼びます．

• 文字列に文字を挿入する
• 文字列から文字を削除する
• 文字列の文字を別の文字に置き換える

具体的に例えば，s1 = cat , s2 = dog といったケースを考えます．

cat を dog に変換するためには， c -> d , a -> o , t -> g といった操作を行えば良いことから，cat と dog の編集力は 3 ということが出来ます．

一番ちかいクエリが複数あるケース

たとえば，入力されたクエリが grnt だとした場合に，以下のような用語が修正先の候補として考えられます．

• grant
• grunt

これらはどちらも，編集距離でいうと 1 になるため，どちらを候補として返せばよいかを決める必要があります．

２. 正しいスペルのクエリが複数ある場合には，より一般的なものを選択する

ここでいう，より一般的なもの をどのように決めるかということです．

方針としては，以下のようなものがあります．

• 文書の中でより多く出現する方を一般的なものとする
• 他のユーザーがより多くクエリとして入力した方を一般的なものとする

Web の検索エンジンなどでは，後者が用いられることが多いようです．

スペルミスかどうかの判定

上記の編集距離で，文字列同士の近さを得ることができましたが，そもそもその文字列がスペルミスかどうかを判定する必要があります．

スペル修正を行う戦略として，以下のようなものがあります．

• 常にスペルミス修正をおこなったクエリを含めて検索する
• 元のクエリが辞書に含まれない場合に，スペル修正し検索する
• 元のクエリの文書のヒット数が少ない場合に，スペル修正し検索
• 元のクエリの文書のヒット数が少ない場合に，スペル修正し候補として表示する

3番目と4番目の違いとしては，3番目はスペル修正した用語で検索した文書も返すのに対し，4番目は検索は行わず候補だけ返します．（もしかして○○？）

また，ヒット数が少ない場合というのは，あらかじめ閾値を用意しておいてヒットした文書数がそれ以下かどうかで判定することが出来ます．

文脈依存の補正

たとえば，from と入力したつもりが，form とスペルミスしてしまったケースを考えます．

この場合，form も正しい用語であるため単独では，スペルミスと判定することができないため，文脈を判定してスペルミス補正をする必要性があります．

まとめ

今回は，スペルミスを修正するロジックの概要についてまとめました．普段 Google などを使用していて何気なく目にする機能ではありますが，実際に実装しようとすると様々なことを考慮する必要があることがわかりました．

レーベンシュタイン距離の具体的な実装や，辞書が多い場合にすべての用語をクエリの距離を求めるのに大きなコストがかかるので，その効率化などまだまだ気になる点があるので，引き続き調べていきます．

参考

• 情報検索の基礎