algorithm - 自动完成的后端

Question

这是一道面试题：为自动完成设计一个分布式后端。

我会回答如下：

自动完成是按给定后缀在字典中搜索。字典应该被组织成trie。该词典是根据最常见的查询构建的，但这是另一回事。

现在我假设字典不会经常更改（例如，每天一次而不是每毫秒一次）。因此，我们可以在处理自动完成查询的多个服务器之间复制字典（例如，使用负载平衡器和循环策略）。

我们也应该考虑字典，但这也是另一回事。

是否有意义？我错过了什么吗？

Answer 1

看看SOLR 4.0是什么（solr 有 trie 并且是分布式的）。它高度依赖于他们期望自动完成功能如何工作。如果它只是一个通配符过滤器，而不是像 trie 这样的东西，对于简单的 ASCII 来说就可以了……否则，如果他们想要自动更正，它会变得更加复杂。话虽这么说，我怀疑如果它是一个通用字段（即不是 SKU 或专用 ID），它会为您带来良好的结果，否则您将拥有一个非常大且效率低下的 trie。

看一眼：

• 具体看它的Suggester：http ://wiki.apache.org/solr/Suggester
• 和 Solr 的分析器：http ://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters
  • 更具体地说：http://wiki.apache.org/solr/AnalyzersTokenizersTokenFilters#solr.EdgeNGramFilterFactory

Answer 2

这看起来是个正确的问题。trie 的想法非常好，可以帮助您在log(n). 更改频率取决于信息，所以我不会说确切的时间，但我会动态调整它。假设您每天更改一次，如果树发生了多大变化，那就太好了。并且您可以给出一个边界（例如 10%）。如果超出边界，您可以更频繁地更新 trie。这还取决于保持最新状态的重要性，因为在大多数情况下并非如此。负载均衡器的想法也不错。