可変長整数エンコーディング

2018年3月26日

いくつかの可変長整数エンコーディング実装について。このページの話題は任意精度整数演算ではなくデータ圧縮の目的で整数値をエンコーディングする方法である。

Protocol Buffers

Protocol Buffers の可変長整数は 0 に近い値が多いサイズ効率が高くなるように設計されている。まず整数全体のビットを下位から 7 ビット単位に分割してそれぞれ 8 ビット幅に格納し、それぞれのバイトの最上位ビットを最上位バイト以外で 1 とする。このバイト配列をリトルエンディアンとなるように配置を入れ替えたものが Protocol Buffers の可変長符号無し整数エンコーディングである。

具体例で示すと 0x000A0B0C = 638,188 = 0b10100000101100001100 を Protocol Buffers の可変長整数としてエンコードすると以下のように 0x8C9628 となる。

00001010 00001011 00001100
.0101000 .0010110 .0001100  // 1. 7bit 単位で再配置
00101000 10010110 10001100  // 2. 最上位バイト以外の最上位ビットを 1 に設定
10001100 10010110 00101000  // 3. リトルエンディアンに再配置

アプリケーションは前方から可変長整数を読み込む場合、読み込んだバイト値の最上位ビットが 1 であれば後ろにフィールドが続いていると判断することが出来る。

この方法は 0x00～0x7F の範囲であれば 1 バイトしか使用しないため (元の整数型が int か long かに拘らず)、統計的に 0 に近い値を取る傾向の整数を空間効率よく保存するのに向いている。7ビットごとに1ビット増加するため、数値表現に必要なビット幅は \(\frac{8}{7}\) 倍に増加する。

Bitcoin

Bitcoin の Blockchain で使用されている可変長整数エンコーディングは固定長整数 UINT8/16/32/64 の符号化を前提としている (任意精度整数の符号化ではない) この方法は最初のバイト値が 0x00～0xFC の範囲であれば整数値そのものを表しており、0xFD 以上であれば続く整数の大きさを示している。

10進数	バイトシーケンス
0～252	00 - FC
253～65,535	FD 00 FD - FD FF FF
65,536～4,294,967,295	FE 00 01 00 00 - FE FF FF FF FF
4,294,967,296～	FF 00 00 00 01 00 00 00 00 - FF FF FF FF FF FF FF FF FF

数値に対して必要なバイトサイズについて Protocol Buffers と比べてみると 0x00-0x7F で同等、0x80-0xFC で有利だがそれより大きくなると無駄なバイトが必要となる。

符号付き整数

符号付き整数に関しては ZigZag エンコーディングを使用して符号無し整数に変換し Protocol Buffers のような 0 近傍値によるサイズ圧縮を期待する方法を使用することができる。

ZigZag エンコーディングは以下の変換式で符号付き整数 \(i_s\) を符号無し整数 \(i_u\) へ変換する。\[ \begin{eqnarray*} i_u & = & \left\{ \begin{array}{ll} -2 i_s - 1 & \ \ \ {\rm if}\ i_s \lt 0 \\ 2 i_s & \ \ \ {\rm otherwise} \end{array} \right. \\ i_s & = & \left\{ \begin{array}{ll} \frac{n_u}{2} & \ \ \ {\rm if}\ n_u \ {\rm mod}\ 2 = 0 \\ - \frac{n_u + 1}{2} & \ \ \ {\rm othersise} \end{array} \right. \\ \end{eqnarray*} \]

これは整数型のビット演算を使用して以下のように書くこともできる。ここで bit_width は符号付き整数 n_s のビットサイズ (16, 32, 64) である。

i_u = (i_s << 1) ^ (i_s >> (bit_width - 1))

\(i_s\)	→	\(i_u\)
0	→	0
-1	→	1
1	→	2
-2	→	3
2	→	4
-3	→	5
3	→	6

この ZigZag エンコーディングは符号の正負にかかわらず 0 に近い値は小さな符号なし整数値に変換されるため Protocol Buffers のような「小さな値の空間効率が良い」エンコーディングを利用することができる。

参照

Encoding | Protocol Buffers | Google Developers
Protocol documentation (Bitcoin Wiki)