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

$X=x_1{x}_2\cdots x_6=\mathrm{BRIDGE}$、$Y=y_1{y}_2\cdots y_6=\mathrm{BADGER}$ とし、$X$ の先頭 $i$ 文字を $Y$ の先頭 $j$ 文字に変える最小コストを $D(i,j)$ とおく（$0\le i,j\le 6$）。

漸化式 最適な操作列で、$X$ の先頭 $i$ 文字の最後の文字 $x_i$ と $Y$ の先頭 $j$ 文字の最後の文字 $y_j$ の扱いを考えると、次のどれかになる。

• $x_i$ を削除する: $D(i-1,j)+2$
• $y_j$ を挿入する: $D(i,j-1)+2$
• $x_i$ を $y_j$ に対応させる（同じ文字ならそのまま、異なれば置換）: $D(i-1,j-1)+c_{ij}$。ただし $x_i=y_j$ のとき $c_{ij}=0$、$x_i\ne y_j$ のとき $c_{ij}=3$

よって
$$D(i,j)=\min \{D(i-1,j)+2,D(i,j-1)+2,D(i-1,j-1)+c_{ij}\}$$
であり、初期値は $D(i,0)=2i$（すべて削除）、$D(0,j)=2j$（すべて挿入）である。

表の計算 行を $X$ の先頭 $i$ 文字、列を $Y$ の先頭 $j$ 文字として、上の行から順に埋める。

いくつかの成分の計算を示す。

• $D(1,1)$: $x_1=y_1=\mathrm{B}$ なので $\min \{2+2,2+2,0+0\}=0$。
• $D(2,2)$: $\mathrm{R}\ne \mathrm{A}$ なので $\min \{D(1,2)+2,D(2,1)+2,D(1,1)+3\}=\min \{4,4,3\}=3$。
• $D(4,3)$: $x_4=y_3=\mathrm{D}$ なので $\min \{D(3,3)+2,D(4,2)+2,D(3,2)+0\}=\min \{8,9,5\}=5$。
• $D(5,4)$: $x_5=y_4=\mathrm{G}$ なので $\min \{D(4,4)+2,D(5,3)+2,D(4,3)+0\}=\min \{9,9,5\}=5$。
• $D(6,5)$: $x_6=y_5=\mathrm{E}$ なので $\min \{D(5,5)+2,D(6,4)+2,D(5,4)+0\}=\min \{9,9,5\}=5$。
• $D(6,6)$: $\mathrm{E}\ne \mathrm{R}$ なので $\min \{D(5,6)+2,D(6,5)+2,D(5,5)+3\}=\min \{11,7,10\}=7$。

したがって $d(X,Y)=D(6,6)=7$ である。

最適な操作列の例 表をたどると、次の操作列が得られる。

1. $\mathrm{R}$ を $\mathrm{A}$ に置換（コスト $3$）: $\mathrm{BRIDGE}\to \mathrm{BAIDGE}$
2. $\mathrm{I}$ を削除（コスト $2$）: $\to \mathrm{BADGE}$
3. 末尾に $\mathrm{R}$ を挿入（コスト $2$）: $\to \mathrm{BADGER}$

合計コストは $3+2+2=7$ である。なお、挿入と削除だけを使うと、最長共通部分列 $\mathrm{BDGE}$（長さ $4$）を残して削除 $2$ 回・挿入 $2$ 回が必要になり、コストは $8$ になる。置換 $1$ 回が削除と挿入の組（コスト $4$）より安いことが効いて、最小値は $7$ になる。

重み付き編集距離の最小値を、アラインメント（対応づけ）で考える。

まず上界を求める。次の操作列で $\mathrm{BRIDGE}$ を $\mathrm{BADGER}$ に変えられる。
- B は一致するのでコスト $0$
- R を A に置換する（コスト $3$）
- I を削除する（コスト $2$）
- D, G, E は一致するのでコスト $0$
- 末尾に R を挿入する（コスト $2$）

合計は $3+2+2=7$ である。

次に、これより小さくできないことを確かめる。
- 最長共通部分列は BDGE（長さ $4$）である。
- BDGE を一致させる場合、X 側の余りは R, I で、Y 側の余りは A と、末尾の R である。
- B と D の間は、X 側が RI、Y 側が A である。コスト最小は置換と削除の組合せで $3+2=5$ である。
- E の後は、Y 側にだけ R がある。挿入で $2$ かかる。
- 合計は $7$ である。
- 置換が $3$ で、挿入と削除の和 $4$ より安いので、置換を使うのが有利である。ただし、一致が $4$ 文字より少ない対応づけは、余る文字が増えてコストが $7$ 以上になる。例えば B と E だけを一致させると、間の RIDG と ADG の対応づけに少なくとも $3+3+3+2=11$ かかる。
- 一致 BDGE を使わない場合も、$7$ を下回る対応づけはない。

よって最小コストは $7$ である。