京都大学 情報学研究科 知能情報学専攻 2020年8月実施 情報学基礎 F2-1

标签：

• Kyoto-University
• Minimum-Edit-Distance

Author

祭音Myyura

Description

削除、挿入、置換により数列 $A$ を数列 $B$ に変形する編集操作列を考える。$A$ と $B$ の各要素は以下の通りである。

$$A[1] = 8, \; A[2] = -4, \; A[3] = 1, \; A[4] = -6$$

$$B[1] = 7, \; B[2] = 2, \; B[3] = -4, \; B[4] = 3$$

任意の $A$ の要素 $a$ と $B$ の要素 $b$ に対し、$a$ を削除するコストは $|a|$, $b$ を挿入するコストは $|b|$, $a$ から $b$ へ置換するコストは $|a - b|$ とする。 なお $A$ の左端や右端にも挿入操作は可能である。 以下では2つの編集操作列において、編集操作の順序がのみ異なる場合は、同一の編集操作列とみなす。 例えば図1のように、$A$ の左端に $7$ を挿入、$8$ を $2$ に置換、$-4$ を削除、$1$ を $-4$ に置換、$-6$ を $3$ に置換する編集操作列のコストは $7 + 6 + 4 + 5 + 9 = 31$ となるが、これは最小ではない。

図1: 編集操作列の例（順不同）

     8    -4    1    6
|    |     |    |    |
7    2         -4    3

$A[i:j]$ を $A$ の $i$ 番目から $j$ 番目の連続する要素で構成される数列とし、$B[i:j]$ も同様に定義する。 $M(m, n)$ を $A[1:m]$ を $B[1:n]$ に変形するコスト最小の編集操作列のコストとする。 動的計画法に基づくアルゴリズムに関する以下の設問に答えよ。

設問1 $M(1, 1), M(1, 2), M(1, 3), M(1, 4)$ の値をそれぞれ求めよ。

設問2 $M(2, 1), M(3, 1), M(4, 1)$ の値をそれぞれ求めよ。

設問3 $M(4, 4)$ を $M(3, 3), M(3, 4), M(4, 3)$ を用いて表現せよ。

設問4 $M(4, 4)$ の値を求めよ。

設問5 $A$ を $B$ に変形するコスト最小の編集操作列をすべて図1のように示せ。

题目描述

用删除、插入、替换把数列

$$A=(8,-4,1,-6)$$

变为

$$B=(7,2,-4,3).$$

删除 $a$ 的代价为 $|a|$，插入 $b$ 的代价为 $|b|$，将 $a$ 替换为 $b$ 的代价为 $|a-b|$；也可在 $A$ 两端插入。若两个编辑方案仅操作顺序不同，视为同一方案。题中示例方案总代价为 $7+6+4+5+9=31$，但并非最小。

令 $A[i:j]$、$B[i:j]$ 表示相应连续子序列，$M(m,n)$ 为把 $A[1:m]$ 变为 $B[1:n]$ 的最小代价。基于动态规划回答：

1. 分别求 $M(1,1),M(1,2),M(1,3),M(1,4)$。
2. 分别求 $M(2,1),M(3,1),M(4,1)$。
3. 用 $M(3,3),M(3,4),M(4,3)$ 表示 $M(4,4)$。
4. 求 $M(4,4)$。
5. 按题中对齐图的形式，列出把 $A$ 变为 $B$ 的全部最小代价编辑方案。

考点

• 最小编辑距离动态规划：以两个前缀长度为状态，在删除、插入、替换三种末步间取最小，并使用本题的数值相关代价。
• 最优方案回溯：从 DP 表右下角沿所有达到最小值的前驱回溯，枚举不同对齐方式且去除仅操作顺序不同的重复方案。

Kai

$$M[i][j] = \min \begin{cases} M[i-1][j]+|A_{i}|\\ M[i][j-1]+|B_{j}|\\ M[i-1][j-1]+|A_{i}-B_{j}| \end{cases}$$

設問1

$$M(1,1) = 1, \ M(1,2) = 3, \ M(1,3) = 7, \ M(1,4) = 10$$

設問2

$$M(2,1) = 5, \ M(3,1) = 6, \ M(4,1) = 12$$

設問3

$$M(4,4) = \min \begin{cases} M(3,3) + 9\\ M(3,4) + 6\\ M(4,3) + 3 \end{cases}$$

設問4

$$M(4,4) = 11$$

設問5

 8        -4    1   -6
 |    |    |    |    |
 7    2   -4    3

 8   -4    1   -6   
 |    |    |    |    |
 7         2   -4    3