0

バイト配列に/から設定された定義済みの文字列で特定の文字列をエンコード/デコードする汎用アルゴリズムを探しています。最小限のスペースを使用する必要があります。

Base'n' to Base 2 アルゴリズムの一種である私の開発を始めましたが、そのようなものはすでに開発されているに違いないと思います。

私の必要性は、既知の制限された文字セットを使用して、最小限のビット数の文字列でエンコードすることです。多分私はbzip2を使うべきですか？

編集:文字列の長さの最大値は 160 文字です。必要に応じてパディングできます。

Edit2: 最悪の場合のビット数を知っている必要があります。

byte[] encode(string charset, string value)

string decode(string charset, byte[] encodedValue)

使用法：

string myString = "HELLO WORLD";
string charSet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "; // Base 27
byte[] encodedString = encode(charset, myString); // Base 27 -> Base 2
Debug.Assert(myString.Equals(decode(charset, encodedString))); // Base 2 -> Base 27
4

1 に答える 1

2

文字あたりk ビットまたはk -1ビットを使用する単純で高速なプレフィックス コードを使用できます。次に、最悪のケースは、 m文字に対してmkビットです。

ベースnの場合、k = 上限 (log 2 ( n )) とします。シンボルに 0 からn-1までのインデックスを付けます。シンボルのインデックスxが2 k -n未満の場合、xをk-1ビット整数として出力します。それ以外の場合は、2 k -n+xをkビット整数として出力します。

これは、それぞれ乗算/除算を必要とする基本エンコード/デコードよりもはるかに高速です。基本エンコーディングがたまたま 64 ビットにできるだけうまく収まるという極端なケースを見てみましょう。(基数が 2、4、16、または 256 などの些細なケースを除きます。) 最良のケースは、138 シンボルがあり、9 つのそのようなシンボルが 64 ビットにちょうど収まる場合であり、マシンを使用できます。 64 ビット符号なし整数の乗算および除算命令。138 9 =18151468971815029248、これは 2 64 =18446744073709551616 の 98.4% です。基本エンコーディングでは、シンボルあたり 7.111 ビットです。上記のプレフィックス エンコーディングでは、シンボルあたり平均 7.145 ビットになります。

上記のプレフィックス エンコーディングは、すべての文字の確率が等しい場合に最適なハフマン コードです。そうではなく、ある程度の圧縮を実現したい場合は、データの大規模なサンプルを調べて文字の固定ハフマン コードを生成するか、各メッセージを個別にハフマン コード化することができます。後者の場合、各メッセージでメッセージ固有のハフマン コードを送信するオーバーヘッドが発生します。これには、特定の圧縮性と長いメッセージが必要であり、利益を実現できます。

于 2015-06-26T23:25:32.500 に答える