两个正则表达式之间的编辑距离

Question

两个正则表达式之间的编辑距离

regexstringalgorithmdynamic-programming

7

我在面试中遇到了这个问题：

给定两个正则表达式，计算它们之间的编辑距离。编辑距离被定义为由两个正则表达式分别生成的任意两个字符串之间的最小编辑距离。

形式上，我们正在寻找 d(L1,L2) = min { d(x,y) | x from L1, y from L2 }，其中L1和L2是由两个正则表达式生成的语言。

我在面试中无法解决这个问题。即使现在我也不知道如何解决。有什么想法吗？

我认为这与http://www.spoj.com/problems/AMR10B/相同。

- Quixotic

2

我不确定我理解了，正则表达式生成的是一种语言，可以是无限的，而不是一个字符串，你如何定义两种语言之间的距离？你能举个例子吗？ - amit

好的，我明白了 - 你的意思是 d(L1,L2) = min { d(x,y) | x from L1, y from L2 } 吗？ - amit

@amit：是的，我就是这个意思。 - Quixotic

在我看来，我们可以像解决两个字符串之间的最小编辑距离一样来解决这个问题。 - Pham Trung

1个回答

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

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

- Paul Hankin · Accepted Answer

有限状态机表示两种语言。假设第一种语言有状态S[1]、S[2]、...、S[N1]和转移c：S[i]->S[j]（表示状态i在输入字符c下转移到状态j），第二种语言有状态T[1]、T[2]、...、T[N2]和自己的转移集合。

现在，您可以构建带权重的多图，其中节点是状态对，并且如果满足以下任何四种情况之一，则对(S[i1]，T[i2])到(S[j1]，T[j2])的对进行边缘连接：

- 存在c：S[i1] -> S[j1]且i2 = j2。这个权重为1。 - 存在c：T[i2] -> T[j2]且i1 = j1。这个权重为1。 - 存在c：S[i1] -> S[j1]和c：T[i2] -> T[j2]。这个权重为0。 - 存在c：S[i1] -> S[j1]和d：T[i2] -> T[j2]。这个权重为1。

然后，从起始状态对到任何接受状态对的最低权重路径即为最小编辑距离。