デルタエンコーディング

数値の差分は、上記の例に示すように、減算によって簡単に定義できます。算術演算の性質により、数値の差分は対称です。つまり、後者の値が前者より小さい場合、前者の値は前者より小さくなります。${\displaystyle b}$が既知であれば、デルタを適用することが可能です${\displaystyle ba}$逆方向に操作して前の値を取得する${\displaystyle a}$。

数値的な「デルタのデルタ」を生成することも可能です。これは、基となるデータが次のようなプロセスによって生成される場合に役立ちます。${\displaystyle f(x)=ax+b}$2次デルタではデータがゼロの列に平坦化されてしまうため、これは問題です。タイムスタンプはしばしばこのように動作します。^{[ 1 ]}実際のデータでは、さらに高次のデルタも役立つ場合があります。たとえば、時間経過に伴う航法衛星までの測定距離（擬似距離）は、3次デルタ、つまり「デルタのデルタのデルタ」を使用して最もよく圧縮されます。^{[ 2 ]}

減算に加えて、ビットごとの排他的論理和(XOR) も対称的な差分を生成します。時系列データベースでは、XOR 演算が浮動小数点数間の差分としてよく使用されます。これは、XOR 演算によって、ほとんどがゼロビットで構成される圧縮しやすい差分が生成されるためです。^{[ 1 ]}

もう1つのバリエーションは、デルタ演算に使用される要素間の距離を変更することです。${\displaystyle ba}$シーケンスで${\displaystyle (a,b,c,d)}$「距離2」のデルタは、${\displaystyle ca}$これは、 xzの「デルタ」フィルターで確認できます。^{[ 3 ]}

void encode ( uint8_t buffer [], size_t length ) { uint8_t last = 0 ; for ( size_t i = 0 ; i < length ; ++ i ) { uint8_t current = buffer [ i ]; buffer [ i ] = current - last ; last = current ; } }void decode ( uint8_t buffer [], size_t length ) { uint8_t last = 0 ; for ( size_t i = 0 ; i < length ; ++ i ) { uint8_t delta = buffer [ i ]; buffer [ i ] = delta + last ; last = buffer [ i ]; } }

値のシーケンスまたはセット（文字列や画像など）間の差分については、デルタは対称デルタと有向デルタの2つの方法で定義できます。2つのセット間の対称デルタには、可逆性を確保するために十分な情報が含まれています。

$\displaystyle \Delta ({\mathit {version}}_{1},{\mathit {version}}_{2})=({\mathit {version}}_{1}\setminus {\mathit {version}}_{2})\cup ({\mathit {version}}_{2}\setminus {\mathit {version}}_{1}).}$

2 つのシーケンスの差分も同様に定義されますが、追加と削除の位置を示す情報が追加されます。コンピュータの実装では、diff コマンドの出力(デフォルト、統合、コンテキストモード) にその例が示されます。出力は「位置」という形式の命令です。${\displaystyle x}$（古いコンテンツを）（新しいコンテンツ）に置き換えます。

方向付きデルタ（変更とも呼ばれる）は、（基本的な）変更操作のシーケンスであり、${\displaystyle {\mathit {version}}_{1}}$、別のものを生み出す、${\displaystyle {\mathit {version}}_{2}}$（データベースのトランザクションログとの対応関係に注目してください）。コンピュータ実装では、通常、2 つのコマンドを持つ言語の形式をとります。${\displaystyle {\mathit {version}}_{1}}$そして、リテラルデータを書き込みます。例としては、スクリプト編集モードでdiffコマンドを実行したときの出力が挙げられます。

デルタエンコーディングの使用例としては、 RFC 3229「HTTPにおけるデルタエンコーディング」が挙げられます。このRFCでは、HTTPサーバーは更新されたWebページをバージョン間の差分（デルタ）の形で送信できるようにすべきだと提案しています。これは、ほとんどのページは繰り返し完全に書き換えられるのではなく、時間の経過とともにゆっくりと変化するため、インターネットトラフィックを削減するはずです。

この文書では、デルタエンコーディングをHTTP/1.1の互換性のある拡張機能としてサポートする方法について説明します。

HTTP（ハイパーテキスト転送プロトコル）リクエストの多くは、クライアントが既にキャッシュエントリを持っているリソースの、わずかに変更されたインスタンスの取得を引き起こします。研究によると、このような変更更新は頻繁に発生し、変更内容は通常、実際のエンティティよりもはるかに小さいことがわかっています。このような場合、HTTPはリソースの新しいインスタンス全体ではなく、変更内容の最小限の説明を転送できれば、ネットワーク帯域幅をより効率的に利用できます。

