差分検出アルゴリズム三種盛り

こんばんは. 気がつけばもうずいぶんと涼しくなってきました. 勢い余って凍ってしまったりせぬよう, くれぐれも普段の言動にはお気をつけください.

はじめに

さて, 我々人類にはどうしても二つの文字列 (あるいは行ごとに区切られたテキスト) 間の差分を求めなければいけない瞬間が発生します. 先人たちはそういった時のために diff のようなツールを開発し, それを利用することで文明はめざましい発展を遂げてきました.

f:id:susisu:20171009132044p:plain

しかしながら, 使用するアルゴリズムを比較検討したい場合, 「差分」の定義を変えるなどして既存のアルゴリズムに変更を加えたい場合, diff のない異世界に飛ばされて自分で実装しなければいけない時などにおいては, 差分検出アルゴリズムについての理解が必要不可欠です.

というわけで, この記事では文字列間の差分検出とは何かということと, 差分を求める三種類のアルゴリズムの紹介・解説をします.

記事中のサンプルコードは全て JavaScript で書かれていますが, もし JavaScript を知らなくても擬似コードとしても読めるように注意して書いているつもりです. 読めなかったらメンゴ.

編集距離・SES

二つの文字列 A, B の差分は, A を B に (あるいは B を A に) 変える編集操作の列と考えることができます. そのような操作列は無数に考えられますが, 不必要な操作が含まれていてもあまり役に立たないので, そのうち最短のもの (shortest edit script, 以下 SES) が重要になります. また SES の長さ (必要な最小の操作の数) を A–B 間の編集距離 (edit distance) と定義します.

ここでは文字列に対する編集操作として,

任意の位置への一文字の挿入
任意の一文字の削除

の二つのみを考えることとします.

例えば kitten と sitting の間の SES は,

5文字目 e を削除
1文字目 k を削除
1文字目に s を挿入
5文字目に i を挿入
7文字目に g を挿入

で, 編集距離は 5 です.

編集距離としてはレーベンシュタイン距離がよく知られていますが, こちらは上の挿入・削除に加えて, 任意の一文字の置換操作も一操作として含むものです. ここでは置換には削除 + 挿入の二操作が必要です.

この記事では主に編集距離を求めることのみを考えますが, 次の編集グラフの節で説明するように, 編集距離を求める際に同時に SES を求めることも可能です.

編集グラフ

編集距離や SES を考える上で便利なのが編集グラフ (edit graph) と呼ばれるグラフです.

文字列 A, B の長さをそれぞれ $M$ , $N$ としたとき, A–B 間の編集グラフは次のように構成されます.

頂点 $(i, j), i \in \lbrack 0, M \rbrack, j \in \lbrack 0, N \rbrack$ を用意する
$i \in \lbrack 1, M \rbrack, j \in \lbrack 0, N \rbrack$ に対して縦に辺 $(i - 1, j) \rightarrow (i, j)$ を結ぶ
$i \in \lbrack 0, M \rbrack, j \in \lbrack 1, N \rbrack$ に対して横に辺 $(i, j - 1) \rightarrow (i, j)$ を結ぶ
もし A の $i$ 文字目と B の $j$ 文字目が等しければ斜めに辺 $(i - 1, j - 1) \rightarrow (i, j)$ を結ぶ

要するに格子を書いて適当に斜めに線を引っ張っただけと思えば良いです (良くはない).

上で挙げた例の kitten と sitting の間の編集グラフは次の図のようになります.

f:id:susisu:20171009010755p:plain

文字列 A–B 間の編集グラフ上で左上 $(0, 0)$ から右下 $(M, N)$ に向かう経路は, A を B に変える編集操作と以下のように対応づけることができます.

縦の辺 $(i - 1, j) \rightarrow (i, j)$ = A の $i$ 文字目を削除
横の辺 $(i, j - 1) \rightarrow (i, j)$ = B の $j$ 文字目を挿入
斜めの辺 = 編集操作なし (同じ文字なので)

