language-agnostic - 全文搜索优化技术

Question

我有一本300000+字的书。
每个单词都有元数据(语法信息；解析细节和词条 [词根形式])

构建数据的最佳方式是什么，以便我可以搜索单词或单词组并快速获得结果。我也希望能够根据对元数据的要求进行搜索。

我需要能够搜索准确的短语或只搜索彼此接近的词。

我的问题是关于数据库设计和查询方法。

Answer 1

在这种情况下，我强烈推荐 Rabin–Karp 算法。尽管 Rabin-Karp 不如其他一些搜索算法快，但它擅长匹配多个模式，并且由于您说过您将搜索多个短语和词条，因此它是最合适的。平均情况和最佳情况都在 O(n + m) 中，其中 n 是 300,000 个单词的总长度，m 是您要搜索的模式的总长度。在最坏的情况下，您达到了 O(mn) 时间。

就存储数据而言，您可以使用大型哈希滚动表或更理想的 bloom filter .

这里有一些相关的问题、文章和 C 和 ruby​​ 的实现。希望这会有所帮助。

• Using Rabin-Karp to search for multiple patterns in a string
• Hashing n-grams by cyclic polynomials - java implementation
• String Searching Algorithm Comparison
• The Rabin-Karp Algorithm (Harvard Article)
• Pattern Searching
• C implementation
• Ruby implementation