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

Question

私が今までに見つけた最も近い候補は、yEnc（2％）とASCII85（25％のオーバーヘッド）です。主に8ビットの文字セットを使用していることを考えると、yEncではいくつかの問題があるようです。これは別の考えにつながります：UTF-8文字セットに基づくバイナリからテキストへのエンコードがありますか？

Answer 1

インスピレーションのため、the Twitter Image Encoding Challengeをチェックしてください。これは、できるだけ多くの画像情報を140 Unicode文字でエンコードすることに関するものです。これは本質的に、画像データに特に関連した質問の損失の多いバージョンです。

Answer 2

これは本当にバイナリデータの性質と、 "text"が出力に与える制約に依存します。

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

今、なぜテキストが必要ですか？通常、通信チャネルはすべての文字を均等に通過しないためです。例えば印刷可能な文字の範囲が0x20-0x7Eの純粋なASCIIテキストが必要な場合があります。あなたは95文字で遊ぶことができます。各文字は理論的にlog2（95）〜= 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ビットを表します。 A6ビットシンボルおよびB7ビットシンボルを有する場合、

A + B = 95（シンボルの総数） 2A + B = 128（7ビットプレフィックスの総数2つの接頭辞を6ビットの記号で開始することも、7ビットの記号で開始することもできます）。

システムを解決すると、A = 33、B = 62となります。

 
Raw  Encoded 
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ビットの出力を生成します。

一様分布のデータの場合、これは最適だと思います。あなたのソースにあるものよりもゼロが多いことがわかっている場合は、7ビットコードをスペースの先頭にマッピングして、7ビットコードを使用する可能性が高くなるようにします。

Answer 3

あなたは既に答えがあるようなサウンド、Mark。 UTF-8はバイナリエンコーディングとしては有用ではありません。なぜなら、1バイトを超えるUTF-8文字は、テキスト（バイトあたり2ビット以上）を格納する場合でも25％を超えるオーバーヘッドを持つからです。 Base64エンコードは既にそれより優れています。 Wikipediaによれば

Answer 4

はWikipediaに記載されているものに "basE91は、圧縮8ビットバイナリ入力するための最短プレーンASCII出力を生成"

Answer 5

次に、Bommanewsある：

B- UUEncodeおよびBase64エンコーディングに固有のオーバーヘッドの重さを取り除くために、ニュース（またはBommanews）が開発されました。新しいエンコード方法を使用して、バイナリデータをテキストメッセージに埋め込みます。この方法は、より多くのCPUリソースを消費しますが、UUEncodeの約40％から、メッセージ内のANSI制御コードの使用を避けながら、これらの数字の間の小数点がモニタの汚れではないことを約40％から低下させます体。 source

yencのは、B-ニュースより少ないCPU集約型で、オーバーヘッドの同じ低レベル程度に達するが、それはすべての制御コードの使用を避けることはありません：

それはyencのに匹敵します（実験的に）観察されたものをいくつかのサーバーに望ましくない影響を与えないようにしているだけです。つまり、B-NewsよりもRFCに準拠していません。

• http://b-news.sourceforge.net/
• http://www.iguana.be/~stef/
• http://bnews-plus.sourceforge.net/

Answer 6

短い答えは次のようになります。いいえ、まだありません。

コントロール文字、バックスラッシュ、引用符のないUTF-8を意味するJSON文字列に多くの情報をエンコードすることで問題が発生しました。

私は出て、有効なUTF-8バイトにいくつのビットを絞ることができるか調べました。私は、UTF-8があまりにも多くのオーバーヘッドをもたらすことを示す回答には同意しない。それは真実ではない。

1バイトシーケンスのみを考慮すると、標準ASCIIと同じくらい強力です。 1バイトあたり7ビットを意味します。しかし、すべての特殊文字を切り取ると、Ascii85のようなものが残されます。

しかし、より高い飛行機では制御文字が少なくなります。したがって、6バイトのチャンクを使用すると、チャンクごとに5バイトをエンコードできます。出力には、任意の長さのUTF-8文字の組み合わせ（1〜6バイト）が得られます。

これはAscii85：4/5の代わりに5/6より良い結果をもたらし、80％ではなく83％の効率をもたらします。理論的にはチャンクの長さを増やすとさらに向上します.19バイトのチャンクで約84％です。

私の意見では、エンコーディングプロセスはあまりにも複雑になり、利益はほとんど得られません。だからAscii85またはそれのいくつかの修正版（私はZ85を見ている）が良いだろう。

Answer 7

昨年、最も効率的なバイナリからテキストへのエンコードを探しました。私はコンパクトさが唯一の基準ではないということを自分自身で認識しました。最も重要なのは、エンコードされた文字列を使用できる場所です。たとえば、yEncには2％のオーバーヘッドがありますが、これは8ビットのエンコードであるため、その使用は非常に制限されています。

私の選択はZ85です。許容されるオーバーヘッドは25％で、エンコードされた文字列はXML、JSON、ソースコードなどほぼすべての場所で使用できます。詳細はZ85 specificationを参照してください。

最後に、私はZ85 libraryをC/C++で書いて、本番環境で使用しています。

Answer 8

私は最近asciiとしてバイナリをエンコードする必要がありました。これが私が思いついたものです。私はこれが最も効率的（おそらくない）かどうかわからないが、それは単純で速い。 基本的には、バイトを16進数でエンコードしますが、基本セット（0-9、A-F）ではなく（a-p）を使用します。セットは連続的なので、テーブルルックアップは必要ありません。 yencのバイナリをテキストに変換しない

//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); 
    } 
}