Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

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

このコミットは、Go言語の実験的なexp/normパッケージにおけるUnicode正規化処理の最適化に関するものです。具体的には、文字情報と分解テーブルのデータ構造を統合し、ルーン（Unicodeコードポイント）ごとのトライ（trie）ルックアップ回数を削減することで、パフォーマンス向上とコードの簡素化を図っています。

コミット

commit a52fb458dfd6fcf45256099ab6b03c45c065b621
Author: Marcel van Lohuizen <mpvl@golang.org>
Date:   Mon Feb 13 14:54:46 2012 +0100

    exp/norm: merged charinfo and decomposition tables. As a result only
    one trie lookup per rune is needed. See forminfo.go for a description
    of the new format.  Also included leading and trailing canonical
    combining class in decomposition information.  This will often avoid
    additional trie lookups.
    
    R=r, r
    CC=golang-dev
    https://golang.org/cl/5616071

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

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

元コミット内容

exp/norm: charinfoと分解テーブルをマージしました。その結果、ルーンごとに必要なトライルックアップは1回だけになりました。新しいフォーマットについてはforminfo.goを参照してください。また、分解情報に先行および後続の正準結合クラスを含めました。これにより、追加のトライルックアップを回避できることがよくあります。

変更の背景

Unicodeの正規化処理は、異なるバイト表現を持つ同じ文字（例: 「é」が単一のコードポイントU+00E9で表現される場合と、'e'と結合文字U+0301で表現される場合）を統一された形式に変換するために不可欠です。この処理は、文字列の比較、検索、ソートにおいて、論理的に同じ文字が異なるバイナリ表現を持つことによる問題を解決します。

Go言語のexp/normパッケージ（現在はgolang.org/x/text/unicode/normに移行）は、このUnicode正規化機能を提供しています。正規化処理の効率は、特に大量のテキストを扱うアプリケーションにおいて重要です。

このコミット以前は、文字情報（結合クラスなど）と分解情報（文字がどのように分解されるか）が別々のデータ構造（トライ）に格納されていたと考えられます。これにより、一つのルーンに対して複数のトライルックアップが必要となり、パフォーマンスのボトルネックとなる可能性がありました。

このコミットの目的は、これらのテーブルを統合し、ルーンごとのルックアップ回数を削減することで、正規化処理の効率を向上させることにあります。また、分解情報に先行（leading）および後続（trailing）の正準結合クラス（Canonical Combining Class, CCC）を含めることで、さらなる最適化を図っています。これにより、分解された文字の結合クラスを別途ルックアップする手間を省き、正規化アルゴリズムの複雑性を軽減し、実行時のオーバーヘッドを削減することが期待されます。

前提知識の解説

Unicode正規化 (Unicode Normalization)

Unicodeには、同じ文字を複数の方法で表現できる「等価性」の概念があります。例えば、アクセント付きの文字「é」は、単一のプリコンポーズド文字（U+00E9）として表現することも、基本文字「e」（U+0065）と結合アキュートアクセント（U+0301）の組み合わせとして表現することもできます。これらは視覚的には同じですが、バイナリ表現は異なります。

Unicode正規化は、このような等価な文字シーケンスを統一された単一の表現に変換するプロセスです。これにより、文字列の比較やソートが正しく行われるようになります。

Unicode標準では、以下の4つの正規化形式が定義されています。

  • NFC (Normalization Form C - Composition): 結合済み文字を優先する形式。可能な限り結合文字をプリコンポーズド文字に変換します。Webコンテンツなどで最も一般的に推奨される形式です。
  • NFD (Normalization Form D - Decomposition): 分解済み文字を優先する形式。文字を基本文字と結合文字に分解します。
  • NFKC (Normalization Form KC - Compatibility Composition): 互換性分解と結合を行う形式。NFCに加えて、互換性等価性を持つ文字（例: 全角数字と半角数字、上付き文字と通常の文字）も統一します。これにより、文字の視覚的な表現が変わる可能性があります。
  • NFKD (Normalization Form KD - Compatibility Decomposition): 互換性分解を行う形式。NFDに加えて、互換性等価性を持つ文字も分解します。

トライ (Trie)