ただし, 編集操作を適当な順番で行ってしまうと (どう記録・適用するかにもよるけれど) A を B に正しく変えられなかったりするので, ここでは, 先に後ろから削除を行い, A と B の共通部分のみにした後, 先頭から挿入を行う, というように決めておきます. こうしておけば「A の $i$ 文字目を削除」は編集途中の文字列の $i$ 文字目を何も考えずに削除すれば良いし, 「B の $j$ 文字目を挿入」は文字列の $j$ 文字目に挿入すれば良いです.

さて, 編集操作と編集グラフ上の経路の対応を念頭に置くと, A–B 間の SES は, グラフの縦横の辺にコスト 1, 斜めの辺にコスト 0 を割り当てたときに, $(0, 0)$ から $(M, N)$ まで向かうときの最小コストの経路と対応づけられます. また, そのときのコスト (縦横移動の数) が A–B 間の編集距離となります.

以下の図中に太線で示したものが kitten と sitting の間の最小コストの経路です. 縦横移動の数と編集距離, 経路と SES が対応していることを確認してください.

f:id:susisu:20171009010824p:plain

動的計画法

上で挙げた Wikipedia のレーベンシュタイン距離のページに書かれているものと同様に, ナイーブな動的計画法 (DP) を使って編集距離を求めることが可能です.

以下では文字列 X の $i_1$ 文字目から $i_2$ 文字目までを $X(i_1, i_2)$ と書きます.

二つの文字列 A, B に対して, DP アルゴリズムは, 編集グラフ上の各頂点 $(i, j)$ について, $(0, 0)$ からそこに辿り着くまでの最小コスト, 言い換えると, $A(1, i)$ と $B(1, j)$ との距離 $D(i, j)$ を, グラフの左上から順番に求めていきます. 注目すべき点は,

空文字列と長さ $L$ の文字列との距離は自明に $L$
$A(1, i)$ と $B(1, j)$ の距離は, それより短い部分同士の距離から求められる

の二つです. 2 について具体的には, $A(1, i)$ から $B(1, j)$ への SES が,

A の $i$ 文字目を削除 + $A(1, i - 1)$ から $B(1, j)$ への SES
$A(1, i)$ から $B(1, j - 1)$ への SES + B の $j$ 文字目を挿入
もし A の $i$ 文字目と B の $j$ 文字目が同じならば (斜めの辺があれば), $A(1, i - 1)$ から $B(1, j - 1)$ への SES

の三つの内, 最も短いものとなるので, このことを用いて $D(i, j)$ は,

斜めの辺 $(i - 1, j - 1) \rightarrow (i, j)$ が存在すれば $D(i, j) = \min(D(i - 1, j) + 1, D(i, j - 1) + 1, D(i - 1, j - 1))$
斜めの辺 $(i - 1, j - 1) \rightarrow (i, j)$ が存在しなければ $D(i, j) = \min(D(i - 1, j) + 1, D(i, j - 1) + 1)$

と求められます. これを繰り返すことで, 最終的に $D(M, N)$ , つまり A–B の編集距離が求められます.

というわけで, 編集距離を求めるプログラムは以下のようになります.

function distance(A, B) {
  const M = A.length;
  const N = B.length;
  // DP のテーブル (大きさ (M + 1) * (N + 1) の 2 次元配列)
  // D[i][j] = (0, 0) から (i, j) までの最小コスト (編集距離)
  const D = new Array(M + 1);
  for (let i = 0; i <= M; i++) {
    D[i] = new Array(N + 1);
    // (0,0) から (i, 0) までの距離は i
    D[i][0] = i;
  }
  for (let j = 1; j <= N; j++) {
    // (0,0) から (0, j) までの距離は j
    D[0][j] = j;
  }
  // D[i][j] を順番に求める
  for (let i = 1; i <= M; i++) {
    for (let j = 1; j <= N; j++) {
      // 縦横については + 1, 斜めの辺 (あれば) については + 0
      D[i][j] = A[i - 1] === B[j - 1]
        ? Math.min(D[i - 1][j] + 1, D[i][j - 1] + 1, D[i - 1][j - 1])
        : Math.min(D[i - 1][j] + 1, D[i][j - 1] + 1);
    }
  }
  return D[M][N];
}

