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

このコミットは、Go言語の実験的なロケール照合（collation）パッケージ exp/locale/collate における、収縮（contraction）トライ（trie）の実装調整に関するものです。特に、ミャンマー語（ビルマ語）のような、非常に大きな収縮テーブルを持つ言語のサポートを改善するために行われました。主な変更点は、トライの次の状態へのオフセット計算方法の変更と、関連する定数の導入です。

コミット

commit adc19ac5e3fc4914df4b09400686c964e379532b
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Fri Jul 13 11:38:00 2012 +0200

    exp/locale/collate: adjusted contraction trie to support Myanmar (Burmese),
    which has a rather large contraction table. The value of the next state
    offset now starts after the current block, instead of before.  This is
    slightly less efficient (on extra addition per state change), but gives
    some extra range for the offsets.
    Also introduced constants for final (0) and noIndex (0xFF).
    tables.go is updated in a separate CL.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6346092

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

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

元コミット内容

exp/locale/collate パッケージにおいて、収縮トライをミャンマー語（ビルマ語）に対応させるために調整しました。ミャンマー語は非常に大きな収縮テーブルを持つため、次の状態オフセットの値が現在のブロックの「前」ではなく「後」から始まるように変更されました。これにより、状態遷移ごとに1回の追加演算が必要となり、わずかに効率が低下しますが、オフセットの範囲が広がり、より大きなテーブルに対応できるようになります。また、final (0) と noIndex (0xFF) の定数が導入されました。tables.go の更新は別の変更リスト（CL）で行われます。

変更の背景

この変更の背景には、Go言語の国際化（i18n）および地域化（l10n）サポートの強化があります。特に、文字列のソート順序を定義する「照合（collation）」において、特定の言語が持つ複雑なルールへの対応が課題となっていました。

ミャンマー語（ビルマ語）は、その文字体系と照合規則において、複数の文字が結合して一つの照合単位を形成する「収縮（contraction）」が頻繁に発生します。例えば、特定の文字の組み合わせが、単一の文字として扱われたり、異なる重み付けを持ったりすることがあります。このような収縮を効率的に処理するために、通常はトライ（Trie）のようなデータ構造が用いられます。

しかし、ミャンマー語の収縮テーブルが非常に大きいため、既存のトライ実装におけるオフセット計算の仕組みでは、表現できる範囲に限界がありました。具体的には、次の状態へのポインタ（オフセット）が、現在のブロックの開始位置を基準に計算されていたため、テーブルが大きくなるとオフセット値が表現可能な範囲（おそらくuint8などの8ビット整数）を超えてしまう問題が発生していました。このコミットは、このオフセットの範囲制限を緩和し、ミャンマー語のような大規模な収縮テーブルを持つ言語でも正しく機能するようにするための対応です。

前提知識の解説

1. ロケール照合 (Locale Collation)

ロケール照合とは、異なる言語や地域（ロケール）において、文字列を正しい順序でソートしたり比較したりするための規則のことです。例えば、英語では 'a' の次に 'b' が来ますが、ドイツ語では 'ä' が 'a' と 'b' の間に位置したり、スウェーデン語では 'å' が 'z' の後に来たりします。これらの規則は、単なる文字コード順ではなく、言語学的な慣習に基づいています。

照合には、以下のような複雑な要素が含まれます。

アクセントとダイアクリティカルマーク: e, é, è, ê などが同じ文字として扱われるか、異なる文字として扱われるか。
大文字・小文字の区別: 大文字と小文字が同じと見なされるか、異なる順序を持つか。
収縮 (Contractions): 複数の文字が結合して一つの照合単位を形成する場合。例: スペイン語の ch や ll がかつては単一の文字として扱われたり、ドイツ語の ß が ss と同等に扱われたりする。
拡張 (Expansions): 一つの文字が複数の照合単位に展開される場合。例: ドイツ語の ä が ae と同等に扱われる。
無視される文字: ハイフンやアポストロフィなど、照合順序に影響を与えない文字。

2. トライ (Trie) データ構造

トライ（Trie、またはプレフィックスツリー）は、文字列の集合を効率的に格納し、プレフィックス検索を行うための木構造のデータ構造です。各ノードは文字列の1文字に対応し、ルートからノードへのパスが文字列を表します。

照合における収縮の処理では、入力文字列を先頭から走査し、トライを使って最長一致の収縮シーケンスを見つけ出すために利用されます。例えば、「ch」という収縮がある場合、トライは「c」のノードから「h」のノードへと遷移し、それが収縮であることを識別します。

