カスタムハフマン符号 - 七誌の開発日記

ZIP勉強会（id:n7shi:20110529）を開催しましたが、時間の都合もありカスタム（動的）ハフマン符号については「RFC 1951を読んでください」で説明を省略しました。IO_Zlib開発者のid:yoyaさんからコメントを頂いたので、某「例示は理解の試金石」を実践してみました。

よやさんのまとめ id:yoya:20110726:io_zlib

.NETのDeflateStreamはどんな短いものでもカスタムハフマンで圧縮します。それを利用して "aaaaa" というASCII文字列をカスタムハフマン圧縮してみます。

open System.IO
open System.IO.Compression
open System.Text

let fs = new FileStream("test.bin", FileMode.Create)
let ds = new DeflateStream(fs, CompressionMode.Compress)
let src = Encoding.ASCII.GetBytes("aaaaa")
ds.Write(src, 0, src.Length)
ds.Dispose()

結果は以下の通りです。やたら長いです。

00: ED BD 07 60 1C 49 96 25 26 2F 6D CA 7B 7F 4A F5
10: 4A D7 E0 74 A1 08 80 60 13 24 D8 90 40 10 EC C1
20: 88 CD E6 92 EC 1D 69 47 23 29 AB 2A 81 CA 65 56
30: 65 5D 66 16 40 CC ED 9D BC F7 DE 7B EF BD F7 DE
40: 7B EF BD F7 BA 3B 9D 4E 27 F7 DF FF 3F 5C 66 64
50: 01 6C F6 CE 4A DA C9 9E 21 80 AA C8 1F 3F 7E 7C
60: 1F 3F 22 32 3C FF 0F

これをRFC 1951に従って解読してみます。

3.1. 全般的な規約

ビットに分解します。最初の4バイトだけを取り上げます。

ED BD 07 60
11101101 10111101 00000111 01100000 （通常の2進数化。左が上位ビット）
10110111 10111101 11100000 00000110 （バイト単位でビット順を反転）

つまり左が下位になるように2進数化します。すべてのデータを変換すると以下の通りです。（アドレスは16進数）

00: 10110111 10111101 11100000 00000110 00111000 10010010 01101001 10100100
08: 01100100 11110100 10110110 01010011 11011110 11111110 01010010 10101111
10: 01010010 11101011 00000111 00101110 10000101 00010000 00000001 00000110
18: 11001000 00100100 00011011 00001001 00000010 00001000 00110111 10000011
20: 00010001 10110011 01100111 01001001 00110111 10111000 10010110 11100010
28: 11000100 10010100 11010101 01010100 10000001 01010011 10100110 01101010
30: 10100110 10111010 01100110 01101000 00000010 00110011 10110111 10111001
38: 00111101 11101111 01111011 11011110 11110111 10111101 11101111 01111011
40: 11011110 11110111 10111101 11101111 01011101 11011100 10111001 01110010
48: 11100100 11101111 11111011 11111111 11111100 00111010 01100110 00100110
50: 10000000 00110110 01101111 01110011 01010010 01011011 10010011 01111001
58: 10000100 00000001 01010101 00010011 11111000 11111100 01111110 00111110
60: 11111000 11111100 01000100 01001100 00111100 11111111 11110000

3.2.3. ブロックフォーマットの詳細

ブロックヘッダを読み込みます。ビットを左から拾います。

00: 101----- -------- -------- -------- -------- -------- -------- --------

BFINAL: 1
BTYPE: 01 → 10（順序反転）: カスタムハフマン符号で圧縮

3.2.7. カスタムハフマン符号を使った圧縮 (BTYPE=10)

アルファベットの説明は飛ばして、カスタムハフマンのヘッダを読みます。「我々は、今、ブロックのフォーマットを定義することができます。」の次の部分に該当します。

00: ---10111 10111101 1------- -------- -------- -------- -------- --------

HLIT: 10111 → 11101（順序反転）: 29
HDIST: 10111 → 11101（順序反転）: 29
HCLEN: 1011 → 1101（順序反転）: 13

次に (HCLEN + 4) × 3 = 51 ビットのデータを読みます。

00: -------- -------- -1100000 00000110 00111000 10010010 01101001 10100100
08: 0110---- -------- -------- -------- -------- -------- -------- --------

110 000 000 000 110 001 110 001 001 001 001 101 001 101 001 000 110
011 000 000 000 011 100 011 100 100 100 100 101 100 101 100 000 011（各データ順序反転）
3, 0, 0, 0, 3, 4, 3, 4, 4, 4, 4, 5, 4, 5, 4, 0, 3（10進数化）

このデータは変則的な順番で並んでいます。

16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15

どういう意味か具体例で示します。結果をhclensという整数配列に入れます。