DP アルゴリズムが探索するのは編集グラフ全体で, したがって実行時間は最悪・平均ともに $O(MN)$ となります. 上のコード例では $O(MN)$ のメモリを使用しますが, 以下のように一行 (列) だけを記録するようにすることで $O(\min(M,N))$ とすることが可能です.

function distance(A, B) {
  const M = A.length;
  const N = B.length;
  // 短い方をテーブルの長さに採用する
  // ループの方向もそれによって変える
  if (M >= N) {
    const D = new Array(N + 1);
    for (let j = 0; j <= N; j++) {
      D[j] = j;
    }
    for (let i = 1; i <= M; i++) {
      D[0] = i;
      // 斜め左上の値は別に覚えておく必要がある
      let diagonal = i - 1;
      for (let j = 1; j <= N; j++) {
        let temp = D[j];
        D[j] = A[i - 1] === B[j - 1]
          ? Math.min(D[j] + 1, D[j - 1] + 1, diagonal)
          : Math.min(D[j] + 1, D[j - 1] + 1);
        diagonal = temp;
      }
    }
    return D[N];
  }
  else {
    const D = new Array(M + 1);
    for (let i = 0; i <= M; i++) {
      D[i] = i;
    }
    for (let j = 1; j <= N; j++) {
      D[0] = j;
      // 斜め左上の値
      let diagonal = j - 1;
      for (let i = 1; i <= M; i++) {
        let temp = D[i];
        D[i] = A[i - 1] === B[j - 1]
          ? Math.min(D[i] + 1, D[i - 1] + 1, diagonal)
          : Math.min(D[i] + 1, D[i - 1] + 1);
        diagonal = temp;
      }
    }
    return D[M];
  }
}

DP はシンプルで実装も簡単ですが, 次の O(ND) アルゴリズムも同程度に実装は簡単ですし, また計算量的にもあまり優れないため, あえて実用で使う必要性は薄いでしょう (全ての部分文字列同士に対して距離を求めたいとかであれば別).

O(ND) アルゴリズム

より高速に編集距離や SES を求めるアルゴリズムとして, Myers による O(ND) アルゴリズム [1] があります. ここでの O(ND) の N は今使っている文字列の長さ $N$ とは異なるので, とりあえずそういうアルゴリズムの名前だと思ってください. 計算量については下でちゃんと説明します.

これは上の DP アルゴリズムとは発想が逆で, 各頂点に辿り着くまでのコストを求めるのではなく, 与えられたコストでどこまで辿り着けるかを考えます.

まず, 頂点 $(i, j)$ を通る傾き $1$ の斜めの直線を $k = j - i$ という番号で呼ぶことにします. 単に番号というとなんのこっちゃですが, $j$ 切片 (または $-i$ 切片) の値です. 例えば以下の図では $k = 1$ の線を破線で描いています.

f:id:susisu:20171009011624p:plain

直線 $k$ 上で, コスト $D$ で辿り着ける最大の $i$ の値を $V_D(k)$ とします.

まずはコスト $0$ の場合 $V_0(k)$ を考えましょう. 明らかに, 値が存在するのは $V_0(0)$ だけで, $(0, 0)$ から右下に斜めの辺を辿るだけで求められます. この「直線 $k$ 上で, $(i, j)$ から斜めの辺を行き止まるまで辿ったときの, 最終的な $i$ の値」を $\text{snake}(k, i)$ と書くことにします. これを用いると $V_0(0) = \text{snake}(0, 0)$ です.

$V_0(k)$ が求められたところで, 次に $V_1(k)$ を考えます. これは二つだけが存在して,

$k = -1$ : $V_0(0)$ から下に移動して $V_1(-1) = \text{snake}(-1, V_0(0) + 1)$
$k = 1$ : $V_0(0)$ から右に移動して $V_1(1) = \text{snake}(1, V_0(0))$

のように求められます. $V_D(k)$ は $i$ の値なので, 横方向 ( $j$ 方向) に移動する場合は $1$ を加える必要はありません.

同様に, $V_{D - 1}(k)$ が全て求められている時, $V_D(k)$ は, 各 $k$ に対して $V_D(k) = \text{snake}(k, \max(V_{D - 1}(k + 1) + 1, V_{D - 1}(k - 1)))$ で求められます. 端 $k = \pm D$ の場合で $V_{D - 1}(k + 1)$ , $V_{D - 1}(k - 1)$ の片方が存在しない時は, 存在する側のみ考えれば良いです.

