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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate に、UTF-8文字列の最初の完全な文字と照合要素（collation element）を関連付けるためのトライ（trie）データ構造を導入するものです。これにより、国際化対応における文字列のソートや比較の効率化が図られます。

コミット

commit bcf48c797176aaecccd3001484ffefc9c31a23a8
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed Apr 25 13:16:57 2012 +0200

    exp/locale/collate: added trie for associating colElems to runes.
    The trie code looks a lot like the trie in exp/norm. It uses different
    types, however. Also, there is only a lookup for []byte and the unsafe
    lookup methods have been dropped, as well as sparse mode.
    There is now a method for generating a trie. To output Go code, one now needs
    to first generate a trie and then call print() on it.
    
    R=r, r, mpvl
    CC=golang-dev
    https://golang.org/cl/5966064

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

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

元コミット内容

exp/locale/collate パッケージに、照合要素（colElems）をルーン（runes）に関連付けるためのトライ（trie）が追加されました。このトライのコードは exp/norm パッケージのトライと多くの点で似ていますが、異なる型を使用しています。また、[]byte のルックアップのみが提供され、安全でないルックアップメソッドやスパースモードは削除されています。トライを生成するためのメソッドが追加され、Goコードとして出力するには、まずトライを生成し、その後に print() メソッドを呼び出す必要があります。

変更の背景

この変更の背景には、Go言語が国際化（i18n）と地域化（l10n）のサポートを強化する取り組みがあります。特に、異なる言語や地域における文字列のソート順序（照合順序）は、単純なバイナリ比較では対応できない複雑なルールに基づいています。例えば、ドイツ語の「ä」は「a」と「e」の間にソートされるべきであったり、特定の言語では複数の文字が単一の照合要素として扱われたりします。

このような複雑な照合ルールを効率的に処理するためには、各文字（または文字シーケンス）に対応する照合要素を高速に検索できるデータ構造が必要です。トライ（プレフィックスツリー）は、キー（ここではUTF-8バイトシーケンス）に基づいて値を検索するのに非常に適したデータ構造であり、この目的のために選択されました。

exp/locale/collate は、Go言語の標準ライブラリに国際化対応の照合機能を取り込むための実験的なパッケージであり、このコミットはその基盤となるデータ構造を整備するものです。既存の exp/norm パッケージにもトライが使用されていますが、照合の目的には異なる要件（例えば、ルックアップの型やスパースモードの有無）があるため、collate 用に特化したトライが実装されました。

前提知識の解説

トライ（Trie / Prefix Tree）

トライ（Trie、またはプレフィックスツリー）は、文字列の集合を格納し、効率的に検索するために使用される木構造のデータ構造です。各ノードは文字列のプレフィックスに対応し、ルートからノードへのパスが特定の文字列を表します。トライの主な特徴は以下の通りです。

• プレフィックス共有: 共通のプレフィックスを持つ文字列は、トライ内で共通のパスを共有します。これにより、メモリ使用量を削減し、検索効率を向上させます。
• 高速な検索: 文字列の検索は、文字列の長さに比例する時間で完了します。これは、ハッシュテーブルのようなデータ構造と比較して、衝突の心配がなく、最悪ケースのパフォーマンスが保証される点で優れています。
• 辞書順ソート: トライを深さ優先探索（DFS）で走査すると、格納されている文字列が辞書順に取得できます。

このコミットでは、UTF-8バイトシーケンスをキーとして、対応する照合要素を値として格納するトライが構築されています。

照合要素（Collation Element）

照合要素（Collation Element、略して colElem）は、Unicode Collation Algorithm (UCA) において、文字列のソート順序を決定するために使用される数値表現です。UCAは、言語や地域に依存する複雑な照合ルールを扱うための標準的なアルゴリズムであり、各文字や文字シーケンスを一つ以上の照合要素にマッピングします。

