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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate における照合要素（collation elements）の挙動を微調整するものです。具体的には、二次的な照合値がデフォルト値よりも小さくなることを許容し、中国語などで使用される「beforeタグ」をサポートするための変更と、重みが増加した後に重要でなくなる照合要素を排除する最適化が含まれています。

コミット

commit b575e3ca99501448cf6bed6e82a83f9a99d938d8
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Thu Oct 25 13:02:31 2012 +0200

    exp/locale/collate: slightly changed collation elements:
    - Allow secondary values below the default value in second form. This is
      to support before tags for secondary values, as used by Chinese.
    - Eliminate collation elements that are guaranteed to be immaterial
      after a weight increment.
    
    R=r
    CC=golang-dev
    https://golang.org/cl/6739051

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

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

元コミット内容

exp/locale/collate: slightly changed collation elements:

二次的な値がデフォルト値よりも小さくなることを、セカンドフォームで許可する。これは、中国語などで使用される二次的な値に対する「beforeタグ」をサポートするためである。
重みが増加した後に重要でなくなることが保証される照合要素を排除する。

変更の背景

このコミットは、Go言語の国際化（i18n）機能の一部である照合（Collation）メカニズムの改善を目的としています。照合とは、異なる言語や文化圏における文字列のソート順を定義するプロセスです。Unicode Collation Algorithm (UCA) は、この照合の国際標準を提供しており、Goのexp/locale/collateパッケージはこのUCAを実装しています。

変更の背景には、主に以下の2点があります。

中国語の照合要件への対応: 中国語のような一部の言語では、特定の文字のソート順を微調整するために「beforeタグ」という概念が使用されます。これは、ある文字が別の文字の「前」にソートされるべきであることを示すためのメカニズムです。従来の照合要素のエンコーディングでは、二次的な値がデフォルト値より小さくなることを許容していなかったため、この「beforeタグ」を正確に表現できませんでした。このコミットは、この制約を取り除き、より正確な中国語の照合を可能にすることを目的としています。
照合要素の最適化: 照合プロセスでは、各文字または文字シーケンスに対して複数の「重み」（プライマリ、セカンダリ、ターシャリなど）が割り当てられます。これらの重みは、ソートの優先順位を決定します。特定の状況下では、ある重みが増加した後に、それ以降の重み（例えば、プライマリ重みが増加した後のセカンダリ重みやターシャリ重み）がソート順に影響を与えなくなることがあります。このような「重要でない」照合要素を排除することで、照合データのサイズを削減し、パフォーマンスを向上させることができます。

前提知識の解説

照合 (Collation)

照合とは、文字列を特定の言語や文化の規則に従ってソートするプロセスです。単に文字コード順にソートするのではなく、アクセント記号の有無、大文字・小文字の区別、特定の文字の組み合わせ（合字など）の扱い、言語固有のソート順（例: ドイツ語のäはaとbの間、またはaeとして扱われる）などを考慮します。

Unicode Collation Algorithm (UCA)

UCAは、Unicode Consortiumによって定義された、国際的な照合のための標準アルゴリズムです。UCAは、各文字に「照合要素（Collation Element, CE）」と呼ばれる一連の重み（通常はプライマリ、セカンダリ、ターシャリの3つのレベル）を割り当てます。

プライマリ重み (Primary Weight): 文字の基本的な形状や文字種を区別します。例えば、aとbは異なるプライマリ重みを持ちます。これは最も重要なソートレベルです。
セカンダリ重み (Secondary Weight): アクセント記号やダイアクリティカルマーク（分音記号）の違いを区別します。例えば、aとáは同じプライマリ重みを持つが、異なるセカンダリ重みを持ちます。
ターシャリ重み (Tertiary Weight): 大文字・小文字の違いや、文字の幅（全角・半角）などを区別します。例えば、aとAは同じプライマリ重みとセカンダリ重みを持つが、異なるターシャリ重みを持ちます。
クォータナリ重み (Quaternary Weight): 一部の言語（日本語など）で、句読点や記号の扱いを区別するために使用されることがあります。

