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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate における、照合（Collation）の「テーラリング（Tailoring）」機能の実装と、それに関連するテーブル生成の改善に関するものです。具体的には、Unicode Collation Algorithm (UCA) に基づく言語固有の並べ替え規則を動的に適用し、その結果を効率的に処理するための内部構造とアルゴリズムが強化されています。

コミット

exp/locale/collate: implementation of tailorings and table generation.
Tailorings are represented by removing and reinserting entries from a linked list.
After all tailorings are done, missing weights are computed and verified.
This implementation assumes that entries that are used in expansions are not
reinserted at a later point.  This considerably simplifies the implementation.

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

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

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

元コミット内容

exp/locale/collate: implementation of tailorings and table generation. Tailorings are represented by removing and reinserting entries from a linked list. After all tailorings are done, missing weights are computed and verified. This implementation assumes that entries that are used in expansions are not reinserted at a later point. This considerably simplifies the implementation.

変更の背景

テキストの並べ替え（ソート）は、言語や文化によってその規則が大きく異なります。例えば、同じアルファベットでも、ドイツ語の「ä」とスウェーデン語の「ä」では並べ替え順序が異なる場合があります。また、特定の文字の組み合わせ（例: スペイン語の「ch」）が単一の文字として扱われることもあります。Unicode Collation Algorithm (UCA) は、これらの複雑な言語固有の並べ替え規則を標準化するためのアルゴリズムです。

「テーラリング（Tailoring）」は、UCAの基本規則を特定の言語やロケールに合わせてカスタマイズするプロセスを指します。このコミットの背景には、exp/locale/collate パッケージが、より正確で言語に特化したテキスト照合機能を提供するために、これらのテーラリングを効率的かつ堅牢に処理できる必要があったという点があります。特に、動的なテーラリングの適用と、それによって生じる照合要素（Collation Element）の重み（Weight）の再計算が課題となっていました。

前提知識の解説

• Unicode Collation Algorithm (UCA): Unicode Consortiumによって定義された、多言語テキストの並べ替え（照合）のための標準アルゴリズム。言語や文化に依存する並べ替え規則を扱うための枠組みを提供します。UCAは、文字を直接比較するのではなく、「照合要素（Collation Element）」と呼ばれる数値のシーケンスに変換し、その照合要素を比較することで並べ替えを行います。
• 照合要素 (Collation Element): UCAにおいて、各文字または文字のシーケンスに割り当てられる数値の組。通常、プライマリ（Primary）、セカンダリ（Secondary）、ターシャリ（Tertiary）の3つのレベルの重み（Weight）を持ちます。
  • プライマリ重み: 大まかな文字の順序（例: 'a' と 'b' の違い）。
  • セカンダリ重み: アクセントやダイアクリティカルマークの違い（例: 'a' と 'á' の違い）。
  • ターシャリ重み: 大文字・小文字や幅の違い（例: 'a' と 'A' の違い、全角と半角の違い）。
• テーラリング (Tailoring): UCAのデフォルトの照合順序を、特定の言語や文化の慣習に合わせて変更するプロセス。例えば、特定の文字の重みを変更したり、文字の並べ替え順序を入れ替えたり、複数の文字を単一の照合要素として扱ったりします。
• Common Locale Data Repository (CLDR): Unicode Consortiumが提供する、ロケール（言語、地域、文化）に関するデータのリポジトリ。UCAのテーラリング規則もCLDRに含まれており、多くの国際化ライブラリで利用されています。
• 連結リスト (Linked List): データ構造の一つで、各要素（ノード）が次の要素への参照（ポインタ）を持つことで、要素が線形に連結されているもの。要素の挿入や削除が効率的に行える特徴があります。

技術的詳細

このコミットの主要な技術的変更点は、テーラリングの内部表現と処理ロジックにあります。

1. 連結リストによるテーラリング表現:

   • コミットメッセージにある通り、テーラリングは「連結リストからのエントリの削除と再挿入」によって表現されます。これは、照合要素の順序を動的に変更するために、既存の照合要素のリストを連結リストとして扱い、その中で要素の位置を操作することを意味します。
   • order.go の entry 構造体に prev, next, level フィールドが追加され、連結リストのノードとしての機能が強化されています。
   • insertAfter および insertBefore メソッドが entry に追加され、連結リスト内での要素の挿入操作を可能にしています。
   • Tailoring 構造体には anchor (挿入の基準となるエントリ) と before (アンカーの前か後か) のフィールドが追加され、テーラリングの挿入位置を制御します。

