Goでの文字列の正規化 (Text normalization in Go)

Goでの文字列の正規化 #

Text normalization in Go by By Marcel van Lohuizen

はじめに #

先の記事では、Goでの文字列、バイト、文字について説明していました。 私は go.text レポジトリ（訳注：現在は golang.org/x/text パッケージ群、以下原文で go.text の部分は置き換える。）で多言語文字列処理向けの様々なパッケージの開発に関わってきました。 これらのパッケージのいくつかは別のブログポストに譲って、この記事では go.text/unicode/norm （訳注：現在は golang.org/x/text/unicode/norm）に焦点を当てたいと思います。 このパッケージは、先の文字列に関する記事、そして本記事のタイトルとなっている、文字列の正規化を扱います。 正規化は生のバイト列よりも高水準での抽象化を扱います。

正規化についてのすべてを知りたければ、Unicode標準の付録15を読むのが良いでしょう。 より読みやすい記事としては、対応するWikipediaのページ（訳注：日本語版）があります。 ここでは、正規化がどのようにGoに関わっているかに焦点を当てます。

正規化とは何か #

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

これら2つの表現の等価性を調べるために1バイトごとに比較していたのでは正しい結果は導けません。Unicodeでは2つの表現が正準に等価で、 同じ正規形に正規化される場合に、そのバイト表現が同じになるような正規形のセットを定義しています。

またUnicodeでは同じ文字を表すけれども見た目が異なる表現を同等とみなす「互換等価」を定義しています。 たとえば上付き文字の数字 ‘⁹’ と通常の数字 ‘9’ はこの形式では等価です。

これら2つ等価な形式に対して、Unicodeでは合成と分解を定義しています。 合成は、結合して1つのルーンにできる複数のルーンをその1つのルーンにい置きv換えることです。 分解は、ルーンを要素に切り離すことを指します。すべてNFから始まる次の表は、Unicodeコンソーシアムが各形式を識別する際に使っているものです。v

合成 分解
正準等価 NFC NFD
互換等価 NFKC NFKD

Goの正規化に対するアプローチ #

文字列に関する記事で言及したように、Goでは文字列内の文字が正規化されていることを保証していません。 しかしながら、golang.org/x/text パッケージがそれを補填してくれます。 たとえば collate パッケージは、Go言語特有の方法で文字列を順場に並べるパッケージで、 これは正規化されていない文字列でも正しく動作します。 golang.org/x/text 内のパッケージは必ずしも入力が正規化されている必要はありませんが、一般的に一貫した結果を得るためには 正規化が必要でしょう。

正規化のコストはタダではないですが速いです。特に、照合や検索の場合、または文字列がNFDかNFCのいずれかで、バイトを並び替えなくても分解するだけで NFDになる場合は顕著です。実際に、99.98%のウェブ上のHTMLページのコンテンツはNFC形式です。（マークアップは含めていません。 含めた場合はその割合はより大きくなります。）ほぼ間違いなくたいていのNFCは（メモリの確保を必要とする）並び替えの必要なく分解するだけでNFDになります。 また、並び替えが必要な場合の検出も効率的なので、それが必要なまれな区画に対してだけ並び替えを行うことで時間を節約することが出来ます。

より効率よくするために、照合（collate）のパッケージは通常は norm パッケージを直接は使わず、代わりに自身が持っている表の中に 正規化に関する情報をインタリーブするために norm パッケージを使います。 並び替えと正規化をインタリーブすることで、パフォーマンスに影響をあたえることなくその場で実行することが可能になります。 オンザフライでの正規化のコストは事前に事前に文字列を正規化する必要がないことで補償され、編集時には正規化形式になっていることを保証します。 特に後者は厄介です。たとえば、2つのNFCで正規化された文字を合成してもNFCになるとは限らないからです。

もちろん、よくあることですが、事前に文字列が正規化済みであることがわかっているのであれば、明白なオーバーヘッドは避けるべきでもあります。

何が困るのか #

これまで正規化をできれば避けたいという話をしてきましたが、そもそもなぜそれが懸念事項になるのか疑問の人もいるでしょう。 その理由は、正規化が必要で、正規化が何か、そして正規化を正しくする方法を理解することが重要である場合があるからです。

これらについて議論する前に、まず「文字」という概念を明確にしなければなりません。

文字とは何か #

文字列に関する記事で説明したとおり、文字は複数のルーンに渡ることがあります。たとえば ’e’ と ‘◌́’（アキュート “\u0301”）は合成して ‘é’ という形式（NFDでは “e\u0301” ）になります。この2つのルーンをまとめて1つの文字を表しています。 文字の定義は実装によって変わります。正規化においては文字を、他のルーンを変更したり後ろ向きに合成しないルーンと定義した開始ルーンから始まり、 （通常はアクセントなどの）修飾などを行う後続ルーンによるルーン列として定義しています。後続ルーンの列は空になりえます。 正規化アルゴリズムは一度に1文字を処理します。

理論上は1つのUnicode文字を作る上でのルーン数には上限はありません。事実、文字に続く修飾の数、その繰り返しの数、修飾の重ねあわせには 上限がありません。 ’e’ に3つアキュートが付いたものを見たことがありますか。これです。’é́́’ これは、標準上は完全に正しい4ルーンの文字です。

結果として、最下層においても、文字列は無制限のチャンクサイズの積み重ねの中で処理が行われる必要があります。 特にこれは、Go標準の Reader や Writer のインターフェースのように、文字列処理をストリームで取り組むときに扱いづらくなります。 なぜなら、このモデルでは潜在的に無制限のサイズを保持するための中間バッファーも持つ必要もあるからです。 また、率直に正規化を実装すると、処理が O(n²) になってしまいます。

