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

コミット

commit 9aa70984a95c24e7ced91432e0d780e6d2361679
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Mon Dec 24 16:42:29 2012 +0100

    exp/locale/collate: include composed characters into the table. This eliminates
    the need to decompose characters for the majority of cases.  This considerably
    speeds up collation while increasing the table size minimally.
    
    To detect non-normalized strings, rather than relying on exp/norm, the table
    now includes CCC information. The inclusion of this information does not
    increase table size.
    
    DETAILS
     - Raw collation elements are now a struct that includes the CCC, rather
       than a slice of ints.
     - Builder now ensures that NFD and NFC counterparts are included in the table.
       This also fixes a bug for Korean which is responsible for most of the growth
       of the table size.
     - As there is no more normalization step, code should now handle both strings
       and byte slices as input. Introduced source type to facilitate this.
    
    NOTES
     - This change does not handle normalization correctly entirely for contractions.
       This causes a few failures with the regtest. table_test.go contains a few
       uncommented tests that can be enabled once this is fixed.  The easiest is to
       fix this once we have the new norm.Iter.
     - Removed a test cases in table_test that covers cases that are now guaranteed
       to not exist.
    
    R=rsc, mpvl
    CC=golang-dev
    https://golang.org/cl/6971044

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

https://github.com/golang/go/commit/9aa70984a95c24e7ced91432e0d780e6d2361679

元コミット内容

exp/locale/collate: 結合済み文字をテーブルに含める。これにより、ほとんどの場合で文字を分解する必要がなくなる。これにより、テーブルサイズを最小限に抑えつつ、照合処理が大幅に高速化される。

非正規化文字列を検出するために、exp/normに依存するのではなく、テーブルにCCC情報を含めるようになった。この情報の追加はテーブルサイズを増加させない。

詳細:

• 生の照合要素が、intのスライスではなく、CCCを含む構造体になった。
• ビルダーがNFDおよびNFCの対応する文字をテーブルに含めることを保証するようになった。これにより、テーブルサイズの増加の大部分を占めていた韓国語のバグも修正される。
• 正規化ステップがなくなったため、コードは文字列とバイトスライスの両方を入力として処理する必要がある。これを容易にするためにソースタイプが導入された。

注意:

• この変更は、縮約（contractions）に対する正規化を完全に正しく処理しない。これにより、いくつかの回帰テストが失敗する。table_test.goには、これが修正されたら有効にできるコメントアウトされたテストがいくつか含まれている。新しいnorm.Iterがあれば、これを修正するのが最も簡単である。
• 存在しないことが保証されるようになったケースをカバーするtable_testのテストケースを削除した。

変更の背景

このコミットは、Go言語の実験的なロケール照合パッケージ（exp/locale/collate）におけるパフォーマンスと正確性の向上を目的としています。特に、Unicodeの照合（Collation）処理において、結合済み文字（Composed Characters）の扱いを改善し、正規化の必要性を減らすことで、処理速度を向上させることが主な動機です。

従来の照合処理では、比較対象の文字列を正規化形式（通常はNFD: Normalization Form D）に分解してから照合要素（Collation Elements）を生成していました。しかし、多くの結合済み文字は、分解せずに直接照合要素にマッピングできるため、この分解ステップは不要であり、オーバーヘッドとなっていました。このコミットは、結合済み文字を直接照合テーブルに含めることで、この不要な分解処理をスキップし、パフォーマンスを向上させようとしています。

また、Unicodeの正規化には、結合文字の順序に関するルール（Canonical Combining Class: CCC）が関係します。非正規化された文字列が入力された場合でも正しく照合を行うためには、これらの情報を考慮する必要があります。このコミットでは、照合テーブル自体にCCC情報を含めることで、外部の正規化パッケージ（exp/norm）に依存することなく、非正規化文字列の検出と適切な処理を可能にしています。これにより、照合処理の自己完結性が高まり、より堅牢な実装を目指しています。

さらに、韓国語の文字（ハングル）は、結合文字の複雑な構造を持つため、従来の正規化処理においてテーブルサイズを不必要に増加させる原因となっていました。このコミットの変更により、韓国語の文字に対する処理も最適化され、テーブルサイズの肥大化が抑制される効果も期待されます。

前提知識の解説

Unicode Collation Algorithm (UCA)

