对有限集中的符号列表进行编码的最紧凑方法是什么？
我感兴趣的是用最少的字节数表示有限集中的符号序列。
例如，假设您有一个仅包含字符 az 的文本字符串。您可以将它们编码为 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
所以我的问题是，是否有一种比我描述的方法更节省空间的方法来编码有限集中的元素列表？
I'm interested in representing a sequence of symbols from a finite set in the least number of bytes.
For example, say you had a text string which only contained the characters a-z. You could encode them as ascii, so 1 byte per symbol (character). However, by doing that you're only using 26 of the possible 256 values per byte.
I've coded a solution which seems to work well, but I'd like to know if anyone knows or can think of a better way.
My method is to treat the sequence as an integer in base n, where n is the size of the set of symbols + 1. For example, if your set or symbols, or "alphabet" was {a, b, c} (length 3) then we'd use base 4. The symbols are assigned numerical values so {a => 1, b => 2, c => 3}. Therefore, the sequence [b, a, c] is treated as the number 213 in base 4, so 39 in decimal. This integer can be encoded in binary, and decoded back to its base 4 representation to retrieve the sequence 2, 1, 3 => [b, a, c].
My Python implementation of the above: radixcodec.py
So my question is, is there a more space efficient method of encoding lists of elements from a finite set than the one I've described?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
使用基数 n，其中 n 是符号的数量（例如
{a => 0, b => 1, c => 2}< /代码>）。如果每个符号出现的可能性相同，则该方法是最佳的。 （当然，您还必须存储字符串的长度。顺便说一句，您的实现使用 Python 字符串；这些绝对不是您能找到的最节省空间的数据结构。）如果符号的频率不同，并且您知道它们，您可以使用霍夫曼编码。如果您不知道频率，可以使用自适应霍夫曼编码。
无论如何，最好的方法取决于应用程序。
Use base n where n is the number of the symbols (e.g.
{a => 0, b => 1, c => 2}). That method is optimal if each symbol is equally likely to appear. (You'll also have to store the length of the string, of course. By the way, your implementation uses Python strings; those are definitely not the most space-efficient data structure you can find.)If the frequencies of the symbols vary, and you know them, you can use Huffman coding. If you don't know the frequencies, there's adaptive Huffman coding.
Anyway, the best method will depend on the application.