Approximate string matching
近似字符串匹配问题。
Levenshtein edit distance
在metric space中衡量两个字符串差异程度的一个指标,即通过一系列单字符的编辑操作把字符串A变成字符串B所需的最小编辑次数,其中的编辑操作可以是插入字符、删除字符以及修改字符。
计算编辑距离有个经典的Wagner-Fischer算法,使用了动态规划,用d(i,j)
表示把字符串A的前i
个字符变成字符串B的前j
个字符所需的最小编辑次数(即子串的编辑距离)。