fuzzy-search - レーベンシュタイン距離ベースの方法とSoundex

Question

関連スレッドのこのコメントに従って、レーベンシュタイン距離ベースの方法がSoundexよりも優れている理由を知りたい.

Answer 1

Soundex はかなり原始的です。元々は手作業で計算するために開発されました。これにより、比較可能なキーが生成されます。

Soundex は、もともと米国の国勢調査データ用に開発されたものであるため、西洋の名前でうまく機能します。音声比較用です。

レーベンシュタイン距離は 2 つの値を見て、それらの類似性に基づいて値を生成します。欠落または置換された文字を探しています。

基本的に、Soundex は、"Schmidt" と "Smith" が同じ姓である可能性があることを見つけるのに適しています。

レーベンシュタイン距離は、ユーザーが「Levnshtein」とタイプミスしたことを発見するのに適しています;-)

Answer 2

Soundex ではなくMetaphoneを使用することをお勧めします。前述のように、Soundex は 19 世紀にアメリカ人の名前のために開発されました。Metaphone は、下手なスペラーの作業をチェックし、音声学的にスペリングを行っている場合に、いくつかの結果を提供します。

編集距離は、文字の繰り返し、文字の転置、または間違ったキーを押すなどのタイプミスを見つけるのに適しています。

どちらがユーザーに最も適しているかを判断するアプリケーションを検討してください。または、両方を一緒に使用して、Levenshtein によって生成された提案を補完する Metaphone を使用してください。

元の質問に関して、私は情報検索アプリケーションでn-gramをうまく使用しました。

Answer 3

Daitch-Mokotoff については同意します。元の米国の国勢調査員が「アメリカ化された」名前を望んでいたため、Soundex は偏っています。

違いの例が役立つかもしれません：

Soundex は、単語の先頭に付加価値を置きます。実際には、最初の 4 つの表音のみを考慮します。そのため、"Schmidt" と "Smith" は "Smith" と "Wmith" に一致しませんが、一致しません。

レーベンシュタインのアルゴリズムは、タイプミスを見つけるのに適しています。1 つまたは 2 つの欠落した文字または置換された文字は高い相関関係を生み出しますが、欠落した文字の音声への影響はそれほど重要ではありません。

どちらが優れているとは思いません。入力された入力をユーザーが修正できるようにするために、距離アルゴリズムと音声アルゴリズムの両方を検討したいと思います。

Answer 4

@キース：

私が他の質問に投稿したように、Daitch-Mokotoff は私たちヨーロッパ人にとってより良いものです (そして私は米国を主張します)。

レーベンシュタインの Wiki も読みました。しかし、Soundex よりも(実生活で)ユーザーにとって優れている理由がわかりません。