algorithm - 按子词搜索字符串

Question

什么样的算法 + 数据结构可以帮助我做到这一点？

让一个文件包含大约 10000~ 行以有序集合的形式加载到内存中。对于给定的搜索字符串，我希望能够得到所有以在搜索字符串 中找到的单词为前缀的单词的行。好吧，让我举个例子来说明这一点:

行:

1. “一只眉毛狐狸飞过。”
2. “箱子里装满了食物。”
3. “猫跑得很慢”
4. “狗恨鹰”
5. “海豚有眼睛和茶”

案例1:

搜索字符串 = "fl b a"

“一只眉毛狐狸飞过。”

• 解释:搜索字符串包含三个词“fl”、“b”和“a”，并且 唯一有一些以单词为前缀的单词的字符串 来自搜索字符串的是第 1 行。

案例二:

搜索字符串“e do ha”

“狗恨鹰”、“海豚有眼有茶”

解决方案

(对我来说足够快，在我的电脑上用了大约 30 毫秒~(包括对最终结果进行排序)在一组 10k 行上，每行 3 个单词)

• 我在回答中使用了建议的 trie。
• 以及其他一些能够过滤掉重复和误报结果的 hacky 方法(为此主要使用哈希集)。

Answer 1

我认为您可能想要的是 trie .为文档中所有单词的集合构造一个，并让每个叶子指向一个哈希集，该哈希集包含叶子的键出现的行的索引。

要执行搜索，您将使用搜索字符串的每个片段导航到树中的一个节点，并对该节点子树中所有叶子的哈希集进行并集。然后，您将这些并集与片段集相交，以获得满足搜索字符串的行列表。