差分符号化
diff と patch
VCDIFF (RFC 3284)
rsync
xdelta
動画のフレームに差分符号化を適用すると効果が大きく、ほとんど全ての動画圧縮コーデックに使われている。
差分には、「相対称差分(symmetric delta)」と「方向的差分(directed delta)」がある。相対称差分は次のように表される。
Δ ( v 1 , v 2 ) = ( v 1 ∖ v 2 ) ∪ ( v 2 ∖ v 1 ) {\displaystyle \Delta (v_{1},v_{2})=(v_{1}\backslash v_{2})\cup (v_{2}\backslash v_{1})}
ここで、v1 と v2 は2つの連続するバージョンを表す。
方向的差分は(基本的な)変更操作の並びであり、それを v1 に適用することで v2 という次のバージョンが得られるようになっている。これはデータベースにおけるトランザクションログにも似ている。
文字列の接頭部や接尾部の差分を符号化する差分符号化を増分符号化(Incremental encoding)と呼ぶ。これは例えば辞書に掲載された単語の一覧のように、ソートされていて前後の文字列との差が小さいような一覧に対して適用すると効果的である(日本語の辞書では漢字があるため必ずしも効率的とは言えない)。
ネットワーク接続された2つのシステムそれぞれにあるファイルのコピーがあるとき、ファイルが前のバージョンからどう変更されたかを検出する方法として、差分符号化による転送で特殊な誤り制御符号を用いる。
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 のネットワーク帯域幅の有効利用に繋がる。