在C#中快速动态模糊搜索100k+字符串

Question

8

让我们假设它们是预加载的股票符号，输入到文本框中。我正在寻找可以复制的代码，而不是要安装的库。

这受到了这个问题的启发：是否有为C#编写的模糊搜索或字符串相似性函数库？ Levenstein距离算法似乎效果很好，但计算需要时间。是否有任何优化策略，考虑到查询将需要在用户输入额外字母时重新运行？我有兴趣显示每个输入最多的前10个匹配项。

- Hamish Grubijan

AForge 有一些模糊的东西，尽管我从未详细阅读过它们。 - zerkms

2个回答

1

这篇博客文章描述了Lucene在这个领域所做的一些工作。他们能够使用有限状态转换器（自动机）相当高效地实现Levenshtein距离模糊匹配，最多可达编辑距离2。虽然代码都是用Java编写的，而且有点复杂，但它是开源的。

但基本思想很简单：将您的字典视为一个巨大的字母状态树。在state0处，您没有任何字母。在state1处，您可以接受任何可能是单词第一个字母的字母。State2由state1条件限制；如果第一个字母是“x”，则下一个状态仅接受可以跟随x（在位置2）的字母。等等。

现在对于Levenshtein匹配，您可以在遍历字母树时允许一些错误：删除、插入（一个字母通配符）和可能的转置（Levenshtein的一个不错的扩展是将转置视为单个编辑而不是2个）。您必须维护状态以便跟踪允许的编辑次数。这可以非常高效地完成-肯定足够快，以便进行交互式“当您输入时”拼写建议。

- Mike Sokolov

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Kirk Broadhurst · Accepted Answer

您需要确定字符串匹配规则。什么决定了“相似的字符串”：

我已经做了大量的字符串匹配算法工作，但尚未找到任何现有库或代码符合我的特定要求。请审查它们，借鉴它们的想法，但您必须不可避免地自定义并编写自己的代码。

Levenstein算法很好，但有点慢。我在Smith-Waterman和Jaro-Winkler算法方面取得了一些成功，但我发现对于我的目的来说，最好的是Monge（从记忆中）。然而，阅读原始研究并确定他们为什么编写他们的算法和目标数据集是值得的。

如果您没有正确定义要匹配和测量的内容，则会在意外匹配上获得高分，在预期匹配上获得低分。字符串匹配非常具体于领域。如果您没有正确定义您的领域，那么您就像一个没有头绪的渔夫，到处扔钩，希望能有所收获。