2. 重みの計算と検証:

   • テーラリングが適用された後、欠落している照合要素の重み（elems）が計算され、検証されます。これは、テーラリングによって新しい照合順序が導入された場合、その順序がUCAの規則に適合しているか、重みの衝突がないかなどを確認するプロセスです。
   • ordering 構造体に getWeight メソッドが追加され、各エントリの照合要素の重みを動的に取得するロジックが実装されています。特に、implicit (暗黙的に導出される) なエントリや before (前挿入) の場合の重み計算ロジックが含まれています。
   • verifyWeights メソッドが追加され、隣接するエントリ間の重みが適切に順序付けられているか（オーバーフローがないか）を検証します。

3. テーブル生成の改善:

   • tables.go の mainExpandElem 配列のサイズが大幅に増加しており、これは生成される照合テーブルのデータ量が大幅に増えたことを示しています。これは、より多くのロケールや複雑なテーラリングに対応するために、内部データ構造が拡張された結果と考えられます。
   • availableLocales と locales マップのオフセット値が変更されており、新しいテーブル構造に合わせてデータ参照が更新されています。

4. 簡素化の仮定:

   • コミットメッセージには「この実装は、拡張で使用されるエントリが後で再挿入されないことを前提としている。これにより、実装が大幅に簡素化される。」とあります。これは、照合要素の拡張（例: 「æ」が「a」と「e」に展開される場合）に関わるエントリが、テーラリングによってリスト内で再配置されることがないという重要な仮定を示しています。この仮定により、アルゴリズムの複雑性が軽減されています。

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

• src/pkg/exp/locale/collate/build/builder.go:
  • Tailoring 構造体に anchor と before フィールドが追加。
  • setAnchor, SetAnchor, SetAnchorBefore メソッドが追加され、テーラリングの挿入位置を設定する機能が実装。
  • Insert メソッドが大幅に拡張され、連結リスト操作によるテーラリングのコアロジックが実装。
  • getWeight, addExtension, verifyWeights メソッドが追加され、重み計算と検証ロジックが導入。
  • buildOrdering 関数内で getWeight と addExtension が呼び出されるように変更。
• src/pkg/exp/locale/collate/build/order.go:
  • entry 構造体に extend, before, lock, skipRemove, implicit フィールドが追加され、テーラリングと重み計算のための状態が追加。
  • nextIndexed メソッドのロジックが変更され、exclude だけでなく len(e.elems) == 0 のエントリもスキップするように。
  • remove メソッドのロジックが変更され、skipRemove フラグが導入。
  • insertBefore メソッドが新しく追加。
  • ordering 構造体に id フィールドが追加。
  • insert メソッドのロジックが変更され、論理アンカー（logical）を持つエントリの処理が追加。
  • patchForInsert メソッドが追加され、挿入のためのリストのパッチ処理を実装。
  • clone メソッド内で patchForInsert が呼び出されるように変更。
• src/pkg/exp/locale/collate/build/order_test.go:
  • TestInsertBefore という新しいテストケースが追加され、insertBefore メソッドの動作を検証。
• src/pkg/exp/locale/collate/tables.go:
  • availableLocales と locales マップのデータが更新され、特に mainExpandElem のサイズが大幅に増加。これは、生成される照合テーブルのデータが拡張されたことを示します。

コアとなるコードの解説

このコミットの核心は、src/pkg/exp/locale/collate/build/builder.go の Insert メソッドと、src/pkg/exp/locale/collate/build/order.go の entry 構造体およびその関連メソッドに集約されます。

builder.go の Insert メソッド: このメソッドは、特定の照合レベル (level) で、指定された文字列 (str) を現在のテーラリングのアンカーポイント (t.anchor) の前または後に挿入する役割を担います。

