Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 11311] ファイルの概要

このコミットは、Go言語の標準ライブラリ compress/flate パッケージにおけるDEFLATE圧縮アルゴリズムの実装に関する修正です。具体的には、ハッシュテーブルのインデックス計算における符号の誤りを修正し、これにより圧縮率が3-4%向上しました。

コミット

commit 4d3b9d97573082152894847f5040876f8febc70f
Author: Ivan Krasin <krasin@golang.org>
Date:   Sat Jan 21 12:18:15 2012 -0500

    compress/flate: fix a typo, improve compression rate by 3-4%.
    
    R=rsc
    CC=golang-dev
    https://golang.org/cl/5556077

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/4d3b9d97573082152894847f5040876f8febc70f

元コミット内容

compress/flate: fix a typo, improve compression rate by 3-4%.

R=rsc
CC=golang-dev
https://golang.org/cl/5556077

変更の背景

この変更は、Go言語の compress/flate パッケージ、特にDEFLATE圧縮アルゴリズムの実装において、圧縮効率を改善するために行われました。DEFLATEは、Zlib、gzip、PNGなどの多くの一般的な圧縮形式の基盤となるアルゴリズムです。効率的な圧縮は、データ転送量の削減やストレージ容量の節約に直結するため、その性能向上は非常に重要です。

コミットメッセージにある「typo（タイプミス）」は、圧縮処理における内部的なハッシュテーブルのインデックス計算に誤りがあったことを示唆しています。この誤りが原因で、アルゴリズムが最適な圧縮パターンを見つけられず、結果として圧縮率が低下していたと考えられます。この修正により、アルゴリズムがより効果的に重複するデータパターンを検出し、より短い符号で表現できるようになり、圧縮率が向上しました。

前提知識の解説

DEFLATE圧縮アルゴリズム

DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせた可逆データ圧縮アルゴリズムです。

  1. LZ77 (Lempel-Ziv 1977):

    • 入力データストリーム内で繰り返されるバイトシーケンス（文字列）を検出し、それらを「長さ-距離ペア」に置き換えることで圧縮します。
    • 「長さ」は繰り返されるシーケンスの長さ、「距離」は以前に出現した同じシーケンスの開始位置までの距離（後方参照）を示します。
    • このアルゴリズムは、スライディングウィンドウと呼ばれる固定サイズのバッファを使用します。このウィンドウは、現在処理中のデータと、以前に処理されたデータの一部を保持します。
    • windowSize はこのスライディングウィンドウのサイズを指し、LZ77アルゴリズムが後方参照できる最大距離を決定します。

  2. ハフマン符号化:

    • LZ77によって生成されたリテラルバイト（圧縮されなかったデータ）と長さ-距離ペアを、可変長のビット列に符号化します。
    • 出現頻度の高いシンボルには短いビット列を、出現頻度の低いシンボルには長いビット列を割り当てることで、全体のデータサイズを削減します。

ハッシュテーブルとDEFLATEにおけるその役割

DEFLATEアルゴリズムの実装では、LZ77の後方参照を効率的に行うためにハッシュテーブルがよく使用されます。

  • 入力ストリームから一定の長さ（例えば3バイト）のシーケンスを読み込み、そのシーケンスのハッシュ値を計算します。
  • このハッシュ値をキーとしてハッシュテーブルに格納し、そのシーケンスがスライディングウィンドウ内のどこに出現したかの情報（オフセットやインデックス）を値として保持します。
  • 新しいシーケンスのハッシュ値を計算した際、ハッシュテーブルを検索することで、以前に出現した同じシーケンスを素早く見つけることができます。
  • hashHead や hashPrev といった配列は、このハッシュテーブルの実装に関連するものです。
    • hashHead[h] は、ハッシュ値 h を持つ最新のバイトシーケンスがスライディングウィンドウ内のどこにあるかを示すインデックスを格納します。
    • hashPrev[i] は、インデックス i の位置にあるバイトシーケンスと同じハッシュ値を持つ、その直前のシーケンスのインデックスを格納します。これにより、同じハッシュ値を持つ複数のシーケンスをリンクリストのように辿ることができます。

圧縮率の評価

圧縮率は、元のデータサイズと圧縮後のデータサイズの比率で評価されます。圧縮率が高いほど、データサイズが小さくなり、効率が良いとされます。テストケースで示されている [...]int の配列は、異なる圧縮レベルや設定での圧縮後のデータサイズ（バイト数）を示している可能性が高いです。数値が小さくなっていることは、圧縮率が向上したことを意味します。

技術的詳細

このコミットの核心は、src/pkg/compress/flate/deflate.go 内の fillDeflate 関数におけるハッシュテーブルのインデックス計算の修正です。

元のコードでは、d.hashPrev 配列から取得した値 h を使用して、以前の出現位置を計算する際に v := -h - windowSize という式が使われていました。これは、h がスライディングウィンドウ内のオフセット（インデックス）を表す場合、その値が負になるか、または windowSize との組み合わせで意図しない結果を生み出す可能性がありました。

