我感兴趣的是用最少的字节数表示有限集中的符号序列。
例如,假设您有一个仅包含字符 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
所以我的问题是,是否有一种比我描述的方法更节省空间的方法来编码有限集中的元素列表?
最佳答案
使用基数n,其中n是符号的数量(例如{a => 0, b => 1, c => 2}
)。如果每个符号出现的可能性相同,则该方法是最佳的。 (当然,您还必须存储字符串的长度。顺便说一句,您的实现使用 Python 字符串;这些绝对不是您能找到的最节省空间的数据结构。)
如果符号的频率有所不同,并且您知道它们,则可以使用 Huffman coding 。如果您不知道频率,可以输入 adaptive Huffman coding .
无论如何,最好的方法取决于应用程序。
关于python - 对有限集中的符号列表进行编码的最紧凑方法是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8995552/