如何最紧凑地编码有限集合中的符号列表？

Question

我想用尽可能少的字节来表示一个有限集合中的符号序列。

举个例子，假设你有一个只包含字母a到z的文本字符串。你可以用ASCII编码来表示它们，这样每个符号（字符）占用1个字节。但这样做的话，你实际上只用了256个字节中可能的26个值。

我写了一个看起来效果不错的解决方案，但我想知道有没有人知道或者能想到更好的方法。

我的方法是把这个序列当作一个以n为底的整数来处理，其中n等于符号集合的大小 + 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

使用基数 n，其中 n 是符号的数量（比如 {a => 0, b => 1, c => 2}）。这种方法在每个符号出现的概率相同的情况下是最优的。（当然，你还需要存储字符串的长度。顺便提一下，你的实现使用的是Python字符串；这并不是最节省空间的数据结构。）

如果符号的出现频率不同，并且你知道这些频率，可以使用 霍夫曼编码。如果你不知道频率，可以使用 自适应霍夫曼编码。

总之，最好的方法取决于具体的应用场景。