3. 収縮トライ (Contraction Trie)

ロケール照合の文脈では、収縮トライは、特定の言語における収縮（複数の文字が単一の照合要素として扱われるシーケンス）を効率的に検索するために特化されたトライです。入力文字列を走査しながら、トライを使って可能な限り長い収縮シーケンスを特定し、それに対応する照合重みを取得します。

このコミットで変更されている ctEntry 構造体は、このトライの各エントリ（ノード）を表しています。

l, h: 文字の範囲（lは下限、hは上限）。
n: 次のブロックの長さ（非最終ノードの場合）。
i: 結果オフセット（最終ノードの場合）。
h (非最終ノードの場合): 次のブロックへの相対インデックス。

4. オフセット計算と範囲制限

トライの実装では、ノード間の遷移や次の状態へのポインタを、メモリ上の配列のインデックス（オフセット）として表現することが一般的です。このオフセットが8ビット整数（uint8）で表現される場合、最大値は255となります。もし、次の状態へのオフセットが255を超える必要がある場合、この8ビットの制限が問題となります。

ミャンマー語のように収縮テーブルが非常に大きい場合、トライの構造が複雑になり、次の状態へのオフセットが255を超える可能性が高まります。このコミットは、このオフセットの計算方法を変更することで、より大きなオフセット値に対応できるようにしています。

技術的詳細

このコミットの主要な技術的変更点は、収縮トライの内部表現と、特に次の状態へのオフセットの計算方法です。

1. オフセット計算の変更

コミットメッセージによると、「The value of the next state offset now starts after the current block, instead of before.」とあります。これは、ctEntry 構造体の h フィールドが表す「次のブロックへの相対インデックス」の解釈が変わったことを意味します。

以前は、states[e.h:] のように、e.h が次のブロックの開始インデックスを直接指していた可能性があります。しかし、変更後は states[int(e.h)+n:] のように、e.h に n（現在のブロックの長さ）を加算して次のブロックの開始位置を計算するようになりました。

この変更の意図は、e.h が表現できるオフセットの範囲を実質的に広げることです。もし e.h が相対オフセットを表す場合、そのオフセットが現在のブロックの終端から始まることで、より大きな絶対インデックスを指すことができるようになります。これにより、uint8 の255という制限内で、より遠くのブロックを参照できるようになります。

ただし、この変更は「slightly less efficient (on extra addition per state change)」と述べられているように、状態遷移ごとに1回の加算演算が追加されるため、わずかなパフォーマンス低下を伴います。しかし、オフセットの範囲を広げるという目的のためには許容されるトレードオフです。

2. 定数 `final` と `noIndex` の導入

以前は、ctEntry 構造体の n フィールドが0の場合に「最終ノード（longest suffixが発見された状態）」を意味し、i フィールドが 0xFF の場合に「結果オフセットがない（さらにバイトが必要）」を意味していました。

このコミットでは、これらのマジックナンバー（0と0xFF）を、より意味のある定数 final と noIndex に置き換えています。

const final = 0
const noIndex = 0xFF

これにより、コードの可読性と保守性が向上します。特に、ctEntry の定義が以下のように変更されています。

// Before:
// type ctEntry struct {
//  l uint8 // non-final: byte value to match; final: lowest match in range.
//  h uint8 // non-final: relative index to next block; final: highest match in range.
//  n uint8 // non-final: length of next block; final: 0
//  i uint8 // result offset. Will be 0xFF if more bytes are needed to complete.
// }

// After:
type ctEntry struct {
	l uint8 // non-final: byte value to match; final: lowest match in range.
	h uint8 // non-final: relative index to next block; final: highest match in range.
	n uint8 // non-final: length of next block; final: final (0)
	i uint8 // result offset. Will be noIndex (0xFF) if more bytes are needed to complete.
}

この変更は、コードの意図を明確にし、将来的な変更やデバッグを容易にします。

3. `build/contract.go` と `contract.go` の変更点

build/contract.go: トライを構築するロジックが含まれています。genStates 関数内で、新しいオフセット計算ロジック (ln := len(*ct) - start - n) が適用され、ctEntry の初期化時に final と noIndex が使用されるようになりました。また、lookup 関数内で、次の状態への遷移時に states[int(e.h)+n:] が使用されるように変更されています。
contract.go: 構築されたトライを使用して実際に文字列をスキャンするロジックが含まれています。scan 関数内で、lookup と同様に states[int(e.h)+n:] が使用されるように変更されています。

