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

Question

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

这是受这个问题的启发:

Are there any Fuzzy Search or String Similarity Functions libraries written for C#?

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

Answer 1

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

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

我在字符串匹配算法方面做了很多工作，但尚未找到满足我特定要求的任何现有库或代码。查看它们，借鉴它们的想法，但您总是必须自定义和编写自己的代码。

Levenstein 算法很好但有点慢。我在 Smith-Waterman 和 Jaro-Winkler 算法方面都取得了一些成功，但我找到的最好的算法是 Monge(根据内存)。然而，阅读原始研究并确定他们编写算法和目标数据集的原因是值得的。

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