编辑距离算法

在 Mon 18 April 2016 发布于 文本算法 分类 • 标签为 编辑距离, Levenshtein Distance

编辑距离, 又叫Levenshtein距离。在wiki上的解释是: 两个不同的字符串, 其中一个字符串转在单字符操作(替换, 插入, 删除)下换成另外一个字符串所需的最少的编辑次数。

例如, 字符串"kitten"转换为字符串"sitting"的编辑次数为3, 且没有比这更少的编辑次数, 过程如下:

  1. kitten --> sitten(k替换成s)

  2. sitten --> sittin(i替换成e)

  3. sittin --> sitting(在字符串末端插入g)

其算法描述的:

现有两个字符串 \(a\)\(b\), 其长度分别为\(m\)\(n\)\(i …


阅读全文