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

このコミットは、Go言語の compress/flate パッケージにおけるDEFLATE圧縮アルゴリズムの「遅延マッチング (lazy matching)」の動作を改善することを目的としています。具体的には、deflate.go 内の定数の使用方法を math.MaxInt32 から skipNever という新しい定数に置き換えることで、コードの可読性と保守性を向上させています。また、deflate_test.go には、より大規模なテキストデータ (Mark.Twain-Tom.Sawyer.txt) を用いた新しいテストケースが追加され、圧縮レベルごとの出力サイズ制限を検証する機能が導入されています。これにより、遅延マッチングの挙動が正しく機能していることを確認し、圧縮効率の改善を目指しています。

コミット

commit c4b16a3864102b45cc50188cee416133c165a460
Author: Ivan Krasin <krasin@golang.org>
Date:   Fri Jan 20 23:35:18 2012 -0500

    compress/flate: make lazy matching work.
    
    R=rsc, imkrasin
    CC=golang-dev
    https://golang.org/cl/5554066

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

https://github.com/golang/go/commit/c4b16a3864102b45cc50188cee416133c165a460

元コミット内容

compress/flate: make lazy matching work.

変更の背景

DEFLATE圧縮アルゴリズムにおいて、圧縮効率を向上させるための重要な最適化手法の一つに「遅延マッチング (lazy matching)」があります。これは、現在の位置で最適なマッチ（繰り返しパターン）が見つかったとしても、すぐにそのマッチを出力するのではなく、次のバイトも見て、より長いマッチが見つかる可能性を探る戦略です。

このコミットの背景には、Go言語の compress/flate パッケージにおけるDEFLATE実装で、この遅延マッチングが意図した通りに機能していなかった、あるいはその挙動が不明瞭であったという問題があったと考えられます。math.MaxInt32 のようなマジックナンバーがコードの複数の箇所で使用されており、これが遅延マッチングのロジックを理解しにくく、また潜在的なバグの原因となっていた可能性があります。

この変更は、コードの可読性と保守性を高めつつ、DEFLATE圧縮の重要な最適化である遅延マッチングが正しく、かつ効率的に動作するように修正することを目的としています。特に、大規模なデータセット（例: Mark.Twain-Tom.Sawyer.txt のような書籍データ）に対する圧縮性能の検証は、この最適化の重要性を示唆しています。

前提知識の解説

DEFLATE圧縮アルゴリズム

DEFLATEは、LZ77アルゴリズムとハフマン符号化を組み合わせた可逆データ圧縮アルゴリズムです。ZIP、gzip、PNGなどのファイル形式で広く使用されています。

LZ77 (Lempel-Ziv 77): データの繰り返しパターンを見つけて、そのパターンを「長さ (length)」と「距離 (distance)」のペアで置き換えることで圧縮します。例えば、「ABCABCABC」という文字列は、「ABC」というパターンが2回繰り返されていると表現できます。
ハフマン符号化 (Huffman Coding): LZ77によって生成されたデータ（リテラルバイト、長さ、距離のペア）を、出現頻度の高いものには短いビット列を、低いものには長いビット列を割り当てることでさらに圧縮します。

遅延マッチング (Lazy Matching)

DEFLATE圧縮における遅延マッチングは、LZ77のステップで最適なマッチを見つけるための戦略です。

貪欲マッチング (Greedy Matching): 現在の入力位置から最も長く、かつ最も近い（距離が短い）マッチを見つけ、それを出力します。これは単純で高速ですが、局所的な最適解に囚われ、全体として最適な圧縮率が得られない場合があります。例: ABCABCDEFABCABC 現在の位置が最初の A の場合、ABC (長さ3) が見つかります。貪欲マッチングではこれを出力します。しかし、もし後続に ABCABC (長さ6) のようなより長いマッチが存在する場合、貪欲に短いマッチを選択してしまうと、全体としての圧縮効率が低下します。
遅延マッチング (Lazy Matching): 現在の入力位置で最適なマッチが見つかったとしても、すぐにそのマッチを出力せず、次の入力バイトも考慮して、より長いマッチが見つかる可能性を探ります。
- 現在の位置でマッチ M1 が見つかったとします。
- 次の位置でマッチ M2 を探します。
- もし M2 が M1 よりも大幅に長い場合、M1 を破棄し、リテラルバイト（マッチしない単一のバイト）を出力してから M2 を採用する方が、全体として圧縮率が向上する可能性があります。
- この「より長いマッチを探す」プロセスには、lazy パラメータや good_match パラメータといった閾値が用いられます。これらの閾値は、圧縮レベルによって調整され、圧縮速度と圧縮率のトレードオフを決定します。

