对有限集合中的符号列表进行编码的最简洁的方法是什么？

Question

我感兴趣的是用最少的字节数表示有限集中的符号序列。在

例如，假设您有一个只包含字符a-z的文本字符串，您可以将它们编码为ascii，因此每个符号（字符）为1个字节。但是，通过这样做，您只使用了每个字节可能的256个值中的26个。在

我已经编写了一个似乎运行良好的解决方案，但我想知道是否有人知道或能想出更好的方法。在

我的方法是将序列视为以n为基数的整数，其中n是the size of the set of symbols + 1。例如，如果你的集合或符号，或者“字母表”是{a, b, c}（长度3），那么我们就用4为基数。这些符号被赋予了数值，因此{a => 1, b => 2, c => 3}。因此，序列[b, a, c]被视为基数4中的数字213，因此十进制数为39。这个整数可以用二进制编码，并解码回它的基4表示，以检索序列2, 1, 3 => [b, a, c]。在

我的Python实现上面的：radixcodec.py

所以我的问题是，有没有比我所描述的更节省空间的方法来编码有限集中的元素列表？在

Answer 1

使用basen其中n是符号的数目（例如{a => 0, b => 1, c => 2}）。如果每个符号出现的可能性相等，则该方法是最佳的。（当然，您还必须存储字符串的长度。顺便说一句，您的实现使用Python字符串；这些字符串绝对不是您能找到的最节省空间的数据结构。）

如果符号的频率不同，并且您知道它们，可以使用Huffman coding。如果你不知道频率，有adaptive Huffman coding。在

无论如何，最好的方法取决于应用程序。在