照合要素 (Collation Element, CE)

UCAでは、各文字または文字シーケンスは、複数の重み（プライマリ、セカンダリ、ターシャリなど）の組み合わせで表現される「照合要素」に変換されます。これらの照合要素のシーケンスを比較することで、文字列のソート順が決定されます。

UCAには、特定の照合要素が他の要素の「前」にソートされるべきであることを示すための「beforeタグ」という概念があります。これは、特に中国語のソート規則で重要になります。例えば、中国語のピンインソートでは、同じ発音の異なる漢字が、特定の順序でソートされる必要があります。beforeタグは、この微細なソート順の調整を可能にします。技術的には、セカンダリ重みやターシャリ重みに、デフォルト値よりも小さい値（負の値や、特定の予約された範囲の値）を割り当てることで表現されます。

重みのインクリメントと「重要でない」照合要素

照合要素のシーケンスを比較する際、あるレベルの重みが異なると、それより下位のレベルの重みはソート結果に影響を与えなくなります。例えば、プライマリ重みが異なる2つの文字列がある場合、セカンダリ重みやターシャリ重みがどうであれ、プライマリ重みによってソート順が決定されます。この場合、プライマリ重みが異なった時点で、それ以降のセカンダリやターシャリの照合要素は「重要でない（immaterial）」と見なすことができます。このような要素をデータから排除することで、照合データの効率化が図れます。

技術的詳細

このコミットは、exp/locale/collateパッケージ内の照合要素のエンコーディングと処理ロジックに焦点を当てています。

二次的な値の「beforeタグ」サポート:
- src/pkg/exp/locale/collate/build/colelem.goのmakeCE関数は、照合要素を構築する際に、二次的な重み（weights[1]）を処理します。
- 変更前は、d := weights[1] - defaultSecondaryとして、二次的な重みの差分を計算していました。ここでdが負の値になることを許容していなかったため、defaultSecondaryよりも小さい二次的な値を表現できませんでした。
- 変更後、d := weights[1] - defaultSecondary + 4とすることで、dの計算にオフセット+4が導入されました。これにより、weights[1]がdefaultSecondaryよりも小さい値を取る場合でも、dが非負の範囲に収まるように調整され、beforeタグを表現するための負のオフセットを間接的にサポートできるようになりました。この+4というオフセットは、defaultSecondaryより小さい4つの値（defaultSecondary-1からdefaultSecondary-4）を表現するために使用されます。
- src/pkg/exp/locale/collate/colelem.goのsplitCE関数では、このエンコーディングに対応するため、w.secondary = defaultSecondary + uint16(ce&0xF) - 4と、デコード時に-4のオフセットを適用して元の二次的な値を復元します。
重要でない照合要素の排除:
- src/pkg/exp/locale/collate/build/colelem.goのnextWeight関数は、与えられた照合要素のシーケンスの次に続く可能性のある照合重みを計算します。
- 変更前は、単に現在の要素をコピーし、指定されたレベルの重みをインクリメントしていました。
- 変更後、nextWeight関数は、level（プライマリ、セカンダリ、ターシャリ）がインクリメントされた後に、ソート順に影響を与えない（重要でない）照合要素をフィルタリングするロジックが追加されました。
- 具体的には、for _, ce := range elems[1:]ループで、現在の要素以外の後続の照合要素を調べます。
- skip := trueで初期化し、for i := collate.Primary; i < level; i++ { skip = skip && ce[i] == 0 }という条件で、現在のlevelよりも上位の重み（プライマリ、セカンダリなど）がすべてゼロであるかどうかをチェックします。もし上位の重みがすべてゼロであれば、その照合要素は「重要でない」と判断され、!skipがfalseとなり、nextスライスに追加されません。
- この最適化により、照合データのサイズが削減され、照合処理の効率が向上します。

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

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

