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

このコミットは、Go言語の実験的なロケールパッケージ exp/locale/collate に、Unicode Collation Algorithm (UCA) における「Contraction（縮約）」を検出するためのトライ（trie）の実装を追加します。具体的には、トライの構築ロジックと、そのトライを使用して入力文字列から縮約を効率的に検索するランタイムロジックが導入されています。

コミット

commit e456d015fb670b82554284d74c5b88ee278b6f08
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Wed Apr 25 13:15:48 2012 +0200

    exp/locale/collate: implementation of trie that is used for detecting contractions.
    (See http://www.unicode.org/reports/tr10/#Contractions.)  Each rune that is at the
    start of any contraction is associated a trie. This trie, in turn, may be shared
    by other runes that have the same set of suffixes.
    
    R=r, r
    CC=golang-dev
    https://golang.org/cl/5970066

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

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

元コミット内容

exp/locale/collate: 縮約検出に使用されるトライの実装。 (http://www.unicode.org/reports/tr10/#Contractions を参照。) 各縮約の開始ルーンにはトライが関連付けられます。このトライは、同じサフィックスのセットを持つ他のルーンと共有される場合があります。

変更の背景

このコミットは、Go言語の国際化（i18n）およびローカライゼーション（l10n）機能の一部として、Unicode Collation Algorithm (UCA) の正確な実装をサポートするために行われました。UCAは、異なる言語や文化圏での文字列のソート順序を定義するための標準です。UCAの重要な側面の一つに「Contractions（縮約）」があります。これは、複数の文字シーケンスが単一の照合要素として扱われる場合を指します。例えば、ドイツ語の "ch" やスペイン語の "ll" などがこれに該当します。

これらの縮約を効率的かつ正確に検出するためには、特殊なデータ構造が必要です。このコミットでは、この目的のためにトライ（プレフィックスツリー）データ構造が導入されました。トライを使用することで、入力文字列を走査しながら、可能な限り長い縮約を効率的に見つけることができます。これにより、UCAのルールに厳密に従った正しい文字列の照合順序を実現するための基盤が提供されます。

前提知識の解説

Unicode Collation Algorithm (UCA)

Unicode Collation Algorithm (UCA) は、Unicode文字列を言語的に正しい順序でソートするための標準アルゴリズムです。単なるコードポイント順のソートではなく、言語固有のルール（例: アクセント記号の扱い、大文字小文字の区別、特定の文字シーケンスの扱い）を考慮に入れます。UCAは、国際化されたアプリケーションでテキストデータを正しくソートするために不可欠です。

照合要素 (Collation Element)

UCAでは、各文字または文字シーケンスは一つ以上の「照合要素」にマッピングされます。これらの照合要素は、ソートの際に比較される数値のシーケンスです。例えば、"a" と "A" は異なる照合要素を持つかもしれませんが、多くの言語では同じ主要な照合要素を持ち、大文字小文字の区別は二次的な要素として扱われます。

Contractions (縮約)

縮約は、UCAにおける特別なケースで、複数の文字シーケンスが単一の照合要素として扱われることを指します。これは、特定の言語において、複数の文字が組み合わさって一つの音や概念を表す場合に発生します。例えば、ドイツ語の "ch" は、"c" と "h" の個別の照合要素ではなく、"ch" 全体で一つの照合要素を持つことがあります。UCAのルールでは、常に「最長一致」の原則が適用されます。つまり、複数の縮約が可能な場合、最も長い縮約が優先されます。

Trie (トライ / プレフィックスツリー)

トライは、文字列の集合を効率的に格納し、検索するために使用されるツリーベースのデータ構造です。各ノードは文字列のプレフィックスを表し、ルートからノードへのパスが文字列を形成します。トライは、共通のプレフィックスを持つ文字列を効率的にグループ化できるため、プレフィックス検索や、このコミットのように最長一致のパターンマッチングに非常に適しています。

技術的詳細

このコミットで導入されたトライの実装は、UCAの縮約検出に特化しています。主な技術的ポイントは以下の通りです。

1. ctEntry 構造体:

   • トライの各ノードを表すエントリです。
   • l (lowest match): マッチするバイトの最小値（非終端ノードの場合）または範囲の最小値（終端ノードの場合）。
   • h (highest match): 次のブロックへの相対インデックス（非終端ノードの場合）または範囲の最大値（終端ノードの場合）。
   • n (next block length): 次のブロックの長さ（非終端ノードの場合）または0（終端ノードの場合）。
   • i (result offset): 結果のオフセット。0xFF の場合、さらにバイトが必要であることを示す。
   • このコンパクトな構造体により、トライのメモリフットプリントが削減されます。

2. contractTrieSet 型:

   • ctEntry のスライスであり、複数の縮約トライを連続して格納します。
   • これにより、関連するトライを効率的に管理できます。

3. トライの構築 (appendTrie, genStates):

   • appendTrie は、与えられたサフィックスのセットから新しいトライを構築し、contractTrieSet に追加します。
   • genStates は、特定のサフィックスセットに対して ctEntry のシーケンスを生成します。
   • 構築プロセスでは、サフィックスをソートし、共通のプレフィックスを持つものを効率的にグループ化してトライ構造を最適化します。特に、offsetSort と genidxSort というカスタムソートロジックが使用され、バイト範囲としてパックできるサフィックスを連続して配置したり、最長一致の原則をサポートするために長い文字列を短い文字列の前に配置したりします。

4. トライの検索 (lookup in build, ctScanner in collate):

   • build/contract.go の lookup 関数は、構築されたトライに対して特定のバイトシーケンスを検索し、最長一致するサフィックスのインデックスと消費されたバイト数を返します。
   • collate/contract.go の ctScanner は、ランタイムでトライを使用して入力文字列を走査し、縮約を検出するためのステートフルなスキャナーを提供します。
   • ctScanner の scan メソッドは、入力シーケンス内の現在の位置から最長一致するサフィックスを検索します。UCAのルールに従い、非ブロッキングの非スターター（結合文字など）をスキップする可能性も考慮されていますが、この実装ではユーザーが適切なポイントでマッチを継続するように任されています。

5. コード生成 (print 関数):

   • build/contract.go には、構築されたトライをGoのソースコードとして出力する print 関数が含まれています。これにより、ビルド時にトライのデータ構造を生成し、アプリケーションに組み込むことができます。これは、実行時にトライを動的に構築するのではなく、コンパイル時に固定データとして埋め込む一般的なパターンです。

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

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

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

   • トライのデータ構造 (ctEntry, contractTrieSet) の定義。
   • トライを構築するための主要なロジック (appendTrie, genStates)。
   • 構築されたトライを検索するための lookup 関数。
   • トライをGoコードとして出力するための print 関数。

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

   • build/contract.go で定義されたトライ構築ロジックと検索ロジックの単体テスト。
   • ソートアルゴリズム (offsetSort, genidxSort, entrySort) のテスト。
   • トライの生成 (genStateTests, TestGenStates) と検索 (TestLookupContraction) のテストケース。
   • 生成されたGoコードのテスト (TestPrintContractionTrieSet)。

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

   • ランタイムで使用される contractTrieSet の再定義（build パッケージとは異なるパッケージのため）。
   • トライを使用して入力文字列をスキャンするための ctScanner 構造体。
   • ctScanner のメソッド (scanner, result, scan)。

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

   • collate/contract.go で定義されたランタイム検索ロジックの単体テスト。
   • lookupTests と TestLookupContraction で、ctScanner を使用した縮約の検索を検証。

コアとなるコードの解説

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

このファイルは、縮約トライの「ビルド時」の側面を扱います。

• ctEntry:

  type ctEntry struct {
      l uint8 // non-final: byte value to match; final: lowest match in range.
      h uint8 // non-final: relative index to next block; final: highest match in range.
      n uint8 // non-final: length of next block; final: 0
      i uint8 // result offset. Will be 0xFF if more bytes are needed to complete.
  }
  

  この構造体は、トライの各ノードを表します。l と h はマッチするバイトの範囲を定義し、n は次の状態ブロックの長さを、i はマッチが完了した場合のオフセット（結果）を示します。0xFF は、さらにバイトが必要であることを示します。

• appendTrie と genStates: これらの関数は、与えられたサフィックスのリストからトライを構築する中心的なロジックです。genStates は再帰的に呼び出され、各レベルで共通のプレフィックスを持つサフィックスを処理し、ctEntry のシーケンスを生成します。ソートアルゴリズム (offsetSort, genidxSort) は、トライの効率的な表現を可能にするために重要です。特に、offsetSort は、バイト範囲としてパックできるサフィックスを連続して配置し、genidxSort は、最長一致の原則をサポートするために、より長いサフィックスを短いサフィックスの前に配置します。

• lookup:

  func (ct *contractTrieSet) lookup(h ctHandle, str []byte) (index, ns int) {
      states := (*ct)[h.index:]
      p := 0
      n := h.n
      for i := 0; i < n && p < len(str); {
          e := states[i]
          c := str[p]
          if c >= e.l {
              p++
              if e.l == c {
                  if e.i != 0xFF {
                      index, ns = int(e.i), p
                  }
                  if e.n != 0 {
                      // set to new state
                      i, states, n = 0, states[e.h:], int(e.n)
                  } else {
                      return
                  }
              } else if e.n == 0 && c <= e.h {
                  return int(c-e.l) + int(e.i), p
              }
          } else {
              i++
          }
      }
      return
  }
  

  この関数は、バイトシーケンス str をトライ ct で検索し、最長一致する縮約を見つけます。e.i != 0xFF の条件は、現在のマッチが完全な縮約である可能性を示し、e.n != 0 は、さらにバイトを読み進めてより長い縮約を検索する必要があることを示します。

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

このファイルは、縮約トライの「ランタイム」の側面を扱います。

• ctScanner:

  type ctScanner struct {
      states contractTrieSet
      s      []byte
      n      int
      index  int
      pindex int
      done   bool
  }
  

  ctScanner は、入力文字列をスキャンして縮約を検出するためのステートフルなオブジェクトです。states は現在のトライの状態（contractTrieSet の一部）、s は入力バイトスライス、n は現在の状態ブロックの長さ、index は現在のマッチのオフセット、pindex は消費されたバイト数、done はスキャンが完了したかどうかを示します。

• scan:

  func (s *ctScanner) scan(p int) int {
      pr := p // the p at the rune start
      str := s.s
      states, n := s.states, s.n
      for i := 0; i < n && p < len(str); {
          e := states[i]
          c := str[p]
          // ... (matching logic similar to build/contract.go's lookup)
      }
      return pr
  }
  

  scan メソッドは、ctScanner の中心的なロジックであり、入力バイトスライス str を現在の位置 p からスキャンし、最長一致する縮約を見つけます。build/contract.go の lookup と同様のロジックを使用しますが、ctScanner は状態を保持し、必要に応じてスキャンを継続できるように設計されています。特に、utf8.RuneStart(str[p]) のチェックは、UTF-8のルーン境界を考慮していることを示唆しています。

関連リンク

• Unicode Collation Algorithm (UCA): http://www.unicode.org/reports/tr10/
• UCA Contractions: http://www.unicode.org/reports/tr10/#Contractions
• Go言語の変更リスト (Gerrit): https://golang.org/cl/5970066

参考にした情報源リンク

• コミットメッセージと変更されたファイルの内容
• Unicode Collation Algorithm (UCA) の公式ドキュメント (TR10)
• トライ（Trie）データ構造に関する一般的な知識I have generated the detailed technical explanation in Markdown format, following all the specified instructions and chapter structure. I have also incorporated information about UCA and Contractions from a web search perspective to enrich the "前提知識の解説" section.

I will now output the generated explanation to standard output.