このようにして $D$ を増やしながら $V_D(k)$ の値を計算していき, 直線 $k = N - M$ 上で $i = M$ に辿り着いたら, そのときの $D$ の値が A–B 間の編集距離となっています.

これを実装したプログラムは以下のようになります. ポイントとして, 同じ直線 $k$ に戻ってくるには必ず偶数のコストが必要であり, $k$ が偶数 (奇数) のとき, $V_D(k)$ の計算に必要なのは奇数 (偶数) の $k$ に対する $V_{D - 1}(k)$ のみであることから, プログラム中で k を増やすのは 2 ずつで良く, $V_D(k)$ を記録しておく配列 V も, 長さ $2 (M + N) + 1$ だけ用意すれば十分です.

function distance(A, B) {
  const M = A.length;
  const N = B.length;
  const V = new Array(2 * (M + N) + 1);
  const offset = M + N;
  // D を順番に増やして探索する
  for (let D = 0; D <= M + N; D++) {
    for (let k = -D; k <= D; k += 2) {
      let i = D === 0  ? 0
            : k === -D ? V[offset + k + 1] + 1
            : k === D  ? V[offset + k - 1]
            : Math.max(V[offset + k + 1] + 1, V[offset + k - 1]);
      // 斜めの辺が存在すれば行き止まるまで進む (snake)
      while (i < M && i + k < N && A[i] === B[i + k]) {
        i += 1;
      }
      // 右下に辿り着いたら終了
      if (k === N - M && i === M) {
        return D;
      }
      V[offset + k] = i;
    }
  }
  // D は最大で M + N なのでここに来ることはない
  throw new Error("never");
}

このアルゴリズムで探索される範囲は, 以下の図のように $k = -D$ から $k = D$ までの間の領域です.

f:id:susisu:20171009012136p:plain

A–B 間の編集距離が $D$ であったとき, 内側の for ループ内の処理で while を除く部分は, 高々 $(D + 1) (D + 2) / 2 = O(D^2)$ 回実行されます. 一方 while ループで探索されるのは, $k = -D$ から $k = D$ の間の頂点なので, この数は多くとも $\min(M,N) \times (2 D + 1) \leq O((M + N)D)$ です. したがって, 最悪実行時間は $O((M + N)D)$ となります. また, ランダムな文字列同士の距離を求める時の平均実行時間は $O(M + N + D^2)$ となるようです. 必要なメモリは上で説明したとおり $O(M + N)$ です.

上のコードは論文に載っているものをほぼそのまま書いたものですが, 探索範囲はもう少し狭められるはずで, 以下のようにすると $D$ が大きいときに効率が良くなり, メモリ使用量も約半分にできます.

function distance(A, B) {
  const M = A.length;
  const N = B.length;
  const V = new Array(M + N + 1);
  const offset = M;
  for (let D = 0; D <= M + N; D++) {
    // 文字列の範囲外や必要の無くなった領域は探索しない
    const min = D <= M ? -D :  D - 2 * M;
    const max = D <= N   ?  D : -D + 2 * N;
    for (let k = min; k <= max; k += 2) {
      let i = D === 0  ? 0
            : k === -D ? V[offset + k + 1] + 1
            : k === D  ? V[offset + k - 1]
            : Math.max(V[offset + k + 1] + 1, V[offset + k - 1]);
      while (i < M && i + k < N && A[i] === B[i + k]) {
        i += 1;
      }
      if (k === N - M && i === M) {
        return D;
      }
      V[offset + k] = i;
    }
  }
  throw new Error("never");
}

ちなみに D のループの上限を M + N ではなく, それよりも小さくすることで, 途中で探索を打ち切ることが可能です. この場合, 探索が打ち切られた場合は「編集距離が指定した上限より大きい」という結果が得られます. これが嬉しい場合もあるとかないとか.

O(NP) アルゴリズム

