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

Question

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

问题是:我目前使用的是二分查找，时间成本是O(strlen * NlogK)。但是由于排序列表是不变的。不知是否有一种对小排序列表进行预处理的方法，使搜索比logK更快？

Answer 1

一些不错的选择包括 Trie (可能实现为 Patricia trie 或 ternary search tree )，或 perfect hash table .

编辑:要使用 trie 查找不匹配字符串的“插入位置”，首先用其位置标记每个完整的字符串(您可以在最初构建 trie 时这样做)。搜索不匹配的字符串时，您会在不匹配的字符串中的第一个索引处检测到这一点。

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