例えば、英語では「a」と「A」は同じ照合要素を持つことが多く、大文字・小文字を区別しないソートでは同じ順序になります。また、ドイツ語の「ä」は「a」とは異なる照合要素を持ち、特定のソート順序に従います。照合要素は、プライマリ、セカンダリ、ターシャリといった複数のレベルを持つことがあり、これにより大文字・小文字、アクセント、句読点などの違いを段階的に考慮したソートが可能になります。

このコミットのトライは、UTF-8バイトシーケンスから対応する colElem を効率的に取得するためのメカニズムを提供します。

UTF-8エンコーディング

UTF-8は、Unicode文字を可変長のバイトシーケンスで表現する文字エンコーディング方式です。ASCII文字は1バイトで表現され、それ以外の文字は2バイトから4バイト（最大6バイトまで定義されているが、Unicodeの現在の範囲では4バイトまで）で表現されます。

UTF-8の重要な特性は、マルチバイト文字の各バイトが特定のビットパターンを持つことです。

• 1バイト文字: 0xxxxxxx
• マルチバイト文字の最初のバイト: 110xxxxx (2バイト), 1110xxxx (3バイト), 11110xxx (4バイト)
• マルチバイト文字の継続バイト: 10xxxxxx

このコミットのトライは、UTF-8のこの特性を利用して、バイトシーケンスを段階的に処理し、対応する照合要素をルックアップします。特に、trie.go の lookup メソッドでは、c0 < tx (1バイト文字), c0 < t3 (2バイト文字), c0 < t4 (3バイト文字), c0 < t5 (4バイト文字) といった条件で、UTF-8のバイト構造に基づいて処理を分岐させています。

Go言語の exp パッケージ

Go言語の標準ライブラリには、exp というプレフィックスを持つパッケージ群が存在します。これらは「実験的（experimental）」なパッケージであり、まだ安定版として提供されていない、開発中の機能やAPIを含んでいます。exp パッケージのコードは、将来的に標準ライブラリの一部として取り込まれる可能性がありますが、APIの変更や削除が行われることもあります。

exp/locale/collate は、Go言語における国際化対応の照合機能の実験的な実装であり、このコミットはその初期段階の重要な部分を形成しています。

技術的詳細

このコミットでは、照合要素をルーンに関連付けるためのトライが src/pkg/exp/locale/collate/build と src/pkg/exp/locale/collate の2つのパッケージに分けて実装されています。

exp/locale/collate/build パッケージ

このパッケージは、トライの生成ロジックを担当します。

• trie 構造体: 最終的に生成されるトライのデータ構造を定義します。index (uint16のスライス) と values (uint32のスライス) を持ちます。index はルックアップテーブル、values は照合要素の値を格納します。
• trieNode 構造体: トライを構築する際の中間表現として使用されるノードです。table [256]*trieNode を持ち、各バイト値に対応する子ノードを指します。value はノードがリーフの場合に照合要素の値を格納し、内部ノードの場合はオフセットを格納します。
• insert(r rune, value uint32) メソッド: trieNode にルーンとそれに対応する値を挿入します。ルーンをUTF-8バイトシーケンスに変換し、各バイトをパスとしてトライを構築します。
• generate() メソッド: trieNode のツリー構造から、最終的な trie 構造体（index と values のスライス）を生成します。このプロセスでは、共通のブロックを識別し、重複を排除することで、トライのサイズを最適化します。fnv.New32() を使用してブロックのハッシュを計算し、重複するブロックを検出しています。
• print(w io.Writer, name string) メソッド: 生成されたトライの index と values のスライスをGoのソースコードとして io.Writer に出力します。これにより、生成されたトライをGoプログラムに組み込むことができます。

exp/norm のトライとの違いとして、exp/locale/collate のトライは以下の特徴を持ちます。

• 異なる型: collate のトライは colElem (uint32) を値として扱いますが、norm のトライは異なる型を扱います。
• []byte ルックアップのみ: collate のトライは []byte をキーとするルックアップに特化しており、norm のトライにあったような「安全でない（unsafe）」ルックアップメソッドは削除されています。
• スパースモードの削除: norm のトライにあったスパースモードは collate のトライにはありません。これは、照合のユースケースにおいて、特定の最適化が不要であるか、あるいは異なる最適化戦略が採用されていることを示唆します。
• 生成メソッドの追加: トライをGoコードとして出力するための generate() と print() メソッドが追加されました。これにより、トライのデータ構造をコンパイル時にGoのコードとして埋め込むことが可能になります。

