Levenshtein と Damerau-Levenshtein の違いは?

Levenshtein は挿入、削除、置換を許します。Damerau-Levenshtein はさらに、隣接文字の転置(ab → ba を 1 操作で)を許します。Damerau は入力ミス(隣接キーの押し間違い)に適しています。どちらも計算量・空間量は O(m×n) です。

編集距離は実務でどう使われるの?

スペルチェック(誤った綴りに距離が近い辞書語の検索)、あいまい文字列マッチング(完全一致ではないが類似したレコードの検索)、DNA 配列アラインメント、重複排除(距離が小さいレコードの統合)で使われます。大規模なあいまい検索には、効率のために BK ツリーか Levenshtein オートマトンを使いましょう。

編集距離(Levenshtein)を計算する

編集距離は、ある文字列を別の文字列に変換するのに必要な挿入・削除・置換の最小回数を測る指標です。スペルチェックやあいまい検索に使われます。

1

Levenshtein 距離は、文字列 A を文字列 B に変換するのに必要な 1 文字編集(挿入、削除、置換)の最小回数です。「kitten」→「sitting」の距離は 3 です(k→s、e→i、+g)。動的計画法で計算します。cell[i][j] = min(挿入、削除、置換) を前のセルに基づいて埋める行列です。計算量・空間量は O(m×n) です。
2

テキスト差分比較ツール →
2 つのテキストを比較して差分を確認します。text-diff は行レベルの変更を表示しますが、編集距離は文字レベルで動作します。ドキュメントには text-diff を、短い文字列(単語、名前)には編集距離を使いましょう。
3

ワードカウント →
単語レベルの編集距離には、両方のテキストを単語配列にトークン化し、その配列間の距離を計算します。これは文字レベルではなく、単語レベルの変更(単語の挿入、削除、置換)を測定します。

よくある質問

Levenshtein と Damerau-Levenshtein の違いは?: Levenshtein は挿入、削除、置換を許します。Damerau-Levenshtein はさらに、隣接文字の転置(ab → ba を 1 操作で)を許します。Damerau は入力ミス(隣接キーの押し間違い)に適しています。どちらも計算量・空間量は O(m×n) です。
編集距離は実務でどう使われるの?: スペルチェック(誤った綴りに距離が近い辞書語の検索)、あいまい文字列マッチング(完全一致ではないが類似したレコードの検索)、DNA 配列アラインメント、重複排除(距離が小さいレコードの統合)で使われます。大規模なあいまい検索には、効率のために BK ツリーか Levenshtein オートマトンを使いましょう。