動的計画法

問題 3-2 のプログラムでは,文字列 $X$ と $Y$ の編集距離 $c_{m,n}$ を,与えられた文字列長から順に遡って($c_{m, n}, c_{m-1, n-1}, c_{m, n-1}, …, c_{0,0}$)再帰的に計算した.しかし,この方法では,同じ値を複数回計算してしまう可能性があるため,効率面で問題がある.本問題では,編集距離をより効率的に計算する方法の一つとして,動的計画法 (Dynamic Programming) に基づく編集距離の計算を考える.

編集距離の漸化式より,$c_{i,j}$ を求めるためには,$c_{i-1,j-1}, c_{i-1,j}, c_{i,j-1}$ の3つの値が必要である.これを視覚的に理解するために,問題 3-0 の表を思い出して欲しい(一部変更済み):

$i \setminus j$ 0 1 2 3 4 5 6 7 $x_i$
0 0 1 2 3 4 5 6 7  
1 1 1 2 2 3 4 5 6 Q
2 2 2 A B 2 3 4 5 U
3 3 3 3 3 3 3 4 5 E
4 4 4 4 4 4 4 3 4 R
5 5 5 5 5 5 5 4 4 Y
$y_j$   I N Q U I R E  

表の上では,とある編集距離 ($c_{i,j}$) を計算するためには,(1) その左上 ($c_{i-1,j-1}$),(2) その左隣 ($c_{i,j-1}$),(3) その真上 ($c_{i-1,j}$) の値が必要である.裏を返せば,これらの3つの値が計算済みであれば,それらに囲まれるマスの値を計算できるということである.例えば,$c_{2,2}$ (A) は,その左上,左隣,真上である $c_{1,1},c_{1,2},c_{2,1}$ の値を利用して,$min(c_{1,1}+1,c_{1,2}+1,c_{2,1}+1)=min($1$+1,$2$+1,$2$+1)=2$ と求まる.

この位置関係に着目すると,表の一行目は,左から右へ値を五月雨式に埋めることができる.さらに,一行目の値が決まれば,二行目も左から右へ値を埋めていくことができる.例えば,$c_{2,3}$ (B) は,左隣の $c_{2,2}$ (A) の計算結果を利用し,$min(c_{1,2}+1,c_{2,2}+1,c_{1,3}+1)=min($2$+1,$A$=$2$+1,$2$+1)=3$ と求まる.同様に $c_{2,4},c_{2,5},…,c_{3,1},c_{3,2},…,c_{5,7}$ と計算をしていけば全ての値が埋まり,最終的に文字列 $X$ と $Y$ の編集距離 $c_{m,n}$ を求めることができる.

以上のように,再帰計算の深いところから順に値を求めていく(ボトムアップ (bottom up) に求める,ともいう)方法は,動的計画法 として知られている.動的計画法を用いることで,計算回数を $X$ と $Y$ の文字列長の積 $mn$ に抑えることができ,重複して部分的な編集距離を計算することはないため,単純な再帰計算を用いるプログラムよりも多くの場面で効率的である.

課題

動的計画法を用いて,$X = \mbox{“another”}$,$Y = \mbox{“actor”}$の編集距離を求めたい.そこで,$c_{i,j}$の漸化式を$c_{0,j}$および$c_{i,0}$を出発点として,手作業でボトムアップに計算し,すべての$c_{i,j}$の値を求めよ.$c_{i,j}$の値は,上記のような表形式でレポートにまとめよ.

参考資料