遅延マッチングは、特に繰り返しパターンが連続して出現するようなデータにおいて、より高い圧縮率を達成するために重要です。しかし、次のバイトを先読みして追加の計算を行うため、圧縮速度は低下する傾向があります。

`math.MaxInt32` と定数 `skipNever`

math.MaxInt32 は、Go言語の math パッケージで定義されている int32 型の最大値です。このコミットでは、この具体的な数値リテラルを skipNever という名前付き定数に置き換えています。これは、コードの意図を明確にするための一般的なプログラミングプラクティスです。skipNever という名前は、特定の条件で「スキップしない」というロジックを表現しており、math.MaxInt32 がその目的で使用されていることを示唆しています。

技術的詳細

このコミットの主要な技術的変更は、compress/flate/deflate.go 内のDEFLATE圧縮器の内部ロジック、特に遅延マッチングに関連する部分にあります。

skipNever 定数の導入: const ( ... skipNever = math.MaxInt32 ) この変更により、math.MaxInt32 という具体的な数値が skipNever という意味のある定数に置き換えられました。これにより、コードを読んだ際に、この値が「決してスキップしない」という特定の意味を持つことが明確になります。これは、コードの可読性と保守性を大幅に向上させます。
d.blockStart の初期化: 変更前: d.blockStart = math.MaxInt32 変更後: d.blockStart = skipNever blockStart は、圧縮ブロックの開始位置を管理するフィールドと考えられます。math.MaxInt32 で初期化されていたのは、おそらく特定の条件（例えば、ブロックの開始位置がまだ設定されていない、または無効な状態）を示すためでした。skipNever を使用することで、この「無効な状態」または「特別な状態」の意図がより明確になります。
遅延マッチングの条件式の変更: 複数の if 文の条件式で、d.fastSkipHashing != 0 という比較が d.fastSkipHashing != skipNever に変更されています。
- d.fastSkipHashing は、おそらく高速スキップハッシュの閾値、または遅延マッチングの挙動を制御するフラグのようなものと考えられます。
- 元の != 0 という条件は、d.fastSkipHashing がゼロでない場合に特定のロジックを実行することを示していました。
- skipNever を導入し、!= skipNever とすることで、d.fastSkipHashing が skipNever (つまり math.MaxInt32) でない場合にロジックが実行されることを明示しています。これは、d.fastSkipHashing が skipNever の値を持つ場合に、遅延マッチングの特定の側面（例えば、追加の先読みやマッチの評価）を無効にする、あるいは異なる挙動をさせるための変更であると推測されます。
- 特に、d.fastSkipHashing == 0 の条件が d.fastSkipHashing == skipNever に変更されている箇所もあり、これは 0 が「遅延マッチングを無効にする」または「特別なモード」を意味していたものが、skipNever がその役割を担うようになったことを示しています。

これらの変更は、DEFLATE圧縮器がより洗練された遅延マッチング戦略を適用できるようにするためのものです。fastSkipHashing の値が skipNever でない場合に、現在のマッチの長さ (d.length) と以前のマッチの長さ (prevLength) を比較し、より良いマッチを探すための findMatch 関数を呼び出すロジックが調整されています。これにより、圧縮器は局所的な最適解に囚われず、より長い繰り返しパターンを見つけて圧縮率を向上させることが可能になります。

テストの変更点

deflate_test.go では、圧縮レベルごとの圧縮結果のサイズを検証するための機能が追加されています。

