1

我有一个奇怪的要求，我似乎无法理解。我需要想出一个函数，该函数将接受一个文本字符串并返回一个与该字符串相对应的数字 - 这样，在排序时，这些数字将与原始字符串的顺序相同。例如，如果我的函数产生这个映射：

"abcd"  -> x
"abdef" -> y
"xyz"   -> z

那么数字必须是这样的x < y < z。字符串可以是任意长度，但总是非空的，并且字符串比较应该不区分大小写（即"ABC"并且"abc"应该产生相同的数值）。

我的第一个想法是将每个字母映射到相应的数字 1 到 26，然后只得到结果数字，例如a = 1, b = 2, c = 3, ..., z = 26，然后"abc"会变成1*26^2 + 2*26 + 3，但是后来我意识到文本字符串可以包含任何语言的任何文本（即完整的 unicode），所以这行不通。在这一点上，我被困住了。在我告诉客户草皮之前还有其他想法吗？

PS 这个奇怪的要求是由于专有系统的限制，只能按数字字段进行排序。如果任何其他字段类型需要排序，则必须将其转换为某种数字表示 - 然后进行排序。不要问。

4

1 回答 1

0

如果你允许任意精度的实数，你就可以完成这项工作，尽管这有点像作弊。Unicode 字符串是从 1,114,112 个选项中提取的字符序列。因此，您可以将它们视为以 1,114,113 为底的十进制数字：写 0.，然后写出您的 Unicode 字符串，然后您就有一个以 1,114,113 为底的实数（将每个字符的数值上移 1，以便缺失的字符具有值0)。在 base-1,114,113 中比较这些数字中的两个数字会按字典顺序比较数字：如果您从左到右扫描数字，则在两者之间的抢七中他们不同意的第一个数字。这种方法是完全不可行的，除非你有一个任意精度的实数库。

如果你只有 IEEE-734 双打，这种方法是行不通的。看到这一点的一种方法是最多有 2 64 个可能的双精度数（如果允许s，则最多有 2 80long double个），因为 a 中只有 64 (80) 位double，但有无限多不同的字符串。这消除了这种可能性，仅仅是因为有太多的字符串可以绕过。

不幸的是，如果您有任意精度的整数，您将无法完成这项工作。字符串的自然排序有一个有趣的属性，您可以找到在它们之间按字典顺序具有无限多个字符串的字符串对。例如，请注意

a < ab < aab < aaab < aaaab < ... < b

现在想象一下，您有一个函数将每个字符串映射到一个符合您想要的规则的整数。那将意味着

f(a) < f(ab) < f(aab) < f(aaab) < f(aaaab) < ... < f(b)

但这在整数中是不可能的——你不能有两个整数 f(a) 和 f(b)，它们之间有无限多个整数。（f(a) 和 f(b) 之间的整数个数最多为 f(b) - f(a) - 1）。

所以看起来答案是“如果你有任意精度的实数，这是可能double的，对于 s 是不可能的，对于任意精度的整数也是不可能的。” 我基本上会标记“在实践中不会发生”，即使理论上是可能的。:-)

于 2017-07-19T21:28:09.827 回答