character-encoding - 最も効率的なバイナリからテキストへのエンコーディングは何ですか?

Question

これまでに見つけた最も近い候補は、yEnc (2%) と ASCII85 (25% オーバーヘッド) です。yEnc には、主に 8 ビット文字セットを使用しているという事実に関連して、いくつかの問題があるようです。これは別の考えにつながります: UTF-8 文字セットに基づくバイナリからテキストへのエンコーディングはありますか?

score 18 · Accepted Answer

これは、バイナリデータの性質と、「テキスト」が出力に課す制約に大きく依存します。

まず、バイナリデータが圧縮されていない場合は、エンコードする前に圧縮してみてください。次に、1/0 または個々のバイトの分布は多かれ少なかれランダムであると想定できます。

今：なぜテキストが必要なのですか？通常、これは、通信チャネルがすべての文字を均等に通過しないためです。たとえば、印刷可能な文字の範囲が 0x20 ～ 0x7E の純粋な ASCII テキストが必要な場合があります。遊べるキャラクターは95人。各文字は、理論的には log2(95) ~= 1 文字あたり 6.57 ビットをエンコードできます。かなり近い変換を定義するのは簡単です。

しかし、区切り文字が必要な場合はどうすればよいでしょうか? 現在、94 文字しかありません。したがって、エンコーディングの選択は、要件によって異なります。

非常にばかげた例を挙げると、チャネルが 256 文字すべてを問題なく通過し、セパレーターが必要ない場合、100% の効率を達成する簡単な変換を作成できます。:-) その方法は、読者の課題として残されています。

UTF-8 は、任意にエンコードされたバイナリデータの転送には適していません。わずか 14% のオーバーヘッドで値 0x01 ～ 0x7F を転送できます。0x00 が合法かどうかはわかりません。おそらくそうではありません。ただし、0x80 を超えるものはすべて UTF-8 で複数バイトに展開されます。UTF-8 は、0x01 ～ 0x7F、つまり 126 個の一意の文字を渡す制約付きチャネルとして扱います。区切り文字が必要ない場合は、1 文字あたり 6.98 ビットで送信できます。

この問題の一般的な解決策: バイナリエンコーディングが 0 から N-1 である N 文字のアルファベットを想定します。(エンコーディングが想定どおりでない場合は、ルックアップテーブルを使用して、中間の 0..N-1 表現と実際に送受信するものとの間で変換します。)

アルファベットを 95 文字と仮定します。現在: これらのシンボルの一部は 6 ビットを表し、一部は 7 ビットを表します。A 6 ビットシンボルと B 7 ビットシンボルがある場合、次のようになります。

A+B=95 (シンボルの総数) 2A+B=128 (作成できる 7 ビットプレフィックスの総数。2 つのプレフィックスを 6 ビットシンボルで開始するか、1 つを 7 ビットシンボルで開始することができます。 )

系を解くと、A=33、B=62 が得られます。シンボルのテーブルを作成します。

生のエンコード
000000 0000000
000001 0000001
...
100000 0100000
1000010 0100001
1000011 0100010
...
1111110 1011101
1111111 1011110

エンコードするには、まず入力の 6 ビットをシフトオフします。これらの 6 ビットが 100001 以上の場合、別のビットをシフトします。次に、対応する 7 ビットの出力コードを検索し、出力スペースに収まるように変換して送信します。反復ごとに 6 ビットまたは 7 ビットの入力をシフトします。

デコードするには、バイトを受け取り、生の出力コードに変換します。生コードが 0100001 未満の場合、対応する 6 ビットを出力にシフトします。それ以外の場合は、対応する 7 ビットを出力にシフトします。反復ごとに 6 ～ 7 ビットの出力を生成します。

均一に分散されたデータの場合、これが最適だと思います。ソースに 1 よりも 0 の方が多いことがわかっている場合は、7 ビットコードを使用できる可能性が高くなるように、7 ビットコードをスペースの先頭にマップすることをお勧めします。

score 7 · Accepted Answer

ウィキペディアによると

baseE91は、圧縮された 8 ビットバイナリ入力に対して最短のプレーン ASCII 出力を生成します。

score 1 · Accepted Answer

ウィキペディアにリストされているものの隣に、Bommanews があります。

B-News (または bommanews) は、UUEncode および Base64 エンコーディングに固有のオーバーヘッドの重みを軽減するために開発されました。これは、テキストメッセージにバイナリデータを詰め込むために新しいエンコーディング方法を使用します。この方法はより多くの CPU リソースを消費しますが、メッセージでの ANSI 制御コードの使用を回避しながら、UUEncode の約 40% から 3.5% (これらの桁の間の小数点はモニターの汚れではありません) に損失を抑えることができます。体。

これは yEnc: sourceに匹敵します。

yEnc は B-News よりも CPU への負荷が低く、ほぼ同じ低レベルのオーバーヘッドに達しますが、すべての制御コードの使用を回避するわけではなく、(実験的に) 一部に望ましくない影響があることが観察されたコードを除外するだけです。これは、B-News よりも RFC への準拠がやや劣ることを意味します。

score 1 · Accepted Answer

あなたはすでに答えを持っているようですね、マーク。1 バイトを超える UTF-8 文字は、テキスト (1 バイトあたり 2 ビット以上) を格納する場合でも 25% を超えるオーバーヘッドがあるため、UTF-8 はバイナリエンコーディングとしては役に立ちません。Base64エンコーディングは、すでにそれよりも優れています。

score -3 · Accepted Answer

最近、バイナリを ascii としてエンコードする必要がありましたが、これが私が思いついたものです。これが最も効率的かどうかはわかりませんが (おそらくそうではありません)、シンプルで高速です。基本的に、バイトを 16 進数としてエンコードしますが、基本セット (0-9、AF) を使用する代わりに (ap) を使用します。セットは連続しているため、テーブルルックアップは必要ありません。

//buff is a unsigned character array containing the binary data
//N is the number of bytes to be encoded 
string simple_encode(unsigned char *buff, int N)
{
    string sEncode = "";
    for(int i = 0; i<N; i++)
    {
        sEncode += (97 + (buff[i] >> 4));
        sEncode += (97 + (buff[i] & 0x0F));
    }
    return sEncode;
}

//sbuff is a string containing the encoded ascii data
//szDecoded is an unsigned char array that has been allocated to 1/2 
//the length of sbuff
//N is an integer pointer and returns the number of converted bytes
void simple_decode(string sbuff, unsigned char *szDecode, int *N)
{
    *N = sbuff.length()/2;
    for(int i=0; i < *N; i++)
    {
        szDecode[i] = ((sbuff.at(2*i)-97) << 4) + (sbuff.at(2*i+1)-97);
    }
}

character-encoding - 最も効率的なバイナリからテキストへのエンコーディングは何ですか?

9 に答える 9

Related

Reference