差分符号化のソースを表示

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

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

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

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

差分には、「相対称差分（symmetric delta）」と「方向的差分（directed delta）」がある。相対称差分は次のように表される。
{{Indent|<math>\Delta(v_1, v_2) = (v_1 \backslash v_2) \cup (v_2 \backslash v_1)</math>}}
ここで、''v''<sub>1</sub> と ''v''<sub>2</sub> は2つの連続するバージョンを表す。

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

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

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

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

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

<syntaxhighlight lang="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];
     }
 }
</syntaxhighlight>

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

{{quote
|1 = 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.

{{Indent
|1 =
（訳）この文書はHTTP/1.1への互換な拡張として、いかに差分符号化をサポートするかを説明したものである。

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

== 差分符号化を行うソフトウェアと規格 ==
* [[diff]] と [[patch]]
* [[VCDIFF]] ({{IETF RFC|3284}})
* [[rsync]]
* [[xdelta]]

== 外部リンク ==
* {{IETF RFC|3229}} - Delta Encoding in HTTP
* {{IETF RFC|3284}} - The VCDIFF Generic Differencing and Compression Data Format
* [http://sel.ist.osaka-u.ac.jp/~lab-db/Dthesis/archive/10/10.pdf 版管理とソフトウェア再利用の支援に関する研究]

{{データ圧縮}}
{{バージョン管理システム}}

{{DEFAULTSORT:さふんふこうか}}
[[Category:データ圧縮]]
[[Category:データ差分]]