0

我正在寻找一种通用算法，该算法在定义的字符集上对给定字符串进行编码/解码，该字符设置为/从字节数组中。它必须使用最小的空间。

我开始开发我的，这是一种从 Base'n' 到 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 位。

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

于 2015-06-26T23:25:32.500 回答