類似の2つの文字列の検索

Question

私は2つの文字列を取り、 "類似性の要素"を返すアルゴリズムを探しています。

基本的には、スペルが間違っていたり、文字が転置されたりしている可能性があり、可能な値のリストに最も近い一致を見つけなければなりません。

これは、データベースで検索するためのものではありません。私は、一致する文字列が500文字以内のメモリ内のリストを30文字未満で作成するので、比較的遅くなる可能性があります。

私はこれが存在することを知っていますが、以前見たことがありますが、その名前は覚えていません。

---

編集：LevenshteinとHammingを指摘してくれてありがとう。 これで、どちらを実装する必要がありますか？彼らは基本的に異なるものを測定しますが、どちらも私が望むものに使うことができますが、どれが適切かはわかりません。

私はアルゴリズムを読みましたが、Hammingは明らかに高速です。どちらも転置されている2人のキャラクター（すなわち、ジョーダンとジョドラン）を検出しないので、私はよくある間違いになるだろうと思っています。 誰かが私にトレードオフについて少し教えてもらえますか？

Answer 1

オクラホマ

ので、標準的なアルゴリズムは次のとおり

1）同じ長さの文字列のための唯一の良いが、非常に効率的Hamming distance 。基本的には、別個の文字の数を数えるだけです。自然言語テキストのファジー検索には役に立ちません。

2）。 Levenstein距離は、ある文字列を別の文字列に変換するために必要な「操作」の数の点で距離を測定します。これらの操作には、挿入、削除、および代入が含まれます。 Levenstein距離を計算する標準的なアプローチは、動的プログラミングを使用することです。

3）Generalized Levenstein/(Damerau–Levenshtein distance) この距離は、単語内の文字の転置も考慮に入れます。おそらく手動で入力したテキストのファジーマッチングに最も適した編集距離です。距離を計算するアルゴリズムは、Levensteinの距離より少し複雑です（移調の検出は簡単ではありません）。最も一般的な実装は、bitapアルゴリズム（grepなど）の変更です。一般的に

あなたはおそらく、それぞれが2のコストを割り当て、実際には、ハミング、レーベンシュタイン距離の両方が転位を検出kd木

Answer 2

あなたはLevenshtein distance

Answer 3

• Levenstein距離を探している
• ハミング距離
• 同音
• メタフォン

Answer 4

Damerau-Levenshtein distanceは、レーベンシュタイン距離と似ていますが、も含まれます2文字の転置ウィキペディアページ（リンクされている）には、実装するのがかなり簡単な疑似コードが含まれています。