问题:
给定两个字符串 A和B,由A转成B所需的最少编辑操作次数。允许的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
例如将A(kitten)转成B(sitting):
sitten (k→s)替换
sittin (e→i)替换
sitting (→g)插入
思路:
如果我们用 i 表示当前字符串 A 的下标,j 表示当前字符串 B 的下标。 如果我们用d[i, j] 来表示A[1, ... , i] B[1, ... , j] 之间的最少编辑操作数。那么我们会有以下发现:
1. d[0, j] = j;
2. d[i, 0] = i;
3. d[i, j] = d[i-1, j - 1] if A[i] == B[j]
4. d[i, j] = min(d[i-1, j - 1],d[i, j - 1],d[i-1, j]) + 1 if A[i] != B[j]
所以,要找出最小编辑操作数,只需要从底自上判断就可以了。伪代码如下:
int LevenshteinDistance(char s[1..m], char t[1..n])
{
// for all i and j, d[i,j] will hold the Levenshtein distance between
// the first i characters of s and the first j characters of t;
// note that d has (m+1)x(n+1) values
declare int d[0..m, 0..n]
for i from 0 to m
d[i, 0] := i // the distance of any first string to an empty second string
for j from 0 to n
d[0, j] := j // the distance of any second string to an empty first string
for j from 1 to n
{
for i from 1 to m
{
if s[i] = t[j] then
d[i, j] := d[i-1, j-1] // no operation required
else
d[i, j] := minimum
(
d[i-1, j] + 1, // a deletion
d[i, j-1] + 1, // an insertion
d[i-1, j-1] + 1 // a substitution
)
}
}
return d[m,n]
}
参考:
http://en.wikipedia.org/wiki/Levenshtein_distance
分享到:
相关推荐
EditDistance 用C++实现,字符串用链表保存,可以输出到控制台,也可以输出到文件
SQL SERVER实现编辑距离(Edit Distance)算法,可进行模糊匹配查询
动态规划 编辑距离 可以用来判别字符串的差异
自己写的EditDistance的C语言版本
算法中的edit distance问题 给出原序列 再给出目的序列 程序描述出源到目的的转换 编译通过了 本人的算法作业!
编辑距离,又称Levenshtein距离(也叫做Edit Distance),是指两个字串之间,由一个转成另一个所需的最少编辑操作次数。许可的编辑操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。
编辑距离 快速实现编辑距离(Levenshtein距离)。 该库仅使用C ++和Cython实现。 该库中使用的算法由提出 。 二元轮 多亏了 ,Linux,Mac OS和Windows上都有二进制轮子。 安装 您可以通过pip安装: pip install ...
soundx 和 编辑距离的程序 输入两个单词进行比较
编辑距离的perl语言算法,基于词的增加、修改、删除的编辑距离
edit_distance 用于计算序列之间的编辑距离和比对的Python模块。 我需要一种方法来计算Python中序列之间的编辑距离。 我找不到任何合适的库来执行此操作,因此我编写了自己的库。 似乎有许多编辑距离库可用于计算...
编辑器Edit-plus/据说大师级都用最原始的
编辑距离算法-易语言.zip
对任给的两个字符串A,B,用动态规划算法算出他们的最小编辑距离
一个简单的字符串Edit Distance C#程序
编辑距离快速实现编辑距离(Levenshtein...s 多数情况下pypi上应该有轮子apidistance(s1: str, s2: str) -> int 计算编辑距离>>> import editdistance_s>>> editdistance_s.distance( ' hello ' , ' hell:snowman: ' )1
字幕编辑Subtitle Edit v3.6.0
支持多种导出格式,其导出的cookie支持在curl中使用(导出格式选择Netscape HTTP Cookie File)。
Cool Edit Pro是一个非常出色的数字音乐编辑器和MP3制作软件。不少人把Cool Edit形容为音频“绘画”程序。Adobe Audition(前Cool Edit Pro) 是美国 Adobe Systems 公司 (前Syntrillium Software Corporation) 开发的...
JavaScript应用实例-编辑距离py2js.js
No16.HTML在线编辑.颜色.图片.多线程.XmlHttp No16.HTML在线编辑.颜色.图片.多线程.XmlHttp