UCAは、Unicode文字列を言語的に正しい順序でソートするためのアルゴリズムです。単なるコードポイント順のソートでは、言語ごとの慣習（例: ドイツ語のäはaとeの間、スウェーデン語のåはzの後など）を反映できません。UCAは、文字列を「照合要素（Collation Elements: CE）」のシーケンスに変換し、これらのCEを比較することでソート順を決定します。CEは通常、プライマリ、セカンダリ、ターシャリ、クォータナリの4つのレベルの重み（weights）を持ち、それぞれ異なる粒度で比較を行います。

正規化 (Normalization Forms)

Unicodeには、同じ文字を異なるバイトシーケンスで表現できる場合があります（例: éは単一のコードポイントU+00E9で表現することも、e (U+0065) と結合用アキュートアクセント (U+0301) の組み合わせで表現することも可能）。これを「等価性（Equivalence）」と呼びます。UCAでは、これらの等価な文字列が同じソート順になるように、比較前に文字列を特定の「正規化形式（Normalization Form）」に変換することが推奨されています。

• NFD (Normalization Form D): 文字を分解された形式（例: éをeと´に）に変換します。
• NFC (Normalization Form C): 文字を可能な限り結合された形式（例: eと´をéに）に変換します。 UCAの標準的な実装では、通常NFDに正規化してから照合要素を生成します。

Canonical Combining Class (CCC)

Unicodeの結合文字（Combining Characters）には、それぞれ「Canonical Combining Class (CCC)」というプロパティが割り当てられています。CCCは、結合文字が他の文字と結合する際の相対的な順序を定義します。例えば、アキュートアクセントとグレイブアクセントが同じベース文字に適用される場合、CCCの値に基づいてどちらが先に結合されるかが決まります。UCAでは、非正規化された文字列（結合文字の順序が標準的でない文字列）を正しく処理するために、CCC情報が重要になります。

照合要素 (Collation Elements: CE)

UCAにおいて、各文字または文字のシーケンスは、一つ以上の照合要素にマッピングされます。照合要素は、通常、プライマリ、セカンダリ、ターシャリ、クォータナリの4つのレベルの重みを持つ数値のタプルです。

• プライマリ重み: 言語的な主要な違い（例: aとb）を区別します。
• セカンダリ重み: アクセントやダイアクリティカルマーク（例: aとá）を区別します。
• ターシャリ重み: 大文字・小文字や幅の違い（例: aとA、全角と半角）を区別します。
• クォータナリ重み: シフトされた重み付け（Shifted Weighting）ルールが適用される場合にのみ使用され、通常は句読点や記号の扱いを制御します。

技術的詳細

このコミットの主要な技術的変更点は、照合テーブルの構造と照合要素の処理方法にあります。

1. 結合済み文字の直接サポート:

   • 従来のUCA実装では、文字列をNFDに分解してから照合要素を生成するのが一般的でした。しかし、多くの結合済み文字（例: é）は、分解された形式（e + ´）と同じ照合要素を持つことが知られています。
   • このコミットでは、照合テーブルにNFC形式の結合済み文字も直接含めることで、これらの文字が入力された際に分解ステップをスキップし、直接対応する照合要素を取得できるようにしています。これにより、特に頻繁に出現する結合済み文字の処理において、パフォーマンスが大幅に向上します。
   • Builder（照合テーブルを構築するコンポーネント）が、NFDとNFCの両方の形式をテーブルに含めることを保証するようになりました。これは、patchNorm関数によって実現されています。

2. CCC情報の照合要素への組み込み:

   • 以前は、文字列の正規化はexp/normパッケージに依存していました。しかし、このコミットでは、照合要素自体にCCC情報（Canonical Combining Class）を含めるように変更されました。
   • rawCE構造体が導入され、従来の[]int（重みのみ）に加えてccc uint8フィールドを持つようになりました。
   • makeCE関数（照合要素をuint32形式にパックする関数）も更新され、CCC情報をエンコードできるようになりました。これにより、照合処理中に結合文字の順序を考慮し、非正規化された文字列でも正しく処理できるようになります。外部の正規化ステップを不要にすることで、処理の効率化と自己完結性を高めています。

3. 入力ソースの抽象化:

   • 正規化ステップがなくなったことで、照合処理は生の文字列（string）またはバイトスライス（[]byte）を直接入力として受け取れるようになりました。
   • これを容易にするために、sourceという新しい構造体が導入されました。これは、入力がstringであるか[]byteであるかを内部的に管理し、rune()やlookup()などのメソッドを通じて統一されたインターフェースを提供します。これにより、照合ロジックが入力形式に依存しなくなり、コードの柔軟性が向上します。

