仍然排序的最佳整数编码

Question

UTF-8的一个优点是,如果你逐个字节地比较两个字符串(带有<),你会得到相同的答案,就好像你比较了它们逐个代码点.我想知道是否有类似的编码是最佳的大小(例如UTF-8"浪费"空间,通过用10xxxxxx标记字节,如果它们不是表示代码点的第一个字节).

这里的最优性假设是,如果n < m,则非负数n比数m更频繁.

我最感兴趣的是知道是否存在适用于整数的(字节可比较的)编码,其中n比m更频繁.n | <| m |.

Answer 1

您是否考虑过霍夫曼编码的变体？传统上，人们会递归地合并两个最不频繁的符号，但为了保持顺序，人们可以合并具有最小和的两个相邻符号。

看起来这个问题已经被充分研究了（并且贪心算法不是最优的）。最佳算法由 Hu 和 Tucker 给出，在此处进行了描述，并在本论文中进行了更详细的介绍。

这篇讨论基于字典的保序压缩的论文看起来也很有趣。