アヤさん、Asci85 のリンクをありがとうございます。とても良いアイデアがあります。
私たちの場合のために以下にそれらを開発しました。
UTF-8 文字の可能性:
1 バイト文字 (0xxxxxxx) の場合: 1 バイトあたり 96 の可能性
+UTF-8 ASCII 文字 0xxxxxxx = +2^7-UTF-8 制御文字 000xxxxx = -2^5+XML で許可されている UTF-8 制御文字 (00000009、0000000A、0000000D) = +3-XML エンティティで許可されていない文字 (<、>、&) = -3
編集: これは XML1.0 仕様用です。XML 1.1 仕様では、0x00 以外の制御文字を使用できます...
2 バイト文字 (110xxxxx 10xxxxxx) の場合: 2 バイトあたり 1920 個の可能性
+UTF-8 全角文字 110xxxxx 10xxxxxx = +2^11-UTF-8 の不正な非正規文字 (1100000x 10xxxxxx) = -2^7
3 バイト文字 (1110xxxx 10xxxxxx 10xxxxxx) の場合: 3 バイトあたり 61440 個の可能性
+UTF-8 3バイト文字 1110xxxx 10xxxxxx 10xxxxxx = +2^16-UTF-8 の不正な非正規文字 (11100000 100xxxxx 10xxxxxx) = -2^11-Unicode 予約済み UTF-16 コードポイント (11101101 101xxxxx 10xxxxxx) = -2^11
そして、私は 4 バイト文字の計算を行いません。それは無意味です: 可能な数はごくわずかであり、この範囲には不正な UTF-8 文字が多すぎます。
コーディングの可能性は、3バイトのスペースとしましょう
それでは、3 バイト (24 ビット) 空間でどのような組み合わせができるか見てみましょう。
- 0xxxxxxx 0xxxxxxx 0xxxxxxx : 96*96*96 = 884736 の可能性
- 0xxxxxxx 110xxxxx 10xxxxxx : 96*1920 = 184320 の可能性
- 110xxxxx 10xxxxxx 0xxxxxxx : 1920*96 = 184320 の可能性
- 1110xxxx 10xxxxxx 10xxxxxx : 61440 = 61440 通りの可能性
他の可能性があります（スペースで終了または開始する3バイトの文字のように、4バイトの文字のように、（私にとって）評価が難しく、おそらく無視できます）。
可能性の総数:
- 3 バイトのスペースには 2^24 = 16777216 通りの可能性があります。
- そのスペースでの UTF-8 COMPATIBLE の可能性は、884736+2*184320+61440 = 1314816 の可能性です。
それはどのくらいのオーバーヘッドを意味しますか？
- 24 ビット空間の使用可能ビット : Log2(16777216)=24 (もちろん、これは数学的な理解のためです)
- このスペースの UTF-8 有効ビット: Log2(1314816)=20,32 有効ビット。
- つまり、20,32 ビットの有用な情報をエンコードするには、24 ビットのスペースが必要です。理論上の最小オーバーヘッドは
18% overheadです。Base64 の 33% のオーバーヘッドと Ascii85 の 25% のオーバーヘッドよりもはるかに優れています!
編集: これは XML1.0 仕様用です。XML1.1 (広くサポートされていません...) では、理論上のオーバーヘッドは 12.55% です。XML1.1 の 14.7% のオーバーヘッドでバイナリ セーフなアルゴリズムを作成することができました。
この 18% のオーバーヘッドに近づくにはどうすればよいでしょうか?
悪いニュースは、大きな「辞書」 (つまり、長いエンコンディング セット) を使用しないと、その 18% のオーバーヘッドを簡単に達成できないことです。しかし、20% を取得するのは簡単で、19% を取得するのは非常に簡単ですが、あまり実用的ではありません。
適切なコーディング長の候補:
- 6 ビットは 20% のオーバーヘッドで 5 ビットをエンコードできます (2^(6*0,84) > 2^5)
- 12 ビットは 20% のオーバーヘッドで 10 ビットをエンコードできます (2^(12*0,84) > 2^10)
- 24 ビットは 20% のオーバーヘッドで 20 ビットをエンコードできます (2^(24*0,84) > 2^20)
- 25 ビットは、19% のオーバーヘッド (2^(25*0,84) > 2^21) で 21 ビットをエンコードできます。
注意: 0.84 は、スペース ビット (20,32/24) の平均的な「有用性」です。
エンコーディング アルゴリズムの構築方法
「空間の可能性」（アルゴリズムの選択されたコーディング長に応じて、長さが5、10、20、または21ビットのビットのランダムシーケンス-1つを選択する）をutf8-にマップする「辞書」を構築する必要があります-互換性のあるシーケンス (長さが 6、12、24、または 25 ビットの utf8 ビット シーケンス)。
最も簡単な出発点は、20 ビット シーケンスを 24 ビット互換の UTF-8 シーケンスにエンコードすることです。これはまさに、可能性を計算するために上で使用した例であり、長さは 3 UTF-8 バイトです (したがって、未終了について心配する必要はありません)。 UTF8 文字)。
20% のオーバーヘッドに到達するには、2 バイト (またはそれ以上) の UTF-8 文字エンコーディング スペースを使用する必要があることに注意してください。1 バイト長の UTF8 文字のみを使用すると、RADIX-24 で 25% のオーバーヘッドしか達成できません。ただし、3 バイト長の UTF-8 文字は 20% のオーバーヘッドに達する必要はありません。
それがこの質問に対する次の課題です。誰が遊びたいですか？:)
アルゴリズムの提案、XML には BaseUTF-8 という名前を付けます
エンコードする 20 バイナリ ビット: ABCDEFGHIJKLMNOPQRST
"encoded" という名前の結果の UTF-8 文字列: 24 ビット長
数学的エンコーディング アルゴリズム (既知のプログラミング言語に基づくものではありません):
If GH != 00 && NO != 00:
encoded = 01ABCDEF 0GHIJKLM 0NOPQRST # 20 bits to encode, 21 space bits with restrictions (1-byte UTF-8 char not starting by 000xxxxx ie ASCII control chars)
If ABCD != 0000:
If GH == 00 && NO == 00: # 16 bits to encode
encoded = 0010ABCD 01EFIJKL 01MPQRST
Else If GH == 00: # 18 bits to encode, 18 space bits with restrictions (1-byte UTF-8 ASCII control char, 2-bytes UTF-8 char noncanonical)
encoded = 0NOFIJKL 110ABCDE 10MPQRST
Else If NO == 00: # 18 bits to encode
encoded = 110ABCDE 10MPQRST 0GHFIJKL
If ABCD == 0000: # 16 bits to encode
encoded = 0011EFGH 01IJKLMN 01OPQRST
On "encoded" variable apply:
convert < (0x3C) to Line Feed (0x0A)
convert > (0x3E) to Cariage Return (0x0D)
convert & (0x26) to TAB (0x09)
そして、それが 20% のオーバーヘッドのみを得る方法です。
このアルゴリズムは、エンコードする文字列が 20 の倍数でない場合、文字列の終了を管理する方法をまだ提供していません。デコード アルゴリズムも提供する必要がありますが、それは非常に簡単です (例外を強制的にスローすることを忘れないでください)。デコードの単一性)。