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

このコミットは、Go言語の実験的なexp/locale/collateパッケージ内のbuildサブパッケージに対する変更です。exp/locale/collateパッケージは、Unicode Collation Algorithm (UCA) に基づいて、多言語環境での文字列の比較とソートを正確に行うための機能を提供します。具体的には、ロケール（地域や言語の設定）に応じた文字列の並べ替え順序（照合順序）を構築するためのビルダ（Builder）の実装に関連する変更が含まれています。

コミット

exp/locale/collate: added indices to builder for reusing blocks between locales.
Refactored build + buildTrie into build + buildOrdering.
Note that since the tailoring code is not checked in yet, all tailorings are identical
to root.  The table therefore should not and does not grow at this point.

R=r
CC=golang-dev
https://golang.org/cl/6500087

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

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

元コミット内容

exp/locale/collate: added indices to builder for reusing blocks between locales. Refactored build + buildTrie into build + buildOrdering. Note that since the tailoring code is not checked in yet, all tailorings are identical to root. The table therefore should not and does not grow at this point.

変更の背景

このコミットの主な背景は、Go言語のexp/locale/collateパッケージにおける照合テーブルの構築効率の向上です。Unicode Collation Algorithm (UCA) は、異なる言語や地域（ロケール）で文字列を正しくソートするための複雑なルールを定義しています。これらのルールは、文字の展開（Expansion）や縮約（Contraction）、そして特定のロケールに合わせた調整（Tailoring）を含みます。

以前の実装では、異なるロケールごとに照合テーブルを構築する際に、共通するデータブロック（展開や縮約の定義など）が重複して生成される可能性がありました。これはメモリ使用量の増加や構築時間の延長につながります。

このコミットの目的は、Builderにインデックスを追加することで、これらの共通ブロックをロケール間で再利用できるようにすることです。これにより、特に多くのロケールをサポートする場合に、照合テーブルのサイズを削減し、構築プロセスを効率化することが期待されます。

また、buildとbuildTrieという2つの関数がbuildとbuildOrderingにリファクタリングされています。これは、コードの構造を改善し、照合順序の構築ロジックをより明確に分離するためです。

コミットメッセージにある「tailoring code is not checked in yet」という記述は、この時点ではロケールごとの具体的な調整（tailoring）がまだ実装されていないため、すべてのロケールがデフォルトの照合順序（root）と同一であることを示唆しています。そのため、現時点ではテーブルのサイズが大きくならないことが言及されていますが、将来的にtailoringが実装された際には、この再利用の仕組みがより重要になります。

前提知識の解説

Unicode Collation Algorithm (UCA)

Unicode Collation Algorithm (UCA) は、Unicode文字列を言語的に正しい順序で比較・ソートするための標準的なアルゴリズムです。Unicode Technical Report #10 (UTS #10) で定義されており、世界中の多様な言語のソート規則に対応するために設計されています。

UCAの主要な概念は以下の通りです。

照合要素 (Collation Elements): UCAは、文字列を直接比較するのではなく、まず文字列を「照合要素」のシーケンスに変換します。各照合要素は、通常、プライマリ、セカンダリ、ターシャリの3つの重み（weight）を持ちます。
- プライマリ重み: 文字の基本的な順序を決定します（例: 'a' と 'b' の違い）。大文字・小文字やアクセント記号は無視されます。
- セカンダリ重み: アクセント記号やダイアクリティカルマークの違いを考慮します（例: 'a' と 'ä' の違い）。
- ターシャリ重み: 大文字・小文字の違いや、その他の言語固有の規則を考慮します（例: 'a' と 'A' の違い）。
展開 (Expansions): 一つの文字が複数の照合要素に展開されることがあります。例えば、ドイツ語の「ß」が「ss」としてソートされたり、合字（ligature）の「Œ」が「OE」として扱われたりする場合があります。
縮約 (Contractions): 複数の文字のシーケンスが、一つの照合要素として扱われることがあります。例えば、スロバキア語の「ch」は、一つの文字として「h」の後にソートされます。
テーラリング (Tailoring): UCAは、デフォルトの照合順序（Default Unicode Collation Element Table: DUCET）を提供しますが、特定の言語やロケールに合わせてこの順序をカスタマイズする機能も持ちます。これをテーラリングと呼びます。テーラリングにより、言語固有のソート規則（例: スペイン語の「ñ」が「n」の後に来る、辞書順と電話帳順の違いなど）を適用できます。Unicode Common Locale Data Repository (CLDR) は、多くの言語のテーラリングデータを提供しています。

