編集距離がわからないのでまとめてみる🤔

参考

編集距離について勉強してもあまりしっくり来ず YouTube で動画を探していたところ、説明が非常に分かりやすい動画を見つけました。

大変感謝です🙇🏻‍♂️

情報工学概論（アルゴリズムとデータ構造）09動的計画法02編集距離 - YouTube

編集距離

2つの文字列が与えられた時どちらかに変更を何回か加えてもう一つの文字列にする 編集操作回数の最小値 のことをいいます。

例

S: snowy
T: sunny

S と T を何回か編集操作をして同じ文字列にする場合を考えます。

Phase	S	T	備考
0	snowy	sunny	初期状態
1	snnwy	sunny	S: o を n に変更
2	sunnwy	sunny	S: u を s の後に挿入
3	sunnwy	sunnwy	T: w を n の後に挿入

この編集の仕方だと編集操作回数は 3 回なので、編集距離は 3 以下 であることがわかりました。

注意！

この時点ではまだ、編集距離が 3 であるとは言えません。
編集距離は定義だと、編集操作回数の 最小値 ということだからです。まだ少ない編集操作回数のケースがあるかもしれません。

なので考え得るケースを考慮しそのケースごとに緩和処理で最小になるように編集回数テーブルを調整して最終的な答えを求めていきます。

最適性原理を用いて漸化式を作る

まず、以下を定義します。

文字列 S = (s1, s2, ..., sm)、文字列 T = (t1, t2, ..., tn) の編集距離を E(S, T) で表す

このとき、以下の最適性原理が成り立ちます。

E(S, T) =
  E((s1, s2, ..., sm-1), (t1, t2, ..., tn)) + 1 +
  E((s1, s2, ..., sm), (t1, t2, ..., tn-1)) + 1 +
  E((s1, s2, ..., sm-1), (t1, t2, ..., tn-1)) + D(sm, tn)

ただし、D(sm, tn) は
sm == tn のとき 0,
sm != tn のとき 1

つまり、求めたい文字列同士のどちらかの最後の一文字が欠けている場合と、両方欠けている場合の編集距離がわかっている状態から、求めたい完全な文字列の編集距離に至る過程を考えているということです。

D(sm, tn) については最後に考えるべき最後の文字列が等しい場合は操作をする必要がなく、等しくない場合は置き換え操作を一回する必要があることを示しています。

どちらかが欠けているパターンの時は、どちらかに挿入、または削除操作を一回することになります。

最終的なコード

// 緩和用のメソッド
func chmin(target: inout Int, new: Int) {
  if new < target {
    target = new
  }
}

let S = "logistic"
let T = "algorithm"

let s: [Character] = Array(S)
let t: [Character] = Array(T)

// 文字列 S = (s0, s1, ..., sm-1)
// 文字列 T = (t0, t1, ..., tn-1)
//
// この二つの文字列について、
// Sについて最初の m文字分、
// Tについて最初の n文字分 同士の編集距離を dp[m][n] とする。
// （注意すべきは S の最初の m文字分ということは最後の一文字は S[m-1] ということ）

var dp = Array(
  repeating: Array(repeating: Int.max, count: t.count + 1),
  count: s.count + 1
)

for i in 0...s.count {
  for j in 0...t.count {

    // dp[i][j] を考える時、ここに至るまでの経路は以下の3つ
    // 1. dp[i-1][j] の編集距離に S[i-1] について編集操作を一回行う
    // 2. dp[i][j-1] の編集距離に T[j-1] について編集操作を一回行う
    // 3. dp[i-1][j-1] の編集距離に S[i-1], T[j-1] について必要であれば
    //    編集操作を一回行う

    if i == 0, j == 0 {
      dp[i][j] = 0
      continue
    }

    // 1. dp[i-1][j] の編集距離に S[i-1] について編集操作を一回行う
    if i > 0 {
      chmin(target: &dp[i][j], new: dp[i-1][j] + 1)
    }

    // 2. dp[i][j-1] の編集距離に T[j-1] について編集操作を一回行う
    if j > 0 {
      chmin(target: &dp[i][j], new: dp[i][j-1] + 1)
    }

    // 3. dp[i-1][j-1] の編集距離に S[i-1], T[j-1] について必要であれば
    //    編集操作を一回行う
    if i > 0, j > 0 {
      let edOfEnds = s[i-1] == t[j-1] ? 0 : 1
      chmin(target: &dp[i][j], new: dp[i-1][j-1] + edOfEnds)
    }
  }
}