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

このコミットは、Go言語の実験的なexp/locale/collateパッケージに、照合（Collation）テーブルを生成するためのBuilder型を導入するものです。これにより、Unicode Collation Algorithm (UCA) に基づく照合順序をプログラム的に構築できるようになります。現時点では、ルートテーブル（基本となる照合順序）の生成のみを実装していますが、将来的にロケール固有のテーラリング（カスタマイズ）をサポートするための基盤を築いています。

コミット

このコミットは、exp/locale/collateパッケージにBuilder型を追加し、完全な照合テーブルを生成する機能を提供します。現在のところ、ルートテーブルの生成のみが実装されています。

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

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

元コミット内容

commit fdce27f7b8f671e3399d2c116dbd15ec2e612af2
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed Apr 25 13:19:35 2012 +0200

    exp/locale/collate: Added Builder type for generating a complete
    collation table. At this moment, it only implements the generation of
    a root table.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6039047

変更の背景

Go言語は、国際化（i18n）と地域化（l10n）のサポートを強化する過程にありました。その中で、文字列のソート順序を言語や地域（ロケール）に応じて適切に処理する「照合（Collation）」の機能は不可欠です。Unicode Collation Algorithm (UCA) は、この照合順序を定義するための標準的なアルゴリズムですが、その実装は複雑であり、大量のデータ（Unicode Collation Element Table: DUCET）を必要とします。

このコミット以前は、Go言語にはUCAに準拠した照合テーブルをプログラム的に生成・管理するメカニズムがありませんでした。exp/locale/collateパッケージは照合機能を提供しますが、その内部で使用するテーブルは事前に生成されたものでした。このコミットは、そのテーブル生成プロセスをGo言語内で完結させ、より柔軟かつ効率的に照合テーブルを構築できるようにすることを目的としています。特に、将来的にロケール固有のテーラリング（特定の言語や地域に合わせた照合順序のカスタマイズ）をサポートするためには、このようなBuilder型の存在が不可欠でした。

前提知識の解説

照合 (Collation)

照合とは、文字列を特定の順序で並べ替える（ソートする）プロセスです。単に文字コードの数値順に並べるのではなく、言語や文化の慣習に基づいて「正しい」順序で並べ替えることが求められます。例えば、ドイツ語では「ä」は「a」と「b」の間ではなく、「a」の後に来るべきとされたり、スウェーデン語では「z」の後に「å, ä, ö」が来たりします。

Unicode Collation Algorithm (UCA)

UCAは、Unicode Consortiumによって定義された、多言語環境での文字列照合のための標準アルゴリズムです。UCAは、言語や文化に依存しない一貫した照合順序を提供することを目的としています。UCAは、各文字に「照合要素（Collation Element: CE）」と呼ばれる一連の重み（プライマリ、セカンダリ、ターシャリなど）を割り当てることで機能します。

照合要素 (Collation Element: CE) と重み

UCAでは、各文字または文字のシーケンスは、複数のレベルの重みを持つ照合要素に変換されます。

プライマリ重み (Primary Weight): 文字の基本的な形状やアルファベット順を決定します。例えば、'a'と'A'は同じプライマリ重みを持ちます。
セカンダリ重み (Secondary Weight): アクセント記号やダイアクリティカルマークの違いを区別します。例えば、'a'と'á'は異なるセカンダリ重みを持ちます。
ターシャリ重み (Tertiary Weight): 大文字・小文字の違いや、文字の幅（全角・半角）などを区別します。例えば、'a'と'A'は異なるターシャリ重みを持ちます。
クォータナリ重み (Quaternary Weight): 日本語の濁点・半濁点など、特定の言語での追加の区別に使用されることがあります。

これらの重みを比較することで、文字列の照合順序が決定されます。

