Output-sensitive algorithm の話 + diff や LCS など

導入

diff というコマンドがありますね。ファイルの差分を出力してくれます。

% 
_
% cat << '' > old  # ここから空行までの内容をファイル old に書き込む
changed foo
unchanged
removed
unchanged

% cat << '' > new  # 同じく new に書き込む
changed bar
unchanged
unchanged
added
added
added

% diff old new  # old と new を比較
_1c1
< changed foo
---
> changed bar
3d2
< removed
4a4,6
> added
> added
> added

c d a はそれぞれ「変化した」「削除された」「追加された」の意味で、その両隣の値は行数（複数行なら範囲）を意味します。< は左のファイルにのみある内容で、> は右のファイルにのみある内容です。 たとえば、3d2 < removed は、左のファイルの 3 行目の removed が削除され、右のファイルの 2 行目の位置に対応するという感じです。

競プロ er にこれを実装してくれと言えば、「復元もするのか」「復元は非本質」などと意味不明な発言をしながらも数分で実装してくれることでしょう。

多くの競プロ er は、文字列 \(S, T\) に対して常に \(\Theta(|S|\cdot |T|)\) 時間で走るアルゴリズムをすぐ書くと思います¹。 しかし、これを実用するとなると若干厳しい場面があります。次のような例を考えます。

% diff <(seq 1 1000000) <(seq 1 1000000)
% diff <(seq 1 1000000) <(seq 2 1000001)
1d0
< 1
1000000a1000000
> 1000001

<(seq 1 1000000) は 1 から 1000000 が一行ずつ順に書かれたファイル、<(seq 2 1000001) は 2 から 1000001 が一行ずつ順に書かれたファイルの意味だと思って差し支えないです。前者は差分なし、後者は 1 を削除して 1000001 を追加するのが差分に相当します。

このように、二つの文字列が全く同じである場合や、一部しか違わない場合にも \(\Theta(|S|\cdot |T|)\) 時間かかるのはあまりうれしくないです²。

Output-sensitive algorithm について

競プロにおいては、入力サイズのみから最悪ケースを考えて、それ以外のケースの計算量は特に考慮しないことが多いですが、全てのアルゴリズムの最悪ケースが入力サイズのみから決まるわけではありません。 典型例として以下の問題を考えます。

パターン文字列の集合 \(\mathscr{P} = \{P_1, P_2, \dots, P_m\}\) とテキスト文字列 \(T\) が与えられる。 各 \(i\) (\(1\le i\le m\)) に対して、\(P_i\) が \(T\) 中に現れる開始位置を列挙せよ。

• \(|\mathscr{P}|\le 10^6\)
• \(\sum_{P\in\mathscr{P}} |P| \le 10^6\)
• \(|T| \le 10^6\)

出力が多くなるケースとして、\(T = \mathtt{a}^{10^6}\), \(\mathscr{P} = \{\mathtt{a}, \mathtt{aa}, \dots, \mathtt{a}^{1413}\}\) のようなものがあります。列挙される個数は \(10^9\) 個以上になります。 列挙される個数を \(z\) とすると \(\sum_{P\in\mathscr{P}} |P|\) の上限を \(U\) として \(z \approx \sqrt{U}\cdot |T|\) 程度になる入力は作れそうです。

とはいえ、この問題は \(O(|T| + (\sum_{P\in\mathscr{P}} |P|) + z)\) 時間で解けるため、列挙パートのせいで入力の制約を小さめにしてしまうのももったいない気がします。 そこで、「出力の個数は \(10^7\) を超えない」などの制約の下で出題されたりします。

このような、出力に関する値（ここでは個数）が計算量に絡んでくるアルゴリズムは output-sensitive algorithm と呼ばれます。

というわけで、元の問題において、たとえば差分の量で抑えられるようなアルゴリズムがあればうれしいな〜という気持ちになります。

本題

\(\Theta(|S|+|T|+\delta(S, T)^2)\) 時間のアルゴリズムを紹介します。 ただし \(\delta(S, T)\) は \(S\) と \(T\) の差分の量 (= 削除の個数 + 追加の個数) です。書き換えができない場合の編集距離と見ることもできます。

ここで、\(\delta(S, T) \in [0, |S|+|T|]\) です。最悪 \(\Theta((|S|+|T|)^2)\) 時間となり、普通の DP の \(\Theta(|S|\cdot|T|)\) より悪そうですが、「まず今回のアルゴリズムを走らせて、\(\Theta(|S|\cdot|T|)\) 時間かかってしまったら DP でやり直す」とすれば、定数倍で少し損するだけにできるので ok です。

