为二进制搜索预处理一组常量字符串

Question

我有几个字符串的排序列表（大小= K < 1000）。我需要在排序列表中查找数十亿（大小= N）字符串的插入位置。该列表保持不变，并将字符串插入到子节点中。

现在的问题是：我目前使用二进制搜索，其时间成本是O（strlen * NlogK）。但是，因为排序的列表是恒定的。我想知道在小排序列表上是否有预处理方法使搜索比logK更快？

Answer 1

一些很好的替代品包括Trie，或perfect hash table（可能为Patricia trie或ternary search tree实现）。

编辑：要找到“插入位置”使用一个trie的非匹配字符串，首先标记每个完整的字符串与它的位置（当你最初建立trie时，你可以做到这一点）。当搜索不匹配的字符串时，您会在不匹配的字符串中的第一个索引处检测到该字符串。

例如，假设您在包含CAN NOT和CATASTROPHE的trie中查找字符串CAR（并且没有其他相关内容）。您会在R处检测到这种不匹配，因为R不在A以下。但是，应该很容易知道该位置的周围字母是N和T.前往N然后继续向下并向右会把你带到不能去的地方。或者，去T，然后继续往下走，会带给你灾难。

Answer 2

除了Chris Okasaki，我建议你计算每个树节点（trie或patricia）在相应子树中的树叶数量（你可以用深度优先遍历来做到这一点）。

为了与你走在树和叶子的数量之和（即预先计算），你在离开子树被从当前位置留下了一个字符串的查询。当你在位置停下来时，如果不与查询字符串发生冲突，就不能继续树形路径，这意味着你可以找到这个字符串的位置。指数是用总和计算的所有留下的叶子的数量。