Add(str []rune, colelems [][]int) error: ルート照合要素テーブルにエントリを追加します。これは、特定のルーン（文字）シーケンスが、どのような照合要素のシーケンスに対応するかを定義します。colelemsは、プライマリ、セカンダリ、ターシャリなどの重みを含むintのスライスで構成されます。
AddTailoring(locale, x, y string, l collate.Level) error: 特定のロケールに対して、照合順序のテーラリング（カスタマイズ）を定義します。例えば、「x」が「y」の後に来るように、特定のレベル（プライマリ、セカンダリなど）で順序を変更する指示を与えます。このコミット時点では、このメソッドはまだ実装されていません（// TODO: implement.）。
Build(locale string) (*collate.Collator, error): 構築された照合テーブルに基づいて、collate.Collatorインスタンスを生成します。
Print(w io.Writer) (int, error): 構築されたテーブルをGoのソースコード形式で指定されたio.Writerに出力します。これにより、生成されたテーブルをGoのパッケージとして組み込むことができます。

内部データ構造と処理フロー

Builderは、照合テーブルを構築するためにいくつかの内部処理とデータ構造を使用します。

entry struct: 照合要素テーブルの単一のエントリを追跡するために使用されます。
- runes: 照合されるルーンのシーケンス。
- elems: 対応する照合要素のシーケンス。
- str: string(runes)と同じ。
- decompose: NFKD分解を使用して照合要素を生成できるかどうかを示すフラグ。
- expansionIndex: 拡張テーブルへのインデックス。
- contractionHandle, contractionIndex: 収縮テーブルへのハンドルとインデックス。
contractCJK(): CJK（中国語、日本語、韓国語）文字の特殊な照合要素（DUCETでは2つのCEで表現される）を、Goの内部表現で1つのCEに変換する処理を行います。これは、UCAの「Implicit Weights」のルールに基づいています。
simplify(): 照合テーブルを最適化し、冗長なエントリを削除します。
- NFD (Normalization Form D) 分解によって同じ照合要素に正規化されるエントリを削除します。
- NFKD (Normalization Form Compatibility Decomposition) 分解によって同じ照合要素に正規化されるエントリをdecomposeフラグでマークします。これにより、実行時に動的に照合要素を生成できるようになります。
processExpansions(): 拡張（Expansion）とは、1つの文字が複数の照合要素に展開されるケースです。例えば、ドイツ語の「ß」が「ss」として照合される場合などです。この関数は、拡張される文字とその照合要素のシーケンスをexpandElemテーブルに格納し、各entryにそのインデックスを記録します。
processContractions(): 収縮（Contraction）とは、複数の文字のシーケンスが1つの照合要素として扱われるケースです。例えば、スペイン語の「ch」が1つの文字として扱われる場合などです。この関数は、収縮のパターンをトライ木（Trie）構造で管理し、各entryに収縮テーブルへのハンドルとインデックスを記録します。
buildTrie(): 最終的な照合テーブルのルックアップに使用されるメインのトライ木を構築します。このトライ木は、各ルーンから対応する照合要素へのマッピングを効率的に行います。

これらの処理は、UCAの複雑なルールと最適化をGo言語で実装するための基盤となります。

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

このコミットでは、以下の2つの新しいファイルが追加されています。

src/pkg/exp/locale/collate/build/builder.go: 照合テーブルを生成するためのBuilder型とその関連ロジックが定義されています。
- entry struct: 照合エントリの内部表現。
- Builder struct: 照合テーブル構築のメイン構造体。
- NewBuilder(): Builderのコンストラクタ。
- Add(): ルートテーブルに照合エントリを追加。
- AddTailoring(): ロケール固有のテーラリングを追加（TODO）。
- baseColElem(), colElem(): 照合要素の生成ロジック。
- build(): 内部的なテーブル構築プロセスを調整するメイン関数。
- Build(): collate.Collatorを生成。
- Print(): 生成されたテーブルをGoコードとして出力。
- reproducibleFromNFKD(), equalCE(), equalCEArrays(): 照合要素の比較ユーティリティ。
- genColElems(): 文字列から照合要素を生成。
- simplify(): テーブルの簡素化と最適化。
- convertLargeWeights(): 大きな重みを持つ照合要素の変換。
- contractCJK(): CJK文字の特殊処理。
- appendExpansion(), processExpansions(): 拡張の処理。
- processContractions(): 収縮の処理。
- buildTrie(): メインのトライ木構築。
src/pkg/exp/locale/collate/build/builder_test.go: builder.goで定義された機能の単体テストが含まれています。
- cjk(), pCE(), pqCE(), ptCE(), sCE(), stCE(): テスト用の照合要素ヘルパー関数。
- ducetElem struct: テストデータ構造。
- newBuilder(): テスト用のBuilderインスタンスを生成。
- TestConvertLarge(): 大きな重みの変換テスト。
- TestGenColElems(): 照合要素生成のテスト。
- TestSimplify(): simplify関数のテスト。
- TestExpand(): 拡張処理のテスト。
- TestContract(): 収縮処理のテスト。

