Posted on 2011-01-11 16:21
王之昊 阅读(449)
评论(0) 编辑 收藏 引用 所属分类:
字符串
求两个正规式之间的编辑距离
正规式与编辑距离都是常见知识，如果不熟悉请见原题[1]
两个字符串之间的编辑距离的经典解法是动态规划。然而正规式可能包含无穷多个字符串。 不好将它转化到两字符串的编辑距离上。另外一个问题，首先要有一种能够识别正规式的方法，就像进行表达式计算时，用递归下降方法来识别就很顺手。
一时之间想不起用什么来表示正规式，后来看到解题报告 [2] 才有恍然大悟的感觉，用一个NFA[3]来表示正规式（编译原理课上学过的，还是重点）。这样状态非常的清晰。
首先将正规式转换成NFA的形式，这样两个正规式，就变成了两个NFA。设<x , y>表示当前匹配到第一个NFA的x状态，第二个NFA的y状态所消耗的当前最少代价。对于当前的状态<s1, s2>寻找他所有的后继<t1, t2>，如果发现能够更新后继<t1,
t2>,那么更新它，并且将它入队，用于更新其他的状态。当队列里空了时候，那么就求到了最小编辑距离。
这里有个小技巧，就是标记当前状态是否已经在队列中，防止队列中出现重复状态。具体实现可以参考UESTC_Melody的代码[4]，写的非常优美。
引用
[1]http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=5109
[2]
http://icpc.amrita.ac.in/2010/images/solution_logic.pdf
[3]
http://en.wikipedia.org/wiki/Nondeterministic_finite_state_machine
[4]
http://acm.hust.edu.cn:8080/judge/problem/viewSource.action?id=56951