更快的编辑距离算法

Question

问题:我知道琐碎的编辑距离DP公式和O(mn)中的2个大小为n和m的字符串的计算.但我最近才知道,如果我们只需要计算编辑距离f的最小值并且它是有界| f | <= s,那么我们可以用O(min(m,n)+ s ^ 2)计算它或者O(s*min(m,n))[维基百科]时间.

如果这是基于DP或解释算法,请解释它背后的dp配方.

请查看链接improved algorithm部分 : http ://en.wikipedia.org/wiki/Edit_distance.

关于改进的UKKONEN'S算法的另一个链接http://www.berghel.net/publications/asm/asm.php

提前致谢.

Answer 1

你可以用O(min(n,m)*s)时间计算编辑距离使用下一个简单的想法:

考虑DP表中的第i个字符串.

所以,如果我们知道那个答案<= s,那么我们就会在坐标为(i,i-s),(i,i-s + 1),...,(i,i + s)的单元格中出现.因为在其他细胞中答案严格大于s.

例如,假设我们知道,"abacaba"和"baadba"之间的编辑距离小于3.

此字符串的DP表

所以,我们可以跳过红细胞,因为它们的价值超过了s.

算法O(min(n,m)*s)的渐近因为我们计算了主对角线左右两侧的s单元格.

如果某些细胞依赖于红细胞,我们可以假设红细胞具有值s.当然,使用此算法我们无法正确计算所有值.重要的是,该算法正确计算所有值不超过s的单元格.因此,我们可以找到编辑距离(因为我们知道它不会超过s). (2认同)
http://ntz-develop.blogspot.ru/2011/03/fuzzy-string-search.html在此页面上,您可以阅读字符串之间的距离.此外,关于上述算法还有一些说法. (2认同)
我们可以根据问题的具体情况来计算S. 可能是,我们将忽略具有一些大编辑距离的字符串(我认为它可能在某些文本分析中有用).但我不知道快速算法,它可以计算S.(我在互联网上找到一些文章:http://www.mit.edu/~andoni/papers/compEdit.pdf可能会有趣) (2认同)