トレラント検索とワイルドカード検索

トレラント検索は、スペル、ワイルドカード、発音の違いがある場合でも、検索システムがクエリを照合できるようにするものです。これにより、クエリとテキストが完全に一致しない場合でも、ユーザーは関連するドキュメントを見つけることができます。

Definition

トレラント検索は、ワイルドカード展開、編集距離に基づくスペル訂正、音響符号化など、不完全な入力、スペルミスのある入力、または音響的に異なる入力にもかかわらず、クエリ用語をインデックス化された用語に照合させる辞書レベルの技術を指します。

Scope

このトピックでは、辞書レベルで厳密な用語照合を緩和する技術について扱います。具体的には、permutermインデックスとk-gramインデックスを用いたワイルドカードクエリ処理、編集距離と文脈によるスペル訂正、Soundexなどの音響照合が含まれます。これらの近似検索をサポートするために用語辞書がどのように拡張されるか、また、候補用語がどのように生成されランク付けされるかについて説明します。これは、表面的な形式ではなく意味を扱うセマンティックマッチングとは異なります。

Core questions

• プレフィックス、サフィックス、インフィックスパターンなどのワイルドカードクエリは、辞書に対してどのように評価されますか？
• permutermインデックスとk-gramインデックスは、ワイルドカード検索をどのようにサポートしますか？
• スペルミスのあるクエリ用語に対して、最も近い正しいスペルの用語はどのように見つけられますか？
• 編集（レーベンシュタイン）距離は、2つの文字列間の違いをどのように定量化しますか？
• Soundexのような音響照合は、似たような音の用語をどのようにグループ化しますか？

Key concepts

• ワイルドカードクエリ
• permutermインデックス
• k-gramインデックス
• 編集（レーベンシュタイン）距離
• スペル訂正
• 音響照合（Soundex）
• 近似文字列照合
• 候補用語生成

Key theories

permutermインデックスとk-gramインデックスを用いたワイルドカードインデックス作成

用語を回転させてワイルドカードが常に末尾に来るようにする（permuterm）か、用語をその文字k-gramでインデックス化することにより、システムはワイルドカードパターンを通常の辞書検索に変換し、候補用語を取得することができます。

編集距離によるスペル訂正

ある文字列を別の文字列に変換するために必要な単一文字の挿入、削除、置換の最小回数（編集距離）は、クエリ用語に対する正しいスペルの代替案を提案するための原理的な尺度を提供し、しばしば用語の頻度や文脈と組み合わせて使用されます。

Clinical relevance

トレラント検索は、日常的な検索機能、例えば「もしかして」のスペル提案、オートコンプリートやプレフィックス検索、名前や製品用語の寛容な照合などを支えています。クエリに誤字が含まれる場合や、ユーザーが正確なスペルを知らない場合に、検索結果の再現率とユーザーエクスペリエンスを大幅に向上させます。

History

近似照合とスペル訂正は、コンピューティングにおいて長い歴史を持ち、Soundexは20世紀初頭の記録索引付けにまで遡ります。Kukichによる1992年の調査は自動スペル訂正技術を統合し、Navarroによる2001年の調査は近似文字列照合を体系化しました。これらの方法は、ウェブ検索が寛容なクエリ処理を不可欠なものとしたことで、検索辞書の標準的な構成要素となりました。

Key figures

• Karen Kukich
• Gonzalo Navarro

Seminal works

• manning2008
• kukich1992
• navarro2001

Frequently asked questions

検索エンジンは「comput*」のようなワイルドカードをどのように処理しますか？

permutermインデックスやk-gramインデックスなどの補助的な辞書構造を使用して、パターンに一致するすべての用語（computer、computing、computationなど）を見つけ、それらの用語が明示的にリストされていたかのように元のクエリを評価します。

編集距離とは何ですか、またスペル訂正に利用されるのはなぜですか？

編集距離は、ある単語を別の単語に変えるのに必要な最小の単一文字の挿入、削除、置換の数を数えます。スペルミスのあるクエリ用語と辞書用語の間の編集距離が小さい場合、その辞書用語が意図された訂正である可能性が高いことを示唆しています。