Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1023816
  • 博文数量: 242
  • 博客积分: 10209
  • 博客等级: 上将
  • 技术积分: 3028
  • 用 户 组: 普通用户
  • 注册时间: 2008-03-12 09:27
文章分类

全部博文(242)

文章存档

2014年(1)

2013年(1)

2010年(51)

2009年(65)

2008年(124)

我的朋友

分类: C/C++

2010-07-13 15:45:58

编辑距离的定义:
   The edit distance between two strings of characters is the number of operations required to transform one of them into the other。

    编辑距离有很多种不同的定义方法,我们可以用多种不同的distance来反映edit distance.

比如 Hamming distance、 Levenshtein distance、 Longest common subsequence等等。

1.若使用Longest common subsequence来度量edit distance,则允许的操作有addition和deletion。

2.若使用Damerau-Levenshtein distance来度量edit distance,则允许的操作有addition、
  deletion、substitution和transposition of two adjacent characters。

3.若使用Hamming distance,则允许的操作只有substitution。(这也就要求比较的两个字符串是等长的)

4.若使用Levenshtein distance,则允许的操作有addition、deletion和substitution。

这里所说的操作的具体含义,解释如下:
比如计算字符串S1="ki" 和 字符串S2="si" 的编辑距离,若使用substitution操作,则距离为1,即把S1中的k替换为s,S1就可以变成S2了。 但若不允许使用substitution操作,只能使用add和delete操作,则距离为2,因为需要一次delete和一次add才能把S1转换成S2。

采用动态规划方法计算Levenshtein distance的代码如下:
 int LevenshteinDistance(char s[1..m], char t[1..n])
{
// d is a table with m+1 rows and n+1 columns
declare int d[0..m, 0..n]

for i from 0 to m
d[i, 0] := i // deletion
for j from 0 to n
d[0, j] := j // insertion

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]
else
d[i, j] := minimum
(
d[i-1, j] + 1, // deletion
d[i, j-1] + 1, // insertion
d[i-1, j-1] + 1 // substitution
)
}
}

return d[m,n]
}

比较"ketten"和"sitting"的过程和产生的矩阵如下:






阅读(2304) | 评论(1) | 转发(0) |
给主人留下些什么吧!~~

chinaunix网友2010-09-03 14:14:03

简单明了,一下子就看懂了,非常感谢!