algorithm - 请建议一个智能静态单词完成算法

Question

这不是作业；我正在尝试简化和增强用 C#/Winform/Sql Server 2008 编写的现有笨拙的 GUI 界面。如果你能对这些技术提出一些特定的东西，那会很酷，但如果你能指出其他东西，比如 Java/MySql 解决方案，那么我也会对此感到满意。

有人问过类似的问题，但问题/答案并不像我所追求的那样先进:Given a list of words - what would be a good algorithm for word completion in java? Tradeoffs: Speed/efficiency/memory footprint

假设我有一个包含书籍信息的表格:书名、作者姓名、描述。我知道，这三个不一定都属于同一张表，但我们假设这样做是有意义的。因此，当用户在文本框/组合框或某些自定义控件中键入内容(比如“Hari po”)时，他们应该得到的第一个建议可能是“Harry Potter”，以及相应的描述和作者。为了使问题简单化，让我们将搜索限制在标题上。请注意，我不在乎“Hari”听起来像“Harry”——该应用程序并非针对非母语人士，但我确实关心“Hari po”与“Harry Po”仅几步之遥这一事实。所以，http://en.wikipedia.org/wiki/Levenshtein_distance想到了，但这并不是我所需要的，因为我希望在我开始输入时立即获得有意义的结果(考虑不同目的的谷歌建议)。我需要某种经过修改的 Levenshtein 距离算法，它可以很好地处理部分匹配，并且不会假设我输入的内容应该位于我要匹配的文本的开头。例如，这本书可能叫做“这个叫哈利·波特的男孩如何影响我们的社会。”，我确实希望这个书名出现在搜索中，但是，我希望看到类似“哈利·波特与骑士团”的内容the Phoenix” 出现在顶部，因为我的查询以此开头。

我可以针对查询长度 +/- 2 的所有可能子字符串多次尝试 Levenshtein 距离，然后通过子字符串“sort off”出现在字符串中的位置以某种方式对它们进行加权，然后选择最大值匹配系数。我这样做的第一个担心是效率低下。其次，必须有办法获得更好的结果，即使速度不是问题。第三，以前肯定有人做过类似的事情，为什么要重新发明轮子？

数据库中的唯一行数将达到 20,000。我所追求的有点像 Google 搜索建议或 Visual Studio 2010 IntelliSense(代码自动完成)，只是它不应该尝试记住用户过去输入的内容并根据此调整建议。不需要做查询扩展；只处理实际内容。从用户的角度来看，它应该类似于 Google 搜索和 IntelliSense，例如它应该提出一些排名的选择，并且还提出一种智能的方法来在正确的点切断该列表(例如，如果没有任何东西真正匹配查询，那么什么都不建议而不是显示最差的最佳匹配) ，并且如果前几个结果的排名很高，但随后的结果相对于最前面的结果要弱得多，那么也许隐藏弱的。

也许您知道一个大小合理的开源工具/库，其中公开了可读的源代码，我可以从中获取灵感？

我的下一个问题是关于如何最好地处理搜索词可应用于标题、和/或作者和/或描述的情况，但我怀疑我当前的问题已经加载。

如果对我所追求的内容有任何不清楚的地方，请提出澄清问题。

Answer 1

我建议好好看看 Lucene .它支持广泛的查询类型，包括(我认为)增量搜索、近似搜索。此外，它是开源且免费的。 :)