问题背景
大家好,我正在处理一个搜索相关文档的项目,基于提供的查询。由于这是一个小型项目,我的内存结构很典型,我假设我没有超过100个文档,每个文档不超过1000个单词(一个单词不超过10个字符)。我会收到许多查询,并且必须尽快处理查询(绝对不能超过1秒)。
我的第一种方法(幼稚且不可扩展):
由于用户可以上传文档,因此每当我收到一个文档时,我会查找“潜在”关键字并将关键字作为键和文档作为值对或在MYSQL表中存储。显然,这必须手动完成,不像程序员所做的那样。
我的第二种方法(略微改善):
我取出每个文档,扫描其中的每个单词,并将此单词添加到Trie数据结构中,因此对于100个文档,我必须搜索100个Trie,并且如果查询长度为l,则该方法将花费最坏的O(所有文档中的单词数*最大单词长度)来构建trie,并查询O(查询长度)。这相当合理。 为了实现这一点,我将每个文档的Trie根节点保留在向量中,并遍历每个Trie节点并在每个Trie内搜索。如果我至少匹配查询的一半单词,我将将该文档存储为潜在结果。我不会给出超过某个截止文档数的结果。
我的问题:
我想问问社区,您对我的方法有何看法?我如何优化它们?我可以在现有方法中进行哪些其他改进?是否可以使用其他算法或数据结构更有效地完成此任务? 在浏览网络时,我发现了像Boyer-Moore和Aho-Corasick这样的算法,以及一些建议调整Lucene Apache所实现的算法等。你有什么建议吗?