Wuのアルゴリズムの問題点
Wuのアルゴリズムは2つの要素列が似通っている場合,
- 注9)
- リスト1のように編集距離だけを求めるのであれば,
探索する範囲は広くなっても, メモリの消費はさほど大きくなりません。問題となるのはSESの経路記録です。
その他のアルゴリズム
本稿ではWuのアルゴリズムについて解説しましたが,
動的計画法(Dynamic Programming)
動的計画法
また,
最後にこの情報を逆順にたどっていけば,
DPを使った差分の計算では単純に各部分列のLCSの長さを保存しようとすると,
Myersのアルゴリズム
MyersのアルゴリズムはWuのアルゴリズムと同じく,
GNU diffutilsや分散型バージョン管理システムの1つであるGitのdiffエンジンとして採用されているXLibdiffの実装はこのアルゴリズムを基にしています
- 注10)
- P≦Dなので,
素のMyersのアルゴリズムはWuのアルゴリズムよりも計算コストが高いですが, これらの実装ではMyersのアルゴリズムに差分をヒューリスティックに求める改良を施して, 精度を落とす代わりに計算速度を向上させています (ここで言う 「精度を落とす」 とは, 「最短経路ではない経路で解を求める」 という意味で, 「差分の解析結果の精度を落とす」 という意味ではありません)。実際, dtlやSubversionのdiffエンジンよりもこれらの実装のほうが計算速度は速いです。
Gestalt Approach
Gestalt ApproachはWuのアルゴリズムやMyersのアルゴリズムと違い,
最後に
本稿のサンプルコードでは,
コラム「dtl開発の苦労話」
筆者はdtlを開発しているとき,
プログラムではWuのアルゴリズムの経路探索の過程でその配列にSESの経路候補の座標を追加していき,
少々悩んだあと,
- ① SESの座標候補の配列に座標を追加していく
- ② SESの座標候補の配列のサイズが一定のサイズになったら,
いったんそこまでのLCSやSESを計算する - ③ 座標候補の配列を空にする
- ④ 2つの要素列の比較が最後まで終わっていない場合は①に戻る。終わっている場合は⑤へ
- ⑤ これまでに計算した複数のLCSやSESを全部つなげて1つにする
この方法により,
しかし,
- 注A)
- OSに付属のプロセスモニタを見ると,
dtlを使ったプログラムのメモリ使用量が1Gバイトを越えていました。 - 注B)
- 近似アルゴリズムについて詳しく勉強したい方は参考文献の
『近似アルゴリズム』 が参考になるかもしれません。
- 参考文献・
URL - E.
W.MYERS, "An O(ND) Difference Algorithm and Its Variations" - Sun Wu, Udi Manber, G.
Myers, W. Miller, "An O(NP) Sequence Comparison Algorithm" 『アルゴリズムイントロダクション 「第2巻」 アルゴリズムの設計と解析手法 改訂2版』
T.コルメン,C.ライザーソン, R.リベスト, C.シュタイン共著/ 浅野哲夫, 岩野和生, 梅尾博司, 山下雅史, 和田幸一共訳/ 近代科学社/ 987-4-7649-0335-7 『近似アルゴリズム』 V. V.ヴァジラーニ著/ 浅野孝夫訳/ シュプリンガー・ ジャパン/ 987-4-4317-00991-6 - PATTERN MATCHING:THE GESTALT APPROACH
URL:http://www. ddj. com/ 184407970?pgno=5 - 文書比較アルゴリズム
URL:http://hp. vector. co. jp/ authors/ VA007799/ viviProg/ doc5. htm - Webサイト
「/0」 内の記事――diff(1), diff(2), diff(3),
URL:http://www. slash-zero. jp/ archives/ program/ 466
URL:http://www. slash-zero. jp/ archives/ program/ 468
URL:http://www. slash-zero. jp/ archives/ program/ 476 - 各種言語(C, Go, Java, Lua, Perl, Python, Ruby)によるWuのアルゴリズムの実装
URL:https://github. com/ cubicdaiya/ onp
- E.