LD算法

原理

LD算法（Levenshtein Distance）又成为编辑距离算法（Edit Distance）。它是以字符串A通过插入字符、删除字符、替换字符变成另一个字符串B，那么操作的过程的次数表示两个字符串的差异。

例如：字符串A：kitten如何变成字符串B：sitting。

​ 第一步：kitten——》sitten。k替换成s

　第二步：sitten——》sittin。e替换成i

　第三步：sittin——》sitting。在末尾插入g

故kitten和sitting的编辑距离为3

定义说明

LD(A,B)表示字符串A和字符串B的编辑距离。很显然，若LD(A,B)=0表示字符串A和字符串B完全相同

Rev(A)表示反转字符串A

Len(A)表示字符串A的长度

A+B表示连接字符串A和字符串B

性质

LD(A,A)=0

LD(A,"")=Len(A)

LD(A,B)=LD(B,A)

0≤LD(A,B)≤Max(Len(A),Len(B))

LD(A,B)=LD(Rev(A),Rev(B))

LD(A+C,B+C)=LD(A,B)

LD(A+B,A+C)=LD(B,C)

LD(A,B)≤LD(A,C)+LD(B,C)（注：像不像“三角形，两边之和大于第三边”）

LD(A+C,B)≤LD(A,B)+LD(B,C)

讲解定义

为了讲解计算LD(A,B)，特给予以下几个定义

A=a1a2……aN，表示A是由a1a2……aN这N个字符组成，Len(A)=N

B=b1b2……bM，表示B是由b1b2……bM这M个字符组成，Len(B)=M

定义LD(i,j)=LD(a1a2……ai,b1b2……bj)，其中0≤i≤N，0≤j≤M

故：　　LD(N,M)=LD(A,B)

　　　　LD(0,0)=0

　　　　LD(0,j)=j

　　　　LD(i,0)=i

对于1≤i≤N，1≤j≤M，有公式一

若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

举例说明：A=GGATCGA，B=GAATTCAGTTA，计算LD(A,B)

第一步：初始化LD矩阵　　

第二步：利用上述的公式一，计算第一行

第三步，利用上述的公示一，计算其余各行

则最右下角的值就是编辑距离：

LD(A,B)=LD(7,11)=5

我们往往不仅仅是计算出字符串A和字符串B的编辑距离，还要能得出他们的匹配结果。

以上面为例A=GGATCGA，B=GAATTCAGTTA，LD(A,B)=5

他们的匹配为：

A：GGA_TC_G__A

B：GAATTCAGTTA

如上面所示，蓝色表示完全匹配，黑色表示编辑操作，_表示插入字符或者是删除字符操作。如上面所示，黑色字符有5个，表示编辑距离为5。

利用上面的LD矩阵，通过回溯，能找到匹配字串

第一步：定位在矩阵的右下角　　

第二步：回溯单元格，至矩阵的左上角

　　若ai=bj，则回溯到左上角单元格

若ai≠bj，回溯到左上角、上边、左边中值最小的单元格，若有相同最小值的单元格，优先级按照左上角、上边、左边的顺序

若当前单元格是在矩阵的第一行，则回溯至左边的单元格

若当前单元格是在矩阵的第一列，则回溯至上边的单元格

依照上面的回溯法则，回溯到矩阵的左上角

第三步：根据回溯路径，写出匹配字串

　　若回溯到左上角单元格，将ai添加到匹配字串A，将bj添加到匹配字串B

　　若回溯到上边单元格，将ai添加到匹配字串A，将_添加到匹配字串B

　　若回溯到左边单元格，将_添加到匹配字串A，将bj添加到匹配字串B

　　搜索晚整个匹配路径，匹配字串也就完成了

从上面可以看出，LD算法在不需要计算出匹配字串的话，时间复杂度为O(MN)，空间复杂度经优化后为O(M)

　　不过，如果要计算匹配字符串的话，时间复杂度为O(MN)，空间复杂度由于需要利用LD矩阵计算匹配路径，故空间复杂度仍然为O(MN)。这个在两个字符串都比较短小的情况下，能获得不错的性能。不过，如果字符串比较长的情况下，就需要极大的空间存放矩阵。