--- a/src/pkg/exp/locale/collate/build/contract.go
+++ b/src/pkg/exp/locale/collate/build/contract.go
@@ -41,6 +41,11 @@ import (
 // also includes the length and offset to the next sequence of entries
 // to check in case of a match. 
 
+const (
+	final   = 0
+	noIndex = 0xFF
+)
+
 // ctEntry associates to a matching byte an offset and/or next sequence of 
 // bytes to check. A ctEntry c is called final if a match means that the
 // longest suffix has been found.  An entry c is final if c.n == 0.
@@ -50,24 +55,24 @@ import (
 // Examples:
 // The suffix strings "ab" and "ac" can be represented as:
 // []ctEntry{
-//     {'a', 1, 1, 0xFF},  // 'a' by itself does not match, so i is 0xFF.
+//     {'a', 1, 1, noIndex},  // 'a' by itself does not match, so i is 0xFF.
 //     {'b', 'c', 0, 1},   // "ab" -> 1, "ac" -> 2
 // }
 // 
 // The suffix strings "ab", "abc", "abd", and "abcd" can be represented as:
 // []ctEntry{
-//     {'a', 1, 1, 0xFF}, // 'a' must be followed by 'b'.
-//     {'b', 2, 2, 1},    // "ab" -> 1, may be followed by 'c' or 'd'.
-//     {'d', 'd', 0, 3},  // "abd" -> 3
+//     {'a', 1, 1, noIndex}, // 'a' must be followed by 'b'.
+//     {'b', 1, 2, 1},    // "ab" -> 1, may be followed by 'c' or 'd'.
+//     {'d', 'd', final, 3},  // "abd" -> 3
 //     {'c', 4, 1, 2},    // "abc" -> 2, may be followed by 'd'.
-//     {'d', 'd', 0, 4},  // "abcd" -> 4
+//     {'d', 'd', final, 4},  // "abcd" -> 4
 // }
 // See genStateTests in contract_test.go for more examples.
 type ctEntry struct {
 	l uint8 // non-final: byte value to match; final: lowest match in range.
 	h uint8 // non-final: relative index to next block; final: highest match in range.
-	n uint8 // non-final: length of next block; final: 0
-	i uint8 // result offset. Will be 0xFF if more bytes are needed to complete. 
+	n uint8 // non-final: length of next block; final: final
+	i uint8 // result offset. Will be noIndex if more bytes are needed to complete. 
 }
 
 // contractTrieSet holds a set of contraction tries. The tries are stored
@@ -124,7 +129,7 @@ func (ct *contractTrieSet) genStates(sis []stridx) (int, error) {
 			}
 			if !added {
-				*ct = append(*ct, ctEntry{l: c, i: 0xFF})
+				*ct = append(*ct, ctEntry{l: c, i: noIndex})
 			}
 		} else {
 			for j := len(*ct) - 1; j >= start; j-- {
@@ -140,7 +145,7 @@ func (ct *contractTrieSet) genStates(sis []stridx) (int, error) {
 			}
 			if !added {
-				*ct = append(*ct, ctEntry{l: c, h: c, i: uint8(si.index)})
+				*ct = append(*ct, ctEntry{l: c, h: c, n: final, i: uint8(si.index)})
 			}
 		}
 	}
@@ -150,7 +155,7 @@ func (ct *contractTrieSet) genStates(sis []stridx) (int, error) {
 	for i, end := start, len(*ct); i < end; i++ {
 		fe := (*ct)[i]
 		if fe.h == 0 { // uninitialized non-final
-			ln := len(*ct) - start
+			ln := len(*ct) - start - n
 			if ln > 0xFF {
 				return 0, fmt.Errorf("genStates: relative block offset too large: %d > 255", ln)
 			}
@@ -238,16 +243,16 @@ func (ct *contractTrieSet) lookup(h ctHandle, str []byte) (index, ns int) {
 		if c >= e.l {
 			p++
 			if e.l == c {
-				if e.i != 0xFF {
+				if e.i != noIndex {
 					index, ns = int(e.i), p
 				}
-				if e.n != 0 {
+				if e.n != final {
 					// set to new state
-					i, states, n = 0, states[e.h:], int(e.n)
+					i, states, n = 0, states[int(e.h)+n:], int(e.n)
 				} else {
 					return
 				}
-			} else if e.n == 0 && c <= e.h {
+			} else if e.n == final && c <= e.h {
 				return int(c-e.l) + int(e.i), p
 			}
 		} else {

`src/pkg/exp/locale/collate/contract.go`

--- a/src/pkg/exp/locale/collate/contract.go
+++ b/src/pkg/exp/locale/collate/contract.go
@@ -37,6 +37,11 @@ func (s *ctScanner) result() (i, p int) {
 	return s.index, s.pindex
 }
 
+const (
+	final   = 0
+	noIndex = 0xFF
+)
+
 // scan matches the longest suffix at the current location in the input
 // and returns the number of bytes consumed.
 func (s *ctScanner) scan(p int) int {
@@ -53,12 +58,12 @@ func (s *ctScanner) scan(p int) int {
 		if c >= e.l {
 			if e.l == c {
 				p++
-				if e.i != 0xFF {
+				if e.i != noIndex {
 					s.index = int(e.i)
 					s.pindex = p
 				}
-				if e.n != 0 {
-					i, states, n = 0, states[e.h:], int(e.n)
+				if e.n != final {
+					i, states, n = 0, states[int(e.h)+n:], int(e.n)
 					if p >= len(str) || utf8.RuneStart(str[p]) {
 						s.states, s.n, pr = states, n, p
 					}
@@ -67,7 +72,7 @@ func (s *ctScanner) scan(p int) int {
 					return p
 				}
 				continue
-			} else if e.n == 0 && c <= e.h {
+			} else if e.n == final && c <= e.h {
 				p++
 				s.done = true
 				s.index = int(c-e.l) + int(e.i)

コアとなるコードの解説

1. `const (final = 0; noIndex = 0xFF)` の導入

これは、ctEntry 構造体内で使用される特殊な値に名前を付けることで、コードの意図を明確にするための変更です。

final: ctEntry.n がこの値の場合、そのエントリが文字列の最長一致の終端（最終ノード）であることを示します。
noIndex: ctEntry.i がこの値の場合、そのエントリがまだ完全な結果オフセットを持っていない（つまり、さらに文字を読み進める必要がある）ことを示します。

2. `ctEntry` 構造体のコメント更新

ctEntry の n と i フィールドのコメントが、新しい定数名に合わせて更新されています。これにより、構造体の各フィールドの役割がより明確になります。

3. `genStates` 関数 (`build/contract.go`) の変更

genStates 関数は、収縮トライを構築する際に状態を生成する役割を担っています。

*ct = append(*ct, ctEntry{l: c, i: noIndex})
- 以前は 0xFF を直接使用していましたが、noIndex 定数を使用するように変更されました。
*ct = append(*ct, ctEntry{l: c, h: c, n: final, i: uint8(si.index)})
- 以前は n: 0 を使用していましたが、final 定数を使用するように変更されました。
ln := len(*ct) - start - n
- これがオフセット計算の核心的な変更です。以前は ln := len(*ct) - start でしたが、n（現在のブロックの長さ）を減算することで、次のブロックの開始位置を現在のブロックの終端から相対的に計算するように変更されました。これにより、ln が表現できる範囲が実質的に広がり、より大きなオフセットに対応できるようになります。

4. `lookup` 関数 (`build/contract.go`) および `scan` 関数 (`contract.go`) の変更

これらの関数は、構築されたトライを走査して収縮を検索する役割を担っています。

if e.i != noIndex { ... }
- 0xFF の代わりに noIndex を使用。
if e.n != final { ... }
- 0 の代わりに final を使用。
i, states, n = 0, states[int(e.h)+n:], int(e.n)
- これが最も重要な変更点です。以前は states[e.h:] で次の状態のブロックを参照していましたが、int(e.h)+n とすることで、e.h が示す相対オフセットに現在のブロックの長さ n を加算し、次のブロックの開始位置を計算しています。これにより、e.h が8ビットの範囲内であっても、より大きな絶対インデックスを指すことが可能になります。
else if e.n == final && c <= e.h { ... }
- e.n == 0 の代わりに e.n == final を使用。

これらの変更により、トライの走査ロジックが新しいオフセット計算方法と定数に適合するように更新されています。

参考にした情報源リンク

コミットメッセージと差分
Go言語のソースコード（src/pkg/exp/locale/collate パッケージ）
Unicode Collation Algorithm (UCA) の概念に関する一般的な知識
トライ（Trie）データ構造に関する一般的な知識

comemo