2つの文字列を受け取り、「類似性の要素」を返すアルゴリズムを探しています。
基本的に、スペルが間違っている、文字が入れ替わっているなどの入力があり、可能な値のリストから最も近いものを見つける必要があります。
これはデータベースで検索するためのものではありません。照合する文字列が500文字程度のメモリ内リストがあり、すべて30文字未満であるため、比較的遅くなる可能性があります。
私はこれが存在することを知っています、私はそれを前に見ました、しかし私はその名前を思い出せません。
編集：レーベンシュタインとハミングを指摘してくれてありがとう。さて、どれを実装すればよいですか？それらは基本的に異なるものを測定し、どちらも私が望むものに使用できますが、どちらがより適切かはわかりません。
アルゴリズムを読みましたが、ハミングは明らかに速いようです。どちらも転置されている2つの文字（つまり、ジョーダンとジョドラン）を検出しないので、これはよくある間違いであると私は信じています。誰かがトレードオフについて少し教えてもらえますか？
さて、標準的なアルゴリズムは次のとおりです。
1)ハミング距離 同じ長さのストリングにのみ有効ですが、非常に効率的です。基本的には、単純に個別の文字数をカウントします。自然言語テキストのあいまい検索には役に立ちません。
2)レーベンスタイン距離. レーベンスタイン距離は、ある文字列を別の文字列に変換するために必要な「操作」の数で距離を測定します。これらの操作には、挿入、削除、および置換が含まれます。レーベンシュタイン距離を計算する標準的な方法は、動的計画法を使用することです。
3) Generalized Levenstein/(Damerau-Levenshtein 距離) この距離は、単語内の文字の転置も考慮されており、おそらく手入力テキストのあいまい一致に最も適した編集距離です。距離を計算するアルゴリズムは、レーベンシュタイン距離よりも少し複雑です (転置の検出は簡単ではありません)。最も一般的な実装は、bitapアルゴリズム (grep など) を変更したものです。
一般に、kd ツリーに基づくある種の最近傍検索で実装された 3 番目のオプションの実装を検討することをお勧めします。
Damerau-Levenshtein 距離はLevenshtein 距離に似ていますが、2 文字の転置も含まれます。ウィキペディアのページ (リンク) には、実装がかなり簡単な疑似コードが含まれています。
レーベンシュタイン距離を探しています