編集距離(edit distance)とは、2 つの文字列の一方を他方に変えるのに必要な 1 文字の削除・挿入・置換の最小の回数で、Levenshtein 距離ともいい、綴りの訂正、配列の比較、文字列の検索に使う。文字列の全体の上の距離であり、最小の回数は 2 つの文字列をそろえる整列の費用の最小値に等しい。整列の最後の列で場合分けした再帰式により、長さ $m,n$ の文字列で $O(mn)$ の手間で計算できる。距離が小さいときは帯の中だけを計算すれば速く、解の復元は $O(m+n)$ の記憶でできる。
編集距離(edit distance)は、2 つの文字列の違いを、一方を他方に変えるのに必要な 1 文字の削除・挿入・置換の最小の回数で測る量である。Levenshtein 距離(Levenshtein distance)ともいう。綴りの誤りの訂正、遺伝子の配列の比較、音声認識、近い文字列の検索など、「ほぼ同じ」文字列を扱う場面の基本の道具である。
たとえば KITTEN は、K を S に、E を I に置き換え、末尾に G を挿入すると SITTING になるので、KITTEN と SITTING の距離は $3$ 以下で、実際 $3$ である。「$3$ より少なくできない」ことは、操作の列をいくら眺めても見えない。この記事の要点は、操作の列の問題を、2 つの文字列を縦に並べる 整列 の問題に直すことにある。
有限集合 $\Sigma$ を 文字 の集合とし、$\Sigma$ の元の有限列を 文字列 という。文字列の全体を $\Sigma^*$ と書き、$X=x_1\cdots x_m$ の長さを $\lvert X\rvert=m$ と書く。長さ $0$ の文字列(空文字列)を $\epsilon$ と書く。
文字列に対する次の 3 つを 編集操作 という。
(a) 削除:1 文字を取り除く。
(b) 挿入:任意の位置に 1 文字を入れる。
(c) 置換:1 文字を別の文字に置き換える。
$X$ を $Y$ に変える編集操作の列の長さの最小値を $X,Y$ の 編集距離 といい、$d(X,Y)$ と書く。
$X$ の文字をすべて削除してから $Y$ の文字を挿入すれば $Y$ になるので、$d(X,Y)\le m+n$ で、最小値は存在する。
次に、操作の順序を捨てて、対応だけを記録する。
$X=x_1\cdots x_m$、$Y=y_1\cdots y_n$ の 整列 とは、集合 $M\subset\{1,\dots,m\}\times\{1,\dots,n\}$ で、異なる 2 つの元 $(i,j),(i',j')\in M$ について、$i< i'$ と $j< j'$ が同値であるものをいう。この条件は、$M$ の元どうしで $i$ も $j$ も重ならず、対応の線が交差しないことを表す。その 費用 を
$$
c(M):=(m-\lvert M\rvert)+(n-\lvert M\rvert)+\#\{(i,j)\in M:x_i\ne y_j\}
$$
と定める。第 1 項は対応のない $X$ の文字の数、第 2 項は対応のない $Y$ の文字の数、第 3 項は文字の異なる対応の数である。
2 行に書くと、整列は隙間 $-$ を入れて文字列をそろえたものである。
$$
\begin{array}{ccccccc}
\mathrm{K}&\mathrm{I}&\mathrm{T}&\mathrm{T}&\mathrm{E}&\mathrm{N}&-\\
\mathrm{S}&\mathrm{I}&\mathrm{T}&\mathrm{T}&\mathrm{I}&\mathrm{N}&\mathrm{G}
\end{array}
$$
この整列は費用 $3$ で、文字の異なる列の数がそのまま費用である。
使える条件は次のとおりである。
(i) 操作の費用が 1:3 つの操作の費用がすべて $1$ である。費用を変えるときは、費用が三角不等式を満たすことが要る(rem-ed-weighted)。
(ii) 文字の比較が $O(1)$:手間の評価は、文字の比較が 1 回の演算でできるとしたものである。
(iii) 操作は 1 文字ずつ:隣の 2 文字の交換のような操作を足すと、別の距離になる(ex-ed-counterexamples)。
$X,Y$ の長さを $m,n$ とする。
| 量 | 式または再帰式 | 手間 | 距離の公理 | 根拠 |
|---|---|---|---|---|
| 編集距離 $d$ | thm-ed-recursion | $O(mn)$ | 満たす | thm-ed-metric |
| 削除と挿入だけの距離 $d_{\mathrm{id}}$ | $m+n-2L(X,Y)$($L$ は最長共通部分列の長さ) | $O(mn)$ | 満たす | prop-ed-indel |
| Hamming 距離 | 長さが等しい文字列の、文字の異なる位置の数 | $O(n)$ | 満たす | 定義から直接 |
| 帯での判定 $d\le k$ | 帯 $\lvert i-j\rvert\le k$ の中だけ再帰式を計算 | $O((k+1)\min\{m,n\})$ | prop-ed-band | |
| 検索 | $S(0,j)=0$ として同じ再帰式 | $O(mn)$ | prop-ed-search | |
| 重み付きの編集距離 | $+1$ を操作の費用に替える | $O(mn)$ | 費用が距離なら満たす | rem-ed-weighted |
| 隣の交換を足した再帰式 | $D(i-2,j-2)+1$ の項を足す | $O(mn)$ | 満たさない | ex-ed-counterexamples |
| 長さで割った値 $d/\max\{m,n\}$ | $O(mn)$ | 満たさない | ex-ed-counterexamples |
手間の下界:文字が 7 種類の長さ $n$ の文字列の編集距離が、ある $\delta>0$ について $O(n^{2-\delta})$ で計算できれば、$N$ 変数 $M$ 節の CNF の充足可能性がある $\varepsilon>0$ について $M^{O(1)}2^{(1-\varepsilon)N}$ の手間で解け、強指数時間仮説(SETH)に反する(BI17 pp. 1、3。この記事では証明しない)。SETH はこれを否定する仮説である。BI17 の時点で知られていた最速の厳密な方法の手間は $O(n^2/\log^2n)$ である(BI17 p. 1)。
整列を合成する。$M$ を $X,Y$ の整列、$M'$ を $Y,Z$ の整列とし、
$$
M'\circ M:=\{(i,k):\text{ある }j\text{ について }(i,j)\in M,\ (j,k)\in M'\}
$$
とおく。$M,M'$ が単調なので、$M'\circ M$ も $X,Z$ の整列である。
$c(M'\circ M)\le c(M)+c(M')$ である。
$c(M'\circ M)$ の項は次の 3 種類である。
$X$ の文字 $i$ で $M'\circ M$ の対応がないもの:$M$ に対応がなければ、$c(M)$ の「対応のない $X$ の文字 $i$」に結びつける。$(i,j)\in M$ なら、$j$ は $M'$ の対応をもたないので、$c(M')$ の「対応のない $Y$ の文字 $j$」に結びつける。
$Z$ の文字 $k$ で $M'\circ M$ の対応がないもの:$M'$ に対応がなければ、$c(M')$ の「対応のない $Z$ の文字 $k$」に結びつける。$(j,k)\in M'$ なら、$j$ は $M$ の対応をもたないので、$c(M)$ の「対応のない $Y$ の文字 $j$」に結びつける。
対応 $(i,k)\in M'\circ M$ で $x_i\ne z_k$ のもの:$(i,j)\in M$、$(j,k)\in M'$ となる $j$ について、$x_i\ne y_j$ か $y_j\ne z_k$ である。前者なら $c(M)$ の「文字の異なる対応 $(i,j)$」に、そうでなければ $c(M')$ の「文字の異なる対応 $(j,k)$」に結びつける。
この結びつけ方は単射である。$M$ と $M'$ のそれぞれについて項の種類を見ると、$c(M)$ の「対応のない $X$ の文字」と「文字の異なる対応」、$c(M')$ の「対応のない $Z$ の文字」と「文字の異なる対応」には、もとの項が 1 つしか結びつかない。$c(M')$ の「対応のない $Y$ の文字 $j$」には $(i,j)\in M$ となる $i$ だけが、$c(M)$ の「対応のない $Y$ の文字 $j$」には $(j,k)\in M'$ となる $k$ だけが結びつき、$M,M'$ の中で $j$ の相手は 1 つである。よって項の数を比べて主張を得る。$\square$
$$
d(X,Y)=\min_Mc(M)
$$
である。$M$ は $X,Y$ の整列全体を動く。
$d(X,Y)\le c(M)$:整列 $M$ が与えられたとする。文字の異なる対応 $(i,j)$ ごとに $x_i$ を $y_j$ に置換し、対応のない $X$ の文字を削除すると、$M$ の第 2 成分の順に並んだ $Y$ の部分列になる。対応のない $Y$ の文字を正しい位置に挿入すると $Y$ になる。操作の数は $c(M)$ である。
$\min_Mc(M)\le d(X,Y)$:まず $X$ から 1 回の操作で $Y$ が得られるとき、費用 $1$ の整列がある。$x_i$ の削除なら $\{(k,k):k< i\}\cup\{(k,k-1):k>i\}$、挿入はこの逆、置換なら $\{(k,k):1\le k\le m\}$ である。空の操作の列には費用 $0$ の整列 $\{(k,k)\}$ が対応する。操作の列 $X=X_0\to X_1\to\dots\to X_r=Y$ について、各段の費用 $1$ 以下の整列を順に合成すると、lem-ed-compose により費用 $r$ 以下の $X,Y$ の整列を得る。$\square$
$X,Y,Z\in\Sigma^*$ とし、$m=\lvert X\rvert$、$n=\lvert Y\rvert$ とする。
(1) $d(X,Y)=0$ と $X=Y$ は同値である。
(2) $d(X,Y)=d(Y,X)$ である。
(3) $d(X,Z)\le d(X,Y)+d(Y,Z)$ である。
(4) $\lvert m-n\rvert\le d(X,Y)\le\max\{m,n\}$ である。
(5) $m=n$ なら、$d(X,Y)$ は文字の異なる位置の数(Hamming 距離)以下である。
(6) 文字列を逆順にしても距離は変わらない。
とくに $(\Sigma^*,d)$ は 距離空間 である。
$X_i:=x_1\cdots x_i$、$Y_j:=y_1\cdots y_j$、$D(i,j):=d(X_i,Y_j)$ とし、$x_i=y_j$ なら $\delta_{ij}:=0$、そうでなければ $\delta_{ij}:=1$ とする。
$D(i,0)=i$、$D(0,j)=j$ であり、$i,j\ge1$ について
$$
D(i,j)=\min\{D(i-1,j)+1,\ D(i,j-1)+1,\ D(i-1,j-1)+\delta_{ij}\}
$$
である。
$D(i,0)=i$、$D(0,j)=j$ は thm-ed-metric の (4) から従う。$i,j\ge1$ とする。
$\le$:$X_{i-1},Y_j$ の整列は $X_i,Y_j$ の整列でもあり、費用は $1$ 増える。$X_i,Y_{j-1}$ の整列も同様である。$X_{i-1},Y_{j-1}$ の整列に $(i,j)$ を足すと、費用は $\delta_{ij}$ 増える。thm-ed-alignment により右辺の 3 項は左辺以上である。
$\ge$:$X_i,Y_j$ の最小費用の整列 $M$ をとる。$(i,j)\in M$ なら、$(i,j)$ を除くと $X_{i-1},Y_{j-1}$ の整列で費用は $\delta_{ij}$ 減る。$(i,j)\notin M$ のとき、$i$ に対応がないか、$j$ に対応がない。実際、$(i,j')\in M$、$(i',j)\in M$ なら $i'< i$、$j'< j$ で、対応が交差する。$i$ に対応がなければ $M$ は $X_{i-1},Y_j$ の整列で費用は $1$ 小さく、$j$ に対応がなければ $X_i,Y_{j-1}$ の整列で費用は $1$ 小さい。どの場合も左辺は右辺の 1 項以上である。$\square$
$(i,j)$ を部分問題とし、3 つの場合を選択とすると、結合の関数 $x+1$、$x+1$、$x+\delta_{ij}$ は単調で、$i+j$ が減るので依存に閉路がない。これは 動的計画法 の定理「再帰式の正しさ」の形である。
$i,j\ge1$ について次が成り立つ。
(1) $\lvert D(i,j)-D(i-1,j)\rvert\le1$、$\lvert D(i,j)-D(i,j-1)\rvert\le1$ である。
(2) $0\le D(i,j)-D(i-1,j-1)\le1$ である。
(3) $x_i=y_j$ なら $D(i,j)=D(i-1,j-1)$ である。
削除と挿入だけを許す操作の列の長さの最小値を $d_{\mathrm{id}}(X,Y)$ とし、$X,Y$ の共通部分列の長さの最大値を $L$ とする。このとき
$$
d_{\mathrm{id}}(X,Y)=m+n-2L,\qquad d(X,Y)\le d_{\mathrm{id}}(X,Y)\le2\,d(X,Y)
$$
である。
第 1 の等式は 最長共通部分列 の定理「3 つの量の関係」である(そこでの $D(X,Y)$ が $d_{\mathrm{id}}(X,Y)$ である)。
$d\le d_{\mathrm{id}}$ は明らかである。置換 1 回は削除と挿入の 2 回で実現できるので $d_{\mathrm{id}}\le2d$ である。$\square$
$k\ge0$ を整数とし、$m,n\ge1$ とする。再帰式を $\lvert i-j\rvert\le k$ のマスだけで計算し、帯の外のマスの値を $+\infty$ として得た値を $D_k$ とする。このとき、$d(X,Y)\le k$ なら $D_k(m,n)=d(X,Y)$ であり、$d(X,Y)>k$ なら $D_k(m,n)>k$ である。手間は $O\bigl((k+1)\min\{m,n\}\bigr)$ である。ただし $\lvert m-n\rvert>k$ なら、計算せずに $d(X,Y)>k$ と答える。
表の上で $(0,0)$ から $(m,n)$ へ、$(i-1,j)$、$(i,j-1)$、$(i-1,j-1)$ から $(i,j)$ へ進む道を考える。辺の費用はそれぞれ $1,1,\delta_{ij}$ である。thm-ed-recursion から、$D(i,j)$ は $(i,j)$ への道の費用の最小値である。同様に $D_k(i,j)$ は帯の中の道の費用の最小値なので、$D_k\ge D$ である。
費用 $r$ の道が $(i,j)$ を通るとする。そこまでの部分の費用は $D(i,j)\ge\lvert i-j\rvert$ 以上である(thm-ed-metric の (4))。よって $r\ge\lvert i-j\rvert$ である。したがって費用が $k$ 以下の道はすべて帯の中にある。$d(X,Y)\le k$ なら最小費用の道は帯の中にあるので $D_k(m,n)=d(X,Y)$ である。$d(X,Y)>k$ なら $D_k(m,n)\ge d(X,Y)>k$ である。
手間:thm-ed-metric の (2) により $m\le n$ としてよい。行は $m+1$ 個で、各行の帯のマスは $2k+1$ 個以下である。$\square$
$d(X,Y)$ が分からないときは、$k=1,2,4,8,\dots$ と増やして、$D_k(m,n)\le k$ となったら止める。手間の和は最後の $k$ の定数倍で抑えられ、$O\bigl((d(X,Y)+1)\min\{m,n\}\bigr)$ である。よく似た長い文字列では、これは全体の表よりずっと速い。
距離の値だけなら、表の前の行だけを残せばよいので、記憶は $O(\min\{m,n\})$ で済む。整列そのものを復元するには全体の表が要るように見えるが、次の式で分割統治ができる。
$0\le h\le m$ を固定し、$X=X'X''$($\lvert X'\rvert=h$)とする。このとき
$$
d(X,Y)=\min_{0\le j\le n}\bigl\{d(X',Y_j)+d(X'',y_{j+1}\cdots y_n)\bigr\}
$$
である。
$\le$:$X',Y_j$ の整列と、$X'',y_{j+1}\cdots y_n$ の整列を(添字をずらして)合わせると、$X,Y$ の整列で費用は和である。
$\ge$:$X,Y$ の最小費用の整列 $M$ をとる。$i\le h$ の元の第 2 成分の最大値を $j$ とする(なければ $j=0$)。$M$ を $i\le h$ の部分と $i>h$ の部分に分ける。単調性から、$i>h$ の元の第 2 成分は $j$ より大きい。前半は $X',Y_j$ の整列、後半は $X'',y_{j+1}\cdots y_n$ の整列で、費用の和は $c(M)$ に等しい。thm-ed-alignment による。$\square$
計算は次のとおりである。$h=\lfloor m/2\rfloor$ とし、前半は表の最後の行 $D(h,\cdot)$ を、後半は逆順の文字列の表の最後の行を、2 行だけの記憶で計算する。和を最小にする $j$ を選び、$(X',Y_j)$ と $(X'',y_{j+1}\cdots y_n)$ について再帰する。
$2\le m\le n$ とする(長さが逆なら $X,Y$ を入れ替える)。上の方法の手間は $O(mn)$、記憶は $O(m+n)$ である。
再帰の深さ $t$ の部分問題を $(X_s,Y_s)$ とし、長さを $m_s,n_s$ とする。$X$ を半分に切り続けるので $m_s\le m/2^t+1$ であり、部分問題は $2^t$ 個以下で、$Y_s$ は $Y$ の互いに交わらない部分なので $\sum_sn_s\le n$ である。1 つの部分問題の手間はマスの数 $(m_s+1)(n_s+1)$ の定数倍なので、深さ $t$ の手間の和は
$$
\sum_s(m_s+1)(n_s+1)\le\Bigl(\frac m{2^t}+2\Bigr)(n+2^t)=\frac{mn}{2^t}+m+2n+2^{t+1}
$$
以下である。$m_s\le1$ になれば再帰を止めるので、深さは $L:=\lceil\log_2m\rceil$ 以下である。$t=0,\dots,L$ で足すと $2mn+(L+1)(m+2n)+2^{L+2}$ 以下である。$m\le n$ と $L+1\le2m$、$2^L< 2m$ から、これは $O(mn)$ である。
記憶:計算中に残すのは、今の部分問題の 2 行と、再帰の途中の添字($O(\log m)$ 個)と、得られた対応のリスト($O(m+n)$)である。行は $j$ を選んだら捨てる。$\square$
長い文字列 $T=t_1\cdots t_n$ の中に、パターン $P=p_1\cdots p_m$ に近い部分があるかを調べる。部分文字列の始まりを自由にするには、表の最初の行を $0$ にすればよい。
$S(i,j):=\min_{0\le a\le j}d(p_1\cdots p_i,\ t_{a+1}\cdots t_j)$ とおく。$S(0,j)=0$、$S(i,0)=i$ であり、$i,j\ge1$ について
$$
S(i,j)=\min\{S(i-1,j)+1,\ S(i,j-1)+1,\ S(i-1,j-1)+\delta_{ij}\}
$$
である。ここで $\delta_{ij}$ は $p_i=t_j$ なら $0$、そうでなければ $1$ である。とくに $\min_jS(m,j)$ は、$P$ と $T$ の部分文字列の編集距離の最小値である。
$S(0,j)=0$ は $a=j$ でわかり、$S(i,0)=i$ は定義から従う。$i,j\ge1$ とし、$P_i:=p_1\cdots p_i$、$T_{a,j}:=t_{a+1}\cdots t_j$ とおく。$a< j$ のとき thm-ed-recursion から
$$
d(P_i,T_{a,j})=\min\{d(P_{i-1},T_{a,j})+1,\ d(P_i,T_{a,j-1})+1,\ d(P_{i-1},T_{a,j-1})+\delta_{ij}\}
$$
である。$a=j$ のとき $d(P_i,\epsilon)=i=d(P_{i-1},\epsilon)+1$ である。$a$ について最小をとる。第 1 項は $0\le a\le j$ の全体で $S(i-1,j)+1$ になり、第 2・第 3 項は $0\le a\le j-1$ で $S(i,j-1)+1$、$S(i-1,j-1)+\delta_{ij}$ になる。$a=j$ の値は第 1 項の中にある。$\square$
| 状況 | 方法 | 手間 | 記憶 |
|---|---|---|---|
| 値だけが要る | 2 行の計算 | $O(mn)$ | $O(\min\{m,n\})$ |
| 整列が要る、短い文字列 | 全体の表 | $O(mn)$ | $O(mn)$ |
| 整列が要る、長い文字列 | 分割の式 | $O(mn)$ | $O(m+n)$ |
| 距離が小さいと分かっている | 帯 | $O((k+1)\min\{m,n\})$ | $O(k+1)$ |
| 長い文字列の中の検索 | 最初の行を $0$ に | $O(mn)$ | $O(m)$ |
SATURDAY と SUNDAY の編集距離の表。各マスに値が書かれ、差が 2 以下の帯のマスに色が付いている。左上から右下への最小費用の道は帯の中を通り、右下の値は 3 である。
使う公式:thm-ed-recursion。
答え:$d=5$ である。
行が INTENTION、列が EXECUTION である。
| E | X | E | C | U | T | I | O | N | ||
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
| I | 1 | 1 | 2 | 3 | 4 | 5 | 6 | 6 | 7 | 8 |
| N | 2 | 2 | 2 | 3 | 4 | 5 | 6 | 7 | 7 | 7 |
| T | 3 | 3 | 3 | 3 | 4 | 5 | 5 | 6 | 7 | 8 |
| E | 4 | 3 | 4 | 3 | 4 | 5 | 6 | 6 | 7 | 8 |
| N | 5 | 4 | 4 | 4 | 4 | 5 | 6 | 7 | 7 | 7 |
| T | 6 | 5 | 5 | 5 | 5 | 5 | 5 | 6 | 7 | 8 |
| I | 7 | 6 | 6 | 6 | 6 | 6 | 6 | 5 | 6 | 7 |
| O | 8 | 7 | 7 | 7 | 7 | 7 | 7 | 6 | 5 | 6 |
| N | 9 | 8 | 8 | 8 | 8 | 8 | 8 | 7 | 6 | 5 |
末尾の 3 文字 ION は prop-ed-table の (3) により除ける。残りは $D(6,6)=5$ で、INTENT の 5 文字を置き換える整列(最後の T を対応させる)で実現する。
SATURDAY($m=8$)と SUNDAY($n=6$)について、距離が $2$ 以下かを判定する。
使う公式:prop-ed-band。
答え:帯 $k=2$ のマス $32$ 個の計算で $D_2(8,6)=3>2$ となり、距離は $2$ を超える。$k=3$ でも値は $3$ で、$d=3$ と確定する。全体の表は $63$ マスである。
SATURDAY を SATU と RDAY に切る。
使う公式:thm-ed-split。
答え:SUNDAY の前の $j$ 文字と SATU の距離は $j=0,\dots,6$ で $4,3,2,3,3,4,5$、残りと RDAY の距離は $3,2,1,1,2,3,4$ である。和は $7,5,3,4,5,7,9$ で、$j=2$ で最小値 $3$ をとる。よって (SATU, SU) と (RDAY, NDAY) に分けて再帰すればよい。
パターン RING を文字列 THEBRINKOFGROUPS の中で探す。
使う公式:prop-ed-search。
答え:最小値は $1$ で、$j=7$ の RIN と $j=8$ の RINK で達する。最後の行は $4,4,4,4,4,3,2,1,1,2,3,3,3,3,3,3,4$ である($j=0,\dots,16$)。
KITTEN と SITTING の最長の共通部分列は ITTN で $L=4$ である。
使う公式:prop-ed-indel。
答え:$d_{\mathrm{id}}=6+7-2\cdot4=5$ で、$d=3$ である。不等式 $3\le5\le6$ が確かめられる。
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 条件 (i):費用の三角不等式 | 置換 $a\to c$、削除、挿入の費用 $10$、置換 $a\to b$ と $b\to c$ の費用 $1$ | 再帰式の値 $10$ が操作の列の最小値 $2$ と異なる |
| 条件 (iii):操作は 1 文字ずつ(隣の交換を 1 回と数える再帰式) | CA, AC, ABC | 三角不等式が成り立たない |
| $d$ そのものを使う(長さで割らない) | $d/\max\{m,n\}$ で ab, aba, ba | 三角不等式が成り立たない |
| thm-ed-metric の (5) の等号(ずれがないこと) | ABABAB と BABABA | Hamming 距離は $6$ だが $d=2$ |
$\Sigma':=\Sigma\cup\{\epsilon\}$ の上の費用 $w\colon\Sigma'\times\Sigma'\to[0,\infty)$ を考える。$w(a,b)$ は $a$ を $b$ に置換する費用、$w(a,\epsilon)$ は削除の費用、$w(\epsilon,a)$ は挿入の費用である。整列の費用も同様に定める。$w$ が $\Sigma'$ の上の距離なら、lem-ed-compose の証明で項を結びつける代わりに $w(x,z)\le w(x,y)+w(y,z)$ を使って、整列の合成で費用が増えないことが同じように示せる。よって thm-ed-alignment と thm-ed-recursion は、$1$ と $\delta_{ij}$ を $w$ に替えて成り立つ。三角不等式がないと、thm-ed-alignment は成り立たないことがある。
費用の三角不等式:$a$ を $c$ に変えるとき、再帰式は直接の置換 $10$(または削除と挿入)しか見ない。操作の列なら $a\to b\to c$ で費用 $2$ である。整列は 1 文字に 1 つの対応しか持たないので、途中の文字を表せない。置換の費用の表を、途中の文字を経由する最短の費用で置き直せばよい。
隣の交換:再帰式に、$x_i=y_{j-1}$、$x_{i-1}=y_j$ のとき $D(i-2,j-2)+1$ の項を足した量を $d'$ とする。$d'(\mathrm{CA},\mathrm{AC})=1$、$d'(\mathrm{AC},\mathrm{ABC})=1$ だが、$d'(\mathrm{CA},\mathrm{ABC})=3$ である。この再帰式は、交換した 2 文字の間に文字を入れる操作を表せない。交換を 4 つ目の操作として def-ed-main に足し、操作の列の最小で定めた量なら距離になるが($d'(\mathrm{CA},\mathrm{ABC})$ に当たる値は $2$)、thm-ed-alignment の型の主張が成り立たないので、この再帰式の値とは一致しない。
長さで割る:$d(\mathrm{ab},\mathrm{ba})=2$ なので、割った値は $2/2=1$ である。$d(\mathrm{ab},\mathrm{aba})=1$、$d(\mathrm{aba},\mathrm{ba})=1$ で割った値はどちらも $\frac13$ であり、$1>\frac13+\frac13$ である。割った値は長さの異なる比較には便利だが、距離の性質を使う探索には使えない。
Hamming 距離:ABABAB の先頭の A を削除し、末尾に A を挿入すると BABABA になる。thm-ed-metric の (5) は不等式で、ずれのある文字列では大きく差がつく。
| 誤り | 正しくは | なぜ |
|---|---|---|
| 長さが等しければ Hamming 距離に等しいと考える | Hamming 距離は上界にすぎない | ex-ed-counterexamples |
| 再帰式の第 3 項で $\delta_{ij}$ を常に足す | 文字が同じなら $0$ | thm-ed-recursion |
| 置換の費用を $2$ にした再帰式の値を編集距離と呼ぶ | それは $d_{\mathrm{id}}$ で、定義が違う | prop-ed-indel |
| 検索で表の最初の列も $0$ にする | 最初の行だけ $0$ にする。最初の列は $S(i,0)=i$ | prop-ed-search |
| 隣の交換を足した再帰式を距離として使う | 三角不等式が成り立たない | ex-ed-counterexamples |
| 長さで割った値に三角不等式を使う | 使えない | ex-ed-counterexamples |
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する