好记性不如铅笔头

编程

【转】Levenshtein Distance (LD算法) 编辑距离算法原理

本文转自【Levenshtein Distance (LD算法) 编辑距离算法原理_Steve_Stone的博客-CSDN博客_编辑距离算法原理】,有删改。

CONTENTS

LD算法介绍

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

LD算法目的:计算出两字符序列的编辑距离,同时也能求出两序列的匹配序列

假设比对的俩序列为:

则两序列的长度分别为len(A)=n Len(B)=m
LD(A,B):字符串A和字符串B的编辑距离,即将字符串A转换为字符串B所用的最少字符操作数
LD(A,B)=0表示两个字符串完全一样。
LD(i,j)=LD(a1a2……ai,b1b2……bj),其中0≤i≤n,0≤j≤m

算法步骤:

1.初始化算法分数矩阵H,使行i表示字符ai,列j表示字符bj;

2.计算矩阵中每一项的LD(i, j):
若ai = bj,则LD(i, j) = LD(i-1, j-1) 取左上角的值
若ai ≠ bj,则LD(i, j) = Min( LD(i-1, j-1), LD(i-1, j), LD(i, j-1) ) +1

3.回溯,从矩阵右下角开始:
若ai=bj,则回溯到左上角单元格;
若ai≠bj,回溯到左上角、上边、左边中值最小的单元格,若有相同最小值的单元格,优先级按照左上角、上边、左边的顺序。

4.根据回溯路径,写出匹配字符串:
若回溯到左上角单元格,将ai添加到匹配字串A‘,将bj添加到匹配字串B’;
若回溯到上边单元格,将ai添加到匹配字串A’,将_添加到匹配字串B’;
若回溯到左边单元格,将_添加到匹配字串A’,将bj添加到匹配字串B’。

5.矩阵右下角的值即为俩序列的编辑距离,回溯结果为全部匹配序列。

示例:

A=GGATCGA,B=GAATTCAGTTA

1.评分矩阵:

2.回溯:

3.结果:
LD(A,B) = 5;

可见LD算法的流程和needleman wunsch算法是很类似的,区别在于LD算法使用的是最小值,NW算法使用的是最大值。

发表评论

4 + 19 =

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据