Trie (トライ木)

Trie（トライ木、またはプレフィックス木）は、文字列の集合を効率的に格納し、検索するために使用される木構造のデータ構造です。各ノードは文字列のプレフィックスを表し、ルートノードは空の文字列に対応します。各ノードの子は、そのノードが表すプレフィックスに1文字追加したプレフィックスを表します。

Trieの主な特徴は以下の通りです。

高速なプレフィックス検索: 特定のプレフィックスを持つすべての文字列を効率的に検索できます。
空間効率: 共通のプレフィックスを持つ文字列は、Trie内でパスを共有するため、空間効率が良い場合があります。
辞書順ソート: Trieを深さ優先探索することで、格納されている文字列を辞書順に取得できます。

UCAの実装において、Trieは特に縮約（Contraction）の処理に有用です。例えば、「ch」のような複数文字のシーケンスを一つの単位として認識するために、Trieを使って入力文字列のプレフィックスを効率的にマッチングさせることができます。

技術的詳細

このコミットは、exp/locale/collate/buildパッケージ内のBuilder構造体と関連する関数に、照合テーブル構築の効率化と構造改善のための重要な変更を加えています。

`Builder`構造体の変更

Builder構造体には、以下の新しいフィールドが追加されました。

expIndex map[string]int: 展開（expansions）の文字列表現をキーとし、その展開が格納されているインデックスを値とするマップです。これにより、同じ展開が複数回出現する場合でも、一度だけ格納し、そのインデックスを再利用できるようになります。
ctHandle map[string]ctHandle: 縮約（contractions）のサフィックスの連結文字列をキーとし、その縮約のトライ木へのハンドルを値とするマップです。これにより、同じ縮約パターンが複数回出現する場合に、トライ木を再利用できます。
ctElem map[string]int: 縮約要素（collation elements for contractions）の文字列表現をキーとし、その要素が格納されているインデックスを値とするマップです。これにより、同じ縮約要素が複数回出現する場合に、そのインデックスを再利用できます。

これらのマップは、NewBuilder関数で初期化されるようになりました。

`Tailoring`構造体の変更

Tailoring構造体には、以下の新しいフィールドが追加されました。

builder *Builder: このテーラリングを構築したBuilderへのポインタ。
index *ordering: このテーラリング固有の照合順序（ordering）へのポインタ。以前はidフィールドのみでしたが、これによりテーラリングが自身の照合順序を持つことができるようになります。

Tailoring関数で新しいTailoringが作成される際に、builderフィールドとindexフィールドが適切に設定されます。indexは、ルートの照合順序（b.root）をクローンしたものとして初期化されます。

`build`および`buildOrdering`関数のリファクタリング

以前はbuild関数が照合テーブル全体の構築とTrieの構築を担っていましたが、このコミットではそのロジックがbuildOrdering関数に分離されました。

