バイナリ差分アルゴリズム

[戻る]
シャノン 2004/07/05(月) 17:34:55
2つのデータを比較して差分を求め、パッチ化するアルゴリズムってどうやるのかご存
知の方いらっしゃいませんか?
やり方、サンプルコード、VC++ アプリに組み込めるライブラリ等、もしご存知でしたら
教えていただけないでしょうか。

やりたいことは、ファイルのインクリメンタル・バックアップです。
最初にあるファイルを保存し、以降の更新では更新差分だけを取得して保存しておく。
最初のファイルから差分を順次適用していくことで、任意の時点のファイルを復元した
いと考えています。

LZ 法の応用でできるという話も聞くので、その方面でも調べてみようと思います。

シャノン 2004/07/05(月) 17:41:50
追記
パッチのサイズはできるだけ小さくなる、という条件つきで。
とことん小さくしようと思ったら難しい論文とか読まなきゃいけないのかもしれません
が、例えば、元ファイルの先頭に1バイト挿入されただけで、まったく違うものとみな
すような差分はお断り、とゆーことでひとつ。

よろしくお願いします。

こじま 2004/07/05(月) 18:53:34
よく使われているらしい差分アルゴリズムとして、ONPというのがあります。
pukiwikiのdiffで使っているはず。昔、ここで、ちょっとだけ議論していました。
論文へのリンクもあります。
http://pukiwiki.sourceforge.jp/dev/?PukiWiki%2F1.4%2FDiff

どっちかというとテキスト向けのアルゴリズムなので、
バイナリに使うのは、大げさ過ぎてもったいない気もしますが、
まあ1Kbyteずつくらいにブロックを区切って、
ブロックを単位として、ONPをやればいい気がします。

シャノン 2004/07/06(火) 10:12:38
情報ありがとうございます。
調べてみたいと思います。

他にもご存知の方がいらっしゃいましたら、よろしくお願いいたします。

シャノン 2004/07/09(金) 20:28:41
[[解決]]
こじまさん、貴重な情報をありがとうございました。
あわよくば、他にも情報をくださる方がいらっしゃらないかと図々しくも待ってみまし
たが、ひとまず、こじまさんの教えてくださった方法を元に調べてみたいと思います。
このままスレを閉じないのも申し訳ありませんので、解決チェックといたします。

古いスレッドには追加発言できません。