--- a/src/pkg/exp/locale/collate/build/colelem.go
+++ b/src/pkg/exp/locale/collate/build/colelem.go
@@ -70,7 +70,7 @@ func makeCE(weights []int) (uint32, error) {
 			ce = uint32(weights[0]<<maxSecondaryCompactBits + weights[1])
 			ce |= isPrimary
 		} else {
-			d := weights[1] - defaultSecondary
+			d := weights[1] - defaultSecondary + 4
 			if d >= 1<<maxSecondaryDiffBits || d < 0 {
 				return 0, fmt.Errorf("makeCE: secondary weight diff out of bounds: %x < 0 || %x > %x", d, d, 1<<maxSecondaryDiffBits)
 			}
@@ -258,21 +258,31 @@ func convertLargeWeights(elems [][]int) (res [][]int, err error) {
 // nextWeight computes the first possible collation weights following elems
 // for the given level.
 func nextWeight(level collate.Level, elems [][]int) [][]int {
-	nce := make([][]int, len(elems))
-	copy(nce, elems)
-
-	if level != collate.Identity {
-		nce[0] = make([]int, len(elems[0]))
-		copy(nce[0], elems[0])
-		nce[0][level]++
-		if level < collate.Secondary {
-			nce[0][collate.Secondary] = defaultSecondary
+	if level == collate.Identity {
+		next := make([][]int, len(elems))
+		copy(next, elems)
+		return next
+	}
+	next := [][]int{make([]int, len(elems[0]))}
+	copy(next[0], elems[0])
+	next[0][level]++
+	if level < collate.Secondary {
+		next[0][collate.Secondary] = defaultSecondary
+	}
+	if level < collate.Tertiary {
+		next[0][collate.Tertiary] = defaultTertiary
+	}
+	// Filter entries that cannot influence ordering.
+	for _, ce := range elems[1:] {
+		skip := true
+		for i := collate.Primary; i < level; i++ {
+			skip = skip && ce[i] == 0
 		}
-		if level < collate.Tertiary {
-			nce[0][collate.Tertiary] = defaultTertiary
+		if !skip {
+			next = append(next, ce)
 		}
-	}
-	return nce
+	}
+	return next
 }
 
 func nextVal(elems [][]int, i int, level collate.Level) (index, value int) {

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

--- a/src/pkg/exp/locale/collate/colelem.go
+++ b/src/pkg/exp/locale/collate/colelem.go
@@ -93,7 +93,7 @@ func splitCE(ce colElem) weights {
 	} else if ce&secondaryMask == 0 {
 		w.tertiary = uint8(ce & 0x1F)
 		ce >>= 5
-		w.secondary = defaultSecondary + uint16(ce&0xF)
+		w.secondary = defaultSecondary + uint16(ce&0xF) - 4
 		ce >>= 4
 		w.primary = uint32(ce)
 	} else {

`src/pkg/exp/locale/collate/build/colelem_test.go` および `src/pkg/exp/locale/collate/colelem_test.go`

これらのファイルでは、上記の変更に対応するためのテストケースの修正が行われています。特に、ceTestsにおける期待される照合要素の値の変更や、TestNextWeight関数におけるextra変数の定義変更とテストロジックの拡張が見られます。これにより、新しい照合要素のエンコーディングとnextWeight関数のフィルタリングロジックが正しく機能するか検証しています。

コアとなるコードの解説

`src/pkg/exp/locale/collate/build/colelem.go` の `makeCE` 関数

この関数は、与えられた重み（プライマリ、セカンダリ、ターシャリなど）から単一の照合要素（uint32）を構築します。

// 変更前:
// d := weights[1] - defaultSecondary
// 変更後:
d := weights[1] - defaultSecondary + 4

この変更は、二次的な重みweights[1]がdefaultSecondaryよりも小さい値を取ることを可能にするためのものです。defaultSecondaryは通常、二次的な重みの「基準」となる値ですが、beforeタグを表現するためには、この基準値よりも小さい値が必要になります。+4というオフセットを加えることで、weights[1]がdefaultSecondary - 4からdefaultSecondary - 1の範囲にある場合でも、dが0から3の範囲に収まり、既存のエンコーディングスキーム内で負のオフセットを表現できるようになります。

`src/pkg/exp/locale/collate/build/colelem.go` の `nextWeight` 関数

この関数は、照合要素のシーケンスが与えられたときに、指定されたレベル（プライマリ、セカンダリなど）で重みをインクリメントした後の、次に続く可能性のある照合重みのシーケンスを計算します。

// 変更前:
// nce := make([][]int, len(elems))
// copy(nce, elems)
// if level != collate.Identity {
//     // ... 重みのインクリメント ...
// }
// return nce

// 変更後:
if level == collate.Identity {
    next := make([][]int, len(elems))
    copy(next, elems)
    return next
}
next := [][]int{make([]int, len(elems[0]))}
copy(next[0], elems[0])
next[0][level]++
if level < collate.Secondary {
    next[0][collate.Secondary] = defaultSecondary
}
if level < collate.Tertiary {
    next[0][collate.Tertiary] = defaultTertiary
}
// Filter entries that cannot influence ordering.
for _, ce := range elems[1:] {
    skip := true
    for i := collate.Primary; i < level; i++ {
        skip = skip && ce[i] == 0
    }
    if !skip {
        next = append(next, ce)
    }
}
return next

この変更の主要な部分は、// Filter entries that cannot influence ordering.とコメントされた部分です。これは、重みが増加した後にソート順に影響を与えない照合要素を排除するための最適化です。

level == collate.Identityの場合（つまり、重みをインクリメントしない場合）、元の要素をそのまま返します。
それ以外の場合、まず最初の要素の指定されたlevelの重みをインクリメントし、それより下位の重み（セカンダリ、ターシャリ）をデフォルト値にリセットします。
次に、元のelemsの2番目以降の要素（elems[1:]）をループ処理します。
skipフラグは、現在の照合要素がスキップされるべきかどうかを示します。
for i := collate.Primary; i < level; i++ { skip = skip && ce[i] == 0 }のループでは、現在の照合要素ceの、インクリメント対象のlevelよりも上位の重み（プライマリ、セカンダリなど）がすべてゼロであるかをチェックします。
- もし、上位の重みがすべてゼロであれば、その照合要素は「重要でない」（つまり、ソート順に影響を与えない）と判断され、skipはtrueのままになります。
- もし、上位の重みのいずれかがゼロでなければ、その照合要素はソート順に影響を与える可能性があるため、skipはfalseになります。
if !skip { next = append(next, ce) }の条件により、skipがfalse（つまり、重要である）と判断された照合要素のみが結果のnextスライスに追加されます。

このフィルタリングにより、照合データの冗長性が減り、照合処理の効率が向上します。

`src/pkg/exp/locale/collate/colelem.go` の `splitCE` 関数

この関数は、単一の照合要素（colElem）をその構成要素である重み（プライマリ、セカンダリ、ターシャリ）に分解します。

// 変更前:
// w.secondary = defaultSecondary + uint16(ce&0xF)
// 変更後:
w.secondary = defaultSecondary + uint16(ce&0xF) - 4

この変更は、makeCE関数で行われたエンコーディングの変更に対応するものです。makeCEで+4のオフセットが加えられたため、splitCEでデコードする際には、そのオフセットを - 4することで元の二次的な重み値を正確に復元します。ce&0xFは、エンコードされた二次的な重みの差分（0-15の範囲）を取り出します。

参考にした情報源リンク

Unicode Collation Algorithm (UCA) の公式ドキュメント
Go言語のgolang.org/x/text/collateパッケージのドキュメントとソースコード (現在の実装を理解するため)
中国語の照合に関する情報源 (特にピンインソートとbeforeタグの概念)
Gitのコミットログと差分表示
Go言語のexpパッケージの目的と歴史に関する情報

comemo