如果是这样，请解释如何。
回复：什么是距离——“两个字符串之间的距离定义为将一个字符串转换为另一个字符串所需的最少编辑次数。”
例如，xyz 到 XYZ 需要 3 次编辑，因此字符串 xYZ 更接近 XYZ 和 xyz。
如果模式是 [0-9]{3} 或例如 123，则 a23 将比 ab3 更接近模式。
如何找到正则表达式和不匹配字符串之间的最短距离？
以上是Damerau-Levenshtein距离算法。
问问题
2391 次
2 回答
7
您可以使用有限状态机有效地执行此操作（即时间线性）。如果您使用转换器，您甚至可以相当紧凑地编写转换规范，并进行比简单的插入或删除更细微的转换 - 请参阅 wikipedia for Finite State Transducer作为起点，以及诸如 FSA 工具包或 FSA6 之类的软件（它也有一个不完全稳定的网络演示）。有很多用于 FSA 操作的库；我不想建议前两个是您唯一或最好的选择，只是我听说过的两个。
但是，如果您只想要高效的近似搜索，则存在一个不太灵活但已经为您实现的选项：TRE，它具有返回匹配成本的近似匹配函数- 即到匹配的距离，从你的角度来看。
于 2010-10-20T22:13:59.770 回答
3
如果您的意思是最接近的匹配字符串和样本之间的 levenshtein 距离最小的字符串，那么我很确定它可以完成，但是您必须自己将 Regex 转换为 DFA，然后尝试匹配并且无论何时某些事情失败了，不确定地继续，就好像它已经通过了一样，并跟踪数字差异。您可以为此使用 A* 搜索或类似的东西，但效率会很低（O(2^n) 最坏的情况）
于 2010-10-20T02:38:31.133 回答