buildOrdering(o *ordering):
- この関数は、与えられたorderingオブジェクト（照合順序）に対して、ソート、簡略化（simplify）、展開の処理（processExpansions）、縮約の処理（processContractions）を行います。
- その後、ordering内のエントリからTrieを構築し、そのTrieのハンドルをorderingのhandleフィールドに設定します。
- この関数は、ルートの照合順序だけでなく、各ロケールのテーラリングされた照合順序に対しても呼び出されるようになります。
build():
- build関数は、まずルートの照合順序に対してbuildOrderingを呼び出します。
- 次に、登録されている各ロケール（b.locale）のテーラリングされた照合順序に対してもbuildOrderingを呼び出します。
- 最後に、b.index（Trieのビルダ）から最終的なインデックスを生成し、それをb.t.indexに設定します。

このリファクタリングにより、照合順序の構築ロジックがモジュール化され、ルートとテーラリングされたロケールの両方で共通の処理を適用できるようになりました。

`simplify`, `processExpansions`, `processContractions`関数の変更

これらの関数は、以前はBuilderのメソッドとしてb.rootを暗黙的に操作していましたが、このコミットにより、引数として*orderingを受け取る独立した関数（またはBuilderのメソッドだが引数でorderingを受け取る）に変更されました。

simplify(o *ordering): b.rootではなく、引数で渡されたorderingを操作するようになりました。
processExpansions(o *ordering): 同様に、引数で渡されたorderingを操作し、b.expIndexマップを使用して展開のインデックスを管理するようになりました。
processContractions(o *ordering): 引数で渡されたorderingを操作し、b.ctHandleとb.ctElemマップを使用して縮約のハンドルと要素のインデックスを管理するようになりました。

これらの変更により、各ロケールのテーラリングされた照合順序に対しても、これらの処理を適用できるようになり、コードの再利用性が向上しました。

`order.go`の変更

ordering構造体にhandle *trieHandleフィールドが追加されました。これは、そのorderingに対応するTrieのハンドルを保持するために使用されます。

また、clone()メソッドでlogicalフィールドもクローンされるようになりました。

これらの変更は、照合テーブルの構築プロセスをより柔軟にし、将来的なテーラリングの実装に向けて基盤を強化するものです。特に、展開や縮約のデータ構造を効率的に再利用することで、メモリフットプリントと構築時間の削減に貢献します。

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

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

Builder構造体にexpIndex, ctHandle, ctElemの3つのマップが追加されました。これらは、展開と縮約の共通ブロックを再利用するためのインデックスとして機能します。
NewBuilder関数でこれらのマップが初期化されるようになりました。
Tailoring構造体にbuilderとindexフィールドが追加され、Tailoring関数でこれらが設定されるようになりました。
build()関数が大幅にリファクタリングされました。以前のbuildTrieのロジックがbuildOrdering関数に分離され、build()はルートと各ロケールのorderingに対してbuildOrderingを呼び出すようになりました。
buildOrdering(o *ordering)関数が新しく追加されました。この関数は、特定のorderingオブジェクトに対して、ソート、簡略化、展開処理、縮約処理、そしてTrieの構築を行います。
simplify(), processExpansions(), processContractions()の各関数が、*orderingを引数として受け取るように変更されました。これにより、これらの処理が特定のorderingインスタンスに対して適用できるようになりました。また、processExpansionsとprocessContractionsでは、Builderの新しいインデックスマップ（expIndex, ctHandle, ctElem）が使用されるようになりました。

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

TestSimplify, TestExpand, TestContractの各テスト関数で、simplify, processExpansions, processContractionsの呼び出し方が、新しい関数シグネチャに合わせて変更されました。具体的には、b.rootを直接操作するのではなく、&b.rootを引数として渡すようになりました。

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

ordering構造体にhandle *trieHandleフィールドが追加されました。これは、そのorderingに対応するTrieのハンドルを保持します。
clone()メソッドで、logicalフィールドもクローンされるように修正されました。

コアとなるコードの解説

`Builder`構造体の新しいインデックス