exp/locale/collate パッケージ

このパッケージは、生成されたトライを使用してルックアップを実行するロジックを担当します。

• trie 構造体: build パッケージで生成された index と values のスライスを保持します。
• lookupValue(n uint16, b byte) colElem メソッド: index と values スライスを使用して、特定のバイトシーケンスに対応する colElem をルックアップします。
• lookup(s []byte) (v colElem, sz int) メソッド: UTF-8バイトシーケンス s の最初の文字に対応する colElem と、その文字のバイト長を返します。このメソッドは、UTF-8のバイト構造（1バイト、2バイト、3バイト、4バイト文字）に基づいて、トライの index と values スライスをトラバースします。不正なUTF-8シーケンスや、バイトが不足している場合には、適切なゼロ値とバイト長を返します。

この分離された設計により、トライの構築ロジックと使用ロジックが明確に区別され、コードの保守性と再利用性が向上しています。build パッケージは、照合データが更新された際に新しいトライを生成するために使用され、collate パッケージは、実行時にその生成されたトライを使用して照合を実行します。

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

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

1. src/pkg/exp/locale/collate/build/trie.go:

   • トライの構築ロジック、中間ノード (trieNode) の定義、ルーンの挿入 (insert)、最終的なトライ (trie) の生成 (generate)、およびGoコードとしての出力 (print) を含みます。
   • blockSize (64) を定数として定義し、トライのブロックサイズを管理しています。
   • fnv.New32() を使用してブロックのハッシュを計算し、重複するブロックを効率的に管理しています。

2. src/pkg/exp/locale/collate/build/trie_test.go:

   • build パッケージのトライ生成ロジックのテストコードです。
   • makeTestTrie 関数でテスト用のトライを生成し、TestGenerateTrie でその出力が期待されるGoコードと一致するかを検証しています。
   • testRunes というテストデータセットが含まれており、様々なUTF-8バイト長のルーンをカバーしています。

3. src/pkg/exp/locale/collate/trie.go:

   • 生成されたトライ (trie 構造体) の定義と、そのトライを使用して照合要素をルックアップするロジック (lookup, lookupValue) を含みます。
   • UTF-8のバイト構造を解析するための定数 (t1, tx, t2, t3, t4, t5, t6, te, maskx, mask2, mask3, mask4) が定義されています。

4. src/pkg/exp/locale/collate/trie_test.go:

   • collate パッケージのトライルックアップロジックのテストコードです。
   • TestLookupTrie 関数で、testRunes を使用した正常系のルックアップと、不正なUTF-8シーケンスや短いシーケンスに対するエラーハンドリングをテストしています。
   • tests という構造体スライスで、不正なルーンのテストケースが定義されています。

これらのファイルはすべて新規追加であり、Go言語の国際化対応における照合機能の基盤を形成しています。

コアとなるコードの解説

src/pkg/exp/locale/collate/build/trie.go

• type trie struct { index []uint16; values []uint32 }:

  • これは、最終的にGoコードとして出力され、実行時に使用されるトライのコンパクトな表現です。
  • index は、UTF-8バイトシーケンスの各バイトが次にどのブロックに進むべきかを示すオフセットを格納します。
  • values は、最終的な照合要素の値を格納します。

• type trieNode struct { table [256]*trieNode; value int64; b byte; leaf bool }:

  • トライを構築する過程で使用される一時的なノード構造です。
  • table は、現在のノードから次のバイト値に対応する子ノードへのポインタの配列です。
  • value は、ノードがリーフの場合にそのノードが表すルーンに対応する照合要素の値を保持します。内部ノードの場合は、生成プロセス中に計算されるオフセットを保持します。
  • leaf は、そのノードがルーンの終端を表すかどうかを示します。

