1

我正在编写词典学软件，理论上可能需要使用任意（特定于词典项目的）排序规则对数万个字符串进行排序。有两种指定自定义排序规则的方法：

  1. 将字素映射到 unicode 样式的多级排序规则键。
  2. 一个按排序顺序排列的字母字素数组（可能包括二合字母等），可以在内部转换为排序规则的映射。

比较字符串的天真的方法是逐个检查字形，直到找到不匹配，然后查找不匹配字素的排序规则键进行比较，但我希望有一种更有效的方法。

到目前为止，我得到的最好的想法取决于注意到相等长度的字符串可以被视为 little-endian base-n 数字，因此我可以为每个字符串预先计算一个整数键，从而将排序规则转换为廉价的整数比较。但是，这会破坏不同长度的字符串（在对字典进行排序时很重要），并且对可以生成的整数的大小没有限制。为了考虑长度差异，我想我可以计算每个字符串的所有前缀的键列表，然后只比较长度等于被比较的较短字符串的前缀的键。这似乎做得很好，但密钥大小仍然是无限的，存储密钥可能会占用大量内存。

有没有办法改进这种方法？还是我只是完全错误地处理它，并且有一种更好的方法可以使用任意排序规则对字符串进行排序？

4

2 回答 2

2

逐字形基数排序怎么样？你得到 Big O n（单词数）* m（最长单词的长度）排序。这个想法应该相当简单，将所有以 A 开头的单词放在 A 存储桶中，Bs 放在 B 存储桶中，依此类推。

于 2012-10-25T01:04:44.090 回答
1

我不是专家，但我可能会建议在幼稚方法和您的方法之间进行某种混合。在每个字符串中查看固定数量的字节时，将其视为小端数并使用预先计算的排序规则。然后，如果它们相同，则移动到相同长度的下一组并执行相同操作。棘手的部分是处理可变长度字素（例如 UTF-8 或二合字母）。最简单的解决方案是在字典中使用固定宽度的表示，但可能还有另一种更复杂的解决方案，我现在想不出。

一旦到达较短字符串的末尾，您将零扩展它以满足下一个边界，然后进行比较。

您还可以查看排序规则的开源实现，看看它们是否做了更复杂的事情（例如 strcoll C 函数的 GNU 实现）。

于 2012-10-25T00:10:03.713 回答