func (t *Tailoring) Insert(level collate.Level, str, extend string) error {
	if t.anchor == nil {
		return fmt.Errorf("%s:Insert: no anchor point set for tailoring of %s", t.id, str)
	}
	str = norm.NFD.String(str) // 文字列を正規化
	e := t.index.find(str)     // 既存のエントリを検索
	if e == nil {
		e = t.index.newEntry(str, nil) // なければ新しいエントリを作成
	} else if e.logical != noAnchor {
		return fmt.Errorf("%s:Insert: cannot reinsert logical reset position %q", t.id, e.str)
	}
	if e.lock {
		return fmt.Errorf("%s:Insert: cannot reinsert element %q", t.id, e.str)
	}
	a := t.anchor // アンカーエントリを取得

	// アンカーからの相対的な挿入位置を決定し、連結リストを操作
	e.before = t.before
	if t.before {
		// アンカーの前に挿入する場合
		t.before = false // 次の挿入はデフォルトでアンカーの後
		if a.prev == nil {
			a.insertBefore(e) // リストの先頭に挿入
		} else {
			// 指定されたレベルより小さいか等しいレベルで異なる最初の要素を見つけ、その後に挿入
			for a = a.prev; a.level > level; a = a.prev {
			}
			a.insertAfter(e)
		}
		e.level = level // 新しいエントリのレベルを設定
	} else {
		// アンカーの後に挿入する場合
		// 指定されたレベルより小さいか等しいレベルで異なる最初の要素を見つけ、その前に挿入
		for ; a.level > level; a = a.next {
		}
		e.level = a.level // 新しいエントリのレベルをアンカーのレベルに設定
		if a != e {
			a.insertAfter(e) // アンカーの後に挿入
			a.level = level  // アンカーのレベルを更新
		} else {
			// アンカー自体を再挿入する場合の特殊処理
			a.prev.level = level
		}
	}
	e.extend = norm.NFD.String(extend) // 拡張文字列を設定
	e.exclude = false                  // テーブルに含める
	e.elems = nil                      // 照合要素をリセット（後で再計算）
	t.anchor = e                       // 新しいアンカーを挿入されたエントリに設定
	return nil
}

この Insert メソッドは、UCAのテーラリング規則（特に「reset」ディレクティブと挿入ロジック）を直接反映しています。連結リストの entry オブジェクトを操作することで、文字の並べ替え順序を動的に変更し、新しい照合要素の重みを割り当てる準備をします。

order.go の entry 構造体と insertBefore/insertAfter: entry 構造体は、個々の照合要素を表すだけでなく、連結リストのノードとしての役割も果たします。

type entry struct {
	str    string // same as string(runes)
	runes  []rune
	elems  [][]int // the collation elements
	extend string  // weights of extend to be appended to elems
	before bool    // weights relative to next instead of previous.
	lock   bool    // entry is used in extension and can no longer be moved.

	// prev, next, and level are used to keep track of tailorings.
	prev, next *entry
	level      collate.Level // next differs at this level
	skipRemove bool          // do not unlink when removed

	decompose bool // can use NFKD decomposition to generate elems
	exclude   bool // do not include in table
	implicit  bool // derived, is not included in the list
	logical   logicalAnchor

	expansionIndex    int // used to store index into expansion table
	contractionHandle uint32
	contractionIndex  int // used to store index into contraction table
}

// insertAfter inserts n after e.
func (e *entry) insertAfter(n *entry) {
	// ... (省略) ...
	n.next = e.next
	n.prev = e
	if e.next != nil {
		e.next.prev = n
	}
	e.next = n
}

// insertBefore inserts n before e.
func (e *entry) insertBefore(n *entry) {
	// ... (省略) ...
	n.prev = e.prev
	n.next = e
	if e.prev != nil {
		e.prev.next = n
	}
	e.prev = n
}

これらのメソッドは、entry オブジェクトを連結リスト内で効率的に移動させるための基本的な操作を提供します。テーラリングのロジックは、これらの低レベルなリスト操作を組み合わせて、複雑な並べ替え規則を実装しています。

重み計算 (getWeight) と検証 (verifyWeights): getWeight は、テーラリングによって変更された順序に基づいて、各エントリの最終的な照合要素の重みを決定します。特に、before フラグが設定されている場合（アンカーの前に挿入された場合）の重み計算ロジックは、UCAの複雑な規則を反映しています。verifyWeights は、計算された重みがUCAの要件（例えば、重みが単調増加であること）を満たしていることを確認し、潜在的なエラー（オーバーフローなど）を検出します。

これらの変更により、exp/locale/collate パッケージは、Unicode Collation Algorithmの複雑なテーラリング要件をより正確かつ効率的に処理できるようになり、多言語環境でのテキスト並べ替えの精度が向上しました。

関連リンク

• Unicode Collation Algorithm (UCA)
• Common Locale Data Repository (CLDR)
• Go言語の x/text/collate パッケージ (この exp/locale/collate は、後に x/text/collate に統合された実験的なパッケージです)

参考にした情報源リンク

• Go.dev - golang.org/x/text/collate
• appspot.com - Go Collation Design Document (これは golang.org/x/text/collate の設計ドキュメントであり、このコミットの背景にある概念を理解するのに役立ちます)
• PostgreSQL Documentation - ICU Collation (テーラリングの概念を理解するための一般的な情報源として)