testToFromWithLevelAndLimit 関数が新しく導入され、圧縮後のバッファサイズが指定された limit を超えないことを検証できるようになりました。
testToFrom 関数は、この新しい testToFromWithLevelAndLimit を呼び出すように変更され、デフォルトで limit を -1 (無制限) に設定しています。
deflateInflateStringTest 構造体が定義され、テスト対象のファイル名、ラベル、そして各圧縮レベル (0 から 9) における期待される圧縮サイズの上限 (limit) を配列で持つようになりました。
TestDeflateInflateString 関数は、この新しい構造体 deflateInflateStringTests をループ処理し、../testdata/e.txt と ../testdata/Mark.Twain-Tom.Sawyer.txt という2つのテストファイルに対して、各圧縮レベルでの圧縮と解凍のテストを実行し、同時に圧縮サイズが期待値を超えないことを検証します。

特に注目すべきは、Mark.Twain-Tom.Sawyer.txt という非常に大きなテキストファイル（8858行）がテストデータとして追加されたことです。これは、実際のテキストデータに対する圧縮性能、特に遅延マッチングのような最適化が大規模データでどのように機能するかを検証するために重要です。各圧縮レベルで異なる limit 値が設定されていることから、圧縮レベルが上がるにつれて圧縮率が向上し、出力サイズが減少することが期待されていることがわかります。

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

`src/pkg/compress/flate/deflate.go`