[...] この文書の後半で説明する「インスタンス操作」フレームワークを使用してrsyncをサポートできる可能性があると考えていますが、詳細はまだ検討されていません。

提案されたrsyncベースのフレームワークは、HTTPプロキシのペアとしてrproxyシステムに実装されました。 ^{[ 6 ]}基本的なvcdiffベースの実装と同様に、どちらのシステムもほとんど使用されていません。

差分コピーは、以前のバージョンがコピー先の場所に存在する場合に、部分的に変更されたファイルを高速にコピーする方法です。差分コピーでは、ファイルの変更された部分のみがコピーされます。これは通常、バックアップまたはファイルコピーソフトウェアで使用され、多くの場合、プライベートネットワークまたはインターネットを介してコンピュータ間でコピーする際の帯域幅を節約します。注目すべきオープンソースの例の 1 つはrsyncです。^{[ 7 ] [ 8 ] [ 9 ]}

Diffはファイル比較プログラムで、主にテキストファイルで使用されます。デフォルトでは、可逆的な対称差分を生成します。ソフトウェアパッチに使用される2つのフォーマット、contextとunifiedは、行番号のずれを許容するための追加のコンテキスト行を提供します。

Git ソースコード管理システムは、補助的な「git repack」操作でデルタ圧縮を採用しています。リポジトリ内のまだデルタ圧縮されていないオブジェクト（「ルーズオブジェクト」）は、ヒューリスティックに選択された他のすべてのオブジェクトのサブセットと比較され、共通データと差分が「パックファイル」に連結され、従来の方法で圧縮されます。ソースファイルやデータファイルがコミット間で段階的に変更される一般的な使用例では、これにより大幅な容量削減が可能になります。リパック操作は通常、「git gc」^{[ 10 ]}プロセスの一部として実行され、ルーズオブジェクトまたはパックファイルの数が設定されたしきい値を超えると自動的にトリガーされます。

このフォーマットは、Git ドキュメントの pack-format ページに記載されています。これは、指向性デルタを実装しています。^{[ 11 ]}

指向性デルタ符号化の一般的なフォーマットの一つに、 RFC 3284で規定されているVCDIFFがある。フリーソフトウェアによる実装としては、Xdeltaやopen-vcdiffなどが挙げられる。

汎用差分フォーマット（GDIFF）は、別の指向性デルタ符号化フォーマットです。これは1997年にW3Cに提出されました。 ^{[ 12 ]}多くの場合、VCDIFFはGDIFFよりも圧縮率が優れています。

Bsdiff はサフィックスソートを使用するバイナリ差分プログラムです。ポインタアドレスの変更が多い実行ファイルの場合、VCDIFF タイプの「コピーとリテラル」エンコーディングよりも優れたパフォーマンスを発揮します。その目的は、アセンブリコードを解析することなく (Google の Courgette のように) 小さな差分を生成する方法を見つけることです。Bsdiff は、エラーのある「コピー」マッチを許可し、バイトごとの差分の追加「追加」配列を使用してエラーを修正することでこれを実現します。この配列は、オフセットの変更に対してほとんどがゼロまたは繰り返し値であるため、圧縮後には小さなスペースしか占有しません。^{[ 13 ]}

bsdiff は差分更新に役立ちます。Google は Chromium と Android で bsdiff を使用しています。RPMパッケージマネージャのdeltarpm機能は、ハッシュテーブルを使用してマッチングできる大幅に変更された bsdiff に基づいています。^{[ 14 ]} FreeBSDも更新に bsdiff を使用しています。^{[ 15 ]}

2005年にbsdiff 4.3がリリースされて以来、さまざまな改良や修正が行われてきました。Googleは、各製品向けに複数のバージョンのコードを維持しています。^{[ 16 ]}divsufsort FreeBSDは、主に脆弱性の修正とより高速なサフィックスソートルーチンへの切り替えなど、Googleの互換性のある変更の多くを取り入れています。 ^{[ 17 ]} Debianは、このプログラムに一連のパフォーマンス調整を加えています。^{[ 18 ]}

ddelta は、Debian のデルタ アップデートで使用するために提案された bsdiff の書き直しです。他の効率改善の中でも、メモリと CPU コストを削減するためにスライディング ウィンドウを使用しています。^{[ 19 ]}