![テスト（Python）
• zlibの出力からヘッダ（先頭2バイト）とチェック
サム（末尾4バイト、Adler-32）を取り除けば
生のDeflateデータが得られる
• 展開で渡すマイナスのパラメータはヘッダや
Adler-32が存在しないことを示す
>>> import zlib
>>> zlib.compress('aaaaa')[2:-4]
'KL¥x04¥x02¥x00'
>>> zlib.decompress('KL¥x04¥x02¥x00', -8)
'aaaaa'](https://image.slidesharecdn.com/deflate-101003104709-phpapp01/75/Deflate-4-2048.jpg)
![テスト（F#）
• 出力はハフマン符号テーブル付きのため、短
い入力ではPythonよりも冗長
open System.IO
open System.IO.Compression
let ms1 = new MemoryStream()
let ds1 = new DeflateStream(ms1, CompressionMode.Compress)
let src = Encoding.ASCII.GetBytes("aaaaa")
ds1.Write(src, 0, src.Length)
ds1.Close()
let compressed = ms.ToArray()
let ms2 = new MemoryStream(compressed)
let ds2 = new DeflateStream(ms2, CompressionMode.Decompress)
let buf = Array.zeroCreate<byte> 256
let len = ds2.Read(buf, 0, buf.Length)
let decompressed = Encoding.ASCII.GetString(buf.[..len - 1])](https://image.slidesharecdn.com/deflate-101003104709-phpapp01/75/Deflate-5-2048.jpg)
![固定ハフマン符号 （2）
• Pythonの出力例を分析
>>> zlib.compress('aaaaa')[2:-4]
'KL¥x04¥x02¥x00'
• 4B 4C 04 02 00
• 01001011 01001100 00000100 00000010
00000000
• 1101001000110010001000000100000000000000
• 1（最終）, 10（1=固定）, 10010001（0x61='a'）,
1001001（0x61='a'）, 0000001（0x101=長さ3）,
00000（0x00=距離1）, 0000000（0x100=終端）](https://image.slidesharecdn.com/deflate-101003104709-phpapp01/75/Deflate-26-2048.jpg)
Deflate
- 1. Deflate 七誌
- 2. このスライドについて • Deflateの実装に必要な知識はRFC 1951に 網羅されている • しかし定義が並んでいるだけなので、いきな り読んでも意味がわからない • 実際のDeflateのデータとRFC 1951を見比 べながら試行錯誤して、ようやく把握 • RFC 1951を読む前の導入的なスライドを目 指して作成、網羅的解説ではない
- 3. Deflate • ZIP, gzip, PNGで使われている圧縮方式 – ZIPはコンテナ込み、gzipはコンテナなし（→tar） • RFC 1951で定義 • 圧縮率はtar.gz, tar.bz2, tar.xzを比較すれば 目安になる – そこそこの圧縮率とそこそこの処理速度 • バイトの可変長bit化とコピペで圧縮 – 可変長bit化をハフマン符号化と呼ぶ – コピペをLZSSを呼び、LZ77の亜種
- 4. テスト（Python） • zlibの出力からヘッダ（先頭2バイト）とチェック サム（末尾4バイト、Adler-32）を取り除けば 生のDeflateデータが得られる • 展開で渡すマイナスのパラメータはヘッダや Adler-32が存在しないことを示す >>> import zlib >>> zlib.compress('aaaaa')[2:-4] 'KL¥x04¥x02¥x00' >>> zlib.decompress('KL¥x04¥x02¥x00', -8) 'aaaaa'
- 5. テスト（F#） • 出力はハフマン符号テーブル付きのため、短 い入力ではPythonよりも冗長 open System.IO open System.IO.Compression let ms1 = new MemoryStream() let ds1 = new DeflateStream(ms1, CompressionMode.Compress) let src = Encoding.ASCII.GetBytes("aaaaa") ds1.Write(src, 0, src.Length) ds1.Close() let compressed = ms.ToArray() let ms2 = new MemoryStream(compressed) let ds2 = new DeflateStream(ms2, CompressionMode.Decompress) let buf = Array.zeroCreate<byte> 256 let len = ds2.Read(buf, 0, buf.Length) let decompressed = Encoding.ASCII.GetString(buf.[..len - 1])
- 7. 符号化（固定長） • 1バイト＝8ビット＝0x00～0xFF • すべての値が使われているとは限らない • 例: 00 00 23 00 AA 00 55 00 • 00, 23, 55, AA（昇順）の4種類だけ • それぞれ00, 01, 10, 11と2ビット化 • → 00 00 01 00 11 00 10 00 • 8ビット→2ビットでデータ量が1/4に！
- 8. 符号化（可変長） • 値は出現頻度が異なることが多い 00 00 • 例: 00 00 00 23 5A AA 23 55 23 00 23 01 • 00と23の出現頻度が高い 55 100 • 頻度が高いものを短く符号化 5A 101 • →00 00 00 01 101 110 01 100 01 00 AA 110 • 最初の2ビットを取り出した段階で10以上は、もう1 ビット取り出して解釈する – 考え方としてはUTF-8のようなマルチバイトと同じ • このような可変長符号をハフマン符号と呼ぶ – ハフマン木表現は実装にあまり関係ないので省略
- 9. 符号化のバランス • あまり短いビットを割り当ててしまうと、それ 以降のビットの収容数が減る – 極端な例が0を使用したケース 0 00 00 00 10 01 01 01 110 10 10 100 1110 110 110 101 11110 111 1110 1100 111110 打ち止め 11110 1101
- 10. 符号長表現 （1） • ハフマン符号のビット長を並べたものから、ハ フマン符号が作り出せる – 組み合わせによっては溢れるので注意！ 2 00 2 00 3 000 3 000 2 01 2 01 3 001 3 001 3 100 2 10 3 010 4 0100 3 101 3 110 4 0110 4 0101 3 110 3 111 4 0111 4 0110 3 111 3 不可能 4 1000 4 0111
- 11. 符号長表現 （2） • ビット長は必ずしもソートされているとは限ら ないので、短いビットから順番に処理 – 実データの符号化で必要になる 2 00 4 1000 4 0110 4 0100 3 100 3 010 4 0111 4 0101 3 101 3 011 3 000 4 0110 2 01 2 00 4 1000 3 000 3 110 4 1001 3 001 4 0111 3 111 4 1010 3 010 3 001
- 12. 符号長表現 （3） • 実際のデータに適用してみる 00 00 2 • 例: 00 00 EA 13 14 FF EA 00 13 100 3 • 00とEAの出現頻度が高い 14 101 3 • 頻度が高いものを短く符号化 EA 01 2 • → 00 00 01 100 101 110 01 00 FF 110 3 • ビット長は0x00～0xFFの全てを定義する必要があ るため、欠番は0として、ランレングスで表現 • → 2, 0×18, 3×2, 0×213, 2, 0×20, 3 • 「符号長定義＋符号化データ」をセットにする
- 13. まとめ ハフマン符号化 • データに出現する値を集計する • 出現頻度に応じてハフマン符号を割り振る • 割り振ったハフマン符号でデータを符号化 復元 • ランレングスによる符号長定義からハフマン符号を 復元 • 得られたハフマン符号によりデータを復元
- 15. LZ77 • 以前に同じバイトパターンが出ていた場合、 戻り距離と長さを指定してコピペする – 開発したのがLempel氏とZiv氏 • 例: 21 ED AC 7C E5 ED AC 7C FB → 21 ED AC 7C E5 （距離 4, 長さ 3） FB • LZ77: (距離,長さ,不一致記号） • (0,0,21) (0,0,ED) (0,0,AC) (0,0,7C) (0,0,E5) (4,3,FB) • 不一致部分で0,0が頻発して冗長
- 16. LZSS • Deflateで使われているのはこちら • バイト（0x00～0xFF）の後に終端（0x100）と 一致長（0x101～0x11D）を付けて符号化 – ハフマン符号化の時点で8bit縛りはない – LZ77とはペアの順序が逆→長さ・距離 • 例: 21 ED AC 7C E5 ED AC 7C FB → 21 ED AC 7C E5 （長さ 3, 距離 4） FB → 21 ED AC 7C E5 101 3 FB 100 – 【注】距離符号が3なのはミスではない（後述）
- 17. スライド窓 • Deflateの仕様で指定できる長さ・距離の範囲 が制限されている – 長さ: 3～258, 距離: 1～32768 • データが進んでいくに従って、コピペ対象とな る範囲（窓）が移動していく→スライド窓 進行方向→ データ ↑ ↑ 対象範囲 現在位置
- 18. 長さ符号 • 0x101～0x11Dで3～258の 0x101 3 一致長を表現する 0x102 4 • 0x109～は複数の長さを表す ・・・ – 符号に拡張ビットを後続させて 0x109 11～12 補完（符号ごとの固定長） – 14→13+1→0x10A,1 0x10A 13～14 – 197→195+2→0x11B,00010 ・・・ • 258は特別扱い 0x11B 195～226 – 227+31(0x11C,11111)は欠番 0x11C 227～257 – 259でないのは偶数狙い？ 0x11D 258
- 19. 距離符号 • 0x00～0x1Dで1～32768 0x00 1 の一致距離を表現する 0x01 2 – 長さ同様に拡張ビットあり ・・・ • 長さ符号の後に必ず来る • バイト・長さ符号とは別に 0x04 5～6 ハフマン符号化 0x05 7～8 – 符号長定義も別々 ・・・ • 前の例で距離4が3に符号 0x1B 12289～16384 化されていたのは、距離 が1から始まっているため 0x1C 16385～24576 0x1D 24577～32768
- 20. コピーの重複 • コピー元とコピー先が重複している場合、普 通は処理方向を分ける（memcpy等） – 下の例では、後ろからコピーしないと壊れる コピー元 コピー先 • Deflateではわざと先頭からコピーすることで、 繰り返しデータを表現（ランレングス相当） • 例: ‘a’, ‘b’, ‘c’, 長さ 6, 距離 3 → abcabcabc
- 22. ビットストリーム • データから1ビットずつ取り出しながら処理す る→ビットストリーム • 下位ビットから取り出す • “ab” ←① ←② → 01100001 01100010 → 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0 • ハフマン符号は可変長のため、バイト揃えの パディングは考えない – 無圧縮ブロックは例外
- 23. バイト順序 • 数値は下位ビットから配置 • ハフマン符号だけは上位ビットから配置 • 長さ符号・距離符号は、ハフマン符号が上位 から、拡張ビットが下位から並ぶ • 例： 0x1Bのハフマン符号を1101と仮定 距離15000→12289+2711 ①→ ←② →0x1B（＝1101）,101010010111 →1101111010010101
- 24. ブロック • Deflateストリームは（複数の）ブロックから構成 – ブロックの種類は数値扱いなので下位から配置 最終フラグ ブロックの種類 終端 データ 1bit 2bit (0x100) 0: 無圧縮 1: 固定ハフマン符号 ブロックの種類 2: カスタムハフマン符号 3: 未定義（予約）
- 25. 固定ハフマン符号 （1） • あらかじめ定義されたハフマン符号を使う • バイト・長さ符号は以下の通り – 前述のように値は符号長から算出できる 0x00～0x8F 8bit 00110000～10111111 0x90～0xFF 9bit 110010000～111111111 0x100～0x117 7bit 0000000～0010111 0x118～0x11F 8bit 11000000～11000111 • 距離符号は5ビット固定長を使う – ハフマン符号ではないので下位ビットから配置
- 26. 固定ハフマン符号 （2） • Pythonの出力例を分析 >>> zlib.compress('aaaaa')[2:-4] 'KL¥x04¥x02¥x00' • 4B 4C 04 02 00 • 01001011 01001100 00000100 00000010 00000000 • 1101001000110010001000000100000000000000 • 1（最終）, 10（1=固定）, 10010001（0x61='a'）, 1001001（0x61='a'）, 0000001（0x101=長さ3）, 00000（0x00=距離1）, 0000000（0x100=終端）
- 27. カスタムハフマン符号 • 出現頻度を分析してハフマン符号を定義 • データの前に符号の定義が来る – 前述のランレングスを用いた符号長定義 – .NETのDeflateStreamの出力が冗長なのは、こ の定義が含まれているため • 詳細はRFC 1951参照 – 長さ符号が変な順番で並んでいるが、個数に応じ て末尾が落ちる（ほぼ15の有無） – 16, 17, 18, 0, 8, 7, 9, 6, 10, 5, 11, 4, 12, 3, 13, 2, 14, 1, 15
- 28. まとめ • Deflateはハフマン符号化とLZSSを組み合わ せて圧縮する • ハフマン符号は途中で切り替えることができ る→ブロック分割 • 最適なハフマン符号を求めようとすると、組み 合わせが爆発して事実上困難 – いわゆる巡回セールスマン問題 – どこで割り切るかは実装者の裁量 • 後はRFC 1951を読んでください・・・
- 29. ご清聴ありがとうございました