トライ（またはプレフィックスツリー）は、文字列の集合を効率的に格納し、検索するために使用されるツリー状のデータ構造です。各ノードは文字列のプレフィックスに対応し、ルートからノードへのパスが文字列を形成します。Unicodeの文字情報や分解情報をルーン（文字）に基づいて高速に検索するために、トライがよく利用されます。

結合クラス (Combining Class - CCC)

Unicodeの結合文字（例: アクセント、ダイアクリティカルマーク）は、先行する基本文字と結合して表示されます。結合クラス（CCC）は、これらの結合文字がどの順序で結合されるべきかを定義する数値です。正規化処理において、結合文字の順序が正しくなるように並べ替えるためにCCCが使用されます。

ルーン (Rune)

Go言語では、Unicodeコードポイントを表現するためにrune型が使用されます。これはint32のエイリアスです。

技術的詳細

このコミットの核心は、Unicode正規化に必要な文字情報と分解情報を、単一のデータ構造に統合することです。以前は、文字の結合クラスやクイックチェック情報、そして分解情報が別々のトライに格納されていたため、一つのルーンを処理する際に複数のトライルックアップが必要でした。

新しいアプローチでは、forminfo.goで定義されているように、各ルーンに対応するuint16値に、文字情報と分解情報の両方をパックします。

forminfo.goの変更点から、新しいデータフォーマットの概要が読み取れます。

  • runeInfo構造体の変更:
    • cccフィールドが「leading canonical combining class」を意味するように変更され、tccc（trailing canonical combining class）フィールドが追加されました。これにより、分解情報に先行および後続の結合クラスを直接含めることが可能になります。
    • indexフィールド（uint16型）が追加され、分解情報が格納されているdecompsバイト配列へのインデックスを保持します。
  • トライ値の新しい形式:
    • v >= 0x8000の場合：この値は分解を持たないルーンの情報を表します。
      • 0..8ビット: ccc (結合クラス)
      • 9..12ビット: qcInfo (クイックチェック情報)
      • 16ビット目: 1 (分解がないことを示すフラグ)
    • v < 0x8000の場合：この値は分解を持つルーンの情報を表し、decompsバイト配列へのインデックスとなります。
      • decomps配列のv番目のバイトはヘッダーバイトであり、分解されたバイト列の長さと、追加のqcInfoビットを含みます。
      • 分解されたバイト列の後に、必要に応じて後続のCCC (tccc)、さらに先行のCCC (lccc) が続きます。これにより、分解された文字の結合クラスを別途ルックアップする必要がなくなります。

この統合により、input.go内のcharinfoおよびdecomposeNFC/decomposeNFKC関数が、charinfoNFC/charinfoNFKCに統一され、単一のトライルックアップで必要な全ての情報を取得できるようになりました。

maketables.goでは、この新しいデータ構造に合わせてテーブル生成ロジックが変更されています。特に、printCharInfoTables関数が、文字情報と分解情報を統合した新しいトライを生成するように修正されています。printDecompositionTables関数は削除され、その機能はprintCharInfoTablesに吸収されました。

この変更は、Unicode正規化処理におけるデータアクセスを効率化し、特に結合文字を含む複雑な正規化シナリオにおいて、パフォーマンスの向上に寄与します。

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

  • src/pkg/exp/norm/composition.go: info.hasDecomposition()の場合の分解処理が、rb.f.decompose(src, i)からinfo.decomposition()を直接呼び出すように変更されています。これは、分解情報がruneInfo構造体内に直接含まれるようになったためです。
  • src/pkg/exp/norm/forminfo.go:
    • runeInfo構造体にtccc (trailing canonical combining class) と indexフィールドが追加されました。
    • decompFunc型が削除され、formInfo構造体からdecompose decompFuncフィールドが削除されました。
    • decomposition()メソッドがruneInfoに追加され、indexフィールドを使用してdecompsバイト配列から分解情報を取得するように変更されました。
    • lookupInfoNFCとlookupInfoNFKC関数が、新しいcompInfoヘルパー関数を呼び出すように変更されました。このcompInfo関数が、uint16値からruneInfo構造体を構築する新しいロジックを含んでいます。
    • 新しいデータフォーマットに関する詳細なコメントが追加されました。
  • src/pkg/exp/norm/input.go:
    • charinfo, decomposeNFC, decomposeNFKCメソッドが削除され、代わりにcharinfoNFCとcharinfoNFKCが追加されました。これらの新しいメソッドは、それぞれnfcTrieとnfkcTrieを直接ルックアップします。
  • src/pkg/exp/norm/maketables.go:
    • makeCharInfo関数が削除され、printCharInfoTables関数が大幅に修正されました。
    • printDecompositionTables関数が削除されました。
    • 新しいdecompSet型とmkstrヘルパー関数が追加され、分解情報を効率的に管理し、新しい統合されたトライを構築するために使用されます。
    • テーブル生成のメインロジックであるmakeTables関数内で、printDecompositionTables()の呼び出しが削除され、printCharInfoTables()がinfoリストに含まれる場合にのみ呼び出されるように変更されました。
  • src/pkg/exp/norm/normalize.go: info.hasDecomposition()の場合の分解処理が、rb.f.decompose(...)からinfo.decomposition()を直接呼び出すように変更されています。
  • src/pkg/exp/norm/tables.go: decompsバイト配列のデータが更新され、新しい定数（firstCCC, firstLeadingCCC, lastDecomp, maxDecomp）が追加されました。これは、新しい統合されたデータフォーマットを反映しています。

