请建议一个智能静态字完成算法

这不是一个家庭作业;我试图简化和增强用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”）时，第一个建议可能是“哈利波特”，以及相应的描述和作者。为了简化问题，我们只将搜索限制在标题中。请注意，我不在乎“Hari”听起来像“Harry” - 该应用程序不针对非母语人士，但我确实在意“Hari po”离“Harry Po”只有几个击键。所以，我想到了http://en.wikipedia.org/wiki/Levenshtein_distance，但这并不完全是我需要的，因为我一开始打字就想获得有意义的结果（认为Google的建议有不同的目的）。我需要某种修改的Levenshtein距离算法，该算法可以很好地与部分匹配，并且不会假设我输入的内容应该在我尝试匹配的文本的开头。例如，这本书可能被称为“这个叫哈利波特的男孩如何影响我们的社会”，我确实希望这个头衔出现在搜索中，但是，我想看到像“哈利波特与秩序凤凰“出现在顶端，因为我的查询从此开始。

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

数据库中唯一行的数量将高达20,000。我所追求的有点像谷歌搜索建议，或者Visual Studio 2010智能感知（代码自动完成），只是它不应该记住用户以前输入的内容，并根据该建议调整建议。无需查询扩展;只是处理实际的内容。从用户角度来看，它应该与谷歌搜索和智能感知类似，例如它应该提出一些排名的选择，并且还提出了一个聪明的方法来将该列表在合适的位置截断（例如，如果没有什么与查询完全匹配，则没有提供任何内容，而不是展示最好的最佳拟合），并且如果前几项结果的排名很高，但是后面的结果相对于最高的结果来说要弱得多，那么也许可以隐藏那些弱结果。

也许你知道一个合理规模的开源工具/库的暴露，和可读的源代码，我可以得到的想法？

我的下一个问题是如何最好地处理这种情况的检索词可以适用于任何标题，和/或作者，和/或描述的情况，但我怀疑我目前的问题已经加载。

如果事情不清楚，我想问以下问题，请澄清问题。

来源

2011-11-06 Hamish Grubijan

你可能想看看Solr/Lucene。它支持自动完成，效果很好。运行时性能也很好。 – Pankrat

@Hamish Grubijan：在Google中键入*“hari po”*，第二和第三个建议是*“哈利波特”*; ）谷歌使用*“该死的算法”*做它。您距离Levenhstein编辑距离不远：Google正在使用BK-trees IIRC。据我所知，它基本上是一个由Levenhstein编辑距离构建的树。你可以在这里阅读它：http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees Btw与* Levenhstein编辑距离是微不足道的*，bk-树好像很野兽... – TacticalCoder

@ user988052，谢谢，请发表评论作为回答。 –

我建议你好好看看Lucene。它支持广泛的查询类型，包括（我认为）增量式近似搜索。另外它是开源的和免费的。:)

来源

2011-11-06 00:24:19

也许你想寻找卦搜索？卦搜索需要创建3个字母的每个可能性，并在匹配中查找相似的字符串。 http://en.wikipedia.org/wiki/Trigram

来源

2011-11-06 00:32:48 Bytemain

谢谢，维基百科页面的trigram搜索几乎是空的。你能详细解释一下吗？你知道我可以用作示例的任何好的工具/库吗？ –

卦搜索将单词分成2^3个组合，因此总共有64-8个更改。 – Bytemain

对于简单的完成算法，您可以将KWIC索引与基数树结合使用。

基本上，您将采用每个索引字符串，确定“重要”潜在起始点，并根据这些潜在起始点生成N个旋转字符串副本。

然后在字符串上建立一个基数树，这样当你输入“Harry”时，你会在“Harry”之后找到所有可能的下一个单词。虽然这可能听起来像是真的会爆炸你的数据库的大小，但它实际上只是将它加倍，这取决于你如何选择“重要”的起点。（基数树是一定程度上比存储每一行独立，除了使高效的搜索更加紧凑。）

来源

2011-11-06 00:54:22

你的意思是压缩的trie吗？这要比卦搜索要昂贵得多。 – Bytemain

取决于你正在尝试做什么。 OP的全部意图还不清楚。 –

如果你在谷歌中键入“哈日宝”，靠近顶部的建议将正确地“哈利·波特“谷歌它使用”该死的算法“。您距离Levenhstein编辑距离：Google正在使用BK-trees IIRC。

据我所知，它基本上是一棵树，从Levenhstein编辑距离构建。

到目前为止，可能有几篇关于这个主题的论文。我第一次读到它是在几年前，在一个叫“该死的冷静算法”博客：

http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees

但是你要知道，不亚于Levenhstein编辑距离是微不足道的（它可以在大约20行代码中实现），bk-tree看起来像是另一个开发的野兽......

来源

2011-11-08 19:13:58 TacticalCoder

*（顺便说一句OP要求我发表我的评论作为答案，所以在这里我去...）* – TacticalCoder

请建议一个智能静态字完成算法

回答

相关问题