実際に適用する場合には、このような大きな修飾のシーケンスを意味のある形で解釈することはありません。 Unicodeでは Stream-Safe Text format（ストリーム安全な文字列形式）を定義しています。 これは修飾（後続ルーン）の数の上限を最大で30に定めていて、この数は実用では十分な大きさです。 それ以降の修飾はまとめられて、結合書記素結合子（Combining Grapheme Joiner, CGJ, U+034F）に置き換えられます。 この決定によって、原文との一致性は少し下がりますが、より安全に処理できるようになります。

正規化形式で書く #

Goのコード内で正規化をする必要がない場合でもなお、外部とやり取りするときにはそうしたくなる場合があるでしょう。 たとえば、NFCに正規化すると文字列を小さくでき、送信するコストを小さくすることが出来ます。 ある言語、たとえば韓国語では、データを小さくすることは有用です。また、外部のAPIが特定の正規化形式を期待している場合もあります。 あるいは、外部のシステムと同様に、ただ正規化してNFC形式にしたい場合もあるでしょう。

文字列をNFCとして書くには、unicode/normパッケージで io.Writerをラップして使うのが良いでしょう。

wc := norm.NFC.Writer(w)
defer wc.Close()
// 通常と同様にwriteする

短い文字列を手早く変換したい場合は、この簡単な形式でも良いでしょう。

norm.NFC.Bytes(b)

norm パッケージは文字列の正規化のために他にも様々なメソッドを用意しています。 必要に応じて最適なものを選んでください。

類似した文字を見つける #

‘K’（"\u004B"）と ‘K’（ケルビン記号 “\u212A”）あるいは ‘Ω’（"\u03a9"）と ‘Ω’（オーム記号 “\u2126”）の違いがわかりますか。 根本的には同じ文字の異形での細かな差異は、見逃しやすいものです。そのような異形を識別子やそのような類似した文字でユーザを惑わしすことが セキュリティの危険性を晒すような場所で用いることを禁止するのは良い考えです。

NFKCやNFKDというような標準系は見た目が近い同一の形式を一つの値に対応させます。 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)

このスニペットの出力は期待通り “We went to eat at multiple cafes” と表示されます。 それでは、NFD形式で書かれたフランス語の綴りである “café” を含む文字列を考えてみましょう。

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

先程と同じスニペットを使うと、同じく複数形の “s” は ’e’ の後に挿入されますが、アキュートの前に挿入されてしまいます。 結果は “We went to eat at multiple cafeś” となります。これは期待した結果ではありません。

このコードが複数のルーンを使った文字の境界を反映せずに、文字の真ん中にルーンを挿入してしまうことが問題です。 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)

この例は作為的なものですが、このコード片がやろうとしていることは明らかでしょう。 文字は複数のルーンから構成されうるという事実を意識しましょう。 一般的にこのような問題は文字の境界を認識している検索機能（golang.org/x/text パッケージとして計画されているようなもの）を使うことで 避けることが出来ます。

イテレーション #

他に norm パッケージより提供されている、文字列の境界を扱う上で便利な機能にはイテレータがあります。内容は norm.Iter で確認してください。 これは選択した正規化形式での文字を1つずつイテレーションしていきます。

技を披露する #

先にも述べたように、たいていの文字列はNFC形式で、このとき可能な限り土台の文字と修飾子は合成されて1つのルーンにされます。 文字を解析する場合には、しばしばルーンを最小限の要素に分解した後のほうが扱いやすいことがあります。 このようなとき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する

たとえば、このコードは、元の文字列がどのように正規化されていても、すべての “cafés” を “cafes” に変換します。

正規化の情報 #

先に述べたように、パッケージによっては正規化を事前に計算してテーブルに保存し、ランタイムでの正規化を必要最低限にします。 norm.Properties 型はこれらのパッケージに必要なルーン毎の情報にアクセスできるようにしています。 特筆すべきは正規結合クラス（Canonical Combining Class）と分解情報にアクセスできる点です。 この型の詳細を知りたい方は ドキュメント を読んでください。

パフォーマンス #

正規化のパフォーマンスを理解してもらうために、 strings.ToLower のパフォーマンスと比較してみましょう。 次の表の1行目はすべて小文字でNFCになっており、すべての文字はそのまま返されます。 2行目のサンプルは大文字も混じりNFCでない文字も含まれていて、変換が必要になります。

入力 ToLower NFC追加 NFC変換 NFCイテレーション
nörmalization 199 ns 137 ns 133 ns 251 ns (621 ns)
No\u0308rmalization 427 ns 836 ns 845 ns 573 ns (948 ns)

イテレータの結果に関する列ではイテレータの初期化をすでにしている場合としていない場合の両方の計測結果を表示しています。 初期化をした場合は次回以降のイテレーションではバッファを再利用することが出来ます。

ごらんの通り、文字列が正規化されているかどうかは非常に効率的に判断されています。 2行目の正規化のコストはバッファの初期化によるものが大きく、そのコストは大きな文字列を扱う際にはならされます。 これらのバッファはあまり必要ないとわかってきたので、よく使われる小さい文字列の場合にもっと高速化できるように、 いずれ実装を変更するかもしれません。

結論 #

あなたがGoのプログラム内で文字列を扱っているのであれば、通常は文字列の正規化に unicode/norm パッケージを使う必要ありません。 このパッケージは文字列を外のシステムに送るとき、あるいはより発展的な文字列処理をしたいときに、文字列が確実に正規化されているように したい場合には便利です。

この記事では多言語文字列処理と同時に他の golang.org/x/text のパッケージについても簡単に触れまいた。 そしてこの記事で理解したものの数よりも多くの疑問が湧いてきことでしょう。しかしながら、この話題に関する議論はまたの機会にしましょう。

By Marcel van Lohuizen

あわせて読みたい #