差分符号化

ウィキペディア

差分符号化

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/10/02 16:40 UTC 版)

差分符号化（さぶんふごうか、英: 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})$ 圧縮フォーマット

圧縮ソフトウェア