（難解メモですんません） 差分を求めるアルゴリズム
2008年07月15日02:01
差分アルゴリズム
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 のアルゴリズムを実装しているのだ。 これはとても興味深く、とても参考になりそうだ。
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 のアルゴリズムを実装しているのだ。 これはとても興味深く、とても参考になりそうだ。
コメント一覧
