編集距離で理解する動的計画法（DP）

おひさしぶりんこ。

今日は動的計画法（DP）で編集距離（Edit distance）を計算します。

計算結果の記録と漸化式による次の値の計算がDPの要点だと思うので、編集距離の計算を例にこれを見ていきます。

編集距離とは

2つの文字列が与えられたとき、一方の文字列に挿入（Insert）、削除（Delete）、置換（Replace）のいずれかの操作を繰り返し適用すると、もう一方の文字列に一致させることができます。
これら3つの操作を「編集」と呼びます。

一方の文字列を編集し、もう一方の文字列に一致させるのに要する最小の編集回数のことを編集距離といいます。
何の意味もないですが、やろうと思えばいくらでも無駄な操作が可能なので、最小回数が編集距離になります。

編集距離が小さければその文字列はお互いに似ている、ということは直感的にもわかりやすいと思います。

DPによる編集距離の計算

$|S_1| = m$
$|S_2| = n$
とします。

$(m+1) \times (n+1)$の配列$D$を用意し、この上でDPの計算を行います。
結論からいうと、
$D[i][j]$には、

• $S_1$の先頭から$i$文字目まで$S_1^i$と
• $S_2$の先頭から$j$文字目まで$S_2^j$の

編集距離が格納されていきます。

なので、求めたい編集距離は、計算終了後に$D[m][n]$に格納されているはずです。

アルゴリズム

以下の2つの事実により、機械的に計算していくだけで、$D[m][n]$が求まります。

文字列$S_1$を編集し、文字列$S_2$へ帰着させる状況を考えます。

0行目および0列目の値は簡単に埋められる

1つ目は、配列$D$の0行目および0列目の値は簡単に埋められるという点です。

0行目とは、$D[0][j]$ですから、$S_1^0$（空文字列）と$S_2^j$の編集距離です。

これは、$D[0][j]=j$になることがすぐにわかります。なぜなら、$S_2^j$に一致するよう、空文字列$S_1^0$へ$j$回だけ文字を挿入させればよいからです。

同様の議論で、0列目も$D[i][0]=i$となることがわかります。

これで配列$D$の一番上の行（0行目）と一番左の列（0列目）が埋まりました。

セルの値は上・左・左上に隣接する3セルの値から計算できる

もう1つ目は、あるセルの値は上・左・左上に隣接する3セルの値から計算できる、という点です。

これはつまり、$D[i][j]$の値は、左の$D[i-1][j]$、上の$D[i][j-1]$、左上の$D[i-1][j-1]$から計算できるということになります。

左の$D[i-1][j]$と、$D[i][j]$を比べると、後者のほうが$S_1$側文字列が1文字長い状態です。

つまり、$S_1^{i-1}$に$i$文字目をInsert（挿入）すれば、$S_1^{i}$になり、$D[i][j]$と同じ状態になります。挿入操作が1回必要なので、

=> $D[i][j]=D[i-1][j]+1$

同様の議論で、

=> $D[i][j] = D[i][j-1]+1$

になります。

最後に、左上の$D[i-1][j-1]$のケースです。
これは、$D[i][j]$とどのように関係があるのでしょうか。
これに関しては、$S_1$の$i$文字目と、$S_2$の$j$文字目が一致するかどうかで場合分けします。

一致している場合、$S_1$の$i$文字目と、$S_2$の$j$文字目は一切編集不要なので、$S_1^{i-1}$と、$S_2^{j-1}$の編集距離のみ考えればよく、これは$D[i-1][j-1]$そのものです。

=> $D[i][j] = D[i-1][j-1]$

一致しない場合、$S_1$の$i$文字目を、$S_2$の$j$文字目にReplace（置換）すると、上記「一致する場合」と同じ状態になります。置換操作が1回必要なので、

=> $D[i][j] = D[i-1][j-1]+1$

となります。
このように、$D[i-1][j-1]$との関係は場合分けして計算します。

以上をもって$D[i][j]$の候補は、

• $D[i-1][j]+1$
• $D[i][j-1]+1$
• $D[i-1][j-1]$ if $S_1[i]==S_2[j]$ else $D[i-1][j-1]+1$

の3択に絞られました。
正解はこの中の最小値を取ります。編集距離は最小回数なので、最小値を取らないと無駄な操作をした回数を含んでしまいます。

一見して、1足しているだけのものが多いですが、$D[i-1][j]$、$D[i][j-1]$、$D[i-1][j-1]$はそれぞれ別の値なので、やはりこの中から最小値を選ぶ必要があります。

このように、漸化式などを用いて以前の計算結果を再利用するので、DPの基本になります。

0行目および0列目はすでに埋まっているため、あとはこの漸化式を適用していくだけで、表のマス目をすべて埋めることができます。

https://gitlab.com/-/snippets/2065496