.net - 快速中缀搜索

Question

我正在构建一个自动完成功能，它必须快速查询 10 多万个单词/短语，并且遇到了一些问题。我的第一个想法是通过某种特里/三叉树结构，但这些都是严格的前缀匹配，这对我的应用程序来说还不够好(我想要完全中缀匹配)。然后我转向了一些更大的解决方案，SqlServer FullText Indexing、Lucene、Solr、Sphinx，但 Lucene 和 SqlServer FullText Indexing 实际上不是全文，而是带有漂亮功能的前缀(soundex、proximity 等)。我试图想出一种 Levenshtein 编辑距离可以提供帮助的方法，但找不到一种方法来至少合理准确并支持具有高编辑距离的单词(即 google 和 ogl。编辑距离为 3，但 3 是在一般情况下提高阈值的方法)。

我的问题是，像 Google/bing 等强者是如何做到的？他们只是在一段时间后暴力破解吗？我想不会，但我找不到任何支持。

任何帮助，将不胜感激!

Answer 1

如果您启用 queryParser.setAllowLeadingWildcard(true);在 Lucene 中，您可以使用前导和尾随通配符，例如:

*talli*

这将提取所有包含“talli”的单字词，包括“Metallica”。

这对您来说可能不够快，但在某些情况下(精确的仅前缀通配符搜索)如果您可以预处理查询字符串，您可能能够使用旧的“反转术语和索引”技巧:

acillateM