修正後のコードでは、v := h - windowSize となっています。 ここで h は d.hashPrev から取得される値であり、これは通常、スライディングウィンドウ内の過去のデータブロックのインデックス（オフセット）を示します。DEFLATEアルゴリズムでは、現在の位置から過去のデータブロックへの「距離」を計算する必要があります。

  • h が過去のデータブロックの絶対インデックスであると仮定します。
  • windowSize はスライディングウィンドウのサイズです。
  • LZ77の距離は、現在の位置から過去のマッチまでの距離です。
  • h - windowSize という計算は、おそらくスライディングウィンドウの「基点」からの相対的な位置、またはウィンドウの境界を考慮したインデックスの調整を行っていると考えられます。

この変更が「typo」であると明記されていることから、元の -h - windowSize は論理的な誤りであり、ハッシュテーブルが正しく過去のマッチを指し示せていなかったことを意味します。符号の誤りにより、アルゴリズムが有効なマッチを見逃したり、誤ったマッチを選択したりしていたため、冗長なデータが圧縮されずに残ってしまい、結果として圧縮率が低下していました。

h - windowSize に修正することで、ハッシュテーブルがスライディングウィンドウ内の正しい位置を指すようになり、DEFLATEアルゴリズムがより多くの、より長い重複パターンを正確に検出できるようになりました。これにより、より効率的な長さ-距離ペアが生成され、最終的な圧縮データサイズが削減され、圧縮率が3-4%向上したという結果につながっています。

deflate_test.go の変更は、この圧縮率の向上を検証するためのものです。Mark.Twain-Tom.Sawyer.txt というテストデータに対する圧縮後の期待値が、修正前よりも小さくなっていることが確認できます。これは、コードの変更が実際に圧縮性能に良い影響を与えたことを示しています。

コアとなるコードの変更箇所

src/pkg/compress/flate/deflate.go

--- a/src/pkg/compress/flate/deflate.go
+++ b/src/pkg/compress/flate/deflate.go
@@ -112,7 +112,7 @@ func (d *compressor) fillDeflate(b []byte) int {
 		d.hashHead[i] = v
 	}
 	for i, h := range d.hashPrev {
-		v := -h - windowSize
+		v := h - windowSize
 		if v < -1 {
 			v = -1
 		}

src/pkg/compress/flate/deflate_test.go

--- a/src/pkg/compress/flate/deflate_test.go
+++ b/src/pkg/compress/flate/deflate_test.go
@@ -291,7 +291,7 @@ var deflateInflateStringTests = []deflateInflateStringTest{
 	{
 		"../testdata/Mark.Twain-Tom.Sawyer.txt",
 		"Mark.Twain-Tom.Sawyer",
-		[...]int{416188, 191483, 185232, 179560, 175233, 171263, 169908, 169758, 169712, 169712},\n+\t\t[...]int{407330, 187598, 180361, 172974, 169160, 163476, 160936, 160506, 160295, 160295},\n 	},\n }

コアとなるコードの解説

src/pkg/compress/flate/deflate.go の変更は、compressor 構造体の fillDeflate メソッド内で行われています。このメソッドは、DEFLATE圧縮の主要なロジックの一部を担っており、特にLZ77の後方参照マッチングに関連する処理が含まれています。

変更された行は以下の通りです。

// 変更前
v := -h - windowSize
// 変更後
v := h - windowSize

このコードスニペットは、d.hashPrev 配列をイテレートし、各要素 h を使用して v という値を計算しています。d.hashPrev は、ハッシュテーブルのチェイン（同じハッシュ値を持つ過去の出現位置のリスト）を構築するために使用される配列です。h は、現在の位置から見て過去のどこかに存在する、以前に出現したバイトシーケンスのインデックス（オフセット）を示します。

windowSize は、DEFLATEアルゴリズムのスライディングウィンドウのサイズを表します。このウィンドウは、LZ77アルゴリズムが後方参照できる最大距離を定義します。

元の v := -h - windowSize という式は、h の値が正のインデックスであると仮定すると、v を非常に大きな負の値にしてしまう可能性がありました。これは、ハッシュテーブルのチェインを辿る際に、有効な過去のマッチを正しく参照できない原因となります。例えば、h がウィンドウ内の有効なインデックスであるにもかかわらず、この計算によって v が無効な値（例えば -1 未満）になってしまうと、そのマッチは無視されるか、誤った処理が行われることになります。

修正後の v := h - windowSize は、h から windowSize を減算することで、おそらくスライディングウィンドウの「基点」からの相対的なオフセットを計算しているか、またはウィンドウの境界を考慮したインデックスの調整を行っていると考えられます。この修正により、v の値が正しく計算され、if v < -1 { v = -1 } という条件分岐と合わせて、ハッシュテーブルのチェインが正しく機能するようになります。

結果として、DEFLATEアルゴリズムはより多くの、そしてより長い重複するバイトシーケンスを正確に検出できるようになり、それらを長さ-距離ペアとして効率的に符号化できるようになります。これが、圧縮率が3-4%向上した主な理由です。

src/pkg/compress/flate/deflate_test.go の変更は、この機能改善を検証するためのテストデータの更新です。deflateInflateStringTests 配列内の Mark.Twain-Tom.Sawyer.txt に対する期待される圧縮後のサイズが、以前の大きな値からより小さな値に更新されています。これは、コードの修正が実際に圧縮性能を向上させたことを示す具体的な証拠です。

関連リンク

参考にした情報源リンク