在 C# 中对 100k+ 字符串进行快速动态模糊搜索
本文关键字：动态 模糊搜索 中对 100k+ 字符串 | 更新日期: 2023-09-27 17:56:16
假设它们是预先加载的股票代码，键入文本框。我正在寻找可以复制的代码，而不是要安装的库。
这是受到这个问题的启发：
是否有为 C# 编写的模糊搜索或字符串相似性函数库？
莱文斯坦距离算法似乎运行良好，但计算需要时间。对于查询需要在用户键入额外字母时重新运行这一事实，是否有任何优化？我有兴趣为每个输入最多显示前 10 名匹配项。
您需要确定字符串周围的匹配规则。什么决定了"相似字符串"
- 匹配字符数
- 不匹配字符数
- 相似的长度
- 拼写错误或语音错误
- 业务特定缩写
- 必须以相同的子字符串开头
- 必须以相同的子字符串结尾
我已经在字符串匹配算法方面做了很多工作，但还没有找到任何满足我特定要求的现有库或代码。回顾它们，从中借用想法，但你总是必须自定义和编写自己的代码。
莱文斯坦算法很好，但有点慢。 我在Smith-Waterman和Jaro-Winkler算法上都取得了一些成功，但我发现最好的算法是Monge（从记忆中）。然而，阅读原始研究并确定他们为什么编写算法和目标数据集是值得的。
如果您没有正确定义要匹配和衡量的内容，那么您会在意外比赛中发现分数很高，而在预期匹配中得分很低。字符串匹配非常特定于域。如果你没有正确定义你的领域，那么你就像一个没有头绪的渔夫，扔钩子，希望得到最好的结果。
这篇博文描述了Lucene在这一领域的一些工作。 他们能够非常有效地使用有限状态传感器（自动机）实现Levenshtein距离模糊匹配，编辑距离可达2。 代码都是用Java编写的，虽然它是开源的，但有点复杂。
但基本思想很简单：把你的字典想象成一棵巨大的字母状态树。 在状态 0 中，您没有字母。 在 state1 中，您允许任何可能是单词的第一个字母的字母。 状态 2 受状态 1 的条件;如果第一个字母是"X"，则下一个状态只允许可以跟随 X 的字母（在位置 2 中）。等。
现在对于 Levenshtein 匹配，您可以遍历字母树，同时允许一些错误：删除、插入（一个字母通配符）和可能的转置（Levenshtein 的一个很好的扩展是将转置视为单个编辑而不是 2）。 您必须维护状态才能跟踪允许的编辑次数。 这可以非常有效地完成 - 对于交互式"在您键入时"拼写建议器来说，速度肯定足够快。