編集距離

編集距離は、一文字の挿入・削除・置換で文字列を別の文字列へ変える最少回数です。Levenshtein の DP は全接頭部対を比較し、最小費用を表へ保存してから、実際の編集手順を逆追跡します。

スペル検査、あいまい検索、OCR 修正、記録の重複排除などで使えます。ここでは一編集の費用を 1 とし、用途によって重みを変えられます。

各セルは末尾の処理を決めます。削除は元の文字、挿入は対象の文字、置換は両方を消費し、一致なら無料で保持します。

編集距離の仕組み

dp[i][j] は source[:i] を target[:j] に変える最少費用です。空の接頭部に行と列を用意します。i 文字を空にする削除は i 回なので dp[i][0] = i。空から j 文字を入れるなら dp[0][j] = j。

source[i - 1] と target[j - 1] が同じなら無料です。

dp[i][j] = dp[i - 1][j - 1]

異なれば最後の操作を三つから選びます。

• 元の末尾を削除：dp[i - 1][j] + 1。
• 対象の末尾を挿入：dp[i][j - 1] + 1。
• 二文字を置換：dp[i - 1][j - 1] + 1。

最小を取ります。隣はすでに小さい接頭部対の最適解です。全体の最適変換から最後の編集を除けば、その隣の問題が残ります。隣にもっと安い解があれば全体も安くなり、最適性に矛盾します。したがって最後の三選択の最小で、このセルの最適を得られます。

右下は距離だけです。逆追跡で一致の対角は無料 keep、不一致の対角は replace、上は delete、左は insert。同点は replace、insert、delete の順に選び、再現可能な一つの最適スクリプトにします。

計算をステップで追う

既定は KITTEN から SITTING。

1. 左境界を 0, 1, 2, ..., 6、上を 0, 1, 2, ..., 7 にする。削除だけ・挿入だけの解。
2. 最初の内部セルは K と S。削除と挿入は 2、K→S の置換は 1。対角の 1 を採用。
3. 行ごとに続ける。最初の I 同士は左上を無料でコピー。不一致は削除・挿入・置換候補を同時に示して最小を確定。同点は脚本を変え得るが距離は変えない。
4. 内部 42 セルが埋まり、右下は 3。操作の帯はまだ空で、手順は未復元。
5. (6, 7) から左へ insert G。その後 keep N、replace E→I、二つの T と I を keep、最後に replace K→S。
6. 右から固定枠を埋め、前向きに読むと replace K→S、keep I、keep T、keep T、replace E→I、keep N、insert G。費用 1 は三つで、dp[6][7] = 3 と一致。
7. 左から脚本を再生し、全元文字を消費して SITTING を書く。最小費用を実現できると確認する。

同じ位置だけの比較が失敗する理由

shift-trap の ABCDEF と BCDEFG は対応する六位置がすべて違います。しかし先頭 A の削除と末尾 G の挿入なら二回です。一編集が後続全体をそろえ直せるため、同じ位置の差だけでは足りません。

時間・空間計算量

m、n は元と対象の長さです。二次元表が規模の制約になりやすくなります。点数や閾値だけなら二行、または正しく更新する一行で O(min(m, n)) 空間です。実際の修正には全表か同等の前駆情報を保ちます。小さい距離 k 以内だけを受け入れるなら、帯状 DP で対角から遠いセルを省けます。

境界ケース

• 両方空なら距離 0。
• 元が空なら対象文字ごとに挿入。empty-source は "" から CAT へ三回。
• 対象が空なら元文字ごとに削除。
• 同じ文字列は無料の対角で距離 0。
• 重複や同点は、同じ費用の複数の最適脚本を作り得る。
• 標準 Levenshtein は隣接交換を一編集としない。CA→AC は 2。
• 各文字列の大文字八文字上限は画面の可読性のため。

よくある間違い

• 境界をすべて 0 にする。 境界は挿入・削除の回数です。
• 一致でも一を加える。 同じ末尾は左上の費用をそのままコピーします。
• 逆追跡の挿入・削除を交換する。 左は対象文字の挿入、上は元文字の削除です。
• 目先の安い編集だけを選ぶ。 接頭部状態を比較し、後続の再整列を考慮します。
• ハミング距離を計算する。 等長列の位置比較では挿入・削除を扱えません。
• 脚本が必要なのに右下だけで終える。 数値は最適費用、逆追跡はそれを達成する手順です。