Goブログ

Goにおけるテキスト正規化

Marcel van Lohuizen
2013年11月26日

はじめに

以前の投稿では、Goにおける文字列、バイト、文字について説明しました。私はgo.textリポジトリのために、多言語テキスト処理のための様々なパッケージに取り組んできました。これらのパッケージのいくつかは別々のブログ投稿に値しますが、今日はgo.text/unicode/normに焦点を当てたいと思います。これは正規化を処理するパッケージであり、文字列の記事でも触れられており、この投稿の主題でもあります。正規化は、生のバイトよりも抽象度の高いレベルで機能します。

正規化について知りたいことのほとんどすべて（そしてさらにいくつか）を学ぶには、Unicode標準の附属書15を読むのが良いでしょう。より分かりやすい記事としては、対応するWikipediaのページがあります。ここでは、正規化がGoとどのように関連しているかに焦点を当てます。

正規化とは何か？

同じ文字列を表す方法は、しばしば複数あります。例えば、é（eアクート）は、単一のルーン（"\u00e9"）として文字列で表現することも、’e’にアクートアクセント（“e\u0301”）を続けたものとして表現することもできます。Unicode標準によると、これら2つは「正準的に等価」であり、等しいものとして扱われるべきです。

バイトごとの比較を使用して等価性を判定すると、明らかにこれらの2つの文字列に対して正しい結果が得られません。Unicodeは、正準的に等価な2つの文字列が同じ正規形に正規化されると、それらのバイト表現が同じになるような正規形のセットを定義しています。

Unicodeはまた、「互換等価」を定義して、同じ文字を表す文字を等しくしますが、視覚的な外観が異なる場合があります。例えば、上付き数字の’⁹’と通常の数字の’9’はこの形式では等価です。

これらの2つの等価性の形式それぞれについて、Unicodeは合成形と分解形を定義しています。前者は、単一のルーンに結合できるルーンをこの単一のルーンで置き換えます。後者は、ルーンをその構成要素に分解します。この表は、Unicodeコンソーシアムがこれらの形式を識別するために使用するNFで始まる名前を示しています。

Goによる正規化へのアプローチ

文字列のブログ投稿で述べたように、Goは文字列内の文字が正規化されていることを保証しません。しかし、go.textパッケージはこれを補うことができます。例えば、collateパッケージは、言語固有の方法で文字列をソートできますが、正規化されていない文字列でも正しく機能します。go.textのパッケージは常に正規化された入力を必要とするわけではありませんが、一般的に、一貫した結果を得るためには正規化が必要になる場合があります。

正規化は無料ではありませんが、高速です。特に照合や検索の場合、または文字列がNFDまたはNFCのいずれかで、バイトの並べ替えなしで分解することでNFDに変換できる場合は特に高速です。実際には、99.98％のWebのHTMLページコンテンツはNFC形式です（マークアップを除く場合、さらに多くなります）。NFCの大部分は、並べ替えを必要としない（割り当てが必要）分解によってNFDに分解できます。また、並べ替えが必要な場合を検出することも効率的であるため、必要なまれなセグメントに対してのみ行うことで時間を節約できます。

さらに良いことに、照合パッケージは通常、normパッケージを直接使用せず、代わりにnormパッケージを使用して正規化情報を独自のテーブルにインターリーブします。2つの問題をインターリーブすることで、パフォーマンスへの影響をほとんど与えることなく、オンザフライで並べ替えと正規化を行うことができます。オンザフライでの正規化のコストは、事前にテキストを正規化する必要がないこと、および編集時に正規形が維持されることを保証することによって補われます。後者は難しい場合があります。例えば、2つのNFC正規化された文字列を連結した結果は、NFCであることが保証されません。

もちろん、文字列が既に正規化されていることが事前に分かっている場合は、オーバーヘッドを完全に回避することもできます。これはよくあることです。

なぜ気にする必要があるのか？

正規化を回避することについてこれほど議論した後、なぜそもそも気にする必要があるのか疑問に思うかもしれません。理由は、正規化が必要なケースがあり、それらが何かを理解し、結果として正しく行う方法を理解することが重要だからです。

それらについて議論する前に、まず「文字」の概念を明確にする必要があります。