hclens[16] = 3
hclens[17] = 0
hclens[18] = 0
hclens[ 0] = 0
hclens[ 8] = 3
hclens[ 7] = 4
hclens[ 9] = 3
hclens[ 6] = 4
hclens[10] = 4
hclens[ 5] = 4
hclens[11] = 4
hclens[ 4] = 5
hclens[12] = 4
hclens[ 3] = 5
hclens[13] = 4
hclens[ 2] = 0
hclens[14] = 3
hclens[ 1] = なし(0)
hclens[15] = なし(0)

※ 推測ですが、後ろのゼロを省略していることを踏まえると、統計的にゼロになりにくい要素から順番に並べている可能性があります。

まとめるとこうなります。

hclens = { 0, 0, 0, 5, 5, 4, 4, 4, 3, 3, 4, 4, 4, 4, 3, 0, 3, 0, 0 }

これは3.2.7の最初で解説されているアルファベットの各要素（0〜18）に対応するハフマン符号長です。これを計算すればアルファベットのハフマン符号が求められます。このアルファベットを仮にclenと名付けます。

※ ハフマン符号は、符号長から符号本体を作ることができます。詳細はRFC 1951(3.2.2. "deflate" フォーマットにおけるハフマン符号化の利用)やZIP勉強会の資料を参照してください。

clen[ 0] = なし
clen[ 1] = なし
clen[ 2] = なし
clen[ 3] = 11110
clen[ 4] = 11111
clen[ 5] = 1000
clen[ 6] = 1001
clen[ 7] = 1010
clen[ 8] = 000
clen[ 9] = 001
clen[10] = 1011
clen[11] = 1100
clen[12] = 1101
clen[13] = 1110
clen[14] = 010
clen[15] = なし
clen[16] = 011
clen[17] = なし
clen[18] = なし

clenによってリテラル/長さのアルファベット（以後lit）と距離アルファベット（以後dist）のハフマン符号長が定義されます。

lit は HLIT + 257 個、dist は HDIST + 1 個の要素から構成されます。litとdistはくっつけてclenで符号化されているため、全体（HLIST + 257 + HDIST + 1 個）をまとめて読み取ります。litとdistをくっつけた符号長リストを頭文字を取って仮にldと名付けます。

今回の例では HLIT = 29, HDIST = 29 なので、29 + 257 + 29 + 1 = 316 個となります。これがldの要素数です。注意するのはclenの16〜18はランレングスを表している点です。繰り返しの分だけ短くなるため、316個のハフマン符号（clenによる）が格納されているわけではありません。

具体的にldをclenで読み取っていきます。数値と異なり、ハフマン符号はビットを拾った後に順序反転しません。

08: ----0100 11110100 10110110 01010011 11011110 11111110 01010010 101011--

010 → clen[14]: 符号長 → ld[0] = 14
011 → clen[16]: 直前反復
- 反復長 2bit: 11 → 11（順序反転） → 3 （+ 3） → 6 → ld[1 .. 6] = 14
010 → clen[14]: 符号長 → ld[7] = 14
010 → clen[14]: 符号長 → ld[8] = 14
1101 → clen[12]: 符号長 → ld[9] = 12
1001 → clen[6]: 符号長 → ld[10] = 6
010 → clen[14]: 符号長 → ld[11] = 14
011 → clen[16]: 直前反復
- 反復長 2bit: 11 → 11（順序反転） → 3 （+ 3） → 6 → ld[12 .. 17] = 14
011 → clen[16]: 直前反復
- 反復長 2bit: 11 → 11（順序反転） → 3 （+ 3） → 6 → ld[18 .. 23] = 14
011 → clen[16]: 直前反復
- 反復長 2bit: 11 → 11（順序反転） → 3 （+ 3） → 6 → ld[24 .. 29] = 14
1110 → clen[13]: 符号長 → ld[30] = 13
010 → clen[14]: 符号長 → ld[31] = 14
1001 → clen[6]: 符号長 → ld[32] = 6
010 → clen[14]: 符号長 → ld[33] = 14
1011 → clen[10]: 符号長 → ld[34] = 10

※ 反復長を順序反転するのに注意してください。この例ではたまたま11しかないため順序反転は無意味ですが、01や10には影響します。

この要領でld[315]まで埋めていきます。結果は以下のようになります。

08: ----0100 11110100 10110110 01010011 11011110 11111110 01010010 10101111
10: 01010010 11101011 00000111 00101110 10000101 00010000 00000001 00000110
18: 11001000 00100100 00011011 00001001 00000010 00001000 00110111 10000011
20: 00010001 10110011 01100111 01001001 00110111 10111000 10010110 11100010
28: 11000100 10010100 11010101 01010100 10000001 01010011 10100110 01101010
30: 10100110 10111010 01100110 01101000 00000010 00110011 10110111 10111001
38: 00111101 11101111 01111011 11011110 11110111 10111101 11101111 01111011
40: 11011110 11110111 10111101 11101111 01011101 11011100 10111001 01110010
48: 11100100 11101111 11111011 11111111 11111100 00111010 01100110 00100110
50: 10000000 00110110 01101111 01110011 01010010 01011011 10010011 01111001
58: 10000100 00000001 01010101 00010011 11111000 11111100 01111110 00111110
60: 11111000 11111100 01000100 0------- -------- -------- --------

