Unicode の保存:文字名からコードポイントへのマッピング

Unicode 文字には名前があり、コードポイントを知らなくても簡単に話すことができます。たとえば、文字 λ (U+03BB) は 01 と呼ばれます .

文字名を指定すると、そのコード ポイントを知ることができます。そのためのいくつかの使用例があります。主な使用例は、Unicode 文字を文字列リテラルに名前で配置できるようにすることです。これは、Python、Perland Perl 6 Raku.C++ 向けに提案された機能でもあり、この投稿は実装経験レポートです。これが実装したい関数です:

constexpr char32_t cp_from_name(std::string_view) noexcept;

それは十分に単純に思えます。残念ながら、多くの Unicode コードポイントがあります - 現在 Unicode 12 では 137,928 です。課題は、その関数のサイズ フットプリントを最小限に抑えることです。

データの分析

Unicode Character Database は、解析が難しいテキスト ファイルのセットとして提供されます。これは CSV に少し似ていますが、そうではありません。幸いなことに、各文字を説明する XML ドキュメントもあります。

これを Python スクリプトに入力すると、文字数のカウントを開始し、必要なデータのサイズをより正確に把握できます。

ほとんどの文字名は生成され、計算によってコードポイントに関連付けることができます。Unicode 標準では、文字名を生成する 2 つの方法について説明しています。たとえば、 (木の漢字の絵文字、U+6728) は 15 と呼ばれます。 であるため、名前からコード ポイントが何であるかを推測するのは簡単です。おそらく、これにより名前の有用性が低下しますが、多くのスペースを節約できます!

生成されるその他の名前は、Jamo と呼ばれるいくつかのコンポーネントで構成されるハングル文字です。ハングル文字は 1,000 を超えますが、Jamo はわずかです。ハングル コード ポイントは、Jamo が文字を作成するものを知っているだけでコードポイントを計算できるように、Unicode データベースに配置されています。これはとてもきれいです。これについて詳しく説明している記事はこちらです。

生成された名前を処理することで、約 31000 文字をカスタム名で処理できます。これらすべての名前をファイルにダンプすると、812KB のデータが作成されます。コードポイントも保存する必要があるため、必要な情報はこれだけではありませんが、いくつかのアイデアが得られます.lzma でデータを圧縮すると、96KB のファイルが得られます.コードポイントを格納するための 80KB これにより、達成を期待できる範囲の適切な下限が得られます。達成できる可能性はほとんどありませんが、少なくとも 180KB が必要であることはわかっています。ランダム アクセスで読み取ることができない圧縮スキームや、静的データに加えて大量のメモリを使用する圧縮スキームは考慮されていません。実際、名前をスペースで区切ると、いくつかの単語が何度も繰り返されていることがわかります

多くの名前は共通の接頭辞を共有しています。 23 で始まる 400 ほどのコード ポイントがあります。 .

基数ツリー

データを表す 1 つの方法は、各ノードが文字であり、子が各名前の次の文字であるツリーを作成することです。

