9

XMLファイル内のバイナリデータをエンコードおよびデコードしたい(Pythonを使用しますが、何でも)。XML タグのコンテンツに不正な文字が含まれているという事実に直面する必要があります。許可されているもののみがXML 仕様で説明されています。

Char ::= #x9 | #xA | #xD | [#x20-#xD7FF] | [#xE000-#xFFFD] | [#x10000-#x10FFFF]

つまり、許可されていないものは次のとおりです。

  • 29 Unicode 制御文字は無効です (0x00 - 0x20) すなわち ( 000xxxxx ) 0x09、0x0A、0x0D を除く
  • 2 バイトを超える Unicode 文字表現 (UTF-16+) は無効です (U+D800 - U+DFFF) 例: ( 11011xxx )
  • 特殊な Unicode 非文字は無効です (0xFFFE - 0xFFFF)、つまり ( 11111111 1111111x )
  • <、>、およびエンティティのコンテンツについては、この投稿によると

1 バイトで 256 の可能性をエンコードできます。これらの制限により、最初のバイトは 256-29-8-1-3 = 215の可能性に制限されます。

その最初のバイトの 215 の可能性のうち、base64は 64 の可能性のみを使用します。Base64 は 33% のオーバーヘッドを生成します (base64 でエンコードされると、6 ビットは 1 バイトになります)。

だから私の質問は簡単です.XML内のバイナリデータをエンコードするために、base64よりも効率的なアルゴリズムはありますか? そうでない場合、どこから作成を開始する必要がありますか? (図書館等)

注意: この投稿に対して、「XML を使用してバイナリ データをエンコードするべきではない...という理由で」と答えることはできません。ただしないでください。良くない XML パーサーのサポートに 215 の可能性を使用しない理由について、せいぜい議論することしかできません。

NB2: 2 番目のバイトについて話しているわけではありませんが、可能性の数と、補助的な Unicode プレーンを使用するときに UTF8 標準を尊重するために 10xxxxxx までに開始する必要があるという事実に関して開発できるいくつかの考慮事項が確かにあります (そうでない場合はどうなりますか? )。

4

3 に答える 3

8

アヤさん、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 の倍数でない場合、文字列の終了を管理する方法をまだ提供していません。デコード アルゴリズムも提供する必要がありますが、それは非常に簡単です (例外を強制的にスローすることを忘れないでください)。デコードの単一性)。

于 2013-06-27T22:56:18.477 に答える
2

私は C コードで概念を開発しました。

プロジェクトは GitHub にあり、最終的に BaseXML と呼ばれます: https://github.com/kriswebdev/BaseXML

20% のオーバーヘッドがあり、バイナリ セーフ バージョンに適しています。

Python のバックグラウンド XML パーサーである Expat で動作させるのに苦労しました (XML1.1 をサポートしていません!)。そのため、XML1.0 の BaseXML1.0 バイナリ セーフ バージョンが見つかります。

リクエストがあれば、後で「for XML1.1」バージョンをリリースする可能性があります (これもバイナリセーフであり、14.7% のオーバーヘッドがあります)。準備ができており、実際に動作しますが、Python の組み込み XML パーサーでは役に立たないので、そうしたくありません。あまりにも多くのバージョンで人々を混乱させます (まだ)。

于 2013-07-04T22:11:24.433 に答える