東北大学 工学研究科 電気・情報系 2018年8月実施 基礎科目 問題4 情報基礎2

标签：

• Tohoku-University
• Minimum-Edit-Distance

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

日本語原文

長さ $m$ の文字列 $X$ から、長さ $n$ の文字列 $Y$ への変換を考える（$m,n\ge0$）。変換には、以下に示す挿入／削除操作を用いる。

• Insertion: $X$ のどこかに任意の一文字を挿入（一回の挿入の操作コストを $C_I$ と表記）
• Deletion: $X$ 中の一文字を削除（一回の削除の操作コストを $C_D$ と表記）

$X$ を $Y$ に変換する操作手順は無数に考えられるが、コストの合計が最小となる操作手順のみを考える。$X$ を $Y$ に変換する操作手順の最小コストを、$X$ から $Y$ への編集距離と呼ぶ。以下の問に答えよ。

(1) $C_I=C_D=1$、$X=acba$ および $Y=abacc$ の場合の編集距離を考える。編集距離を求める問題は、Fig. 4(a) に示すような $(m+1)\times(n+1)$ の格子状グラフを考えることで、辺重み付グラフ上の最短経路問題に帰着できる。Fig. 4(a) 中の右向きの辺は Insertion、下向きの辺は Deletion に対応する。また、右下向きの破線の辺は文字が一致するので Insertion および Deletion が不要であることを表す。

(a) $X_i$ と $Y_j$ を、それぞれ、$X$ の先頭から $i$ 番目の文字までの部分文字列と、$Y$ の先頭から $j$ 番目の文字までの部分文字列とする。全ての $(i,j)$ ペアに対して、$X_i$ から $Y_j$ への編集距離を求め、その結果を Fig. 4(b) にある表の空欄を埋める形式で示せ。

(b) Fig. 4(a) のグラフ中の各頂点を対応する $(i,j)$ で表記する。$(0,0)$ から $(m,n)$ への最短経路を頂点 $(i,j)$ の系列で一つ示せ。

系列の表記の例：$(0,0),(0,1),(0,2),(1,3),(2,4),(3,4),(3,5),(4,5)$

(2) 新たな操作として以下が追加されたとする。

• Substitution: $X$ 中の一文字を別の一文字に置換（一回の置換の操作コストを $C_S$ と表記）

$C_I=C_D=1$、$C_S=1.5$、$X=ccbac$ および $Y=acdb$ の場合の編集距離を考える。

(a) Fig. 4(a) と同じ形式で、$X$ から $Y$ への編集距離を求める問題に対応する最短経路問題のグラフを示せ。Substitution は二重矢印を用いて表せ。

二重矢印の表記の例：$\Rightarrow$

(b) 問 (1)(b) で示した表記の例に従って、$(0,0)$ から $(m,n)$ への全ての最短経路をそれぞれ頂点 $(i,j)$ の系列で示せ。

题目描述

将长度 $m$ 的字符串 $X$ 变为长度 $n$ 的字符串 $Y$。插入、删除一个字符的代价分别为 $C_I,C_D$；总费用的最小值称编辑距离。

以顶点 $(i,j)$ 表示 $X$ 的前 $i$ 个字符到 $Y$ 的前 $j$ 个字符。向右边表示插入，向下边表示删除；当 $X_i=Y_j$ 时，从 $(i-1,j-1)$ 到 $(i,j)$ 有权 $0$ 的匹配边。

(1) $C_I=C_D=1,\ X=acba,\ Y=abacc$。

• (a) 求所有前缀对的编辑距离，填成 $5\times6$ 表格。
• (b) 写出从 $(0,0)$ 到 $(4,5)$ 的一条最短路径的顶点序列。

(2) 增加字符替换操作，费用 $C_S$。令 $C_I=C_D=1,\ C_S=1.5,\ X=ccbac,\ Y=acdb$。

• (a) 画出相应的加权格点图，用双箭头表示替换边。
• (b) 写出每一条最短路径的顶点序列。

Kai

(1)

令 $d_{i,j}$ 为前缀距离，$d_{i,0}=i,d_{0,j}=j$，递推为

$$d_{i,j}=\min\left\{d_{i-1,j}+1,\ d_{i,j-1}+1,\ d_{i-1,j-1}\ \text{（仅当 }X_i=Y_j\text{）}\right\}.$$

(a)

$i\backslash j$	0	1	2	3	4	5
0	0	1	2	3	4	5
1	1	0	1	2	3	4
2	2	1	2	3	2	3
3	3	2	1	2	3	4
4	4	3	2	1	2	3

(b) 最短距离为 $3$，路径为

$$(0,0),(1,1),(2,1),(3,2),(4,3),(4,4),(4,5).$$

即删除原串中的 $c$，末尾插入两个 $c$。

(2)

(a) 横边、竖边权均为 $1$，匹配虚线边权为 $0$，双线替换边权为 $1.5$。

(b) 在递推中增加替换候选值 $d_{i-1,j-1}+1.5$。所得距离表为

$i\backslash j$	0	1	2	3	4
0	0	1	2	3	4
1	1	1.5	1	2	3
2	2	2.5	1.5	2.5	3.5
3	3	3.5	2.5	3	2.5
4	4	3	3.5	4	3.5
5	5	4	3	4	4.5

最短距离为 $\boxed{4.5}$，全部最短路径为

$$\begin{aligned} &(0,0),(1,1),(2,2),(2,3),(3,4),(4,4),(5,4),\\ &(0,0),(0,1),(1,2),(2,3),(3,4),(4,4),(5,4). \end{aligned}$$

第一条：将首个 $c$ 替换为 $a$，在 $b$ 前插入 $d$，删除末尾 $a,c$。

第二条：在开头插入 $a$，将第二个 $c$ 替换为 $d$，删除末尾 $a,c$。