ld = {
  /*   0 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 12,
  /*  10 */   6, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /*  20 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /*  30 */  13, 14,  6, 14, 10, 12, 14, 14, 13, 10,
  /*  40 */   8,  9, 11, 10,  7,  8,  7,  9,  8,  8,
  /*  50 */   8,  9,  8,  9, 10,  9,  8,  9,  9,  8,
  /*  60 */   9, 10,  8, 14, 14,  8,  9,  8,  9,  8,
  /*  70 */   9, 10, 11,  8, 11, 14,  9, 10,  9, 10,
  /*  80 */   9, 12,  9,  9,  9, 10, 12, 11, 14, 14,
  /*  90 */  12, 11, 14, 11, 14, 14, 14,  6,  7,  7,
  /* 100 */   7,  6,  8,  8,  7,  6, 12,  9,  6,  7,
  /* 110 */   7,  6,  7, 13,  6,  6,  6,  7,  8,  8,
  /* 120 */   9,  8, 11, 13, 12, 13, 13, 14, 14, 14,
  /* 130 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 140 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 150 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 160 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 170 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 180 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 190 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 200 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 210 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 220 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 230 */  14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
  /* 240 */  14, 14, 14, 13, 13, 13, 14, 13, 14, 13,
  /* 250 */  14, 13, 14, 14, 14, 14, 14,  4,  3,  4,
  /* 260 */   4,  4,  5,  5,  5,  5,  5,  6,  6,  5,
  /* 270 */   6,  7,  8,  8,  9, 10,  9, 10, 12, 11,
  /* 280 */  12, 14, 14, 14, 12, 11,  6, 10, 11, 11,
  /* 290 */   9,  8,  8,  8,  7,  7,  5,  6,  4,  5,
  /* 300 */   4,  5,  4,  5,  4,  4,  4,  4,  4,  4,
  /* 310 */   4,  5,  4,  5,  5,  5}

これを分割してlitとdistの符号長リストとします。

lit: HLIT + 257 = 29 + 257 = 286 個 → litlen = ld[0 .. 285]
dist: HDIST + 1 = 29 + 1 = 30 個 → distlen = ld[286 .. 315]

これらの符号長を基に、litとdistのハフマン符号を別々に作ります。litは長すぎるため例で出てくる値だけ、distはすべてのハフマン符号を以下に示します。

lit[ 97] = 100110 // 'a'
lit[256] = 11111111111100 // 終端
lit[258] = 000 // 長さ 4

distlen = {
  /*  0 */   6, 10, 11, 11,  9,  8,  8,  8,  7,  7,
  /* 10 */   5,  6,  4,  5,  4,  5,  4,  5,  4,  4,
  /* 20 */   4,  4,  4,  4,  4,  5,  4,  5,  5,  5}

dist[ 0] = 111100
dist[ 1] = 1111111110
dist[ 2] = 11111111110
dist[ 3] = 11111111111
dist[ 4] = 111111110
dist[ 5] = 11111100
dist[ 6] = 11111101
dist[ 7] = 11111110
dist[ 8] = 1111100
dist[ 9] = 1111101
dist[10] = 10110
dist[11] = 111101
dist[12] = 0000
dist[13] = 10111
dist[14] = 0001
dist[15] = 11000
dist[16] = 0010
dist[17] = 11001
dist[18] = 0011
dist[19] = 0100
dist[20] = 0101
dist[21] = 0110
dist[22] = 0111
dist[23] = 1000
dist[24] = 1001
dist[25] = 11010
dist[26] = 1010
dist[27] = 11011
dist[28] = 11100
dist[29] = 11101

以上でリテラル/長さのアルファベットと距離アルファベットのハフマン符号が得られました。

展開

圧縮データの展開に入ります。固定ハフマンとはハフマン符号が異なるだけでやり方は同じです。

60: -------- -------- -------- -1001100 00111100 11111111 111100--

100110 → lit[97] → 'a'
000 → lit[258] → 長さ 4
111100 → dist[0] → 距離 1
11111111111100 → lit[256] → 終端

以上で "aaaaa" が復元できました。

コード例

今回の説明はF#の実装を基にしています。パブリックドメインです。

https://github.com/7shi/FSharpZip/blob/master/Zip/Deflate.fs

具体的には181〜231行目のDynamicHuffmanクラスが該当します。