math - 仍然排序的最佳整数编码

Question

UTF-8 的一个简洁特征是，如果您逐字节比较两个字符串（带有 <），您会得到与逐个代码点比较它们相同的答案。我想知道是否有类似的编码在大小上是最佳的（例如，如果它们不是代表代码点的第一个字节，则 UTF-8 通过用 10xxxxxx 标记字节来“浪费”空间）。

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

我最感兴趣的是知道是否存在适用于整数的（字节可比的）编码，n比m更频繁if | n | < | 米|。

Answer 1

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

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

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

Answer 2

标准编码很少，答案是否定的。UTF-8 之外的任何进一步优化都不应称为“编码”，而应称为“压缩” - 字典上可比的压缩是不同的部门。

如果您要解决现实世界（非纯学术）的问题，我会坚持使用最标准的 UTF8。您可以在 utf8everywhere.org 上了解它与其他标准编码相比的效率。

Answer 3

要完全回答这个问题，您需要知道材料中代码点的频率。UTF-8 最适合英文文本，因为多字节字符在典型的英文文本中非常少见。

使用 UTF-8 作为基本算法对整数进行编码需要将前 n 个整数映射到 1 字节编码，接下来的 m 映射到 2 字节编码等等。这是否是最佳编码取决于分布。如果与较大的数字相比，前 n 个数字非常频繁，那么 UTF-8 将是（接近）最优的。