计算机科学

首页 > 计算机科学

莱文斯坦距离

2018-07-27 10:05:44     所属分类:算法

莱文斯坦距离,又称Levenshtein距离,是距离的一种。指两个字串之间,由一个转成另一个所需的最少操作次数。允许的操作包括将一个字符替换成另一个字符,插入一个字符,删除一个字符。

例如将kitten一字转成sitting:

  1. sitten (k→s)
  2. sittin (e→i)
  3. sitting (→g)

俄罗斯科学家弗拉基米尔·莱文斯坦英语Vladimir Levenshtein在1965年提出这个概念。

应用

  • DNA分析
  • 拼写检查
  • 语音辨识
  • 抄袭侦测

算法

动态规划经常被用来作为这个问题的解决手段之一。

int LevenshteinDistcance(string str11..lenStr1, string str21..lenStr2)
    int d0..lenStr1, 0..lenStr2
    int i, j, cost
 
    for i = 0 to lenStr1
       di, 0 := i
    for j = 0 to lenStr2
       d0, j := j
 
    for i = 1 to lenStr1
        for j = 1 to lenStr2
            if str1i = str2j 
                cost := 0
            else 
                cost := 1
            di, j := min(
                                di-1, j   + 1,     // 删除
                                di  , j-1 + 1,     // 插入
                                di-1, j-1 + cost   // 替換
                            )
 
   return dlenStr1, lenStr2

参见

  • 汉明距离
  • 延森-香农距离
  • 序列比对
  • Soundex

显示全文

取消

感谢您的支持,我会继续努力的!

扫码支持
无需打赏可直接关闭阅读全文
1分,2分不嫌少,钱不钱的无所谓,重要的是你的话语激励我前行!

愿你每天温暖如春!!!


上一篇:水塘抽样
下一篇:洗牌交换连接
相关推荐