ところで、この問題に関しては、文字が == のみでしか比較できない場合は \(\Omega(n^2)\) 時間、<=> で比較できる場合でも \(\Omega(n\log(n))\) 時間の lower bound が知られているようです³。

概要

疲れちゃったので、概要だけ示します。詳細は下記の文献にあります。

まず、これはグラフの問題と見ることができます。

• 頂点数は \( (|S|+1)\cdot(|T|+1)\) 個
• 頂点 \( (i, j)\) から頂点 \( (i+1, j)\) にコスト 1 の辺を張る
  • \(i\in[0, |S|)\), \(j\in[0, |T|]\)
• 頂点 \( (i, j)\) から頂点 \( (i, j+1)\) にコスト 1 の辺を張る
  • \(i\in[0, |S|]\), \(j\in[0, |T|)\)
• 頂点 \( (i, j)\) から頂点 \( (i+1, j+1)\) にコスト 0 の辺を張る
  • \(i\in[0, |S|)\), \(j\in[0, |T|)\), \(S_i = T_j\)

このグラフ上での \( (0, 0)\) から \( (|S|, |T|)\) への最短路が \(S, T\) の差分に対応します。

0/1-BFS などで愚直にこのグラフの最短路を求めようとすると \(\Theta(|S|\cdot|T|)\) 時間かかってしまいますが、工夫した DP により、陽にグラフを持たずに \(\Theta((|S|+|T|)\cdot\delta(S, T))\) 時間で計算できます。

\(i-j=k\) とおいたとき、\(k\) が共通となる点は斜めに並ぶので、そうした点たちが成す直線を diagonal \(k\) と呼びます。「コスト \(d\) で到達できる diagonal \(k\) 上の点のうち、\((0, 0)\) から最も遠い点はどこか？」というのが DP で求められます。

さらに、DP の遷移を suffix tree を使って高速化することで \(\Theta((|S|+|T|)\log(|S|+|T|)+\delta(S, T)^2)\) 時間にできる旨が元論文に記載されています。 同じ diagonal 上は辺がある限りコスト 0 で進めるので、どこまで進めるか求めるのを高速化できるということです。

その高速化パートで、代わりに SA-IS と \(\langle O(n), O(1)\rangle\) RMQ を使うことで、\(\Theta(|S|+|T|+\delta(S, T)^2)\) 時間を達成できます。

Links

参考文献

• Myers, Eugene W. “An \(O(ND)\) difference algorithm and its variations.” Algorithmica 1, no. 1 (1986): 251-266.
  • http://www.xmailserver.org/diff2.pdf

実装例

差分を求めるのと同時に LCS も求められるので、これを使いました。ちょうど復元つきです。

• EDPC F - LCS
  • SA-IS と線形 RMQ で \(O(|S|+|T|+\delta(S, T)^2)\), 424 ms
  • 愚直に遷移して \(O((|S|+|T|)\cdot\delta(S, T))\) time, 170 ms
  • 適当な \(O(|S|\cdot|T|)\) time の DP, 100 ms

笑

上記は復元を雑に行っていて \(\Theta((|S|+|T|)^2)\) 時間になっていたので修正しました。訂正版：#37584015, 502 ms。しんどい。

Notes

📝 編集のコストが 1 のときと 2 のときで常に共通の edit script が存在する？ _<<><__<>><_> のように interleave する必要はなくて _<<<>__<<>>_> のようにできて、その上で _<<=__==_> のようにすればいいから存在すると思った。_ を変えるメリットはないはずだし。< > = _ がそれぞれ removed, added, changed, unchanged。 んー、「編集のコストを 1 として作った edit script で、その編集の部分のコストを 2（追加 + 削除）にしたものを考える。そのときのコストは初めから編集コストを 2 として求めた最適値と同じか？」みたいな感じのことを言いたかった。あるいは、2 として作ったものを適宜「編集」に置き換えて 1 の最適値にできる（ものが常に存在する）か？

だめで、aa ab に対して _a <a >b であれば _a =b にできるが、<a _a >b だと破綻する。たぶんうまく作ればもっとどうしようもない例を作れる気がする。

---

1. 各行 \(O(1)\) 文字ずつと仮定するなどして、各行ごとの等価判定は \(O(1)\) time でできることにします。 ↩

2. 実用の話をしながら極端めな例を挙げていますが、本質的には問題ないでしょう。 ↩

3. それぞれ Ullman, J. D., A. V. Aho, and D. S. Hirschberg. “Bounds on the complexity of the longest common subsequence problem.” Journal of the ACM (JACM) 23, no. 1 (1976): 1–12. と Hirschberg, Daniel S. “An information theoretic lower bound for the longest common subsequence problem.” Rice University ECE Technical Report 7705 (1977). にあるらしい。未履修。 ↩