Unicode正規化を実装する (4) クイックチェック
バックナンバー
- Unicode正規化を実装する (1) UCDにふれる - アジョブジ星通信
- Unicode正規化を実装する (2) 正規分解・互換分解 - アジョブジ星通信
- Unicode正規化を実装する (3) 正規合成 - アジョブジ星通信
本当は正規化の高速化全般について書きたかったのですが、 UAX #15 に「トライ木使うといいんじゃね？」とか書いてあるんですけど、どういう木構造にしたらいいのかさっぱりわからず無事死亡しました。強い方、よろしくお願いします。
というわけで今回は、クイックチェックプロパティを使った、正規化済み判定と合成の高速化について説明していこうと思います。
目次
クイックチェックプロパティ
DerivedNormalizationProps.txt には NFC_QC, NFD_QC, NFKC_QC, NFKD_QC というプロパティがあります。値は N と M 、初期値 Y がありますが、それぞれ次のような意味を持っています。
| 値 | 省略形 | 説明 |
|---|---|---|
| NO | N | このコードポイントは、該当する正規化形式には存在できません。 |
| YES | Y | このコードポイントはスターターで、該当する正規化形式に存在することができます。さらに、 NFKC, NFC では、この文字とそれよりあとの文字で合成することはできますが、この文字とそれより前の文字で合成することはありません。 |
| MAYBE | M | このコードポイントは、正規順序によっては制約付きで存在することができます。具体的には、そのテキストは、その文字が出現する文脈に依存した特定の正規化形式になっていない可能性があります（翻訳力/Zero）。 |
Table 9. Description of Quick_Check Values を雑に翻訳
というわけで、このプロパティを使うと、正規化されているかどうかかそこそこわかります。
正規化されているかを判定する
クイックチェックを使うと、文字列が正規化されているかどうかを高速に判定することができます。 UAX #15 にサンプルコードがあるので、見てみましょう。
public int quickCheck(String source) { short lastCanonicalClass = 0; int result = YES; for (int i = 0; i < source.length(); ++i) { int ch = source.codepointAt(i); if (Character.isSupplementaryCodePoint(ch)) ++i; short canonicalClass = getCanonicalClass(ch); if (lastCanonicalClass > canonicalClass && canonicalClass != 0) { return NO; } int check = isAllowed(ch); if (check == NO) return NO; if (check == MAYBE) result = MAYBE; lastCanonicalClass = canonicalClass; } return result; } public static final int NO = 0, YES = 1, MAYBE = -1;
なお、 isAllowed はクイックチェックプロパティの値を取得するメソッドです。
この quickCheck メソッドは、文字列にクイックチェックプロパティの値が NO になる文字列が含まれている、または正規順序に並んでないない場合に NO を返し、 NO はないが、 MAYBE になる文字が含まれている場合には MAYBE、それ以外の場合に YES を返します。これを使って、正規化されているか判定するプログラムを書くには、戻り値が NO, YES の場合はそれを利用し、 MAYBE の場合には正規化を実行するようにします。
合成を高速化する
注意: このやり方は私が独自に雑に考えた結果なので、もっと良い方法があるかもしれません。
クイックチェックを使って部分的に正規化を行うようにします。
まず、クイックチェックとCCCの取得はセットなので、クイックチェックプロパティ（QC）とCCCをセットにしたテーブルをつくります。
| キー | 値 |
|---|---|
| コードポイント | CCC。ただし QC = N or M の場合は 255 |
（サンプルでは NFC_QC = N or M のとき 255、 NFKC_QC（NFC_QCに含まれているものは除く） = N or M のとき 256 としています。）
そして次の手順で部分正規化を行います。
- QC = N or M または正規順序に並んでいない箇所を探す。
- 1で見つけた文字より前で CCC = 0 の文字を正規化開始点とする。条件を満たす文字がない場合は、文字列の始めを正規化開始点とする。
- 1で見つけた文字より後で CCC = 0 かつ QC = YES の文字を正規化終了点（正規化範囲に含まない）とする。条件を満たす文字がない場合は、文字列の最後を正規化終了点とする。
- 2～3の範囲で、分解と合成を行う。
これを繰り返すことで必要最小限の処理で正規化できるはずです。
サンプルプロジェクトを実行すると、第3回で作った NFC と高速化した NFC の実行速度の比較ができます。サンプルコードを簡単にするため、高速化版のほうがコレクション操作で不利になっていますが、通常版 3.0 秒、高速化版 2.3 秒と、かなり差が出ました（Debugビルド）。
