delta符号

計算機科学

先日gamma符号を紹介したので、今度はdelta符号を。

参考：gamma符号

delta符号はgamma符号と似ているのだが、大きな数値のときにgamma符号より少ないbitで済むように改良されている。一方で小さい数値の時はgamma符号のほうが効率が良い。


具体的に言うと、delta符号では数値を二進数にした時のbit数に対してさらにgamma符号を適用する。そしてその後ろに数値の二進数の先頭の1を除いたものをつける。(数値の二進表記は先頭が常に1であることに注意。常に1なので省いても大丈夫)つまり

数値	二進数	gamma符号	二進数のbit数	bit数のgamma符号	delta符号
1	1	1		1		1			1
2	10	010		2		010			0100
3	11	011		2		010			0101
4	100	00100		3		011			01100
5	101	00101		3		011			01101
6	110	00110		3		011			01110
7	111	00111		3		011			01111

復号化するときは始めにgamma符号を復号化すると、数値のbit数がわかるので、そのbit数分をひとつの数値として復号化すれば良い。例えば

01110
=> [0] 1110        # 0が1つ続いている
=> [0] [11] 10     # 1と、その後ろ1bitを分がひとつの数値
=> (3) 10          # 11を復号化して3になる
=> (3) [1] 10      # 1が省略されているので足す
=> [110]           # 3bit分をひとつの数値として復号化する
=> (6)

となる。2段階で復号化しているので小さな数値では冗長な表現のためdelta符号の方がgamma符号より長くなってしまうが大きな数値ではdelta符号のほうが短くなる。例えば、以下の通り(カッコ内はbit数)

数値	gamma符号			delta符号
1	1                   (1)		1                (1)
5	00101               (5)		01101            (5)
10	0001010             (7)		00100010         (8)
50	00000110010         (11)	0011010010       (10)
100	0000001100100       (13)	00111100100      (11)
500	00000000111110100   (17)	000100111110100  (15)
1000	0000000001111101000 (19)	0001010111101000 (16)

ちなみにunary符号では数値+1が必要なbit数なので、例えば数値が1000だとunary符号で1001bit、gamma符号で19bit、delta符号で16bit必要。gamma符号、delta符号が如何に効率が良いかがわかる。とはいえunary符号には単純であるという強みが有り、rank、selectなどの操作を付加したsuccinct bit vectorを作るときはunary符号のほうが圧倒的に簡単になる。