コアとなるコードの解説

このコミットの最も重要な変更は、src/pkg/exp/norm/forminfo.goにおけるruneInfo構造体の再定義と、compInfoヘルパー関数の導入です。

runeInfo構造体:

type runeInfo struct {
	pos   uint8  // start position in reorderBuffer; used in composition.go
	size  uint8  // length of UTF-8 encoding of this rune
	ccc   uint8  // leading canonical combining class (ccc if not decomposition)
	tccc  uint8  // trailing canonical combining class (ccc if not decomposition)
	flags qcInfo // quick check flags
	index uint16
}
  • cccとtccc: これまで単一のcccフィールドで表現されていた結合クラスが、先行（ccc）と後続（tccc）に分離されました。これにより、分解された文字の結合クラス情報をより正確に保持できるようになります。
  • index: このフィールドが、分解情報が格納されているdecompsバイト配列内のオフセットを指します。これにより、ルーンの分解情報を直接参照できるようになりました。

compInfo関数:

func compInfo(v uint16, sz int) runeInfo {
	if v == 0 {
		return runeInfo{size: uint8(sz)}
	} else if v >= 0x8000 {
		return runeInfo{
			size:  uint8(sz),
			ccc:   uint8(v),
			tccc:  uint8(v),
			flags: qcInfo(v>>8) & qcInfoMask,
		}
	}
	// has decomposition
	h := decomps[v]
	f := (qcInfo(h&headerFlagsMask) >> 4) | 0x1
	ri := runeInfo{size: uint8(sz), flags: f, index: v}
	if v >= firstCCC {
		v += uint16(h&headerLenMask) + 1
		ri.tccc = decomps[v]
		if v >= firstLeadingCCC {
			ri.ccc = decomps[v+1]
		}
	}
	return ri
}

この関数は、トライから取得したuint16値vとルーンのUTF-8バイト長szを受け取り、runeInfo構造体を構築します。

  • v == 0の場合: ルーンに特別な情報がない場合。
  • v >= 0x8000の場合: ルーンが分解を持たない場合。vの下位8ビットがCCC、上位ビットがクイックチェックフラグとして解釈されます。tcccもcccと同じ値に設定されます。
  • v < 0x8000の場合: ルーンが分解を持つ場合。vはdecomps配列へのインデックスとして扱われます。
    • decomps[v]はヘッダーバイトであり、分解されたバイト列の長さとクイックチェックフラグを含みます。
    • ri.indexにvが設定され、分解情報へのポインタとなります。
    • firstCCCやfirstLeadingCCCといった定数を用いて、分解情報に後続のCCC (tccc) や先行のCCC (ccc) が含まれているかを判断し、それらの値をruneInfoに設定します。

このcompInfo関数により、単一のトライルックアップで取得したuint16値から、ルーンの正規化に必要な全ての情報（サイズ、結合クラス、クイックチェックフラグ、分解情報へのインデックス）を効率的に抽出できるようになりました。これにより、正規化アルゴリズムはより少ないデータアクセスで動作し、パフォーマンスが向上します。

関連リンク

参考にした情報源リンク