Wu らによる O(NP) アルゴリズム [2] では, O(ND) アルゴリズムで編集距離 $D$ を使ったところで, かわりに後で定義する $P$ という量を用いることで, より効率的な探索を行います.

以下では A よりも B の方が長く $M \leq N$ であることを仮定します. 逆の場合は単純に A と B を入れ替えて考えましょう. また, 文字列の長さの差を $\Delta = N - M$ と定義します.

DP でもちょっと登場したように, グラフ上の $(0, 0)$ から $(i, j)$ までの最小コストを $D(i ,j)$ と書くことにします. また, その経路に含まれる横の辺の数を $I(i, j)$ , 縦の辺の数を $X(i, j)$ とします. これらはそれぞれ最小の挿入と削除の数に対応し, $D(i, j) = I(i, j) + X(i, j)$ が成り立ちます. 続いて $P(i, j)$ を

$k = j - i \leq \Delta$ ならば $P(i, j) = X(i, j)$
$k > \Delta$ ならば $P(i, j) = X(i, j) + k - \Delta$

と定義します. $k = \Delta$ は最終到達点 $(M, N)$ を含む直線なので, $P$ は $k \leq \Delta$ では削除の数, $k > \Delta$ では削除の数 + $(M, N)$ に辿り着くまでに今後必要となる削除の数に一致します.

$D(M, N)$ , $I(M, N)$ , $X(M, N)$ , $P(M, N)$ を単に $D$ , $I$ , $X$ , $P$ と書くと, $P = X$ であり, $P$ と $D$ の関係は,

$D = I + P$
$\Delta = I - P$

なので, $D = \Delta + 2 P$ のようにして $P$ から $D$ を求めることができます.

さて, アルゴリズムについて, O(ND) の場合と同様に, 直線 $k$ 上で, $P$ で辿り着ける最大の $i$ の値を $V_P(k)$ とします.

まず $P = 0$ のとき, $V_0(k)$ の値が存在するのは $k = 0$ から $k = \Delta$ の範囲内で, $k = 0$ については明らかに $V_0(0) = \text{snake}(0, 0)$ で求められます. 一方, $k > \Delta$ については $V_0(k) = \text{snake}(k, V_0(k - 1))$ のようにして求められます. この領域 ( $k < \Delta$ ) では $P$ は削除操作の数と一致しているので, 横方向への移動 (削除を伴わない) で参照する $V_P(k)$ の $P$ は同じになる ( $P - 1$ ではない!) ことに注意が必要です.

次に $P = 1$ のときを考えると, まず $k = -1$ については, $V_1(-1) = \text{snake}(-1, V_0(0) + 1)$ となり, $k = 0$ から $k = \Delta - 1$ までは, $V_1(k) = \text{snake}(k, \max(V_0(k + 1) + 1, V_1(k - 1)))$ で求められます. こちらも, 横方向への移動 ( $\max$ 内の二つ目) で参照している $P$ は $0$ ではなく $1$ となっています.

続いて $k = \Delta + 1$ については, $V_1(\Delta + 1) = \text{snake}(\Delta + 1, V_0(\Delta))$ で求められます. こちらの領域 ( $k > \Delta$ ) では $P$ は削除の数 + 今後必要な削除の数なので, 横移動では今後必要な削除の数が増えるため $P$ は増加, 縦移動では削除が増えるものの今後必要な削除の数も減って $P$ は変化しません. このため, 縦移動で参照するべき $V_P(k)$ の $P$ は同じ, 横移動では $P - 1$ となり, ここでは横移動なので $V_0(\Delta)$ となっています.

最後に $k = \Delta$ については, $V_1(\Delta) = \max(V_1(\Delta + 1) + 1, V_1(\Delta - 1))$ から右下へ進んだ値です. これは $\max$ 内の一つ目については $k > \Delta$ , 二つ目については $k < \Delta$ のルールを適用した結果です.

同様にして, 一般に $V_{P - 1}(k)$ が求められている時, $V_P(k)$ は,

$k < \Delta$ のとき, $V_P(k) = \text{snake}(k, \max(V_{P - 1}(k + 1) + 1, V_P(k - 1)))$
$k > \Delta$ のとき, $V_P(k) = \text{snake}(k, \max(V_P(k + 1) + 1, V_{P - 1}(k - 1)))$
$k = \Delta$ のとき, $V_P(k) = \text{snake}(k, \max(V_P(k + 1) + 1, V_P(k - 1)))$

