多倍長整数の符号化としての UTF-8
UTF-8 は Unicode で使われる 0 から 0x10FFFF までの正の整数を 1 ~ 4 byte の符号で表現する可変長の符号化方式である. その気になれば, 無限に大きい正の数を表現できるように拡張することもできる. 多倍長整数の符号化方式として捉えたときにどうなるか考えてみた.
概要
UTF-8 は, 面倒な説明が書かれていることが多いが, 次の 2 ステップで符号化すると捉えることもできる.
- 32-32-8-128 進の混合基数で符号化したい値を表現する (leading-zero は禁止)
- 1 byte 単位のパケットに詰め込む
各パケットは, パケットの種類を表すアルファ符号を反転した符号の部分と, 残りのデータ部分からなる. パケットの種類を示す数は次の通りである.
- 1 桁の数の先頭パケット (0)
- 2 byte 目以降のパケット (10)
- 2 桁の数の先頭パケット (110)
- 3 桁の数の先頭パケット (1110)
- 4 桁の数の先頭パケット (11110)
データ部は全て連結されて使われ, 前から順番に値を表現する bit が詰め込まれる.
だいたいこんな感じである. ちなみに語頭符号である.
考察
多倍長の整数を詰め込むことを考えると, 標識に 2 bit とられるので 1 byte あたり 5 bit しか詰め込めず, 非常に効率が悪い. *1 なぜだろう?
不規則な基数
まず, 目につくのは不規則な基数である. 1 桁目が 128 と大きい. これは ASCII の文字列をそのまま UTF-8 の文字列として受理できるようにするためである. しかし, 互換性を気にする必要のない多倍長整数の表現としては無駄な配慮である. ここを直せば, いくらかましになるのではないのか?
実際, パケットの種類の数の 1 と 2 を入れ替えると 64 進数にできて規則的になる. しかもそれだけでなく, 後続パケットで予約されている bit が 2 から 1 になり, 1 byte あたり 6 bit 使えるようになる.
後続パケットの標識
もう少し考えると, そもそも後続パケットに標識をつけることは必要なのだろうかと思い至る. これが必要な理由は UTF-8 の文字列を ASCII と混同されて問題を起こすことを防ぐためである. *2*3 そこを気にする必要がないので省略することにしよう. すると, 1 byte に 7 bit ずつ詰め込める.
結論
もう少し頑張れば 1 byte あたり 7 bit くらい詰め込めるところ, UTF-8 は互換性のためにトリッキーなことをやって規則性と効率を随分と犠牲にしているものなのですね.
しかし, 7 bit 単位で増える整数とかどう考えても扱いにくいので, 無限長は無理になるけどふつーに最初に桁数を書く方式がいいに決まっていますね... 効率を考えてガンマ符号とかに置き換えてもこの辺はどうしようもないあたり残念です.