文字とは何か？

文字列のブログ投稿で述べたように、文字は複数のルーンにまたがる場合があります。例えば、’e’と’◌́’（アクート“\u0301”）は’é’（NFDでは“e\u0301”）を形成するために結合できます。これら2つのルーンは1つの文字です。文字の定義はアプリケーションによって異なる場合があります。正規化では、スタター（他のルーンと後ろ向きに修正したり結合したりしないルーン）で始まるルーンのシーケンスとして定義し、その後、空の可能性のある非スタター（通常はアクセント）のシーケンスが続きます。正規化アルゴリズムは一度に1つの文字を処理します。

理論的には、Unicode文字を構成できるルーンの数に制限はありません。実際、修飾子の数に制限はなく、修飾子は繰り返し、または積み重ねることができます。3つのアクートを持つ’e’を見たことがありますか？これがそれです：’é́́’。これは標準によると完全に有効な4ルーンの文字です。

その結果、最低レベルでも、テキストは不定長のチャンクサイズで処理する必要があります。これは、Goの標準的なReaderとWriterインターフェースで使用されているように、テキスト処理へのストリーミングアプローチでは特に厄介です。そのモデルは、中間バッファのサイズも不定長にする必要がある可能性があるからです。また、正規化の単純な実装はO(n²)のランニングタイムになります。

実用的なアプリケーションでは、これほど多くの修飾子のシーケンスには意味のある解釈がありません。Unicodeはストリームセーフなテキスト形式を定義しており、修飾子（非スタター）の数を最大30個に制限できます。これは実用的な目的には十分すぎるほどです。後続の修飾子は、新しく挿入されたCombining Grapheme Joiner（CGJまたはU+034F）の後に配置されます。Goはすべての正規化アルゴリズムでこのアプローチを採用しています。この決定により、少し適合性が失われますが、安全性が向上します。

正規形での書き込み

Goコード内でテキストを正規化する必要がなくても、外部の世界と通信する際には正規化したい場合があります。たとえば、NFCに正規化するとテキストが圧縮され、ワイヤで送信するコストが安価になります。韓国語などの一部の言語では、節約量は大幅になります。また、一部の外部APIは特定の正規形でのテキストを期待している場合があります。または、単に世界中の他のユーザーに合わせて、テキストをNFCとして出力したいだけかもしれません。

テキストをNFCとして書き込むには、unicode/normパッケージを使用して、選択したio.Writerをラップします。

wc := norm.NFC.Writer(w)
defer wc.Close()
// write as before...

小さな文字列があり、迅速な変換を行いたい場合は、このより単純な形式を使用できます。

norm.NFC.Bytes(b)

normパッケージは、テキストを正規化するためのさまざまな他のメソッドを提供しています。ニーズに最適なものを選択してください。

類似文字の検出

’K’（"\u004B"）と’K’（ケルビン記号“\u212A”）、または’Ω’（"\u03a9"）と’Ω’（オーム記号“\u2126”）の違いを区別できますか？同じ基本的な文字のバリアント間の、時には些細な違いを見落とすのは簡単です。識別子や、そのような類似文字でユーザーを欺くことがセキュリティ上の危険をもたらす可能性のあるものには、そのようなバリアントを許可しないのが一般的です。

互換正規形であるNFKCとNFKDは、視覚的にほぼ同一の多くの形式を単一の値にマッピングします。2つの記号が似ていても、実際には2つの異なるアルファベットからのものである場合、そうはならないことに注意してください。例えば、ラテン文字の’o’、ギリシャ文字の’ο’、キリル文字の’о’は、これらの形式で定義されているように、依然として異なる文字です。

正しいテキスト修正

テキストを変更する必要がある場合にも、normパッケージが役に立つ場合があります。「cafe」という単語を複数形の「cafes」に検索して置換したい場合を考えてみましょう。コードスニペットは次のようになります。

s := "We went to eat at multiple cafe"
cafe := "cafe"
if p := strings.Index(s, cafe); p != -1 {
    p += len(cafe)
    s = s[:p] + "s" + s[p:]
}
fmt.Println(s)

