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

Question

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

问题是：我目前用的是二分查找，时间成本是O(strlen * NlogK)。但是由于排序列表是恒定的。不知道有没有在小排序列表上的预处理方法让搜索比logK快？

Answer 1

一些不错的替代方案包括Trie（可能实现为Patricia trie或三元搜索树）或完美哈希表。

编辑：要使用 trie 查找不匹配字符串的“插入位置”，首先用其位置标记每个完整的字符串（您可以在最初构建 trie 时执行此操作）。搜索不匹配的字符串时，您将在字符串中不匹配的第一个索引处检测到这一点。

例如，假设您在包含 CANNOT 和 CATASTROPHE（没有其他相关内容）的 trie 中查找字符串 CAR。您会在 R 处检测到这种不匹配，因为在 A 下方没有 R 子代。但是应该很容易看出该位置周围的字母是 N 和 T。转到 N 然后向下向右会带你到 CANNOT，在那里你可以读出位置。或者，去 T 然后继续往下和左转会给你带来灾难。

Answer 2

除了 Chris Okasaki 之外，我可能会建议您为每个树节点（trie 或 patricia）计算相应子树中的叶子数（您可以通过深度优先遍历轻松完成）。

要使用字符串进行查询，请按树和叶子的总和（预先计算的）总和，您在当前位置留下的子树中留下。当您停在某个位置并且您无法在不与查询字符串冲突的情况下继续树路径时，这意味着您找到了该字符串的位置。索引是用总和计算的所有左侧叶子的数量。