4. 韓国語のバグ修正:

   • 韓国語のハングル文字は、非常に多くの結合形式を持つため、従来の正規化処理では照合テーブルが不必要に肥大化する原因となっていました。
   • このコミットの変更（特にNFD/NFC対応の改善）により、韓国語の文字に対するテーブル構築が最適化され、テーブルサイズの増加が抑制されるバグが修正されました。

5. iter構造体の変更:

   • 照合要素を順次取得するiter構造体も大幅に変更されました。
   • 以前はexp/norm.Iterを使用していましたが、このコミットではsource構造体と直接連携するように変更されました。
   • next()メソッドのロジックが更新され、CCC情報に基づいて照合要素の正規化（再順序付け）を行うようになりました。これにより、入力文字列が非正規化されていても、正しい照合順序が保証されます。

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

このコミットでは、主に以下のファイルが変更されています。

• src/pkg/exp/locale/collate/build/builder.go: 照合テーブルを構築するロジック。Add関数がrawCE構造体を受け取るようになり、patchNorm関数が追加され、NFD/NFCの対応を保証するようになりました。
• src/pkg/exp/locale/collate/build/colelem.go: 照合要素の定義と操作。rawCE構造体が新しく定義され、makeCE関数がCCC情報を処理するように変更されました。
• src/pkg/exp/locale/collate/build/order.go: 照合順序の管理。entry構造体がrawCEのスライスを持つようになり、newEntry関数がハングル文字の特殊処理を含むようになりました。
• src/pkg/exp/locale/collate/colelem.go: 実行時における照合要素の操作。colElemのビットフィールド定義が更新され、CCC情報を抽出するccc()メソッドや、プライマリ重み、セカンダリ重み、ターシャリ重みを抽出するロジックが変更されました。
• src/pkg/exp/locale/collate/collate.go: 照合器の主要ロジック。iter構造体がsource構造体を使用するように変更され、next()メソッドがCCCに基づく正規化ロジックを含むようになりました。
• src/pkg/exp/locale/collate/contract.go: 縮約（contractions）の処理。ctScannerStringが追加され、文字列入力に対応しました。
• src/pkg/exp/locale/collate/table.go: 照合テーブルのルックアップロジック。appendNext関数がsource構造体を受け取るようになり、ハングル文字の特殊処理や縮約処理が更新されました。
• src/pkg/exp/locale/collate/tables.go: ロケールごとのテーブルデータ。テーブルデータ自体が大幅に更新されています。

コアとなるコードの解説

src/pkg/exp/locale/collate/build/colelem.go の rawCE 構造体と makeCE 関数

type rawCE struct {
	w   []int
	ccc uint8
}

func makeRawCE(w []int, ccc uint8) rawCE {
	ce := rawCE{w: make([]int, 4), ccc: ccc}
	copy(ce.w, w)
	return ce
}

func makeCE(rce rawCE) (uint32, error) {
	weights := rce.w
	// ... (既存の重みチェックロジック) ...

	ce := uint32(0)
	if weights[0] != 0 { // プライマリ重みが非ゼロの場合
		if rce.ccc != 0 { // CCCが非ゼロの場合
			// 新しいエンコーディング形式: isPrimaryCCC | Tertiary | CCC | Primary
			// プライマリ重みがコンパクトな範囲に収まるかチェック
			if weights[0] >= 1<<maxPrimaryCompactBits {
				return 0, fmt.Errorf("makeCE: primary weight with non-zero CCC out of bounds: %x >= %x", weights[0], 1<<maxPrimaryCompactBits)
			}
			// セカンダリ重みがデフォルトであるかチェック
			if weights[1] != defaultSecondary {
				return 0, fmt.Errorf("makeCE: cannot combine non-default secondary value (%x) with non-zero CCC (%x)", weights[1], rce.ccc)
			}
			ce = uint32(weights[2] << (maxPrimaryCompactBits + maxCCCBits)) // ターシャリ重み
			ce |= uint32(rce.ccc) << maxPrimaryCompactBits                  // CCC
			ce |= uint32(weights[0])                                        // プライマリ重み
			ce |= isPrimaryCCC                                              // タイプ識別子
		} else if weights[2] == defaultTertiary { // ターシャリ重みがデフォルトの場合
			// 既存のエンコーディング形式: isPrimary | Primary | Secondary
			// ...
		} else { // ターシャリ重みが非デフォルトの場合
			// 既存のエンコーディング形式: Primary | SecondaryDiff | Tertiary
			// ...
		}
	} else { // プライマリ重みがゼロの場合 (セカンダリまたはターシャリのみ)
		// 既存のエンコーディング形式: isSecondary | Secondary | Tertiary
		ce = uint32(weights[1]<<maxTertiaryBits + weights[2])
		ce += uint32(rce.ccc) << (maxSecondaryBits + maxTertiaryBits) // CCCを追加
		ce |= isSecondary                                             // タイプ識別子
	}
	return ce, nil
}

