手作りネットプロトコル工房コミュのdiffの原理２

差分アルゴリズム
http://en.wikipedia.org/wiki/Diff
http://en.wikipedia.org/wiki/Longest_common_subsequence_problem

こういう差分を求める問題のことを LCS(Longest Common Subsequence)を求めるとか、編集距離とかリーヴェンシュタイン距離を求めるとか言うらしい。

一番簡単なアルゴリズムは WIKIでも説明されているように、２つのデータの各要素を総当りで比較していく方法があるようだ。これは入力データの量に対して二次関数的に処理時間がかかるようになるのだそうで、あまり効率がよくないらしい。 (日本語のwikiには『とても効率がよい』と書いてあるが、よほどのハイスペックマシンを使っている方が書いたに違いない。）

処理結果も、入力データが m と n と二つあったら、 m×n だけ領域が必要になるらしい。つまり１ギガのデータ２つの差分を取ると、１エクサ＝１００京バイト＝１０００，０００，０００ギガの領域が必要になるということになる。私事で恐縮だが、僕はマルチメディア用のファイルをジャーナルするのが目的で調べているので、これでは使い物にならない。

調べたら、既にこれを改善したアルゴリズムを考えて論文を書いた人がいるらしい。

解説
http://www.csse.monash.edu.au/~lloyd/tildeAlgDS/Dynamic/Hirsch/

Hirschbergの論文
http://www.cs.zju.edu.cn/people/yedeshi/Alinearspace-p341-hirschberg.pdf
※ この大学、人の論文をこんな勝手に転載してしまって、いいんだろうか。おかげで助かったけど...。

Hirschberg
http://en.wikipedia.org/wiki/Dan_Hirschberg

まだちゃんと読んでない。再帰的なロジックらしく、よく読んでみる必要がありそうだ。

で、面白いのが、上の monash.edu.au のページは、JavaScript で Hirschberg のアルゴリズムを実装しているのだ。これはとても興味深く、とても参考になりそうだ。

コメント(2)

最初
全て
最新の40件

[1] mixiユーザー 07月15日 06:21

Diffのプログラムって難しいんだよなぁ。。。

昔、困難さをまったく理解していなくて、作れなかったことがあって、
論文でアルゴリズム調べて作らないと無理なんだよなぁ。。。

話は変わって、だいぶ前に、ロボコン（ロボットコンテスト）で日本の学生（高専学校か、大学生かわすれた。。。）が、
インドの学生に負けてました。

パターン認識のアルゴリズムの性能差で勝負がついた記憶が在るのですが、
日本の学生は色々な創意工夫でPGを作成して、
インドの学生は論文を元にしてアルゴリズムを作成していました。

日本人も動作を観察してそれをフィードバックして試行錯誤して工夫しているわけですが、
論文の原文に当たって知識を吸収するとか、そういう姿勢が欠けてるかもしれない
と思いました。

ログインすると、みんなのコメントがもっと見れるよ