アルゴリズムと計算量の問題

$s$ の先頭 $i$ 文字と $t$ の先頭 $j$ 文字の編集距離を $D(i,j)$ とする（$0\le i\le 6$, $0\le j\le 6$）。$s$ の $i$ 文字目を $s_i$、$t$ の $j$ 文字目を $t_j$ と書く。

最後の文字に注目すると、最後の操作は「$s_i$ を削除」「$t_j$ を挿入」「$s_i$ を $t_j$ に合わせる（等しければコスト $0$、異なれば置換でコスト $1$）」のどれかなので、
$$D(i,0)=i,D(0,j)=j,$$
$$D(i,j)=\min \{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+c_{ij}\}$$
が成り立つ。ここで $s_i=t_j$ なら $c_{ij}=0$、$s_i\ne t_j$ なら $c_{ij}=1$ である。

この漸化式で、$i$ の小さい行から順に表を埋める（行が $s$ の文字、列が $t$ の文字）。

いくつか計算を確かめておく。

• $D(1,4)$: $s_1=\text{P}=t_4$ なので $D(0,3)+0=3$。ほかの候補 $D(0,4)+1=5$, $D(1,3)+1=4$ より小さいので $D(1,4)=3$
• $D(3,2)$: $s_3=\text{R}=t_2$ なので $D(2,1)+0=2$
• $D(4,3)$: $s_4=\text{A}=t_3$ なので $D(3,2)+0=2$
• $D(5,4)$: $s_5=\text{D}\ne \text{P}=t_4$ なので候補は $D(4,4)+1=4$, $D(5,3)+1=4$, $D(4,3)+1=3$ で、$D(5,4)=3$
• $D(6,5)$: $s_6=\text{E}=t_5$ なので $D(5,4)+0=3$
• $D(6,6)$: $s_6=\text{E}\ne \text{D}=t_6$ なので候補は $D(5,6)+1=5$, $D(6,5)+1=4$, $D(5,5)+1=5$ で、$D(6,6)=4$

よって編集距離は $D(6,6)=4$ である。

実際、表をたどると次の $4$ 回の操作で変換できる。
$$\text{PARADE}\stackrel{\text{P を削除}}{\to }\text{ARADE}\stackrel{\text{A}\to \text{D}}{\to }\text{DRADE}\stackrel{\text{D}\to \text{P}}{\to }\text{DRAPE}\stackrel{\text{末尾に D を挿入}}{\to }\text{DRAPED}$$

答えは $4$ である。

動的計画法で編集距離表 $d[i][j]$（$s$ の先頭 $i$ 文字と $t$ の先頭 $j$ 文字の編集距離）を作る。漸化式は $d[i][j]=\min (d[i-1][j]+1,d[i][j-1]+1,d[i-1][j-1]+[s_i\ne t_j])$、初期値は $d[i][0]=i,d[0][j]=j$。

$t=$ DRAPED の列 ($j=0,\dots ,6$) に対し、各行は次のようになる。

• 空 : 0 1 2 3 4 5 6
• P : 1 1 2 3 3 4 5
• A : 2 2 2 2 3 4 5
• R : 3 3 2 3 3 4 5
• A : 4 4 3 2 3 4 5
• D : 5 4 4 3 3 4 4
• E : 6 5 5 4 4 3 4

右下の値より、編集距離は $4$。

検算（具体的な操作列）: PARADE から、P を D に置換して DARADE、A を R に置換して DRRADE、R を A に置換して DRAADE、続く A を P に置換して DRAPDE、……とすると 5 回以上かかってしまうので別の経路を使う。PARADE の先頭の P を削除して ARADE、R の前に D を挿入して... とするのも遠回りである。表の経路をたどると、PARADE → (P→D) DARADE → (A→R) DRRADE ではなく、アラインメント P-D, A-R, R-A, A-P, D-E, E-D の 6 置換は 6 回で、これより良い経路として、先頭に D を挿入して DPARADE、P を R に置換して DRARADE、A を残し R を P に置換して DRAPADE、A を削除して DRPDE... のように調整しても 4 に達する経路が表の逆たどりで存在する。表の逆たどり: $(6,6)=4$ は $(5,5)=4$ ではなく $(6,5)=3$ からの挿入（D の挿入）。$(6,5)=3$ は E の一致で $(5,4)=3$、$(5,4)=3$ は P に関して D の削除 ($(4,4)=3$ から)、$(4,4)=3$ は $(4,3)=2$ からの P の挿入、$(4,3)=2$ は A の一致で $(3,2)=2$、$(3,2)=2$ は R の一致で $(2,1)=2$、$(2,1)=2$ は $(1,1)=1$ からの A の削除、$(1,1)=1$ は P→D の置換。すなわち、P→D（置換）、A を削除、R を残す、A を残す、P を挿入、D を削除、E を残す、D を挿入、で PARADE → DRAPED となり、操作は置換 1 + 削除 2 + 挿入 2 の合計 5 ではなく、削除 A・削除 D・挿入 P・挿入 D・置換 P→D の 5 回に見える。これは表の経路と食い違うので表を再確認する。

再確認: 先頭の A（$s_2$）を削除する代わりに $s_4$ の A を使うと、PARADE の P→D（置換）、A→R（置換）、R→A（置換）、A→P（置換）と並べるより、「P→D、A 削除」ではなく次の 4 回の経路がある。PARADE の P を D に置換して DARADE。A を削除して DRADE。A の後に P を挿入して DRAPDE。D を E に置換して DRAPEE ではなく、DRAPDE の D を残して末尾 E の前の D を削除し DRAPE、末尾に D を挿入して DRAPED。ここまでの操作は置換 1 + 削除 1 + 挿入 1 + 削除 1 + 挿入 1 = 5 であり、DRAPDE の D→E の置換と E→D の置換の 2 回でも 5 回になる。

そこでさらに丁寧に表を検算すると、最終行の値 $d[6][6]=\min (d[5][6]+1,d[6][5]+1,d[5][5]+1)=\min (5,4,5)=4$ である。$d[6][5]=3$（EとDPARAの比較ではなく、PARADE と DRAPE の距離）を具体的に作る: PARADE → DRAPE は、P→D 置換、A 削除、R 残す、A 残す、D→P 置換、E 残す、の 3 回。確かに 3 回で DRAPE が得られる（DARADE→DRADE ではなく、PARADE の P→D で DARADE、2 文字目の A を削除して DRADE、D→P で DRAPE）。さらに末尾に D を挿入して DRAPED。合計 4 回。

よって編集距離は $4$。下界は表の最小値より成り立つ。