代码

参考文档：https://blog.csdn.net/koibiki/article/details/83031788?utm_medium=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-1.control&depth_1-utm_source=distribute.pc_relevant.none-task-blog-2~default~BlogCommendFromMachineLearnPai2~default-1.control

import numpy as np

def edit_distance(word1, word2):
    len1 = len(word1)
    len2 = len(word2)
    # 新建一个全为0的矩阵
    dp = np.zeros((len1 + 1,len2 + 1))
    # 遍历列，将第一列全赋值为对应的列值
    for i in range(len1 + 1):
        dp[i][0] = i  
    # 遍历行，将第一行全赋值为对应的行值
    for j in range(len2 + 1):
        dp[0][j] = j
    # 对应的是原理中的图二 
    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            delta = 0 if word1[i-1] == word2[j-1] else 1
            dp[i][j] = min(dp[i - 1][j - 1] + delta, min(dp[i-1][j] + 1, dp[i][j - 1] + 1))
    return dp[len1][len2]
edit_distance("jarrry", "jerr")

优化后：

参考文档：https://blog.csdn.net/Ha_hha/article/details/78834374

# coding=utf-8
# 这里的实现过程对算法进行了稍微的优化(运算结果应该稍快一些)：首先计算两个字符串开头以及结尾的共同字符子串，然后去掉相同部分，重新构造新字符串，减少迭代过程次数。
# 如：string_a = "GGATCGA" string_b = "GAATTCAGTTA"构造的新字符串为：
# new_a = "GATCG" new_b = "AATTCAGTT" 

def LD(string_a, string_b):
    '''
    定义函数实现LD算法
    '''
    # 初始化不同字符串开头的位置
    diff_start = -1
    # 初始化不同字符串结束的位置
    diff_end = -1
    # a字段的长度
    len_a = len(string_a)
    # b字段地长度
    len_b = len(string_b)
    # 找出a,b中的最小长度
    short = min(len_a, len_b)

    # 寻找开头的共同字符串，并记录位置
    for i in range(0, short):
        if string_a[i] != string_b[i]:
            diff_start = i
            break
    # 如果diff_start为-1，意味着有一个字符串为空，直接返回另一个字符串的长度
    if diff_start == -1:
        return abs(len_b - len_a)
    # 寻找结尾的共同字符串，并记录位置
    for i in range(0, short):
        if string_a[len_a - i -1] != string_b[len_b - i - 1]:
            diff_end = i
            break
    # # 如果diff_end为-1，意味着有一个字符串为空，直接返回另一个字符串的长度
    if diff_end == -1:
        return abs(len_b - len_a)

    # 因性质L(A+C, B+C) = LD(A, B)
    # 故除去开头以及结尾相同的字符串，构建新的字符串
#     long_str = str(string_a[diff_start: len_a - diff_end] if len_a >= len_b else string_b[diff_start: len_b - diff_end])
    long_str = string_a[diff_start: len_a - diff_end] if len_a >= len_b else string_b[diff_start: len_b - diff_end]
    short_str = string_a[diff_start: len_a - diff_end] if len_a < len_b else string_b[diff_start: len_b - diff_end]
    # print(long_str)
    # print(short_str)

    # 获取新字符串的长度
    long_len = len(long_str)
    short_len = len(short_str)

    # store保存迭代过程中每次计算的结果
    store = range(0, long_len + 1)

    # 对应的是原理中的每一行推导
    for i in range(short_len):
        temp = [i+1] * (long_len + 1)
        # 对应的是每个单元格的值
        for j in range(long_len):
            # 对应的是原理中当值相等的条件
            if long_str[j] == short_str[i]:
                temp[j+1] = store[j]
            # 对应的是原理中当值不相等的条件
            else:
                # 注意这时各个位置数据的对应关系
                temp[j+1] = min(store[j], store[j+1], temp[j]) + 1
        # 将每一行对应的结果赋值给store
        store = temp
        # print(store)
    # 返回最后的编辑距离
    return store[-1]


# Test
string_a = "GGATCGA"
string_b = "GAATTCAGTTA"

ld = LD(string_a, string_b)
print(ld)