コアとなるコードの解説

`src/pkg/exp/locale/collate/build/builder.go`

このファイルは、照合テーブル生成の心臓部です。

entry構造体: 照合テーブルの各エントリを表します。runesは元の文字シーケンス、elemsはその文字シーケンスに対応する照合要素のリストです。decompose、expansionIndex、contractionHandle、contractionIndexといったフィールドは、UCAの複雑なルール（正規化、拡張、収縮）を効率的に処理するためのメタデータとして機能します。
Builder.Add(str []rune, colelems [][]int) error: このメソッドは、DUCETのような外部データソースから読み込んだ生データをBuilderに供給するために使用されます。colelemsは、プライマリ、セカンダリ、ターシャリの重みを含むintのスライスとして渡されます。Builderは、これらの重みを内部的に処理し、必要に応じてデフォルトの重みを補完します。
Builder.simplify(): この関数は、照合テーブルのサイズを削減し、パフォーマンスを向上させるための重要な最適化ステップです。
- NFD正規化によって同じ照合要素にマッピングされるエントリを削除します。例えば、合成済み文字（例: À）が分解済み文字シーケンス（例: A + \u0300）と同じ照合順序を持つ場合、合成済み文字のエントリは削除され、分解済みシーケンスが使用されます。
- NFKD正規化によって同じ照合要素にマッピングされるエントリをdecomposeフラグでマークします。これにより、これらの文字の照合要素は実行時にNFKD分解してから生成されるため、テーブルに明示的に格納する必要がなくなります。
Builder.processExpansions() と Builder.processContractions(): これらは、UCAの拡張と収縮のルールを実装する部分です。
- processExpansionsは、1つの文字が複数の照合要素に展開されるケース（例: ß -> ss）を処理し、expandElemという内部テーブルにその展開情報を格納します。
- processContractionsは、複数の文字シーケンスが1つの照合要素に収縮されるケース（例: ch -> 1つのCE）を処理します。これは、トライ木を使用して効率的に収縮パターンを検索できるように実装されています。
Builder.buildTrie(): 最終的に、Builderはすべての処理済みエントリから、文字から照合要素へのマッピングを効率的に行うためのトライ木を構築します。このトライ木は、照合処理の高速なルックアップを可能にします。

`src/pkg/exp/locale/collate/build/builder_test.go`

このファイルは、builder.goで実装されたロジックが正しく機能するかを検証するためのテストケースを提供します。

テストヘルパー関数: cjk, pCE, pqCEなどの関数は、テストケースで照合要素を簡潔に表現するために使用されます。
TestConvertLarge: DUCETにおける「大きなプライマリ重み」（CJK文字や特殊な文字に割り当てられる）の変換ロジックが正しく処理されるかをテストします。
TestSimplify: simplify関数が、冗長なエントリを正しく削除し、NFKD分解可能なエントリを適切にマークするかを検証します。
TestExpand と TestContract: 拡張と収縮の処理が、それぞれexpandElemテーブルと収縮トライ木に正しくデータが格納され、期待される照合要素が生成されるかをテストします。

これらのテストは、照合テーブル生成の複雑なロジックが、UCAの仕様に準拠して正確に動作することを保証するために不可欠です。

参考にした情報源リンク

https://unicode.org/reports/tr10/ (Unicode Collation Algorithm)
https://golang.org/cl/6039047 (元のGerritチェンジリスト)
Go言語のexpパッケージに関する一般的な情報（Goの公式ドキュメントやブログ記事）
照合、Unicode、正規化形式（NFD, NFKD）に関する一般的な知識。

comemo