仍然可以排序的最佳整数编码

Question

UTF-8 的一个巧妙特征是，如果您比较两个字符串（使用 <) byte-by-byte, you get the same answer as if you had compared them codepoint-by-codepoint. I was wondering if there was a similar encoding that was optimal in size (e.g. UTF-8 "wastes" space by tagging bytes with 10xxxxxx if they are not the first byte representing a codepoint).

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

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

Answer 1

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

看起来这个问题已经被充分研究了（而且贪心算法不是最优的）。 最佳算法由 Hu 和 Tucker 给出，在here 进行了描述，并且在本thesis中有更多详细信息。

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

Answer 2

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

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

Answer 3

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

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

Answer 4

Levenshtein 编码是渐近最优的并且保留了顺序。它还具有零 (0) 和一 (10) 的短代码。对于介于两者之间的数字（例如 256 到 65536）来说并不是最佳选择。实施起来也不难。