从 utf8 到字节数组的顺序保留映射
Order preserving mapping from utf8 to an array of bytes
我正在使用一种算法来索引任意大的已知固定大小（例如 64 位或 128 位）的无符号整数。我也希望能够将它应用于 utf-8 字符串，但为了做到这一点，我需要有一种可靠的方法来将任意长度的给定字符串映射到固定大小的无符号字节数组至少保留字符串前缀的字典顺序的方式。
最简单的做法是简单地获取字符串的前 X 个字符，并为每个字符提供完整的四个字节，并根据需要在实际值前面加上零。但是，这将占用 X * 4 字节。我希望有一种方法可以做到这一点 space-高效。
---- 编辑 ----
非常重要：有碰撞是可以接受的。
使用上述的简单方法并给出字符串：
['Alabama', 'Alakazam', 'Alaska', 'Arkansas', 'Corduroy']
如果我们将 X 设置为 3，则 'Alabama'、'Alaska' 和 'Alakazam' 会发生冲突——只会产生三个唯一的 12 字节值映射（'Ala'、'Ark' 和 'Cor' 的每个字符 4 个字节的表示）。但是，这三个值保持其字典顺序非常重要。
我们必须使用 4 个字节，因为（我相信）这是 utf-8 中单个字符可以占用的最大大小。为了保证我们的映射给我们一个固定大小的字节数组（至少在这个方案中），我们必须有偶数的ASCII字符，通常只占用一个字节，最多占用四个字节。
'A' => 01100001，用零填充：00000000000000000000000001100001
'l' => 01101100，用零填充：00000000000000000000000001101100
'a' => 01100001，用零填充：00000000000000000000000001100001
因此，在 X = 4 的示例中，任何以 'Ala' 开头的字符串都将映射到：
000000000000000000000000011000010000000000000000000000000110110000000000000000000000000001100001
当被视为 96 位无符号整数时，它的值将小于我们示例中其他前缀（'Ark' 和 'Cor'）的映射值，因此满足映射保留我们的字典顺序的要求。
此方案有效，但将任何字符串的大小要求增加了 4 倍之多。希望找到一种映射方案，以少于 X * 4 个字节完成 utf-8 前缀索引。
令人高兴的是，结果是 UTF-8 编码的字符串 can be sorted lexicographically as-is。
Sorting order: The chosen values of the leading bytes and the fact that the continuation bytes have the high-order bits first means that a list of UTF-8 strings can be sorted in code point order by sorting the corresponding byte sequences.
通过将字符串的字节序列截断为 fixed-length 前缀，您可以实现上述问题中描述的内容。
我正在使用一种算法来索引任意大的已知固定大小（例如 64 位或 128 位）的无符号整数。我也希望能够将它应用于 utf-8 字符串，但为了做到这一点，我需要有一种可靠的方法来将任意长度的给定字符串映射到固定大小的无符号字节数组至少保留字符串前缀的字典顺序的方式。
最简单的做法是简单地获取字符串的前 X 个字符，并为每个字符提供完整的四个字节，并根据需要在实际值前面加上零。但是，这将占用 X * 4 字节。我希望有一种方法可以做到这一点 space-高效。
---- 编辑 ----
非常重要：有碰撞是可以接受的。
使用上述的简单方法并给出字符串：
['Alabama', 'Alakazam', 'Alaska', 'Arkansas', 'Corduroy']
如果我们将 X 设置为 3，则 'Alabama'、'Alaska' 和 'Alakazam' 会发生冲突——只会产生三个唯一的 12 字节值映射（'Ala'、'Ark' 和 'Cor' 的每个字符 4 个字节的表示）。但是，这三个值保持其字典顺序非常重要。
我们必须使用 4 个字节，因为（我相信）这是 utf-8 中单个字符可以占用的最大大小。为了保证我们的映射给我们一个固定大小的字节数组（至少在这个方案中），我们必须有偶数的ASCII字符，通常只占用一个字节，最多占用四个字节。
'A' => 01100001，用零填充：00000000000000000000000001100001
'l' => 01101100，用零填充：00000000000000000000000001101100
'a' => 01100001，用零填充：00000000000000000000000001100001
因此，在 X = 4 的示例中，任何以 'Ala' 开头的字符串都将映射到：
000000000000000000000000011000010000000000000000000000000110110000000000000000000000000001100001
当被视为 96 位无符号整数时，它的值将小于我们示例中其他前缀（'Ark' 和 'Cor'）的映射值，因此满足映射保留我们的字典顺序的要求。
此方案有效，但将任何字符串的大小要求增加了 4 倍之多。希望找到一种映射方案，以少于 X * 4 个字节完成 utf-8 前缀索引。
令人高兴的是，结果是 UTF-8 编码的字符串 can be sorted lexicographically as-is。
Sorting order: The chosen values of the leading bytes and the fact that the continuation bytes have the high-order bits first means that a list of UTF-8 strings can be sorted in code point order by sorting the corresponding byte sequences.
通过将字符串的字节序列截断为 fixed-length 前缀，您可以实现上述问题中描述的内容。