編集距離

$D [i] [j] = min (D [i - 1] [j] + c_{del}, D [i] [j - 1] + c_{ins}, D [i - 1] [j - 1] + c_{sub} \cdot [x_{i} \neq = y_{j}])$ の表を埋めて、2 つの文字列の（重み付き）編集距離を求められる

前提

動的計画法の基本（硬貨の最小枚数）（大学数学アルゴリズムと計算量）

説明

編集距離は、文字列 $x$ を文字列 $y$ に作り替えるのに必要な「削除・挿入・置換」の最小コストです。各操作のコストを $c_{del}, c_{ins}, c_{sub}$ と決めておくと、2 次元の表を左上から順に埋めるだけで求められます。スペル修正の候補選び、DNA 配列の比較、ファイルの差分表示など、2 つの列がどれだけ似ているかを数値で測る場面で使います。

なぜそうしてよいのか

$x = x_{1} x_{2} \dots x_{m}$ を $y = y_{1} y_{2} \dots y_{n}$ に作り替える方法は、次のような「対応づけ」で表せます。 $x$ の各文字は、削除されるか、 $y$ のどれか 1 文字に対応づけられます。対応づけは左から右への順序を保ちます。 $y$ の文字のうち対応相手のないものは、挿入された文字です。対応づけた 2 文字が等しければコストは $0$ 、異なれば置換としてコスト $c_{sub}$ がかかります。コストはすべて $0$ 以上とします。このような対応づけのコスト合計の最小値が編集距離です。

そこで $D [i] [j]$ を「先頭 $i$ 文字 $x_{1} \dots x_{i}$ を先頭 $j$ 文字 $y_{1} \dots y_{j}$ に作り替える最小コスト」と定めます。最適な作り替えで、末尾の文字 $x_{i}$ と $y_{j}$ がどう扱われるかは次の 3 通りしかありません。(1) $x_{i}$ を削除する。残りは $x_{1} \dots x_{i - 1} \to y_{1} \dots y_{j}$ なので $D [i - 1] [j] + c_{del}$ 。(2) $y_{j}$ を挿入する。残りは $x_{1} \dots x_{i} \to y_{1} \dots y_{j - 1}$ なので $D [i] [j - 1] + c_{ins}$ 。(3) $x_{i}$ と $y_{j}$ を対応づける。 $D [i - 1] [j - 1] + c_{sub} \cdot [x_{i} \neq = y_{j}]$ 。ここで $[x_{i} \neq = y_{j}]$ は、 $x_{i} \neq = y_{j}$ なら $1$ 、 $x_{i} = y_{j}$ なら $0$ を表す記号です。

どの場合も、残りの部分は最小コストで作り替えるのが最善です（もっと安い方法があれば、それに取り替えて全体も安くできるから）。よって 3 通りの最小値をとれば $D [i] [j]$ になります。これは硬貨の問題で「最後に使う硬貨 $c$ 」で場合分けして $O (n) = min_{c} {O (n - c) + 1}$ としたのと同じ考え方で、「最後の操作」で場合分けしています。小さい $i, j$ から順に埋めれば、右辺の値はいつもすでに求まっています。

手順

$x$ を縦（行 $i = 0, \dots, m$ ）、 $y$ を横（列 $j = 0, \dots, n$ ）に並べ、 $(m + 1) \times (n + 1)$ の表を用意する。
0 行目と 0 列目を埋める。空文字列から $y_{1} \dots y_{j}$ を作るには挿入のみなので $D [0] [j] = j c_{ins}$ 。 $x_{1} \dots x_{i}$ を空にするには削除のみなので $D [i] [0] = i c_{del}$ 。
残りのマスを、上の行から順に、各行は左から右へ埋める。 $D [i] [j] = min (D [i - 1] [j] + c_{del}, D [i] [j - 1] + c_{ins}, D [i - 1] [j - 1] + c_{sub} \cdot [x_{i} \neq = y_{j}])$ 。上のマスからは削除、左のマスからは挿入、左上のマスからは一致または置換。
右下のマス $D [m] [n]$ が $x$ から $y$ への編集距離である。

例題

削除のコストを $c_{del} = 1$ 、挿入のコストを $c_{ins} = 1$ 、置換のコストを $c_{sub} = 2$ とする。文字列 $x = sea$ を文字列 $y = eat$ に作り替える編集距離を求めよ。

例題の解答

【手順1】 $x$ は $x_{1} = s, x_{2} = e, x_{3} = a$ で $m = 3$ 、 $y$ は $y_{1} = e, y_{2} = a, y_{3} = t$ で $n = 3$ である。 $4 \times 4$ の表を作る。
【手順2】 $D [0] [j] = j$ より 0 行目は $0, 1, 2, 3$ 。 $D [i] [0] = i$ より 0 列目は $0, 1, 2, 3$ 。
【手順3】漸化式で埋める。 $min$ の中は（上 $+ 1$ , 左 $+ 1$ , 左上 $+$ 一致なら $0$ ・不一致なら $2$ ）の順に書く。
1 行目（ $x_{1} = s$ ）：
$D [1] [1] = min (1 + 1, 1 + 1, 0 + 2) = 2$
$D [1] [2] = min (2 + 1, 2 + 1, 1 + 2) = 3$
$D [1] [3] = min (3 + 1, 3 + 1, 2 + 2) = 4$
2 行目（ $x_{2} = e$ ）：
$D [2] [1]$ は $e = e$ で一致なので $min (2 + 1, 2 + 1, 1 + 0) = 1$
$D [2] [2] = min (3 + 1, 1 + 1, 2 + 2) = 2$
$D [2] [3] = min (4 + 1, 2 + 1, 3 + 2) = 3$
3 行目（ $x_{3} = a$ ）：
$D [3] [1] = min (1 + 1, 3 + 1, 2 + 2) = 2$
$D [3] [2]$ は $a = a$ で一致なので $min (2 + 1, 2 + 1, 1 + 0) = 1$
$D [3] [3] = min (3 + 1, 1 + 1, 2 + 2) = 2$
【手順4】 $D [3] [3] = 2$ が編集距離である。実際、先頭の $s$ を削除し（コスト 1）、末尾に $t$ を挿入すれば（コスト 1）、 $sea \to ea \to eat$ とコスト 2 で作り替えられる。

答え: $2$

よくある誤り

0 行目・0 列目をすべて $0$ にしてしまう誤り。正しくは $D [0] [j] = j c_{ins}$ 、 $D [i] [0] = i c_{del}$ である。空文字列との間でも、文字数分の挿入や削除が必要になる。
文字が一致しているのに置換コストを足してしまう誤り（例： $x_{i} = y_{j}$ でも $D [i - 1] [j - 1] + c_{sub}$ とする）。正しくは、一致なら $D [i - 1] [j - 1] + 0$ である。
削除と挿入の向きを取り違える誤り。上のマス $D [i - 1] [j]$ から来るのは $x_{i}$ の削除で $+ c_{del}$ 、左のマス $D [i] [j - 1]$ から来るのは $y_{j}$ の挿入で $+ c_{ins}$ である。 $c_{del} \neq = c_{ins}$ のときに逆にすると、 $y \to x$ の距離を計算したことになり、答えが変わる。
答えとして最終行の最小値や表全体の最小値を取ってしまう誤り。正しくは $x$ 全体を $y$ 全体に作り替えるコストなので、右下の $D [m] [n]$ だけが答えである。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

編集距離

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題