Location : Home > Languages > Perl > Package
Title : Algorithm::GDiffDelta
Toolbox Logo

名称

 Algorithm::GDiffDelta - GDIFF フォーマットバイナリデルタの生成と利用


概要

use Algorithm::GDiffDelta qw(
   gdiff_adler32 gdiff_delta gdiff_apply
);

# 一方は入力用・他方は出力用である2つの GDIFF バイナリデルタのファイルハンドルを利用
gdiff_delta($orig, $changed, $delta);

# 元ファイルとGDIFFデルタから変更されたファイルを再構築
gdiff_apply($orig, $delta, $changed);

# 高速 adler32 ダイジェストの実装も可能
my $adler32 = gdiff_adler32(1, 'some data');
$adler32 = gdiff_adler32($adler32, 'some more data');

説明

 本モジュールは2つのファイルの間の差異を記述するバイナリデルタを生成するために用いられる。第1のファイルとデルタが与えられれば第2のファイルを再構築することができる。
 デルタはUNIXにおける diff プログラムの出力と同等で、バイトの列を含む類似のバイナリファイルの間の差異を効果的に表現する点のみが異なる。これらのデルタは(rsync のように)ネットワークを介してファイルを更新する場合や(Subversion のように)効率的にファイルの変更の履歴を格納する場合に有用である。
 バイナリデルタにはいくつかのフォーマットがある。本モジュールでサポートしているのは極めてシンプルで W3C note としてドキュメント化されている GDIFF フォーマットである(下記参考資料を見よ)。
 本モジュールはファイルハンドルを使ってデルタを生成し、処理する。Perl のファイルハンドル(組み込みの open コマンドで生成される)も正しいメソッドをサポートするオブジェクトも扱うことができる。作業するオブジェクトは、入力用であれば read, seek, tell メソッドを、出力用であれば write メソッドをサポートしている必要がある。IO::Scalar|IO::Scalar オブジェクトまたは類似のものでラップすることで入力用及び出力用に利用することができる。本モジュールの将来のバージョンでは、効率的であるから、直接スカラへの参照を直接読み書きできるようにする。
 本モジュールにおけるアルゴリズムや GDIFF デルタフォーマットがどのように作用するかについては下記のアルゴリズムとデルタフォーマットを参照のこと。


関数

 デフォルトでは何もエクスポートされない。use 行で Exporter に関数名を渡すか、:all タグで全てをインポートするかである。

gdiff_adler32($initial_value, $string_data)

 $initial_value のハッシュ値から始まる $string_data のバイトの Adler32 ダイジェストを生成する。本関数は内部的にのみ利用されるがバイナリデルタファイルの生成・利用には必要ではない。
 $initial_value は通常1である。本関数を読み出した結果(32 ビット符号なし整数値)はチェックサムの初期として渡される。これにより大規模なファイルを別々のチャンクで処理することができる。
 Adler-32 の他の実装は Digest::Adler32|Digest::Adler32 モジュールにある。

gdiff_apply($file1, $file2, $delta_file)

 3つのファイルハンドルを取る。最初の2つは入力用で、必ず発見されなければならない。3つ目めは出力用である。
 これは $file1 から $file2 への変化を記述するバイナリデルタを生成する。デルタは $file1 から $file2 を再構築することができる。
 返り値はなし。エラー時にはエラーメッセージを出力する。

gdiff_delta($file1, $delta_file, $file2)

 3つのファイルハンドルをとる。最初の2つは入力用で、必ず発見されなければならない。3つ目めは出力用である。
 デルタは $file1 から $file2 を再構築するために用いられる。デルタは妥当な GDIFF ファイルでなければならない。
 返り値はなし。エラー時にはエラーメッセージを出力する。


アルゴリズムとデルタフォーマット

 本モジュールで用いられるアルゴリズムといくつかのコードは xdiff ライブラリによる。xdiff(機能的には同等だが GDIFF よりも若干シンプル)で用いられるフォーマットよりもGDIFFデルタを書くために修正されている。
 アルゴリズムがどのように機能するかに関するノートはここに追加される。
 GDIFFファイルは5バイトのヘッダと、それに続くコマンドの列から構成される。各コマンドは引数をもつ1バイトのオプコード('opcode') からなる。デルタファイルはオプコード0で終了する。
 コマンドには2つの型がある。DATA コマンドは出力に挿入される引数の文字的データのチャンクを持つ。COPY コマンドは入力ファイルから出力ファイルへのデータのチャンクをもたらす。
 GDIFFデルタは一方通行である。$file1 から $file2 を生成することはできても、逆はできない。


参考資料

 本モジュールの元になっている xdiff ライブラリは http://www.xmailserver.org/xdiff-lib.html
 GDIFF の仕様は http://www.w3.org/TR/NOTE-gdiff-19970901
 Adler-32 チェックサムアルゴリズムを定義している RFC 1950 は http://www.faqs.org/rfcs/rfc1950.html


著者と著作権

 本ライブラリの一部は Davide Libenzi <davidel@xmailserver.org> の libxdiff のコードから導出されている。残りの部分については Geoff Richards <qef@laxan.com> に著作権がある。
 本ライブラリはフリーソフトウェアであり、フリーソフトウェア財団の発行している GNU Lesser General Public License (2.1 またはユーザの選択でそれ以降)の条件の下で修正/再配布してもよい。ライセンスの条文は http://www.gnu.org/copyleft/lesser.html で入手可能である。

Toolbox Logo
Updated : 2008/01/23