これは、期待どおりに「私たちは複数のカフェで食事に行きました」と出力します。今度は、テキストにフランス語のスペル「café」がNFD形式で含まれているとします。

s := "We went to eat at multiple cafe\u0301"

上記の同じコードを使用すると、複数形の「s」は’e’の後、アクートの前に挿入され、「私たちは複数のカフェで́食事に行きました」という結果になります。この動作は望ましくありません。

問題は、コードが複数のルーンからなる文字間の境界を尊重せず、文字の途中でルーンを挿入していることです。normパッケージを使用すると、このコードを次のように書き直すことができます。

s := "We went to eat at multiple cafe\u0301"
cafe := "cafe"
if p := strings.Index(s, cafe); p != -1 {
    p += len(cafe)
    if bp := norm.FirstBoundary(s[p:]); bp > 0 {
        p += bp
    }
    s = s[:p] + "s" + s[p:]
}
fmt.Println(s)

これは作りこまれた例かもしれませんが、要点は明確でしょう。文字が複数のルーンにまたがる可能性があることに注意してください。一般的に、このような問題は、文字境界を考慮した検索機能（計画中のgo.text/searchパッケージなど）を使用することで回避できます。

反復処理

文字境界の処理に役立つ、normパッケージが提供するもう1つのツールは、イテレータnorm.Iterです。これは、選択した正規化形式で、一度に1文字ずつ文字を反復処理します。

マジックの実行

前述のように、ほとんどのテキストはNFC形式であり、基本文字と修飾子は可能な限り単一のルーンに結合されます。文字を分析する目的では、最小の構成要素に分解した後のルーンを処理する方が簡単なことがよくあります。これがNFD形式が役立つところです。たとえば、次のコードスニペットは、テキストを最小の構成要素に分解し、すべてのアクセント記号を削除してから、テキストをNFCに再合成するtransform.Transformerを作成します。

import (
    "unicode"

    "golang.org/x/text/transform"
    "golang.org/x/text/unicode/norm"
)

isMn := func(r rune) bool {
    return unicode.Is(unicode.Mn, r) // Mn: nonspacing marks
}
t := transform.Chain(norm.NFD, transform.RemoveFunc(isMn), norm.NFC)

生成されたTransformerは、次のように選択したio.Readerからアクセント記号を削除するために使用できます。

r = transform.NewReader(r, t)
// read as before ...

これにより、たとえば、元のテキストがエンコードされた正規化形式に関係なく、テキスト内の「cafés」という記述はすべて「cafes」に変換されます。

正規化情報

前述のように、一部のパッケージでは、実行時の正規化の必要性を最小限に抑えるために、正規化をテーブルに事前に計算しています。型norm.Propertiesは、これらのパッケージ、特に正規化結合クラスと分解情報に必要なルーンごとの情報へのアクセスを提供します。詳細については、この型のドキュメントを参照してください。

パフォーマンス

正規化のパフォーマンスを把握するために、strings.ToLowerのパフォーマンスと比較します。最初の行のサンプルは、小文字でNFC形式であり、すべての場合においてそのまま返すことができます。2番目のサンプルはどちらも当てはまらず、新しいバージョンを作成する必要があります。

イテレータの結果を示す列には、バッファを含むイテレータの初期化の有無にかかわらず測定値が表示されます。これらのバッファは、再利用時に再初期化する必要はありません。

ご覧のとおり、文字列が正規化されているかどうかを検出するのは非常に効率的です。2行目の正規化のコストの多くは、バッファの初期化によるものであり、そのコストは、より長い文字列を処理する場合に償却されます。実際、これらのバッファはほとんど必要ないため、将来的には実装を変更して、小さな文字列の一般的なケースをさらに高速化できる可能性があります。

結論

Go内でテキストを処理する場合、一般的にはunicode/normパッケージを使用してテキストを正規化する必要はありません。このパッケージは、文字列を送信する前に正規化されていることを確認したり、高度なテキスト操作を実行したりする場合に役立つ場合があります。

この記事では、他のgo.textパッケージと多言語テキスト処理についても簡単に触れましたが、答えよりも多くの疑問を提起した可能性があります。ただし、これらのトピックの議論は、またの機会に譲らなければなりません。