なんとなく聞き流しがちな「圧縮」をGoの実装から理解する（可逆圧縮編）
はじめに
「データを圧縮すれば小さいサイズでレスポンスを返せて速くなるぞ」(唐突)
そこで大抵、「まあそうだよね」と答えられるはずです。これは非エンジニアだとしてもなんとなくそういうふうに思えるはずです。
.....でも、よく考えたら、データを「圧縮」「小さくする」って、実際何をしてるんだろうか。
「よし、概念的に調べるぞ、ソースコードも読むぞ」ということで、RFCをはじめ色々調べてみたのでまとめていきます。
なお、読む実装コードの言語はgolangです。
まずはどんなふうに圧縮されているかを概念的に理解したあと、コードを実際に見て確認していきます。
圧縮とは何かを概念的に理解する
圧縮と一口に言っても、大きく２種類あるようです。
- 可逆性圧縮（lossless compression）
- 非可逆性圧縮（lossy compression）
字面の通り、前者は「元に戻せる」後者は「元には戻せない」ようですね。
今回は可逆性圧縮編ということで、前者について見ていきます。（非可逆性についてはまた気が向いたら）
可逆性圧縮
可逆性圧縮はデータ圧縮方法の1つであり、例として以下のフォーマットがあるようです。
- gzip
- zip
- brotli
- png
いくつかよく見るフォーマットがありますね。
これらのフォーマットはそれぞれが特有の圧縮アルゴリズムを用いていますが、brotliを除いた3つはDEFLATEというアルゴリズムを用いているようです。
それでは、可逆性圧縮の代表的アルゴリズムであるDEFLATEについて少し掘りたいと思います。
DEFLATEアルゴリズム
単語の意味自体が、「圧縮/空気を抜く」らしいです。
このアルゴリズムは、2つの技術で構成されています。
それが、LZ77とハフマン符号化です。
DEFLATEアルゴリズムを使って以下のようなテキストを圧縮してみるとします。
She said she will see what she said
1. 文字列に対して、LZ77アルゴリズムを使い「リテラル/シンボル」のトークン列に変換する
繰り返されている文字列部分をシンボルに置き換えます。
概念的に表すと、<length(= 一致した長さ), backward distance(= 参照開始位置までの距離)>のようなものです。
この場合、以下のようなトークン列になるでしょう。
S,h,e, ,s,a,i,d, ,s,h,e, ,w,i,l,l, ,s,e,e, ,w,h,a,t, ,<length=3,distance=18>, ,<length=4,distance=27>
図解で表すと、以下のようになります。
ちなみに、heも重複とできるのでは？と思ったかもしれませんが、重複にマッチできる最短の長さが3であるとRFCで決まっているので、heはそれぞれリテラルとしておきます。
重複文字列を処理できるのにも、「範囲」があります。
Search Buffer(=読み込み済みであり、重複を参照できる範囲)が32K、Look ahead Buffer(=処理できる範囲)が258byteがそれぞれ上限です。
この数値に関してはRFC1951にある通りです。
encoded data blocks in the "deflate" format consist of sequences of symbols drawn from three conceptually distinct alphabets: either literal bytes, from the alphabet of byte values (0..255), or <length, backward distance> pairs, where the length is drawn from (3..258) and the distance is
drawn from (1..32,768)......“deflate” 形式における符号化データブロックは、3つの概念的に異なるアルファベットから取られたシンボルの並びで構成されている。
それらは、次のいずれかである： リテラルバイト（バイト値のアルファベット（0..255）から取られる）、または〈長さ, 後方距離〉のペアであり、ここで長さは (3..258) から、距離は (1..32,768) から取られる。
左から右へSearch Buffer+Look ahead Bufferの範囲がスライドしていく感じになります。
2. ハフマン符号表を作成する
ハフマン符号化によって、
- 出現頻度の高いリテラル/シンボルに対しては小さなbit列を割り当てる
- 出現頻度の低いリテラル/シンボルに対しては大きいbit列を割り当てる
ことを実現し、最終的なサイズを小さくしていきます。
この時、「リテラル/長さ（length）シンボルの符号表」と「距離(distance)シンボルの符号表」が分けられます。
以下のような符号表が出来上がりました。
Literal / Length 用ハフマン表
| シンボル (値) | 意味 | 出現回数 | 符号長 | Canonical 符号 |
|---|---|---|---|---|
| 32 | ' ' (space) | 7 | 2 | 00 |
| 101 | 'e' | 4 | 3 | 010 |
| 104 | 'h' | 3 | 3 | 011 |
| 115 | 's' | 3 | 3 | 100 |
| 97 | 'a' | 2 | 4 | 1010 |
| 105 | 'i' | 2 | 4 | 1011 |
| 108 | 'l' | 2 | 4 | 1100 |
| 83 | 'S' | 1 | 5 | 11010 |
| 100 | 'd' | 1 | 5 | 11011 |
| 116 | 't' | 1 | 5 | 11100 |
| 119 | 'w' | 2 | 5 | 11101 |
| 257 | length = 3 (length code) | 1 | 5 | 11110 |
| 258 | length = 4 (length code) | 1 | 5 | 11111 |
Canonical Huffman符号は、以下の2つの原則に従って決まっています。
- シンボルごとに符号長を決める
符号長 ≒ ハフマン木を作成した時のノードの深さで決まると考えていいと思っています。
つまり、頻度の高いものほどノードは浅くなるので符号長は短くなり、短いCanonical Huffman符号が割り当てられるようになります。
筆者が書いてみたハフマン木は以下の感じです。これをもとに上の表を作りました。
ハフマン木の作り方に関しては以下の記事等をご覧ください。
- 同じ符号長はシンボル順で連続番号の符号を割り当てる
シンボル（値）に関して、リテラルはASCIIコードと一致します。lengthに関しては、257–285までが設けられており、285を超える場合はextra bitsを追加して表現します。
雰囲気、「頻度の高いシンボルには短いbit長を、低いものには長めのbit長を割り当てている」のが把握してもらえればOKです。
Distance 用ハフマン表
backward distanceに関しては別で符号表が作られます。
以下のトグル内の距離テーブルを参照して、「距離コード」を決めます。
距離テーブル
- backward distance table(RFC1951 3.2.5より)
| Code | Extra Bits | Distance |
|---|---|---|
| 0 | 0 | 1 |
| 1 | 0 | 2 |
| 2 | 0 | 3 |
| 3 | 0 | 4 |
| 4 | 1 | 5–6 |
| 5 | 1 | 7–8 |
| 6 | 2 | 9–12 |
| 7 | 2 | 13–16 |
| 8 | 3 | 17–24 |
| 9 | 3 | 25–32 |
| 10 | 4 | 33–48 |
| 11 | 4 | 49–64 |
| 12 | 5 | 65–96 |
| 13 | 5 | 97–128 |
| 14 | 6 | 129–192 |
| 15 | 6 | 193–256 |
| 16 | 7 | 257–384 |
| 17 | 7 | 385–512 |
| 18 | 8 | 513–768 |
| 19 | 8 | 769–1024 |
| 20 | 9 | 1025–1536 |
| 21 | 9 | 1537–2048 |
| 22 | 10 | 2049–3072 |
| 23 | 10 | 3073–4096 |
| 24 | 11 | 4097–6144 |
| 25 | 11 | 6145–8192 |
| 26 | 12 | 8193–12288 |
| 27 | 12 | 12289–16384 |
| 28 | 13 | 16385–24576 |
| 29 | 13 | 24577–32768 |
以下のようなハフマン符号表が作成されます。
| distance-code | Base distance | Extra bits (長さ) | 出現回数 | Canonical Huffman 符号 | このデータでの extra 値 |
|---|---|---|---|---|---|
| 8 | 17 | 3 | 1 | 0 |
001 (18 − 17 = 1) |
| 9 | 25 | 3 | 1 | 1 |
010 (27 − 25 = 2) |
1つ目のdistanceは18でした。Distance(範囲)を参照すると、Codeは8になることがわかります。Code=8の範囲は、17-24だったので、17の数字が基準です。+1個分基準を上回っているため、extra bitを3bit分追加します。このextra bitの数も表に載っています。
3. トークン列をハフマン符号化する
ステップ2では、ハフマン符号表を2つ作成しました。この符号表を元に、トークン列を符号化していきます。
Each type of value (literals, distances, and lengths) in the compressed data is represented using a Huffman code, using one code tree for literals and lengths and a separate code tree for distances.
引用：RFC 1951 - 2. Compressed representation overview
改めて、以下のようにハフマン符号化できます。LZ77による圧縮後のトークン列を、それぞれの表を参照して対応させると以下のようになります。
| トークン | 種別 | Huffman 符号 |
|---|---|---|
S |
Literal (83) | 11010 |
h |
Literal (104) | 011 |
e |
Literal (101) | 010 |
(space) |
Literal (32) | 00 |
s |
Literal (115) | 100 |
a |
Literal (97) | 1010 |
i |
Literal (105) | 1011 |
d |
Literal (100) | 11011 |
(space) |
Literal (32) | 00 |
s |
Literal (115) | 100 |
h |
Literal (104) | 011 |
e |
Literal (101) | 010 |
(space) |
Literal (32) | 00 |
w |
Literal (119) | 11101 |
i |
Literal (105) | 1011 |
l |
Literal (108) | 1100 |
l |
Literal (108) | 1100 |
(space) |
Literal (32) | 00 |
s |
Literal (115) | 100 |
e |
Literal (101) | 010 |
e |
Literal (101) | 010 |
(space) |
Literal (32) | 00 |
w |
Literal (119) | 11101 |
h |
Literal (104) | 011 |
a |
Literal (97) | 1010 |
t |
Literal (116) | 11100 |
(space) |
Literal (32) | 00 |
<len=3,dist=18> |
Length symbol257 |
11110 + dist符号 0 + extra 001
|
<len=4,dist=27> |
Length symbol258 |
11111 + dist符号 1 + extra 010
|
これをLSB(Least Significant Bit first)でビット列に連結すると、データ本体は以下のようになります。
DEFLATEのビットストリーム右端のbitからから順に読み込むので、bitごとにならびを逆転させています。
0101111001000001010111011101100001110010001011111011010011001100001010010001011111001010011100011110100111111010
符号表があればこれは正しく解釈されます。
そして、圧縮データ本体の前には「ヘッダー」が、末尾にはEOFコードが付加されます。
ヘッダーにはまず、このブロックに含まれるデータ本体についてのメタデータを含みます。
| フィールド | ビット長 | 説明 | 値（2ビットの場合） |
|---|---|---|---|
| BFINAL | 1 | このブロックが最後かどうか | 0 = まだ続く, 1 = 最後のブロック |
| BTYPE | 2 | ブロックの圧縮方式 | 00 = 非圧縮 |
| 01 = 固定ハフマン | |||
| 10 = 動的ハフマン | |||
| 11 = 予約（使用不可） |
さらに、動的(つまり、BTYPE=10)の場合は圧縮データの前に2つのハフマン符号表の情報が圧縮データの前に入ります。
最終的なブロック（概念）
gzipによるDEFLATEアルゴリズムを用いた可逆性圧縮をコードで読む
さて、本題はここからです。
今までの話をコードで理解していきましょう。
まず、gzip圧縮するための最小コードを以下に示します。
var buf strings.Builder
gzipWriter := gzip.NewWriter(&buf)
gzipWriter.Write([]byte(data)) # dataは何らかの文字列
gzip.NewWriterから順に追ってみます。
gzip.NewWriter()を見る
名前からも察せる通り、io.Writer型を返す、gzipコンストラクタ関数のようなもののようです。
func NewWriter(w io.Writer) *Writer {
z, _ := NewWriterLevel(w, DefaultCompression)
return z
}
内部的に以下の関数を呼び出しています。
func NewWriterLevel(w io.Writer, level int) (*Writer, error) {
z := new(Writer)
z.init(w, level)
return z, nil
}
z.init()の中で、gzip.Writer構造体の中身を詰めていますね。
func (z *Writer) init(w io.Writer, level int) {
compressor := z.compressor
*z = Writer{
Header: Header{
OS: 255, // unknown
},
w: w,
level: level,
compressor: compressor,
}
}
このz.compressorは、型を見るとflateパッケージのものでした。
type Writer struct {
// 省略
compressor *flate.Writer
}
圧縮してくれる感じのやつ(compressor)がflate型となると、すでにDEFLATEアルゴリズムの匂いがしますね。
これがWriteメソッドでどう使われているかが気になるところです。
(*gzip.Writer) Write()を見る
内部は以下のようになっていて、(d *compressor) writeメソッドを実行しています。
// Write writes data to w, which will eventually write the
// compressed form of data to its underlying writer.
func (w *Writer) Write(data []byte) (n int, err error) {
return w.d.write(data)
}
そして、以下がDEFLATEアルゴリズムの本丸っぽいです。
func (d *compressor) write(b []byte) (n int, err error) {
// 省略
n = len(b) // 戻り値として返す元のバイト数
// メインループ: データを段階的に処理
for len(b) > 0 {
// 圧縮処理を実行
d.step(d)
// データをウィンドウバッファに充填
b = b[d.fill(d, b):]
// 省略
}
return n, nil
}
ここで重要そうなのが、step()とfill()でしょう。
これの定義を見に行こう、と思ったらこれはcompressor構造体のフィールド(メソッド値)でした。
ここでついでにcompressor構造体の全体像も見ておきます。
type compressor struct {
compressionLevel
w *huffmanBitWriter
// compression algorithm
fill func(*compressor, []byte) int // copy data to window
step func(*compressor) // process window
// input window: unprocessed data is window[index:windowEnd]
index int
window []byte
windowEnd int
blockStart int // window index where current tokens start
byteAvailable bool // if true, still need to process window[index-1].
// queued output tokens
tokens []token
// deflate state
length int
offset int
}
さて、step()やfill()はどこで注入されていたのでしょうか。
compressor構造体に圧縮ロジックがどこで注入されているかを見る
上では省略していましたが、(*gzip.Writer) Write()メソッド中の以下でした。
func (z *Writer) Write(p []byte) (int, error) {
// 省略
if !z.wroteHeader {
// 省略
if z.compressor == nil {
// ⭐️ここでcompressor構造体インスタンスが生成されている
z.compressor, _ = flate.NewWriter(z.w, z.level)
}
}
// 省略
// ここが圧縮処理でありDEFLATEアルゴリズムの本丸
n, z.err = z.compressor.Write(p)
return n, z.err
}
flate.NewWriter()コンストラクタを見てみます。
func NewWriter(w io.Writer, level int) (*Writer, error) {
var dw Writer
if err := dw.d.init(w, level); err != nil {
return nil, err
}
return &dw, nil
}
さらにその中のinit()メソッドがcompressor構造体を初期化していそうです。
func (d *compressor) init(w io.Writer, level int) (err error) {
d.w = newHuffmanBitWriter(w)
switch {
// 省略
case level == DefaultCompression:
level = 6
fallthrough // 次のcaseも実行されるキーワード
case 2 <= level && level <= 9:
d.compressionLevel = levels[level]
d.initDeflate()
d.fill = (*compressor).fillDeflate
d.step = (*compressor).deflate
}
return nil
}
引数として渡されるlevelによってcaseの分岐が走っています。少し遡ってgzip.NewWriter()では、DefaultCompressionがgzip.Writer構造体のlevelフィールドに格納されていたので、基本的には上の抜粋箇所のcase level == DefaultCompression:を通るはずです。
そして、fallthroughキーワードによりswitch-case文を抜けず、次のcaseを実行します。以下の処理です。
d.compressionLevel = levels[level]
d.initDeflate() // 構造体のメソッド値以外のフィールドを初期化
d.fill = (*compressor).fillDeflate
d.step = (*compressor).deflate
fill、stepはメソッド値として、fillDeflateメソッド、deflateメソッドが代入されています。
次のセクションで、メソッド2つをそれぞれ見ていきます。
が、その前に、一旦DEFLATEアルゴリズムで圧縮しているwriteメソッドの流れを改めて把握しておきましょう。
(d *compressor) write
func (d *compressor) write(b []byte) (n int, err error) {
// 省略
n = len(b) // 戻り値として返す元のバイト数
// メインループ: データを段階的に処理
for len(b) > 0 {
// 圧縮処理を実行
d.step(d)
// データをウィンドウバッファに充填
b = b[d.fill(d, b):]
// 省略
}
return n, nil
}
では、fillDeflateメソッドから見てみましょう。
(d *compressor) fillDeflate(b []byte)を見る
ここでは、ウィンドウの管理をしていると言えます。
func (d *compressor) fillDeflate(b []byte) int {
if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
// shift the window by windowSize
copy(d.window, d.window[windowSize:2*windowSize])
d.index -= windowSize
d.windowEnd -= windowSize
// 省略
}
n := copy(d.window[d.windowEnd:], b)
d.windowEnd += n
return n
}
先述しましたが、以下のような数値がRFCでは挙げられていました。
- Search Buffer: 過去32KBから重複を検索
- Look-ahead Buffer: 現在から258B先まで処理
なので、理論上は32KB + 258Bがwindowサイズで、それがスライドしていくと考えていましたが、goではそれとは少し異なる実装がされているようです。
というのも、Search Buffer , Look-ahead Bufferの値はRFC準拠だが、スライド効率を上げるために、より広いwindowサイズ（64KB）で管理されていました。
const (
windowSize = 1 << logWindowSize // 32768byte ->32KB
maxMatchLength = 258 // 258byte
)
// 構造体のメソッド値以外のフィールドを初期化するメソッド
func (d *compressor) initDeflate() {
d.window = make([]byte, 2*windowSize) // 32KB * 2 -> 64KB
// 省略
}
中身は触れませんでしたが、initDeflate()メソッドは、先にも登場していました。
さて、一旦ボリューミーなifブロックはskipして、fillDeflate()の最下部の処理を見ましょう。
n := copy(d.window[d.windowEnd:], b)
d.windowEnd += n
return n // 最後に、widowに追加されたバイト数を返す
渡されたbyte sliceぶんをwindowに追加していってる感じですね。
そして、冒頭のif文では、indexが進みwindowサイズ(64KB)が逼迫してきたら、後半32KBのみ残すようにスライドして、32KB分のバッファが新たに生まれます。
if d.index >= 2*windowSize-(minMatchLength+maxMatchLength) {
// shift the window by windowSize
copy(d.window, d.window[windowSize:2*windowSize]) // 後半32KBのみ残す
d.index -= windowSize // この時点では32KB減ってるのでindex - 32KB
d.windowEnd -= windowSize // この時点では32KB減ってるのでend - 32KB
// 省略
}
これらの処理がどう作用するかを整理します。改めて、fillDeflateメソッドが呼ばれる(d *compressor) write箇所を抜粋しました。
for len(b) > 0 {
// 圧縮処理を実行
d.step(d)
// ⭐️ここ
b = b[d.fill(d, b):]
// 省略
}
例えば、bの容量が100KBとして、初回の処理をイメージしてみます。
d.fill(d, b)に差し掛かると、64KB分はwindowに格納されます。そして、このメソッドは格納された分のバイト数が返されるので、64KBが返り、
b = 100KB[64KB:]
となり、これでbが36KB分に更新されます。
これで圧縮処理step()（後述）を繰り返しながらindexが進んでいき、indexが進みwindowサイズ(64KB)が逼迫してきたら、fillDeflate()でwindowのスライドが発生し、32KB分のバッファが追加されるため、bのうちの32KB分が追加されます。
b = 36KB[32KB:]
で、またスライドが発生したら残りの4KBがwindowに追加されていく....みたいな感じです。
(d *compressor) deflate()を見る
こここそ、圧縮のコアロジックです。
大枠の処理は、for loop内で行われています。
func (d *compressor) deflate() {
Loop:
for {
// 1. LZ77：検索ハッシュテーブルを構築(Search Buffer)
// 2. LZ77:マッチ検索を実行する(Look ahead Buffer)
// 3. LZ77:マッチ or リテラルの圧縮トークン生成処理
// 4. 圧縮トークンをCanonical Huffman符号化ブロックとして出力
}
}
ループ処理内で重要そうなところを見ていきます。
1. LZ77：検索ハッシュテーブルを構築(Search Buffer)
if d.index < d.maxInsertIndex { // 境界チェック
// 現在位置の4バイトでハッシュ計算
hash := hash4(d.window[d.index : d.index+minMatchLength])
hh := &d.hashHead[hash&hashMask]
d.chainHead = int(*hh) // 過去の同じハッシュ位置を取得
d.hashPrev[d.index&windowMask] = uint32(d.chainHead) // チェーン構築
*hh = uint32(d.index + d.hashOffset) // 現在位置を新しいヘッドに設定
}
まずは、現在位置（index）から４バイト分のデータをハッシュ値(32bit)に変換しています。
hash := hash4(d.window[d.index : d.index+minMatchLength])
hash4()の実装
func hash4(b []byte) uint32 {
return ((uint32(b[3]) | uint32(b[2])<<8 | uint32(b[1])<<16 | uint32(b[0])<<24) * hashmul) >> (32 - hashBits)
}
以下では、ハッシュ値をさらに短縮して、それを配列indexとしてhashHeadから要素のポインタを得ています。
hh := &d.hashHead[hash&hashMask]
hashHeadは、ハッシュ値をそのまま配列インデックスとして使い、最新の出現箇所を要素として持っています。
つまり、hhには、現在処理しているデータのハッシュ値と同じものが「あれば」、前の出現箇所indexが格納されていると言えます。
以下では、その前の出現箇所indexをd.chainHeadに一旦格納しています。
d.chainHead = int(*hh)
そして、前の出現箇所index(d.chainHead)を、現在のindexから辿れるようにd.hashPrevに格納しています。
d.hashPrev[d.index&windowMask] = uint32(d.chainHead) // チェーン構築
最後に、hashHeadを今のindexに更新します。
*hh = uint32(d.index + d.hashOffset) // 現在位置を新しいヘッドに設定
この一連の処理を整理すると、
- 処理中のデータを4バイト分ハッシュ化し、
hashHeadテーブル（配列）で検索 - 検索で引っかかった（前にも同じバイト列が出現していた）場合は、それを
hashPrevにて現在のindexから過去の出現indexを辿れるように格納する -
hashHeadを現在のindexに更新
のようになります。
このステップは、LZ77アルゴリズムで、Search Bufferから重複箇所を高速に検索できるようにハッシュテーブルを構築している部分だと言えるでしょう。
2. LZ77:マッチ検索を実行する(Look ahead Buffer)
上で検索用のハッシュテーブルを更新した後で、実際に重複箇所のマッチを行います。
先述のとおり、RFCでは現在のindexから258Bまでの範囲が検索対象であり、過去に出現した重複箇所を探せる範囲は32KBでした。
実装を見てみます。
minIndex := d.index - windowSize // 検索範囲の下限
if d.chainHead-d.hashOffset >= minIndex { // 条件に関しては一部省略
// ハッシュチェーンを辿って最適なマッチを探索
if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
d.length = newLength
d.offset = newOffset
}
}
マッチ検索を行う条件に注目します。
if d.chainHead-d.hashOffset >= minIndex {...}
d.chainHeadは、処理データの4バイト分に関して重複していた箇所のindexが格納されている場所でした。
minIndexがどういう数値になっているかというと、minIndex := d.index - windowSizeという計算から、現在indexから32KB分戻ったindexと言えます（windowSizeはすでに登場しており、32KBを表す定数です）。
つまり、同じハッシュ値(4バイト分)を持つ過去のパターンが32KB検索範囲内に存在していたのか という条件だと言えるでしょう。
そして、条件に合致していた場合にマッチ検索が実行されます。
// ハッシュチェーンを辿って最適なマッチを探索
if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead-d.hashOffset, minMatchLength-1, lookahead); ok {
d.length = newLength
d.offset = newOffset
}
findMatch()にそのロジックがあります。
本質部分だけ残した抜粋版を以下に示します。
findMatch()
// Try to find a match starting at index whose length is greater than prevSize.
// We only look at chainCount possibilities before giving up.
func (d *compressor) findMatch(pos int, prevHead int, prevLength int, lookahead int) (length, offset int, ok bool) {
// 探索準備
minMatchLook := maxMatchLength
win := d.window[0 : pos+minMatchLook]
tries := d.chain //complessionLevelにより設定されたマッチ探索回数
length = prevLength
wPos := win[pos:]
minIndex := pos - windowSize
// ハッシュチェーンを辿って候補探索
for i := prevHead; tries > 0; tries-- {
// 実際のバイト比較でマッチ長を計算
n := matchLen(win[i:], win[pos:], minMatchLook)
// より長いマッチが見つかった場合
if n > length {
length = n // 次回ループのマッチ長の比較対象にする & マッチ長として返り値になる
offset = pos - i // 現在indexからマッチした箇所への距離
}
// 32KBまで遡ったら終了
if i == minIndex {
break
}
// ハッシュチェーンで次の候補位置へ移動
// windowMaskでウィンドウ内インデックスに変換し、hashOffsetでスライド分補正
i = int(d.hashPrev[i&windowMask]) - d.hashOffset
}
return
}
コメントに、
Try to find a match starting at index whose length is greater than prevSize.
訳：indexから始まって、prevSizeより長いマッチを見つけようとする。
とあり、prevLengthのパラメータにはminMatchLength-1を渡してfindMatchが呼ばれています。minMatchLengthは4なので、マッチの最短は3であるということですね。
以下では処理範囲を、始点からpos+258までとしてwinに切り出しています。posは現在のindexが入ります。
minMatchLook := maxMatchLength // 258
win := d.window[0 : pos+minMatchLook]
ここまでで、最短3,最長258というのはRFCの内容に準拠していそうなのが分かりますね。
そして、以下のような変数を準備します。
wEnd := win[pos+length] // 現在地index + 3、つまり最短マッチの末尾
wPos := win[pos:] // 現在地indexから末尾までのスライス
minIndex := pos - windowSize // 現在地indexから32KB戻ったindex、つまりSearch Bufferの下限
そして、マッチ検索を行うのが以下のfor loop内です。triesは、compressionLevelによって決まる最適なマッチ検索回数です(今回のdefaultなら128回)。
(結構端折ってます)
// ハッシュチェーンを辿って候補探索
for i := prevHead; tries > 0; tries-- {
// 実際のバイト比較でマッチ長を計算
n := matchLen(win[i:], win[pos:], minMatchLook)
// より長いマッチが見つかった場合
if n > length {
length = n // 次回ループのマッチ長の比較対象にする & マッチ長として返り値になる
offset = pos - i // 現在indexからマッチした箇所への距離
}
// 32KBまで遡ったら終了
if i == minIndex {
break
}
// ハッシュチェーンで次の候補位置へ移動
// windowMaskでウィンドウ内インデックスに変換し、hashOffsetでスライド分補正
i = int(d.hashPrev[i&windowMask]) - d.hashOffset
}
ちょっと長いので順序立ててみると、
- ハッシュテーブルで管理されていた、現在位置と同じ4バイトパターンが過去に現れた最新のindex(
prevHead)まで一旦遡ってマッチを図る - 見つけたマッチ長（length）、距離（offset）を記録
-
d.hashPrev(4バイトパターンで過去にマッチしたindexを格納したハッシュテーブル)を辿ってindexを32KB分遡るまではマッチ探索のループを繰り返す
の流れになります。
それぞれ、ステップごとに見てみます。
1では、まずloop処理の冒頭でマッチ検索をしているのが分かります。
// 実際のバイト比較でマッチ長を計算
n := matchLen(win[i:], win[pos:], minMatchLook)
matchLen()の中身は以下です。
遡っているindexを始点としたスライス&現在地indexを始点としたスライスを比較し、最大258バイト分までのマッチ長を返します。
matchLen()
// matchLenは、2つのスライスa, bの先頭から最大maxバイトまで一致する長さを返す。
// 両方のスライスは少なくともmaxバイト以上ある必要がある。
func matchLen(a, b []byte, max int) int {
a = a[:max] // aをmaxバイトに制限
b = b[:len(a)] // bもaと同じ長さに制限（安全対策）
for i, av := range a {
if b[i] != av { // 1バイトずつ比較し、異なる箇所でその位置を返す
return i
}
}
return max // 全て一致した場合はmaxを返す
}
2では、より長いマッチ長が見つかっていれば返り値として返すlength``offsetに格納します。
// より長いマッチが見つかった場合
if n > length {
length = n // 次回ループのマッチ長の比較対象にする & マッチ長として返り値になる
offset = pos - i // 現在indexからマッチした箇所への距離
}
3では、参照していた過去のマッチパターン（prevHead）より1つ前のマッチパターン(4バイト分)が出現したindexに遡ってi変数を更新し、次のloopでまたマッチ検索を行っています。そして、32KB分まで遡ったらば、マッチ検索loopは終了します。
// 32KBまで遡ったら終了
if i == minIndex {
break
}
// ハッシュチェーンで次の候補位置へ移動
// windowMaskでウィンドウ内インデックスに変換し、hashOffsetでスライド分補正
i = int(d.hashPrev[i&windowMask]) - d.hashOffset
少し長くなりましたがfindMatchを見ました。
findMatchの返り値は、compressor構造体のフィールドに格納されます。
d.length = newLength
d.offset = newOffset
まとめるとこのステップは、現在位置から32KB分遡れる範囲内で、
同じ4バイトパターン（ハッシュ値）を持つ過去の位置をハッシュテーブルで順に辿りながら、
最大258バイトまでの最長マッチ長とその距離（offset）を探索する部分と言えるでしょう。
3. LZ77:マッチ or リテラルのトークン生成処理
ここまでで、マッチ検索を行なって、length , offsetを得られたわけなので、それを表現するためのトークンを生成します。
記事の前半部分で概念的に示していた、以下のようなやつですね。
<len=3,dist=18>
該当コードは以下です。ここも結構端折ってます。
if d.length >= minMatchLength {
// マッチが見つかった場合は <長さ, 距離> のマッチトークンを出力
d.tokens = append(d.tokens, matchToken(uint32(d.length-baseMatchLength), uint32(d.offset-baseMatchOffset)))
// マッチした分だけ現在位置を進める
d.index += d.length
// ハッシュテーブル更新（省略）
// 4. 圧縮トークンをCanonical Huffman符号化ブロックとして出力
} else {
// マッチがなかった場合はリテラルトークンを出力
d.tokens = append(d.tokens, literalToken(uint32(d.window[d.index])))
// 4. 圧縮トークンをCanonical Huffman符号化ブロックとして出力
// 1バイトだけ現在位置を進める
d.index++
}
if d.length >= minMatchLength {としているので、マッチ長が4以上であれば、以降でマッチトークンとして出力をしているようです。
ここまでの流れとRFCを比較すると、微妙に違いがあることがわかります。
- マッチ検索はRFCに準拠して3バイト以上
- マッチトークンとしての出力は4バイト以上
定数定義を見てみると、 以下のようなコメントがありました。
// このパッケージのコンプレッサは、より大きな最小一致長を使うことで、
// 32ビット単位でのロードや比較による最適化を可能にしています。
baseMatchLength = 3 // RFCセクション3.2.5で定められた最小一致長
minMatchLength = 4 // このコンプレッサが実際に出力する最小一致
最適化のために、あえて出力部分だけはGo独自に決めた「より大きな最小一致長」を用いていそうです。
そしてlength >= 4だった場合のマッチトークン出力についてみてみます。トークン配列にappendしています。
// マッチが見つかった場合は <長さ, 距離> のマッチトークンを出力
d.tokens = append(d.tokens, matchToken(uint32(d.length-baseMatchLength), uint32(d.offset-baseMatchOffset)))
matchToken()は、以下です。まあ、あまり負荷ぼらずにいい感じにuint32(32bit)で表現していると把握しておきます。
type token uint32
// Convert a < xlength, xoffset > pair into a match token.
func matchToken(xlength uint32, xoffset uint32) token {
return token(matchType + xlength<<lengthShift + xoffset)
}
そして、マッチ->トークン出力が完了したわけなので、マッチした分に一旦用はありません。現在地indexをマッチした分進めます。
d.index += d.length
その後、ハフマン符号化に進みます。（ステップ４）
length >= 4に満たなかった場合は、リテラルトークンをtokens配列にappendします。
i = d.index
d.tokens = append(d.tokens, literalToken(uint32(d.window[d.index])))
literalToken()の中身は以下です。
// Convert a literal into a literal token.
func literalToken(literal uint32) token { return token(literalType + literal) }
つまり、d.window[i]として、現在地indexの1バイト分をそのままリテラルトークンに入れている感じでした。
その後、同様にハフマン符号化処理が差し込まれます（ステップ4）。
そして、1バイト処理したので、indexを1つ進めます。
d.index++
4. 圧縮トークンをCanonical Huffman符号化ブロックとして出力
最後に、マッチトークン、リテラルトークンの２種類に対してCanonical Huffman符号化を行います。
どちらも同じd.writeBlockメソッドを用いています。
// マッチトークン出力時
if len(d.tokens) == maxFlateBlockTokens {
// （d.indexはすでにマッチ長分進んでいる）
if d.err = d.writeBlock(d.tokens, d.index); d.err != nil {
return
}
d.tokens = d.tokens[:0]
}
// リテラルトークン出力時
if len(d.tokens) == maxFlateBlockTokens {
// （i+1はindexが1つ進むということ）
if d.err = d.writeBlock(d.tokens, i+1); d.err != nil {
return
}
d.tokens = d.tokens[:0]
}
トークンが16384個貯まったらブロック出力するしています。また、その後でトークン配列を空にするのも同じです。
writeBlockメソッドをみてみます。
func (d *compressor) writeBlock(tokens []token, index int) error {
if index > 0 {
var window []byte
if d.blockStart <= index {
window = d.window[d.blockStart:index]
}
d.blockStart = index
d.w.writeBlock(tokens, false, window)
return d.w.err
}
return nil
}
d.blockStartは、処理中windowのどこからどこまでを１ハフマンブロックとするか、その始点を管理するためのものです。ブロックとして出力された時、また、fillDeflate()でウィンドウがスライドした時などにもこの値は補正されます。
本元のロジックはd.w.writeBlock(tokens, false, window)にあります。
これは、compressor構造体のフィールドであるhuffmanBitWriter型のメソッドです。
type huffmanBitWriter struct {
writer io.Writer // ちなみにgzip.NewWriter()で入れたio.Writer型はここに入る
}
(w *huffmanBitWriter) writeBlockは以下のようになっています。効率化のための処理は省略しています。
func (w *huffmanBitWriter) writeBlock(tokens []token, eof bool, input []byte) {
// 終端マーカー追加
tokens = append(tokens, endBlockMarker)
// トークン頻度集計 -> ハフマン符号表を作成
numLiterals, numOffsets := w.indexTokens(tokens)
var literalEncoding = fixedLiteralEncoding
var offsetEncoding = fixedOffsetEncoding
// 各方式のサイズ計算
// 非圧縮（ストアド）方式のサイズと出力可能か
storedSize, storable := w.storedSize(input)
// 固定Huffman方式のサイズ
size := w.fixedSize(0)
// 動的Huffman方式のサイズ
dynamicSize, numCodegens := w.dynamicSize(w.literalEncoding, w.offsetEncoding, 0)
// 最適な方式選択
if dynamicSize < size {
size = dynamicSize
literalEncoding := w.literalEncoding
offsetEncoding := w.offsetEncoding
}
// 非圧縮（ストアド）ブロックが最小ならそれで出力
if storable && storedSize < size {
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
// Huffman符号化で出力（固定 or 動的）
if literalEncoding == fixedLiteralEncoding {
w.writeFixedHeader(eof)
} else {
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
}
w.writeTokens(tokens, literalEncoding.codes, offsetEncoding.codes)
}
あまり細かいところは追いませんが、以下のような順で処理しています。
- EOFコードの追加
- リテラル/長さ（length）、距離(distance)の2つの符号表を作成
- 各方式で圧縮した時のサイズを計算
- 最適な符号化方式を選択し、書き込み
それでは、見ていきます。
- EOFコードの追加
まずは、EOFコードを追加しています。前半の説明でも触れた通りです。
tokens = append(tokens, endBlockMarker)
- リテラル/長さ（length）、距離(distance)の2つの符号表を作成
numLiterals, numOffsets := w.indexTokens(tokens)
// indexTokensは、トークン列（tokens）を走査して、
// リテラル頻度（literalFreq）とオフセット頻度（offsetFreq）を更新し、
// それぞれのHuffman符号化（literalEncoding, offsetEncoding）を生成します。
// 戻り値はリテラルとオフセットの種類数です。
func (w *huffmanBitWriter) indexTokens(tokens []token) (numLiterals int, numOffsets int){...}
indexTokens()の内部処理
func (w *huffmanBitWriter) indexTokens(tokens []token) (numLiterals, numOffsets int) {
// 頻度配列を初期化
clear(w.literalFreq)
clear(w.offsetFreq)
// トークンを走査して頻度を集計
for _, t := range tokens {
if t < matchType {
// リテラルの場合
w.literalFreq[t.literal()]++
continue
}
// マッチの場合（長さ・距離）
length := t.length()
offset := t.offset()
w.literalFreq[lengthCodesStart+lengthCode(length)]++
w.offsetFreq[offsetCode(offset)]++
}
// 実際に使われているリテラル数を算出
numLiterals = len(w.literalFreq)
for numLiterals > 0 && w.literalFreq[numLiterals-1] == 0 {
numLiterals--
}
// 実際に使われているオフセット数を算出
numOffsets = len(w.offsetFreq)
for numOffsets > 0 && w.offsetFreq[numOffsets-1] == 0 {
numOffsets--
}
// Huffman符号化テーブル生成
w.literalEncoding.generate(w.literalFreq, 15)
w.offsetEncoding.generate(w.offsetFreq, 15)
return
}
トークンは、以下の２種類であり、マッチトークンはさらにlength , offsetの2種に分かれます。
- リテラルトークン
- マッチトークン
- length
- offset
前半で、
「リテラル/長さ（length）シンボルの符号表」と「距離(distance)シンボルの符号表」に分かれる
という仕様となっていることを触れました。
実装もその通りになっています。
// トークンを走査して頻度を集計
for _, t := range tokens {
if t < matchType {
// リテラルの場合
w.literalFreq[t.literal()]++
continue
}
// マッチの場合（長さ・距離）
length := t.length()
offset := t.offset()
w.literalFreq[lengthCodesStart+lengthCode(length)]++ // 長さの場合はリテラルの
w.offsetFreq[offsetCode(offset)]++
}
// ハフマン符号化
w.literalEncoding.generate(w.literalFreq, 15)
w.offsetEncoding.generate(w.offsetFreq, 15)
ハフマン符号表はhuffmanBitWriter構造体のフィールドであるhuffmanEncoder型にあります。
type huffmanEncoder struct {
codes []hcode // 符号表はここ
// 省略
}
// hcode is a huffman code with a bit code and bit length.
type hcode struct {
code, len uint16
}
見た感じ、literal用/offset用の２種類の符号表が用意されていそうです。
type huffmanBitWriter struct {
// 省略
literalEncoding *huffmanEncoder
offsetEncoding *huffmanEncoder
// これは符号表情報のハフマン符号表
codegenEncoding *huffmanEncoder
}
- 各方式で圧縮した時のサイズを計算
非圧縮、固定ハフマン、動的ハフマンの３方式で圧縮後サイズを計算します。
// 非圧縮（ストアド）方式のサイズと出力可能か
storedSize, storable := w.storedSize(input)
// 固定Huffman方式のサイズ
size := w.fixedSize(0)
// 動的Huffman方式のサイズ
dynamicSize, numCodegens := w.dynamicSize(w.literalEncoding, w.offsetEncoding, 0)
動的ハフマン符号化による、リテラル/長さ符号表 & 距離符号表自体もハフマン符号化して圧縮している様子も見えます。
// 動的Huffman用の符号表生成
w.generateCodegen(numLiterals, numOffsets, w.literalEncoding, w.offsetEncoding)
// 符号表自体のHuffman符号化
w.codegenEncoding.generate(w.codegenFreq[:], 7)
- 最適な符号化方式を選択し、書き込み
sizeは、w.fixedSize(0)、つまり固定ハフマン符号化をした時の圧縮後サイズです。これよりも、dynamicSize、つまり動的ハフマン符号化による圧縮後サイズの方が小さければ、動的ハフマン符号表を含む構造体でliteralEncoding,offsetEncodingを上書きします。
var literalEncoding = fixedLiteralEncoding
var offsetEncoding = fixedOffsetEncoding
// 最適な方式選択
if dynamicSize < size {
size = dynamicSize // 動的ハフマンのサイズで上書き
literalEncoding := w.literalEncoding
offsetEncoding := w.offsetEncoding
}
ちなみに、固定ハフマン符号表は以下で生成されていました。
var fixedLiteralEncoding *huffmanEncoder = generateFixedLiteralEncoding()
var fixedOffsetEncoding *huffmanEncoder = generateFixedOffsetEncoding()
その後に、非圧縮のサイズと比較します。非圧縮の方が小さければ、その場でヘッダー、未処理データをgzip.NewWriter(w io.Writer)で入れたio.Writer型に書き込みます。
// 非圧縮の方が小さければ非圧縮で書き出す
if storable && storedSize < size {
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
非圧縮では非効率であれば、固定 or 動的でヘッダーを書き込みます。先の動的or固定の比較でliteralEncodingの値は決まっています。
if literalEncoding == fixedLiteralEncoding {
w.writeFixedHeader(eof)
} else {
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
}
そして最後に、ハフマン符号表を用いてビットとして書き出します。
w.writeTokens(tokens, literalEncoding.codes, offsetEncoding.codes)
ヘッダーの書き込み、圧縮データの書き込みと、いずれもgzip.NewWriter(w io.Writer)で入れたio.Writer型に書き込みます。
さて、これでやっと圧縮完了です（コードを見てわかるように、もしかすると非圧縮の場合もありますね）。
最適化のためにGo独自の実装をしている点もあれば、RFC準拠の部分もありました。
圧縮があれば解凍もありますが、ここまでですでにお腹いっぱいなのでここでは触れないことにします。
実際に圧縮を試してみる
圧縮前、後でバイト長はどのくらい変わっているのかを見てみます。
func main() {
data := "She said she will see what she said"
// 圧縮
var buf strings.Builder
gzipWriter := gzip.NewWriter(&buf)
gzipWriter.Write([]byte(data))
gzipWriter.Close()
compressed := buf.String()
fmt.Printf("元のサイズ: %d bytes\n", len(data))
fmt.Printf("圧縮後サイズ: %d bytes\n", len(compressed))
}
そしてさらに、固定ハフマン/動的ハフマン/非圧縮のどれを用いたのかを見るために、以下のログを仕込みます。
ログ仕込み
if storable && storedSize < size {
fmt.Println("Using stored block encoding") // 非圧縮
w.writeStoredHeader(len(input), eof)
w.writeBytes(input)
return
}
if literalEncoding == fixedLiteralEncoding {
fmt.Println("Using fixed Huffman encoding") // 固定
w.writeFixedHeader(eof)
} else {
fmt.Println("Using dynamic Huffman encoding") // 動的
w.writeDynamicHeader(numLiterals, numOffsets, numCodegens, eof)
}
冒頭に示した例だと、以下のようになりました。
固定ハフマンが使われたようです。この短い文章だと、動的ハフマンで符号表の分オーバーヘッドとなるのでしょう。これは圧縮しない方が良さそう（非圧縮にはならないのか）。
Using fixed Huffman encoding
元のサイズ: 35 bytes
圧縮後サイズ: 54 bytes
では、dataを以下のようにしてみます。マッチが頻発し、いい感じに圧縮できるか....。
// 100回
data := strings.Repeat("She said she will see what she said", 100)
結果は以下になりました。
Using dynamic Huffman encoding
元のサイズ: 3500 bytes
圧縮後サイズ: 80 bytes
動的ハフマンが使われたみたいですね！繰り返しがめちゃくちゃに多い分には、超効果的だったようです。
仕組みを知れれば、こういう結果にも納得がいきますね。
おわりに
どうしても圧縮という言葉に引っかかってしまったことから、このテーマを調べてみました。
まずは、RFCや、記事、Youtube等で概念的に理解することから始めました。その後でコードを読み、概念的な理解をコードに当てはめていくのが面白かったです。
需要はあんまりないかもしれませんが、個人的に面白いので定期的にやっていきたいです。
参考
Discussion