按子词搜索字符串

Question

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

使文件包含在有序集中的内存中加载10000~行的行.使用给定的搜索字符串,我希望能够获得所有具有在搜索字符串中找到的单词前缀的单词的行.那么让我举一个例子来澄清这个:

行:

1. "眉毛狐狸飞了."
2. "盒子里装满了食物."
3. "猫跑得慢"
4. "狗讨厌老鹰"
5. "海豚有眼睛和teath"

案例1:

search string ="fl b a"

"眉毛狐狸飞了."

• 说明:搜索字符串有三个单词"fl","b"和"a",唯一的字符串中有一些以搜索字符串中的单词为前缀的单词是第1行.

案例2:

搜索字符串"e do ha"

"狗讨厌鹰","海豚有眼睛和teath"

解

(对我来说足够快,花了大约30ms~(包括对最终结果进行排序)在我的电脑上一组10k行每行3个字)

• 我在回答中使用了trie.
• 还有一些其他hacky方法可以过滤掉重复和误报结果(主要是为此使用哈希集).

Answer 1

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

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