algorithm - 是否有一种有效的算法来执行反向全文搜索？

Question

我在数据库中有一个包含数千个关键字(每个关键字中有一个或多个单词)的有限列表。我想有效地找到给定输入文本中的哪些关键字，而不必一个一个地测试每个关键字(全表扫描)。允许匹配文本中一些拼写错误的单词会更好，但不是必需的。有什么算法/文章建议可以解决这个问题吗？

Answer 1

我认为到目前为止的一些答案误解了所问的问题。我的理解是你有一个(大的)单词列表和一个(大的)正文。您想知道两个列表有哪些相同的词，对吗？

如果是这样，这根本就不是全文问题。基本上，您只有两个单词列表(您的原始关键字和输入文本中的单词列表)。如果对两个列表进行排序，您可以同时浏览两个列表并提取共同的单词。

假设关键字列表已经排序，您可以在 O(n logn) 时间内从文本正文中提取和排序单词，然后同时扫描两个列表是 O(n+m)(其中 n 是正文中的单词数，m 是关键字列表中的单词数)。