編集距離

同義語:Levenshtein距離レーベンシュタイン距離edit distanceLevenshtein distance

概要

編集距離(edit distance)とは、2 つの文字列の一方を他方に変えるのに必要な 1 文字の削除・挿入・置換の最小の回数で、Levenshtein 距離ともいい、綴りの訂正、配列の比較、文字列の検索に使う。文字列の全体の上の距離であり、最小の回数は 2 つの文字列をそろえる整列の費用の最小値に等しい。整列の最後の列で場合分けした再帰式により、長さ $m,n$ の文字列で $O(mn)$ の手間で計算できる。距離が小さいときは帯の中だけを計算すれば速く、解の復元は $O(m+n)$ の記憶でできる。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 距離空間, 動的計画法

編集距離(edit distance)は、2 つの文字列の違いを、一方を他方に変えるのに必要な 1 文字の削除・挿入・置換の最小の回数で測る量である。Levenshtein 距離(Levenshtein distance)ともいう。綴りの誤りの訂正、遺伝子の配列の比較、音声認識、近い文字列の検索など、「ほぼ同じ」文字列を扱う場面の基本の道具である。
たとえば KITTEN は、K を S に、E を I に置き換え、末尾に G を挿入すると SITTING になるので、KITTEN と SITTING の距離は $3$ 以下で、実際 $3$ である。「$3$ より少なくできない」ことは、操作の列をいくら眺めても見えない。この記事の要点は、操作の列の問題を、2 つの文字列を縦に並べる 整列 の問題に直すことにある。

  • 操作の列の最小の回数は、整列の費用の最小値に等しい(thm-ed-alignment)。操作の列は同じ位置を何度も書き換えてよいので、これは証明の要る主張である。
  • 編集距離は文字列の全体の上の距離である(thm-ed-metric)。
  • 整列の最後の列で場合分けすると再帰式が立ち、$O(mn)$ の手間で計算できる(thm-ed-recursion)。
  • 距離が小さいときは帯だけを計算すれば速く(prop-ed-band)、解の復元も $O(m+n)$ の記憶でできる(thm-ed-split)。部分文字列の検索にも同じ表が使える(prop-ed-search)。
    再帰式を表で計算する一般論は 動的計画法 で扱う。削除と挿入だけを許す場合は 最長共通部分列 と同じ問題である(prop-ed-indel)。

定義と使える条件

有限集合 $\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')$ である。

$M'\circ M$ の費用の項を $M$ と $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$ の整列全体を動く。

2 つの向きの不等式

$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)$ は 距離空間 である。

  1. 操作の列の長さが $0$ なら $X=Y$ である。
  2. 削除と挿入は互いの逆で、置換の逆は置換である。操作の列を逆にたどると $Y$ から $X$ への列になる。
  3. $X$ から $Y$ への列と $Y$ から $Z$ への列をつなげる。
  4. 1 回の操作で長さは高々 $1$ しか変わらないので下界を得る。上界:$m\ge n$ とする。整列 $\{(k,k):1\le k\le n\}$ の費用は $(m-n)+\#\{k\le n:x_k\ne y_k\}\le m$ である。thm-ed-alignment を使う。$m< n$ なら (2) による。
  5. 置換だけの列である。
  6. 整列 $M$ に $\{(m+1-i,\ n+1-j):(i,j)\in M\}$ を対応させると、費用を保つ全単射である。thm-ed-alignment による。$\square$

再帰式

$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)$ である。

  1. $d(X_i,X_{i-1})=1$ と三角不等式による。
  2. 上の不等式は再帰式から従う。下の不等式:再帰式の最小を与える項で場合分けする。第 3 項なら明らかである。第 1 項なら $D(i,j)=D(i-1,j)+1\ge D(i-1,j-1)$ である((1) による)。第 2 項も同じである。
  3. 再帰式から $D(i,j)\le D(i-1,j-1)$ で、(2) と合わせる。$\square$
  1. により、末尾の文字が同じならその文字を除いてよい。thm-ed-metric の (6) と合わせると、共通の接頭辞と接尾辞は計算の前に取り除ける。
削除と挿入だけの距離

削除と挿入だけを許す操作の列の長さの最小値を $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\} $$
である。

整列を $h$ の位置で切る

$\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$

計算の手順

  1. 前処理:共通の接頭辞と接尾辞を除く(prop-ed-table)。長さの差が許容の $k$ を超えれば止める(thm-ed-metric の (4))。
  2. 表の形を決める:距離の値だけなら 2 行、上限 $k$ があるなら帯、復元が要るなら全体の表か分割の式を使う。
  3. 初期値を入れる:$D(i,0)=i$、$D(0,j)=j$。検索なら $S(0,j)=0$。
  4. 順に埋める:$i$ の増える順、同じ $i$ で $j$ の増える順に thm-ed-recursion を計算する。
  5. 復元する:右下から、再帰式の最小を与えた項を逆にたどる。第 3 項は対応、第 1 項は $x_i$ の削除、第 2 項は $y_j$ の挿入である。
  6. 確かめる:得られた整列の費用が表の右下の値に等しいことを確かめる。
    状況方法手間記憶
    値だけが要る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 である。 SATURDAY と SUNDAY の編集距離の表。各マスに値が書かれ、差が 2 以下の帯のマスに色が付いている。左上から右下への最小費用の道は帯の中を通り、右下の値は 3 である。

例題

INTENTION と EXECUTION

使う公式:thm-ed-recursion。
答え:$d=5$ である。

表を開く

行が INTENTION、列が EXECUTION である。

EXECUTION
0123456789
I1123456678
N2223456777
T3333455678
E4343456678
N5444456777
T6555555678
I7666666567
O8777777656
N9888888765

末尾の 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 と BABABAHamming 距離は $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

補足

  • 名前:同じ距離は Levenshtein が 1965 年に符号理論の文脈で導入し、Vintsyuk(1968 年)、Ulam(1972 年)らも独立に導入した。再帰式の計算は Wagner と Fischer の 1974 年の記述で知られ、ほかにも独立な発見がある(Eri19 §3.7、pp. 111、114–115)。
  • 距離の使い道:三角不等式により、$d(X,Y)$ と $d(Y,Z)$ が分かれば $d(X,Z)$ の範囲が分かるので、辞書の検索で候補を間引ける。
  • 手間の下界:SETH は証明されていない。
  • グラフの編集距離:同じ「編集距離」の語は、グラフの辺の追加と削除の最小の回数にも使う。この記事の主題とは別の量である。

関連項目

参考文献

[1]
Jeff Erickson, Algorithms, Independently published, 2019, §3.7 Edit Distance(pp. 111–116、名前の由来 p. 111、Wagner と Fischer の記述 pp. 114–115)
[2]
Arturs Backurs, Piotr Indyk, Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false), arXiv:1412.0348, 2017, p. 1(主結果と既知の手間)、p. 3(帰着に要る文字の種類)。arXiv:1412.0348v4

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する