regex - 是否可以计算正则表达式和字符串之间的编辑距离？

Question

如果是这样，请解释如何。

回复:什么是距离 --“两个字符串之间的距离定义为将一个字符串转换为另一个字符串所需的最少编辑次数。”

例如，xyz 到 XYZ 需要 3 次编辑，因此字符串 xYZ 更接近 XYZ 和 xyz。

如果模式是 [0-9]{3} 或例如 123，那么 a23 将比 ab3 更接近模式。

如何找到正则表达式和非匹配字符串之间的最短距离？

以上是Damerau–Levenshtein距离算法。

Answer 1

您可以使用有限状态机有效地(即时间线性)执行此操作。如果您使用转换器，您甚至可以相当紧凑地编写转换规范，并进行比简单插入或删除更细微的转换 - 请参阅维基百科 Finite State Transducer作为起点，还有诸如 FSA 工具包或 FSA6(其具有不完全稳定的 web-demo)之类的软件。有很多用于 FSA 操作的库；我不想建议前两个是您唯一或最好的选择，只是我听说过的两个。

但是，如果您只想要高效的近似搜索，那么存在一个不太灵活但已经为您实现的选项:TRE ，它有一个 approximate matching function从您的角度来看，它会返回比赛的成本 - 即到比赛的距离。