Encode/Decode 最小字节数组中共享给定（非标准）字符集上的给定字符串

Question

我正在寻找一种通用算法，该算法可以将定义的字符集上的给定字符串编码/解码到/从字节数组。它必须使用最小的 space.

我开始开发我的算法，这是一种 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

Answer 1

您可以使用简单、快速的前缀代码，每个字符使用 k 或 k-1 位。那么最坏的情况是 m k bits for m characters.

对于基数 n，让 k = ceiling(log₂(n))。从 0 到 n-1 对符号进行索引。如果符号的索引 x 小于 2^k-n，则发出 x 作为 k-1 位整数。否则，将 2^k-n+x 作为 k 位整数发出。

这比分别需要 multiplication/division 的基础 encoding/decoding 快得多。让我们来看一个极端情况，其中基本编码恰好尽可能适合 64 位。（除了基数为 2、4、16 或 256 的微不足道的情况。）最好的情况是有 138 个符号，其中九个这样的符号正好适合 64 位，您可以使用机器64 位无符号整数的乘法和除法指令。 138⁹=18151468971815029248，即 2⁶⁴=18446744073709551616 的 98.4%。使用基本编码，每个符号有 7.111 位。使用上述前缀编码，每个符号平均有 7.145 位。

上述前缀编码是所有字符均等概率情况下的最优霍夫曼编码。如果不是这种情况并且您想实现一些压缩，那么您可以查看大量数据样本并为字符生成固定的霍夫曼代码，或者您可以单独对每条消息进行霍夫曼编码。在后一种情况下，您将承担随每条消息传输消息唯一霍夫曼代码的开销，这需要一定的可压缩性和长消息才能实现收益。

Encode/Decode 最小字节数组中共享给定（非标准）字符集上的给定字符串

Encode/Decode a given string on a shared given (non standard) charset in a minimal byte array

c#

string

encoding

compression

text-compression