• func (n *trieNode) insert(r rune, value uint32):

  • このメソッドは、与えられたルーン r とその照合要素 value を trieNode のツリーに挿入します。
  • ルーンを []byte(string(r)) でUTF-8バイトシーケンスに変換し、各バイトを順にたどってノードを作成または移動します。
  • シーケンスの最後のバイトに対応するノードを leaf とマークし、value を設定します。

• func (n *trieNode) generate() (t *trie, err error):

  • trieNode のツリー構造から、効率的な trie 構造体（index と values のスライス）を生成します。
  • computeOffsets 関数を再帰的に呼び出し、各ノードの value フィールドに、そのノードが表すブロックのオフセットを設定します。
  • fnv.New32() を使用してブロックのハッシュを計算し、nodeIndex 構造体で重複するブロックを検出・再利用することで、最終的なトライのサイズを最適化します。
  • genValueBlock と genLookupBlock を呼び出して、t.values と t.index スライスを構築します。

• func (t *trie) print(w io.Writer, name string) (n, size int, err error):

  • 生成された trie 構造体の内容を、Goのソースコードとして指定された io.Writer に出力します。
  • printArrays メソッドで index と values のスライスをGoの配列リテラルとして出力し、printStruct メソッドで trie 構造体の初期化コードを出力します。
  • これにより、トライのデータがGoのプログラムに直接埋め込まれ、実行時に外部ファイルを読み込む必要がなくなります。

src/pkg/exp/locale/collate/trie.go

• type trie struct { index []uint16; values []uint32 }:

  • build パッケージで生成された index と values のスライスを保持する、実行時用のトライ構造体です。

• func (t *trie) lookupValue(n uint16, b byte) colElem:

  • index スライスから得られたオフセット n と、現在のバイト b を使用して、values スライスから最終的な colElem を取得します。
  • int(n)<<6 は、blockSize (64) を考慮したブロックの開始オフセットを計算しています。int(b&maskx) は、UTF-8継続バイトの下位6ビットを抽出しています。

• func (t *trie) lookup(s []byte) (v colElem, sz int):

  • このメソッドは、UTF-8バイトシーケンス s の最初の文字に対応する照合要素 v と、その文字のバイト長 sz を返します。
  • c0 := s[0] で最初のバイトを取得し、その値に基づいて switch 文で処理を分岐させます。
  • 1バイト文字: c0 < tx (0x80未満) の場合、values[c0] を直接ルックアップし、バイト長は1です。
  • マルチバイト文字: c0 の値に応じて、2バイト、3バイト、4バイト文字の処理を行います。
    • 各バイトがUTF-8の継続バイト (tx <= cX < t2) であることを確認します。
    • index スライスを使用して、次のバイトのルックアップに使用するオフセットを取得します。
    • 最終的なバイトで lookupValue を呼び出し、colElem を取得します。
    • len(s) をチェックして、バイトが不足している場合は 0, 0 を返します。
  • 不正なルーン: 認識できないバイトシーケンスの場合、0, 1 を返します。

この lookup メソッドは、UTF-8のバイト構造を深く理解し、効率的にトライをトラバースすることで、高速な照合要素のルックアップを実現しています。

関連リンク

• Unicode Collation Algorithm (UCA): https://unicode.org/reports/tr10/
• Go言語の exp パッケージに関する議論: Go言語のメーリングリストやIssueトラッカーで exp/locale や exp/norm を検索すると、関連する議論が見つかる可能性があります。
• Go言語の国際化対応の進捗: Go言語の公式ブログやリリースノートで、国際化対応に関する情報が提供されることがあります。

参考にした情報源リンク

• コミットメッセージの内容
• Go言語の exp/locale/collate/build/trie.go および exp/locale/collate/trie.go のソースコード
• Go言語の exp/norm パッケージのトライ実装（比較のため）
• Unicode Collation Algorithm (UCA) の一般的な知識
• トライ（Trie）データ構造に関する一般的な知識
• UTF-8エンコーディングに関する一般的な知識