で求められます. $k$ がどの領域に含まれているかによって参照する $P$ が異なるので注意が必要です.

これを実装してみると以下のようになります. k の走査方向を領域によって変えることが $V_P(k)$ を求める際に参照する $P$ が変わることに対応しており, またこのことによって $V_P(k)$ を記録しておく配列 V の長さは $M + N + 1$ で済みます.

function distance(A, B) {
  const M = A.length;
  const N = B.length;
  // N >= M であってほしい
  if (M > N) {
    return distance(B, A);
  }
  const V = new Array(M + N + 1);
  const offset = M;
  const Delta = N - M;
  // P を順番に増やして探索する
  for (let P = 0; P <= M; P++) {
    // k = Δ より下の領域
    for (let k = -P; k < Delta; k++) {
      let i = P === 0  ? (k === 0 ? 0 : V[offset + k - 1])
            : k === -P ? V[offset + k + 1] + 1
            : Math.max(V[offset + k + 1] + 1, V[offset + k - 1]);
      // 斜めの辺が存在すれば行き止まりまで進む
      while (i < M && i + k < N && A[i] === B[i + k]) {
        i += 1;
      }
      V[offset + k] = i;
    }
    // k = Δ より上の領域
    for (let k = Delta + P; k > Delta; k--) {
      let i = k === Delta + P ? V[offset + k - 1]
            : Math.max(V[offset + k + 1] + 1, V[offset + k - 1]);
      while (i < M && i + k < N && A[i] === B[i + k]) {
        i += 1;
      }
      V[offset + k] = i;
    }
    // k = Δ
    {
      const k = Delta;
      let i = P === 0 ? (k === 0 ? 0 : V[offset + k - 1])
            : Math.max(V[offset + k + 1] + 1, V[offset + k - 1]);
      while (i < M && i + k < N && A[i] === B[i + k]) {
        i += 1;
      }
      // 右下に辿り着いたら終了
      if (i === M) {
        // D = Δ + 2 P
        return Delta + 2 * P;
      }
      V[offset + k] = i;
    }
  }
  // P は最大で M なのでここに来ることはない
  throw new Error("never");
}

このアルゴリズムでの探索範囲は以下の図のように, $k = -P$ と $k = \Delta + P$ の間の領域となります. O(ND) アルゴリズムよりも探索範囲が狭まっていることが視覚的にもわかると思います.

f:id:susisu:20171009012204p:plain

続いて計算量です. 最悪実行時間を求めるには, P についてのループの一回のイテレーションで while ループにどの程度の時間がかかるのかを考えることが必要ですが, これはちょっと面白いです. まず k < Delta の for ループで, k が増えていくときに V[offset + k] + k ( $j$ 座標) の更新過程を追っていくと, V[offset + (-p)] + (-p) < ... < V[offset + (Delta - 1)] + (Delta - 1) のように増加列になっていることがわかります. このため, このループにおいて探索される頂点の数は高々 $N$ となります. また k > Delta の for ループでは, k が減っていくときに V[offset + k] (今度は $i$ 座標) の更新過程を追っていくと, これも同様に V[offset + (Delta + p)] < ... < V[offset + (Delta + 1)] で増加列になっており, 探索される頂点の数は高々 $M$ です. したがって, A から B への削除の回数が $P$ であったとき, このような $O(N)$ と $O(M)$ の処理が $P + 1$ 回繰り返されるため, 最悪実行時間は $O((M + N)P)$ となります. また, 平均実行時間は (たぶん) $O(M + N + PD)$ となり, 実用的には O(ND) アルゴリズムの倍程度の速度となるようです. 必要なメモリはこれまた上で説明したとおり $O(M + N)$ です.

こちらも P のループの上限を M より小さくすることで探索を打ち切ることができますが, 得られる結果は「削除の数が上限より大きい」なので, 使いみちは O(ND) アルゴリズムのときよりも少なそうです.

実験

