Levenshtein Distance

レーベンシュタイン距離は、二つの文字列を同一にするために必要な単一文字の挿入・削除・置換の最小回数である。

目的

文字列間の編集差異を測定し、あいまいマッチングやスペル修正に用いられる。

メカニズム

動的計画法により d[i][j] = min(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+cost) を計算する。文字が一致すれば cost は 0、異なれば 1 である。計算量は時間・空間とも O(m×n) だが、空間は O(min(m,n)) に最適化できる。

ユースケース

スペルチェックと修正
DNA配列のアライメント
あいまい検索と重複排除
自然言語処理（NLP）への応用

例

入力
```
kitten → sitting
```
Output
```
3
```
Substitute k→s, e→i, and insert g

よくあるエラー

Full O(mn) computation is too slow for long strings: Use a BK-tree or early termination by threshold

関連用語

Hamming Distance

ハミング距離（Hamming Distance）は、等長の 2 つの文字列で対応する文字が異なる位置の数である。等長の比較にのみ適用できる。

Jaro-Winkler Distance

ジャロ・ウィンクラー距離（Jaro-Winkler Distance）はジャロ距離を改良し、共通する接頭辞に重みを付ける。接頭辞が重要な人名などの短い文字列の照合に適する。

編集距離は、ある文字列を別の文字列に変換するのに必要な単一文字編集操作（挿入・削除・置換）の最小回数である。レーベンシュタイン距離が最も一般的な形である。

ファジーサーチ（Fuzzy Search）は、綴りの揺れに耐性を持つ検索技術であり、編集距離、n-gram、音声アルゴリズムなどに基づいて近似した結果を照合する。

関連ツール

ハミング距離計算ツール

Hamming Distance — 純クライアントサイドツール。プライバシーファースト、サーバー往復なし。

References