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

Question

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

regexdistancelevenshtein-distance

7

如果是这样，请解释一下如何实现。

关于距离的定义：“两个字符串之间的距离被定义为将一个字符串转换为另一个字符串所需的最小编辑次数。”

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

如果模式是[0-9]{3}或者123，则a23比ab3更接近该模式。

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

上述内容是Damerau-Levenshtein距离算法。

- blunders

2

我认为我们需要更多的信息。 - rerun

2个回答

3

如果你指的是与样本最接近的字符串之间的最小编辑距离，那么我相信这是可以完成的，但你需要自己将正则表达式转换为DFA，然后尝试匹配，并在每次失败时，非确定性地继续像已经通过一样并记录差异数量。你可以使用A*搜索或类似的算法来实现，尽管效率会很低（最坏情况下为O(2^n)）。

- tobyodavies

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Eamon Nerbonne · Accepted Answer

您可以使用有限状态机来高效地完成这个任务（即，时间复杂度线性）。如果您使用转换器，则甚至可以相对简洁地编写转换规范，并进行比仅仅插入或删除更为微妙的转换 - 可以查看维基百科上的有限状态转换器作为起点，还有像FSA工具包或FSA6这样的软件（其中有一个不完全稳定的Web演示）。有许多用于FSA操作的库；我不想暗示前两者是您唯一或最佳的选择，只是我听说过的两个。

然而，如果您仅需要高效的近似搜索，那么已经为您实现了一个不太灵活但功能齐全的选项：TRE，它具有一个近似匹配函数，返回匹配的成本 - 即从您的角度来看，与匹配的距离。