Edit Distance

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

目的

文字列間の差異の度合いを定量化し、あいまいマッチングや誤り訂正に用いる。

メカニズム

一般枠組み：許容操作集合とコストを定義し、動的計画法で最小総コストを求める。レーベンシュタインは挿入/削除/置換（各コスト 1）を許し、ダメラウ・レーベンシュタインは隣接文字の転置を追加で許し、ハミングは置換のみを許す。

ユースケース

スペル訂正
DNA 配列アラインメント
OCR 誤り訂正
あいまい重複排除

例

入力
```
cat → cut
```
Output
```
1 (substituting a→u)
```
Levenshtein

よくあるエラー

Confusing different edit-distance variants: Make the operation set and costs explicit

関連用語

Levenshtein Distance

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

Hamming Distance

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

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

関連ツール

ハミング距離計算ツール

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

References