c# - 在 C# 中快速动态模糊搜索超过 10 万个字符串

Question

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

这是受到这个问题的启发：

是否有任何为 C# 编写的模糊搜索或字符串相似函数库？

Levenstein 距离算法似乎运行良好，但计算需要时间。当用户输入额外的字母时，查询需要重新运行这一事实是否有任何优化？我有兴趣最多显示每个输入的前 10 个匹配项。

Answer 1

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

• 匹配字符数
• 不匹配字符数
• 相似的长度
• 拼写错误或拼音错误
• 业务特定缩写
• 必须以相同的子字符串开头
• 必须以相同的子字符串结尾

我在字符串匹配算法方面做了很多工作，但还没有找到任何满足我特定要求的现有库或代码。回顾它们，从它们那里借鉴想法，但你总是必须定制和编写自己的代码。

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

如果您没有正确定义要匹配和衡量的内容，那么您会发现意外匹配的高分和预期匹配的低分。字符串匹配是非常特定于域的。如果你没有正确定义你的领域，那么你就像一个毫无头绪的渔夫，四处乱扔鱼钩，并希望得到最好的结果。

Answer 2

这篇博文描述了 Lucene 在这方面的一些工作。他们能够使用有限状态传感器（自动机）非常有效地实现 Levenshtein 距离模糊匹配，最高编辑距离为 2。尽管代码全部用 Java 编写，而且有点复杂，尽管它是开源的。

但是基本的想法很简单：把你的字典想象成一棵巨大的字母状态树。在 state0，你没有字母。在 state1 中，您承认任何可能是单词首字母的字母。State2 以 state1 为条件；如果第一个字母是“x”，则下一个状态只允许可以跟随 x 的字母（在位置 2）。等等

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