[解決済み] Jaro-Winkler距離とLevenshtein距離の違い？[クローズド］

質問

複数のファイルから数百万件のレコードをファジーマッチングしたい。そのために2つのアルゴリズムを確認しました。 ジャロウィンクラー と レーベンシュタイン 距離を編集します。

とは何が違うのか理解できませんでした。それは、どうやら レーベンシュタイン は2つの文字列の間の編集回数を示し ジャロ・ウィンクラー は 0.0 から 1.0 の間で正規化されたスコアを提供します。

私の質問です。

1. 2つのアルゴリズムの根本的な違いは何ですか？

2. 2つのアルゴリズムの性能差は何ですか？

どのように解決するのですか？

レーベンシュタインは、ある文字列を他の文字列に変換するのに必要な編集（挿入、削除、置換）の回数を数えます。Damerau-Levenshtein は、転置も単一の編集として考慮する修正版です。出力は編集数の整数値ですが、これは以下の式で類似度の値を与えるために正規化することができます。

1 - (edit distance / length of the larger of the two strings)

Jaroアルゴリズムは、転置を考慮して、距離の長い方の文字列の長さの半分以下である、共通する文字の尺度です。Winklerはこのアルゴリズムを修正し、文字列の先頭付近の差は末尾付近の差よりも重要であるという考えを支持しました。JaroとJaro-Winklerは、単語や名前のような小さい文字列の比較に向いています。

どちらを使うかを決めるのは、単に性能の問題だけではありません。比較する文字列の性質に適した方法を選択することが重要です。なぜなら、各文字列は他のすべての文字列と比較されなければならず、データセットに何百万もの文字列があれば、それは膨大な数の比較になるからです。これは、各文字列の音声エンコードを計算し、同一のエンコードを共有する文字列を単純にグループ化するような方法よりもはるかに高価です。

これらのアルゴリズムや他のファジー文字列マッチング アルゴリズムに関する詳細な情報は、インターネット上に豊富にあります。これは手始めになります。

個人名照合の比較 マッチングの技法と実際的な課題 課題

その論文によると、私が紹介した4つのJaroとLevenshteinのアルゴリズムの速度は、速いものから遅いものへとなっています。

• Jaro
• ジャロ・ウィンクラー
• レーベンシュタイン
• ダメラウ・レーベンシュタイン

であり、最も遅いものは最も速いものの2～3倍の時間を要します。もちろん、これらの時間は文字列の長さと実装に依存しますし、これらのアルゴリズムを最適化する方法もありますが、使用されていない可能性もあります。