この変更は、照合要素の内部表現を根本的に変えるものです。rawCE構造体は、照合要素の重み（w）に加えて、その要素のCanonical Combining Class（ccc）を直接保持するようになりました。makeCE関数は、このrawCEを受け取り、CCCの値に応じて異なるビットパターンでuint32にエンコードします。これにより、照合処理中にCCC情報を参照できるようになり、非正規化された文字列の正しい処理が可能になります。特に、プライマリ重みが非ゼロでCCCも非ゼロの場合に新しいエンコーディング形式が導入されています。

src/pkg/exp/locale/collate/collate.go の iter 構造体と next() メソッド

type source struct {
	str   string
	bytes []byte
	buf   [16]byte // Used for decomposing Hangul.
}

// ... (source構造体のメソッド群: done, tail, nfd, properties, lookup, rune) ...

type iter struct {
	src source

	wa  [512]colElem
	ce  []colElem
	pce int
	nce int // nce <= len(nce)

	prevCCC  uint8
	pStarter int

	t *table
}

// next appends colElems to the internal array until it adds an element with CCC=0.
// In the majority of cases, a colElem with a primary value > 0 will have
// a CCC of 0. The CCC values of colation elements are also used to detect if the
// input string was not normalized and to adjust the result accordingly.
func (i *iter) next() bool {
	sz := 0
	for !i.src.done() {
		p0 := len(i.ce)
		i.ce, sz = i.t.appendNext(i.ce, i.src) // 次の照合要素を取得
		i.src = i.src.tail(sz)                 // 処理済みバイト数を進める
		last := len(i.ce) - 1
		if ccc := i.ce[last].ccc(); ccc == 0 { // CCCが0の場合
			i.nce = len(i.ce)
			i.pStarter = last
			i.prevCCC = 0
			return true
		} else if p0 < last && i.ce[p0].ccc() == 0 {
			// CCCが0の要素と非0の要素が混在する場合の処理
			// ...
		} else if ccc < i.prevCCC { // CCCが前の要素より小さい場合 (非正規化の可能性)
			i.doNorm(p0, ccc) // 正規化処理を実行
		} else {
			i.prevCCC = ccc
		}
	}
	if len(i.ce) != i.nce {
		i.nce = len(i.ce)
		return true
	}
	return false
}

// doNorm reorders the collation elements in i.ce.
// It assumes that blocks of collation elements added with appendNext
// either start and end with the same CCC or start with CCC == 0.
// This allows for a single insertion point for the entire block.
// The correctness of this assumption is verified in builder.go.
func (i *iter) doNorm(p int, ccc uint8) {
	// ... (CCCに基づく照合要素の再順序付けロジック) ...
}

source構造体は、文字列とバイトスライスの両方を統一的に扱うための抽象化レイヤーです。iter構造体は、このsourceから照合要素を読み込みます。next()メソッドは、入力から次の照合要素のブロックを読み込み、そのCCCをチェックします。もし現在の要素のCCCが前の要素のCCCよりも小さい場合（これはUnicodeの正規化ルールに反する、つまり非正規化された文字列であることを示唆します）、doNorm関数を呼び出して照合要素の順序を修正します。これにより、入力文字列がNFCやNFDに正規化されていなくても、UCAのルールに従って正しく照合が行われるようになります。

関連リンク

• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Unicode Normalization Forms: https://unicode.org/reports/tr15/
• Canonical Combining Class (CCC): https://www.unicode.org/glossary/#Canonical_Combining_Class

参考にした情報源リンク

• Go言語の公式ドキュメント（exp/locale/collateパッケージに関するものがあれば）
• Unicode Technical Reports (TR10, TR15)
• CLDR (Common Locale Data Repository) - 照合ルールやデータが定義されています。
• Go言語のコミット履歴と関連するコードレビュー（CL: Change List）
  • https://golang.org/cl/6971044 (コミットメッセージに記載されているCL)
• Go言語のexp/normパッケージのドキュメント（変更前の参照先として）
  • https://pkg.go.dev/golang.org/x/text/unicode/norm (現在のx/text/unicode/normパッケージ)
• Go言語のunicode/utf8パッケージのドキュメント