レーベンシュタイン距離の計算（編集距離）

レーベンシュタイン距離は、ある文字列を別の文字列に変えるのに必要な、1文字単位の挿入・削除・置換の最小回数です。スペル候補の提示、あいまい検索、重複検出、DNAのアラインメントなどの土台になる指標です。この計算ツールは、距離と類似度（％）を求め、実際の編集内容を一覧にし、短い文字列には動的計画法の表を表示します。また、候補のリスト全体を、自分の文字列にどれだけ近いかで順位付けすることもできます。

使い方

1. 2つの文字列を入力します（または、文字列1つと、1行に候補1つのリスト）。
2. 通常のレーベンシュタインを使うか、隣り合う文字の入れ替えを1回の編集として数えるDamerauを選びます。
3. 必要に応じて、大文字・小文字や空白を無視するか、単語単位で比較します。
4. 距離、類似度、編集内容を確認します。表は20文字以下の文字列で表示されます。

計算式

d[i][j] = min(d[i−1][j] + 1, d[i][j−1] + 1, d[i−1][j−1] + (aᵢ ≠ bⱼ)) · 類似度 = 1 − d ÷ max(|a|, |b|)

d[i][j]は、aの先頭i文字とbの先頭j文字の距離で、d[i][0] = i、d[0][j] = jから始まります。隣接入れ替え（最適文字列アラインメント）の変種では、隣り合う2文字が入れ替わっているときにd[i−2][j−2] + 1を加えますが、同じ部分文字列を2回編集することはありません。制限なしのDamerau–レーベンシュタイン距離はこの制限を外します（CA → ABCは3ではなく2）。文字はUnicodeのコードポイントで、単語は空白で区切ります。

計算例

こんにちは → こんばんは = 2です。に → ば、ち → ん の2文字を置換します。どちらも5文字なので、類似度は1 − 2/5 = 60%です。東京 → 東京都は1（都を挿入）です。こんにちはを基準に、リストのこんばんは、こんにちわ、さようなら、こんにちは世界を順位付けすると、距離1のこんにちわが1位になります。