Levenshtein Distance （LD算法）编辑距离算法原理

向右看齐 2022-02-22 15:08 308阅读 0赞

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

## LD算法原理： ##

*  算法目的：计算出两字符序列的编辑距离，同时也能求出两序列的匹配序列
 *  假设：  
    比对的俩序列为：  
    ![在这里插入图片描述][20190409120517351.]  
    则两序列的长度分别为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**  
    **评分矩阵**：  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70]  
    **回溯：**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70 1]  
结果：  
LD(A,B) = 5;  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70 2]

可见LD算法的流程和needleman wunsch算法是很类似的，区别在于LD算法使用的是最小值，NW算法使用的是最大值。  
needleman wunsch算法介绍详见：  
[SW算法、NW算法介绍][SW_NW]；  
[https://blog.csdn.net/yohjob/article/details/89144032][SW_NW]

[20190409120517351.]: /images/20220222/cad0da3cd6a84b98b645c16f156d6069.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70]: /images/20220222/a414744607ab40aabfadd7e1fd3d73c8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70 1]: /images/20220222/0f95ba96ecba44a894962cfd047980e5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3lvaGpvYg_size_16_color_FFFFFF_t_70 2]: /images/20220222/eb2505ee495148d695ac9cb8ba88df37.png
[SW_NW]: https://blog.csdn.net/yohjob/article/details/89144032