これらのアルゴリズムで実際にどの程度差が出るのかについて, この記事中で書いたサンプルプログラムを使って速度を比較してみます.

比較は macOS 上の Node.js v8.4.0 を使って, ランダムに生成した文字列について, それぞれ 10 回実行した平均時間 (ミリ秒) を記録しています. 繰り返し実行するうちに JIT が効いてくると比較が面倒なので 10 回別々に実行しました. 以下の表では各サンプル毎に最速のものを強調しています.

名前	アルゴリズム
dp	DP
mod-dp	DP メモリ節約版
ond	O(ND)
mod-ond	O(ND) 改良版
onp	O(NP)

M	N	D	P	dp	mod-dp	ond	mod-ond	onp
1000	1000	20	10	41	26	0.23	0.26	0.20
1000	1000	200	100	40	27	5.2	5.8	1.9
1000	1000	1524	762	45	28	42	35	28
10000	10000	20	10	3680	2110	1.59	1.52	1.50
10000	10000	200	100	3700	2100	6.6	6.8	9.7
10000	10000	2000	1000	3800	2130	75	78	40
10000	10980	1000	10	-	-	23	23	9.7
10000	11980	2000	10	-	-	76	80	16

DP は 10000 文字にもなってくると全く使い物になりません. O(ND) と O(NP) を比べると, やはりほとんどのケースで O(NP) が速くなるようです. また予想通り $D$ に比べて $P$ が小さい時は差が顕著です.

参考文献

この記事で解説した O(ND) および O(NP) アルゴリズムは以下の論文で提案されているものです. 論文タイトルでぐぐると無料でも読めるものが見つかります. 正当なコピーかわからないのであまり大きい声で言って良いかわかっていないのですが……

[1] E. W. Myers, "An O(ND) difference algorithm and its variations", Algorithmica 1, 251 (1986)
[2] S. Wu, U. Manber, G. Myers, W. Miller, "An O(NP) sequence comparison algorithm", Information Processing Letters 35, 317 (1990)

DP のアルゴリズムについては以下の Wikipedia に記載されているものを参考にしました.

レーベンシュタイン距離 - Wikipedia

編集距離を求めるアルゴリズムにどういった種類があるのかについては以下が参考になりました. この記事で紹介したアルゴリズムはこちらで挙げられているものです.

文書比較（diff）アルゴリズム

以下の記事では O(NP) アルゴリズムに加え, 各種ソフトウェアがどう実装しているかなどについて詳しく解説されています.

diffの動作原理を知る～どのようにして差分を導き出すのか：一般記事｜gihyo.jp … 技術評論社

あとがき

けっきょく南極大冒険なんで急に差分検出アルゴリズムを調べていたかというと, markdown-table-editor で表を編集した際のテキストエディタへの変更の適用を最小限にしようと思ったためです.

現状では変更があれば表全体を更新するため, 100 行を超えるような大きい表を編集していると, 更新時にエディタがカクつきます (実験的にやっているだけであって真面目にやっているわけではない). そんなに大きな表を編集するなら表計算ソフトを使え. と言っても良いのですが, SES を適用すれば不必要に表全体を更新することで動作がカクつくことはなくなると期待できるので, やっておいても損はないかなというところです.

一方で, 表全体が変更された時は, SES を元に一行一行丁寧に挿入・削除するよりも, 一気に全体を更新したほうが効率が良さそうです. 確かめてないけど. ここで表全体の更新を伴わない場合の編集距離を考えると, 普通は

ただの移動など: 0
行の挿入・削除: 1
行内で完結する編集: 2
行の入れ替え: 2

に加えて, デリミタ行の挿入で + 1 されることがあるので, 最大でも 3 です. 逆に言うと, 距離が 3 より大きいことがわかれば, それは表全体の更新であることがわかります.

というわけで, 実装の単純さも考慮して, O(ND) アルゴリズムを使って, $D$ が $3$ を超えたら打ち切って全体の更新に切り替える, みたいな方向で行こうかなと考えています (100 行程度ならふつうに求めてしまってもいいんですけどね). なんか式年遷宮してるので実装していくのはしばらく先になりますけど, 赤福餅でも食べてゆっくりお待ち下さい (誰も待ってなさそう).