type Builder struct {
	// ... 既存のフィールド ...
	minNonVar int // lowest primary recorded for a variable
	varTop    int // highest primary recorded for a non-variable

	// indexes used for reusing expansions and contractions
	expIndex map[string]int      // positions of expansions keyed by their string representation
	ctHandle map[string]ctHandle // contraction handles keyed by a concatenation of the suffixes
	ctElem   map[string]int      // contraction elements keyed by their string representation
}

これらの新しいマップは、照合テーブルの構築において、展開（expansions）と縮約（contractions）の定義を効率的に再利用するために導入されました。

expIndex: 複数のロケールで同じ展開ルールが使われる場合、その展開ルールに対応するデータは一度だけ生成され、このマップにその文字列表現をキーとしてインデックスが保存されます。これにより、重複するデータの生成を防ぎ、メモリ使用量を削減します。
ctHandle: 縮約は、特定の文字シーケンスが単一の照合要素として扱われるルールです。このマップは、縮約のサフィックス（後続の文字）の組み合わせをキーとして、その縮約に対応するTrieのハンドルを保存します。これにより、共通の縮約パターンを持つロケール間でTrie構造を共有し、再利用できます。
ctElem: 縮約要素は、縮約によって生成される照合要素です。このマップは、縮約要素の文字列表現をキーとして、その要素が格納されているインデックスを保存します。これにより、同じ縮約要素が複数回出現する場合に、そのインデックスを再利用できます。

`buildOrdering`関数の導入

func (b *Builder) buildOrdering(o *ordering) {
	o.sort()
	simplify(o)
	b.processExpansions(o)   // requires simplify
	b.processContractions(o) // requires simplify

	t := newNode()
	for e := o.front(); e != nil; e, _ = e.nextIndexed() {
		if !e.skip() {
			ce, err := e.encode()
			b.error(err)
			t.insert(e.runes[0], ce)
		}
	}
	o.handle = b.index.addTrie(t)
}

このbuildOrdering関数は、照合順序の構築における中心的なロジックをカプセル化しています。以前はbuild関数内に散らばっていた処理がここに集約されました。

o.sort(): 照合順序のエントリをソートします。
simplify(o): 照合順序を簡略化します。これは、冗長なエントリを削除したり、最適化を行ったりするステップです。
b.processExpansions(o): 展開ルールを処理し、expIndexマップを使用して共通の展開をインデックス化します。
b.processContractions(o): 縮約ルールを処理し、ctHandleとctElemマップを使用して共通の縮約パターンと要素をインデックス化します。
Trieの構築: ordering内の各エントリからTrieを構築します。このTrieは、文字列の照合要素へのマッピングを効率的に検索するために使用されます。
o.handle = b.index.addTrie(t): 構築されたTrieをBuilderのインデックスに追加し、そのハンドルをorderingオブジェクトに保存します。

この関数が導入されたことで、ルートの照合順序と、各ロケールにテーラリングされた照合順序の両方に対して、同じ一連の処理を適用できるようになり、コードの再利用性と保守性が向上しました。

`build`関数のリファクタリング

func (b *Builder) build() (*table, error) {
	if b.built {
		return b.t, b.err
	}
	b.built = true
	b.t = &table{
		maxContractLen: utf8.UTFMax,
		variableTop:    uint32(b.varTop),
	}

	b.buildOrdering(&b.root) // ルートの照合順序を構築
	b.t.root = b.root.handle
	for _, t := range b.locale { // 各ロケールのテーラリングされた照合順序を構築
		b.buildOrdering(t.index)
		if b.err != nil {
			break
		}
	}
	i, err := b.index.generate()
	b.t.index = *i
	b.error(err)
	return b.t, b.err
}

新しいbuild関数は、buildOrdering関数を呼び出すことで、照合テーブル全体の構築をオーケストレーションします。まずルートの照合順序を構築し、次に登録されているすべてのロケール（b.locale）のテーラリングされた照合順序を構築します。これにより、各ロケールが独自の照合順序を持ちつつ、共通のデータブロックを効率的に共有できる基盤が確立されました。

comemo