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

Question

如果是这样,请解释如何.

Re:什么是距离 - "两个字符串之间的距离定义为将一个字符串转换为另一个字符串所需的最小编辑数."

例如,xyz到XYZ将进行3次编辑,因此字符串xYZ更接近XYZ和xyz.

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

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

以上是Damerau-Levenshtein距离算法.

Answer 1

您可以使用有限状态机有效地执行此操作(即,线性时间).如果你使用传感器,你甚至可以相当紧凑地编写变换规范,并进行比简单插入或删除更细微的变换 - 参见维基百科的有限状态传感器作为起点,以及软件,如FSA工具包或FSA6(它也有一个不完全稳定的网络演示.FSA操作有很多库; 我不想暗示前两个是你唯一或最好的选择,只有两个我听说过.

但是,如果您只想进行有效的近似搜索,则存在一个不太灵活但已经实现的选项:TRE,它具有近似匹配函数,可返回匹配的成本 - 即匹配的距离,从你的角度来看.