![テスト（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/85/Deflate-4-320.jpg)
![テスト（F#）
? 出力はハフマン符号テーブル付きのため、短
い入力ではPythonよりも冗長
open System.IO
open System.IO.Compression
let ms1 = new MemoryStream()
let ds1 = new DeflateStream(ms1, CompressionMode.Compress)
let src = /7shi/deflate/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/85/Deflate-5-320.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/85/Deflate-26-320.jpg)
More Related Content
What's hot (20)
More from 7shi (9)
Recently uploaded (8)
![ElasticsearchでSPLADEする [Search Engineering Tech Talk 2025 Winter]](https://cdn.slidesharecdn.com/ss_thumbnails/searchtech-250228102455-ddc5ce09-thumbnail.jpg?width=560&fit=bounds)
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 = /7shi/deflate/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. ご清聴ありがとうございました