差分符号化

差分符号化（さぶんふごうか、英: Delta encoding）とは、データの格納や転送を完全なファイルとしてではなく、シーケンシャルなデータの差分の形式で行う方式である。特に変更履歴の保存を目的とする場合（ソフトウェアプロジェクトなど）、差分符号化は差分圧縮（英: Delta compression）とも呼ばれる。デルタ符号化、デルタ圧縮とも呼ばれるが、デルタ符号とは異なる。

概要

例えばUNIXのファイル比較ユーティリティである diff などで「差分」または「デルタ」を作成し、個別にファイルとして記録する。差分は一般に元のファイルよりも小さいので、差分符号化によってデータの冗長性を大幅に削減できる。一連の差分ファイルの方が各バージョンのそのままのファイル群よりも大幅に記録容量が節約できる。

論理的観点から言えば、2つのデータの差分があれば、一方のデータからもう一方のデータを得ることができる。何らかの同値関係にあって同じ値の差分は 0 または零元と呼ばれる。よい差分は、対の一方がない限り、極小元であるか多義的となる。

もっとも単純な例は、シーケンシャルな値間の差分としてバイト列を格納するものである。例えば 2, 4, 6, 9, 7 という値の列があるとき、2, 2, 2, 3, -2 を格納する。これだけではあまり便利とは言えないが、順序性のある値がよく出現するようなデータでは、さらなる圧縮がやりやすくなる。IFF 8SVX 音声ファイルフォーマットはこのような符号化を行ってから圧縮している。ただし、量子化ビット数（ビット深度 (音響機器)）8ビットの音声標本値でも差分符号化が常に効率的とは限らず、16ビット以上ではさらに効果が低くなる。したがって、圧縮アルゴリズムでは差分符号化によって効率が向上する場合のみ差分符号化を選択することが多い。動画のフレームに差分符号化を適用すると効果が大きく、ほとんど全ての動画圧縮コーデックに使われている。

差分には、「相対称差分（symmetric delta）」と「方向的差分（directed delta）」がある。相対称差分は次のように表される。

$\Delta (v_{1},v_{2})=(v_{1}\backslash v_{2})\cup (v_{2}\backslash v_{1})$

ここで、v₁ と v₂ は2つの連続するバージョンを表す。

方向的差分は（基本的な）変更操作の並びであり、それを v₁ に適用することで v₂ という次のバージョンが得られるようになっている。これはデータベースにおけるトランザクションログにも似ている。

文字列の接頭部や接尾部の差分を符号化する差分符号化を増分符号化（Incremental encoding）と呼ぶ。これは例えば辞書に掲載された単語の一覧のように、ソートされていて前後の文字列との差が小さいような一覧に対して適用すると効果的である（日本語の辞書では漢字があるため必ずしも効率的とは言えない）。

ネットワーク接続された2つのシステムそれぞれにあるファイルのコピーがあるとき、ファイルが前のバージョンからどう変更されたかを検出する方法として、差分符号化による転送で特殊な誤り制御符号を用いる。

符号化される対象データの性質によって圧縮アルゴリズムの効果が影響される。差分符号化はデータの変化が小さく、一定の場合に最も効率が良い。値がソートされておらず、ばらばらなデータセットでは、この方法での圧縮効率は小さい。

以下のC言語のコードは、単純な差分符号化/復号を行うものである（もっと効率的なコードも書けるが、分かりやすくするためにこのようなコードになっている）。

 void delta_encode(char *buffer, int length)
 {
     char t = 0;
     char original;
     int i;
     for (i=0; i < length; ++i) {
         original = buffer[i];
         buffer[i] -= t;
         t = original;
     }
 }
 
 void delta_decode(char *buffer, int length)
 {
     char t = 0;
     int i;
     for (i=0; i < length; ++i) {
         buffer[i] += t;
         t = buffer[i];
     }
 }

差分符号化の利用例として、RFC 3229 "Delta encoding in HTTP" がある。これは、HTTPサーバが更新されたWebページを前のバージョンとの差分の形で送信することを提案したもので、これはインターネット上の多くのページが一度に大幅に書き換えられるよりも少しずつ部分的に書き換えられるという事実に着目して、インターネットのトラフィックを削減する目的で提案されている。

This document describes how delta encoding can be supported as a compatible extension to HTTP/1.1.
Many HTTP (Hypertext Transport Protocol) requests cause the retrieval of slightly modified instances of resources for which the client already has a cache entry. Research has shown that such modifying updates are frequent, and that the modifications are typically much smaller than the actual entity. In such cases, HTTP would make more efficient use of network bandwidth if it could transfer a minimal description of the changes, rather than the entire new instance of the resource.

（訳）この文書はHTTP/1.1への互換な拡張として、いかに差分符号化をサポートするかを説明したものである。
多くの HTTP (Hypertext Transport Protocol) 要求は、クライアントがすでにキャッシュエントリを持っているリソースの若干変更されたインスタンスを取り寄せようとするものである。研究によれば、そのような変更は頻繁に行われ、変更規模は実際のリソース全体よりも遥かに小さい。そのような場合、リソースの新たなインスタンス全体よりも変更の最小限の記述を転送したほうが HTTP のネットワーク帯域幅の有効利用に繋がる。

差分符号化を行うソフトウェアと規格

外部リンク

RFC 3229 - Delta Encoding in HTTP
RFC 3284 - The VCDIFF Generic Differencing and Compression Data Format
版管理とソフトウェア再利用の支援に関する研究