--- a/src/pkg/compress/flate/deflate.go
+++ b/src/pkg/compress/flate/deflate.go
@@ -31,6 +31,8 @@ const (
 	hashSize            = 1 << hashBits
 	hashMask            = (1 << hashBits) - 1
 	hashShift           = (hashBits + minMatchLength - 1) / minMatchLength
+
+	skipNever = math.MaxInt32
 )
 
 type compressionLevel struct {
@@ -45,12 +47,12 @@ var levels = []compressionLevel{
 	{3, 0, 32, 32, 6},
 	// Levels 4-9 use increasingly more lazy matching
 	// and increasingly stringent conditions for "good enough".
-	{4, 4, 16, 16, math.MaxInt32},
-	{8, 16, 32, 32, math.MaxInt32},
-	{8, 16, 128, 128, math.MaxInt32},
-	{8, 32, 128, 256, math.MaxInt32},
-	{32, 128, 258, 1024, math.MaxInt32},
-	{32, 258, 258, 4096, math.MaxInt32},
+	{4, 4, 16, 16, skipNever},
+	{8, 16, 32, 32, skipNever},
+	{8, 16, 128, 128, skipNever},
+	{8, 32, 128, 256, skipNever},
+	{32, 128, 258, 1024, skipNever},
+	{32, 258, 258, 4096, skipNever},
 }
 
 type compressor struct {
@@ -100,7 +102,7 @@ func (d *compressor) fillDeflate(b []byte) int {
 		if d.blockStart >= windowSize {
 			d.blockStart -= windowSize
 		} else {
-			d.blockStart = math.MaxInt32
+			d.blockStart = skipNever
 		}
 		for i, h := range d.hashHead {
 			v := h - windowSize
@@ -273,18 +275,18 @@ Loop:
 		}
 
 		if d.chainHead >= minIndex &&
-			(d.fastSkipHashing != 0 && lookahead > minMatchLength-1 ||
-				d.fastSkipHashing == 0 && lookahead > prevLength && prevLength < d.lazy) {
+			(d.fastSkipHashing != skipNever && lookahead > minMatchLength-1 ||
+				d.fastSkipHashing == skipNever && lookahead > prevLength && prevLength < d.lazy) {
 			if newLength, newOffset, ok := d.findMatch(d.index, d.chainHead, minMatchLength-1, lookahead); ok {
 				d.length = newLength
 				d.offset = newOffset
 			}
 		}
-		if d.fastSkipHashing != 0 && d.length >= minMatchLength ||
-			d.fastSkipHashing == 0 && prevLength >= minMatchLength && d.length <= prevLength {
+		if d.fastSkipHashing != skipNever && d.length >= minMatchLength ||
+			d.fastSkipHashing == skipNever && prevLength >= minMatchLength && d.length <= prevLength {
 			// There was a match at the previous step, and the current match is
 			// not better. Output the previous match.
-			if d.fastSkipHashing != 0 {
+			if d.fastSkipHashing != skipNever {
 				d.tokens[d.ti] = matchToken(uint32(d.length-minMatchLength), uint32(d.offset-minOffsetSize))
 			} else {
 				d.tokens[d.ti] = matchToken(uint32(prevLength-minMatchLength), uint32(prevOffset-minOffsetSize))
@@ -296,10 +298,10 @@ Loop:
 			// table.
 			if d.length <= d.fastSkipHashing {
 				var newIndex int
-				if d.fastSkipHashing != 0 {
+				if d.fastSkipHashing != skipNever {
 					newIndex = d.index + d.length
 				} else {
-					newIndex = prevLength - 1
+					newIndex = d.index + prevLength - 1
 				}
 				for d.index++; d.index < newIndex; d.index++ {
 					if d.index < d.maxInsertIndex {
@@ -311,7 +313,7 @@ Loop:
 					d.hashHead[d.hash] = d.index
 					}
 				}
-				if d.fastSkipHashing == 0 {
+				if d.fastSkipHashing == skipNever {
 					d.byteAvailable = false
 					d.length = minMatchLength - 1
 				}
@@ -331,9 +333,9 @@ Loop:
 				d.ti = 0
 			}
 		} else {
-			if d.fastSkipHashing != 0 || d.byteAvailable {
+			if d.fastSkipHashing != skipNever || d.byteAvailable {
 				i := d.index - 1
-				if d.fastSkipHashing != 0 {
+				if d.fastSkipHashing != skipNever {
 					i = d.index
 				}
 				d.tokens[d.ti] = literalToken(uint32(d.window[i]))
@@ -346,7 +348,7 @@ Loop:
 				}
 			}
 			d.index++
-			if d.fastSkipHashing == 0 {
+			if d.fastSkipHashing == skipNever {
 				d.byteAvailable = true
 			}
 		}

`src/pkg/compress/flate/deflate_test.go`

--- a/src/pkg/compress/flate/deflate_test.go
+++ b/src/pkg/compress/flate/deflate_test.go
@@ -225,10 +225,17 @@ func testSync(t *testing.T, level int, input []byte, name string) {
 }
 
 func testToFromWithLevel(t *testing.T, level int, input []byte, name string) error {
+	return testToFromWithLevelAndLimit(t, level, input, name, -1)
+}
+
+func testToFromWithLevelAndLimit(t *testing.T, level int, input []byte, name string, limit int) error {
 	buffer := bytes.NewBuffer(nil)
 	w := NewWriter(buffer, level)
 	w.Write(input)
 	w.Close()
+	if limit > 0 && buffer.Len() > limit {
+		t.Errorf("level: %d, len(compress(data)) = %d > limit = %d", level, buffer.Len(), limit)
+	}
 	r := NewReader(buffer)
 	out, err := ioutil.ReadAll(r)
 	if err != nil {
@@ -244,12 +251,16 @@ func testToFromWithLevel(t *testing.T, level int, input []byte, name string) err
 	return nil
 }
 
-func testToFrom(t *testing.T, input []byte, name string) {
+func testToFromWithLimit(t *testing.T, input []byte, name string, limit [10]int) {
 	for i := 0; i < 10; i++ {
-		testToFromWithLevel(t, i, input, name)
+		testToFromWithLevelAndLimit(t, i, input, name, limit[i])
 	}
 }
 
+func testToFrom(t *testing.T, input []byte, name string) {
+	testToFromWithLimit(t, input, name, [10]int{})
+}
+
 func TestDeflateInflate(t *testing.T) {
 	for i, h := range deflateInflateTests {
 		testToFrom(t, h.in, fmt.Sprintf("#%d", i))
@@ -265,12 +280,33 @@ func TestReverseBits(t *testing.T) {
 	}
 }
 
+type deflateInflateStringTest struct {
+	filename string
+	label    string
+	limit    [10]int
+}
+
+var deflateInflateStringTests = []deflateInflateStringTest{
+	{
+		"../testdata/e.txt",
+		"2.718281828...",
+		[...]int{10013, 5065, 5096, 5115, 5093, 5079, 5079, 5079, 5079, 5079},
+	},
+	{
+		"../testdata/Mark.Twain-Tom.Sawyer.txt",
+		"Mark.Twain-Tom.Sawyer",
+		[...]int{416188, 191483, 185232, 179560, 175233, 171263, 169908, 169758, 169712, 169712},
+	},
+}
+
 func TestDeflateInflateString(t *testing.T) {
-	gold, err := ioutil.ReadFile("../testdata/e.txt")
-	if err != nil {
-		t.Error(err)
+	for _, test := range deflateInflateStringTests {
+		gold, err := ioutil.ReadFile(test.filename)
+		if err != nil {
+			t.Error(err)
+		}
+		testToFromWithLimit(t, gold, test.label, test.limit)
 	}
-	testToFromWithLevel(t, 1, gold, "2.718281828...")
 }
 
 func TestReaderDict(t *testing.T) {

skipNever 定数: math.MaxInt32 を skipNever という定数に置き換えることで、コードの意図が明確になりました。これは、特定の条件で「スキップしない」というロジックを表現するためのものです。
compressionLevel 構造体: levels 配列内の compressionLevel 構造体の最後のフィールドが math.MaxInt32 から skipNever に変更されています。このフィールドは、おそらく遅延マッチングの挙動を制御する閾値（例えば、これ以上の長さのマッチが見つかったら、現在のマッチをスキップして新しいマッチを採用する、といったロジック）として機能していると考えられます。skipNever は、この閾値が事実上無制限であることを示し、常に最も長いマッチを探すように促す役割を果たす可能性があります。
fillDeflate メソッド内の条件式:
- d.blockStart = math.MaxInt32 が d.blockStart = skipNever に変更されました。これは、圧縮ブロックの開始位置をリセットする際に、特別な「スキップしない」状態を示すために skipNever を使用していることを示唆しています。
- d.fastSkipHashing != 0 および d.fastSkipHashing == 0 の比較が、それぞれ d.fastSkipHashing != skipNever および d.fastSkipHashing == skipNever に変更されました。これは、d.fastSkipHashing が遅延マッチングの挙動を制御する重要なパラメータであり、その値が skipNever であるかどうかに応じて、異なるマッチング戦略（例えば、より積極的なマッチング探索か、あるいはリテラルバイトの出力）が適用されることを意味します。この変更により、遅延マッチングのロジックがより正確に、かつ意図通りに機能するようになります。

これらの変更は、DEFLATE圧縮器がよりインテリジェントにマッチング戦略を決定し、特に高い圧縮レベルにおいて、より効率的な圧縮結果を生み出すことを可能にします。

`deflate_test.go` の変更点

testToFromWithLevelAndLimit 関数: この新しい関数は、圧縮後のデータサイズが特定の制限 (limit) を超えないことを検証するために導入されました。これは、圧縮アルゴリズムの効率性を数値的に評価し、特定の圧縮レベルで期待される圧縮率が達成されていることを確認するために非常に重要です。
deflateInflateStringTest 構造体と deflateInflateStringTests 配列: この構造体は、テスト対象のファイル名、テストのラベル、そして各圧縮レベルにおける圧縮サイズの期待値（上限）を保持します。これにより、複数のテストケースを簡単に定義し、各圧縮レベルでの性能を網羅的にテストできるようになりました。
TestDeflateInflateString の更新: このテスト関数は、Mark.Twain-Tom.Sawyer.txt のような大規模なテキストファイルを含む、複数のテストデータに対して圧縮・解凍処理を実行し、圧縮後のサイズが事前に定義された上限内に収まっているかを検証します。これにより、遅延マッチングの改善が実際のデータに対して効果を発揮していることを確認できます。

これらのテストの追加は、圧縮アルゴリズムの変更が意図した通りに機能し、特に大規模なデータセットや異なる圧縮レベルでの性能特性が期待通りであることを保証するためのものです。

参考にした情報源リンク

Go言語の公式リポジトリ (GitHub): https://github.com/golang/go
Go言語のコードレビューシステム (Gerrit): https://go-review.googlesource.com/ (コミットメッセージに記載されている https://golang.org/cl/5554066 は、このGerritインスタンスへのリンクです)
Wikipedia: DEFLATE, LZ77, Huffman Coding (上記「関連リンク」に記載)
「トム・ソーヤーの冒険」プロジェクト・グーテンベルク版: https://www.gutenberg.org/ebooks/74 (テストデータとして使用されているファイルの出典)

comemo