そのデータ構造の最悪の場合のサイズは、約 750,000 ノードになります (平均で 25ただし、多くのノードには子が 1 つしかないため、子が 1 つしかない (そして値がない) すべてのノードをマージすることで、ノードを大幅に圧縮できます。

これは、基数ツリーまたはプレフィックス ツリーと呼ばれます。ルックアップは $\mathcal{O}( size(name) )$ です。良くも悪くもありません - Unicode 名は比較的短いです。

各ノードにはラベル (共通の接頭辞) があり、値 (文字のコード ポイント) と子を持つ場合があります。すべての葉に値がありますが、葉ではない一部のノードにも値があります:/コード> と 44 たとえば、どちらもキャラクター名です。

シリアル化

データの意味がわかったので、次はメモリに配置します。すべてのバイトが重要です。すべてのビットが重要です。

値、名前、および子ノードへのアクセス方法を格納するには、ノードごとに何ビットが必要ですか?

名前

多くのノードには 1 文字の名前があるため、1 文字の名前に 1 バイトを使用できます。しかし、他の多くのノードにはより長い名前があります。 ノード名かもしれません.ノードの名前全体を単純に保存することもできますが、いくつかの単語とサブシーケンスが頻繁に使用されます!63という単語 たとえば、数回表示されます。

代わりに、すべてのノード名の辞書を作成できます。最大の名前を最初に配置して、72 80 を提供できます 、 97103 など。辞書にはもちろん繰り返しがありますが、50K 未満であることが判明しました。65K 未満であるため、2 バイトでインデックスを付けることができます。したがって、1 文字を超える名前には 3 バイトを使用します。

ASCII サブセット

Unicode 名は文字 117 のみを使用します 129 へ 、 132 148 へ と 152 .大文字と小文字は区別されません。したがって、有効な文字は 6 ビットを使用して表すことができます。これを行う簡単な方法は、169 などの文字列のインデックスとして文字をエンコードすることです。

次に、1 文字のケースと長い名前のケースを区別するためにビットを使用できます。

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
名前が長い レター
名前のサイズ インデックス

このスキームを使用すると、単一ノードの名前は 32 ($2 ^6 $) に制限されますが、非常に長い名前は単純に複数のノードに分割できるため、これは問題ではありません。

コードポイント

すべてのリーフ ノードを含む多くのノードには、コード ポイントである値があります。しかし、一部のノードにはまったく値がありません。null のバイトをエンコードして無駄にするのは、すぐに何キロバイトも無駄になるため、避ける必要があります。無料ビットを利用できます!


0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
名前が長い 値あり レター
名前のサイズ インデックス

Unicode は、コード ポイントごとに 21 ビットを使用します。 3 ビットが残ります。エキサイティングです。Unicode コードポイントの 21 ビット サイズは、他の多くの Unicode プロパティで利用できるものです:

24-44 45 46 47

コード ポイントの値に応じて、変数 int (2 または 3 バイトを使用) として値をエンコードできます。空きビットの 1 つを判別式として使用すると、おそらく約 8K 節約できます。シリアル化が少し難しくなります。まだ実装していません。

子供

子ノードがどこにあるかをノードが示す方法が必要です。私の最善の努力にもかかわらず、そのためには 3 バイトが必要になりますが、より快適にすることができます。値を持つほとんどのノードには子がありません。子供がいるかどうかを示すための 3 つの無料ビット (贅沢) の 1 つ:

24-44 45 46 47
子あり

ノードに値がない場合、少なくとも 1 つの子があることがわかります。これは、「値を持つ」ビットが実際に 2 ビットの情報を格納することを意味します。いいね:D

子がいることを知っていると、まだそれらにジャンプする方法が必要です.最初にジャンプ先のオフセットのリストを追加しましたが、それは信じられないほど無駄でした.しばらく時間がかかりましたが、最初の子のオフセットを保存し、すべての子を配置できることに気付きました.指定された親の子を順番に送信します。

数字の基数ツリーを例にとると、幅優先の順序でメモリを配置できます。

170

185 のデータを保存するだけです。 ノード 193 のオフセット .

最後に必要なのは、特定のノードの最初の子の後の終了条件です。幸い、数ビット残っています。オフセットには 24 ビットを使用しました。シリアル化された基数が約 200KB であることを考えると、19 で十分です。また、値の隣に 2 ビットが残っています:

24-44 45 46 47
兄弟あり 子供がいます

結果と今後の改善

私の現在の WIP 実装では、Unicode 12 データベース全体 (エイリアスを含む) に対して、辞書は 48.6KB で、基数ツリーは 213Ki です。これは、生成されていない名前ごとに約 8 バイトです!これは、Bloaty McBloatface などのツールを使用して確認できます。これはでっち上げではありません!

さらにデータを削減することも可能です。たとえば、文字名を構成する文字を 6 ビットでエンコードできることを利用して、辞書を 25% 縮小できます。

名前へのコード ポイント

これについては別の記事で詳しく説明するかもしれませんが、コードポイントから名前へのマッピングにはさまざまなトリックとデータ構造が必要です。基数ツリー全体をスキャンして名前を再構築することが技術的に可能であるとしても、それは非効率的であり、さらに重要なことに、追跡していません。名前の種類 (名前とエイリアスがあります)。

PythonとRustで使用される一般的なソリューションは、コードポイントから名前へのマッピングのみを保存し、完全ハッシュを使用して名前からコードポイントに取得し、変換して結果を確認することです。両方が必要な場合に便利なソリューションです.

他にも改善の可能性や賢い方法があるかもしれません.

コンパイラ エクスプローラでコードを試すことができます。

Unicode データの圧縮はとても楽しいチャレンジです。ぜひ試してみてください!