參考鏈接：https://www.cnblogs.com/jiabei521/p/3353390.html

字符串的編輯距離也被稱為距Levenshtein距離（Levenshtein Distance），屬于經(jīng)典算法，常用方法使用遞歸，更好的方法是使用動態(tài)規(guī)劃算法，以避免出現(xiàn)重疊子問題的反復(fù)計(jì)算，減少系統(tǒng)開銷。

問題：找出字符串的編輯距離，即把一個(gè)字符串s1最少經(jīng)過多少步操作變成編程字符串s2，操作有三種，添加一個(gè)字符，刪除一個(gè)字符，修改一個(gè)字符。
其實(shí)這個(gè)問題的關(guān)鍵是要求兩個(gè)字符串的編輯距離
例如 將aproxiomally一字轉(zhuǎn)成approximatly：

1、 approxiomally （null→p）插入
2、approximally （o→null）刪除
3、approximatly （l→t）修改

下面我們就針對這個(gè)問題來詳細(xì)闡述一下：
我們假定函數(shù)dist(str1, str2)表示字串str1轉(zhuǎn)變到字串str2的編輯距離，那么對于下面3種極端情況，我們很容易給出解答（0表示空串）。

1、dist(0, 0) = 0
2、dist(0, s) = strlen(s)
3、dist(s, 0) = strlen(s)

對于一般的情況，dist(str1, str2)我們應(yīng)該如何求解呢？

假定我們現(xiàn)在正在求解dist(str1+char1, str2+char2)，也就是把"str1+char1"轉(zhuǎn)變成"str2+char2"。在這個(gè)轉(zhuǎn)變過稱中，我們要分情況討論：

1、 str1可以直接轉(zhuǎn)變成str2。這時(shí)我們只要把char1轉(zhuǎn)成char2就可以了（如果char1 != char2）。
2、 str1+char1可以直接轉(zhuǎn)變成str2。這時(shí)我們處理的方式是插入char2。
3、str1可以直接轉(zhuǎn)成str2+char2。這時(shí)的情況是我們需要刪除char1。

綜合上面三種情況，dist(str1+char1, str2+char2)應(yīng)該是三者的最小值。

解析：

首先定義這樣一個(gè)函數(shù)——edit(i, j)，它表示第一個(gè)字符串的長度為i的子串到第二個(gè)字符串的長度為j的子串的編輯距離。

顯然可以有如下動態(tài)規(guī)劃公式：

if i == 0 且 j == 0，edit(i, j) = 0
if i == 0 且 j > 0，edit(i, j) = j
if i > 0 且j == 0，edit(i, j) = i
if i ≥ 1  且 j ≥ 1 ，edit(i, j) == min{ edit(i-1, j) + 1, edit(i, j-1) + 1, edit(i-1, j-1) + f(i, j) }，當(dāng)?shù)谝粋€(gè)字符串的第i個(gè)字符不等于第二個(gè)字符串的第j個(gè)字符時(shí)，f(i, j) = 1；否則，f(i, j) = 0。

我們建立以下表格，將兩個(gè)字符串按照表格1所示的樣子進(jìn)行擺放，規(guī)則按照以上公式進(jìn)行輸入，如下所示：

計(jì)算edit(1, 1)，edit(0, 1) + 1 == 1，edit(1, 0) + 1 == 1，edit(0, 0) + f(1, 1) == 0 + 0 == 0，min(edit(0, 1)，edit(1, 0)，edit(0, 0) + f(1, 1))==0，因此edit(1, 1) == 0。依次類推，有如下表格所示最終的矩陣：

動態(tài)規(guī)劃表

此時(shí)右下角即為我們所需要的兩個(gè)字符串的編輯距離。即字符串 "aproxiomally"和"approximatly"的編輯距離為3.

有了以上的步驟，相信大家已經(jīng)很清楚了，使用動態(tài)規(guī)劃算法的時(shí)候，需要建立子問題的表格，以上的表格就是。而且我們能夠很容易的使用二維數(shù)組建立。代碼實(shí)現(xiàn)也就易如反掌了！

以下是我的實(shí)現(xiàn)過程，希望對大家有用，如果有什么可以優(yōu)化或者錯誤的地方，希望能夠得到批評指正

import numpy as np

'''
函數(shù)說明：計(jì)算近似字符串的邏輯距離
parameter：
    str1
    str2
return：
    distance
'''

def string_distance(str1,str2):
    m = str1.__len__()
    n = str2.__len__()
    distance = np.zeros((m+1,n+1))

    for i in range(0,m+1):
        distance[i,0]=i
    for i in range(0,n+1):
        distance[0,i]=i
    for i in range(1,m+1):
        for j in range(1,n+1):
            if str1[i-1]==str2[j-1]:
                cost =0
            else:
                cost=1
            distance[i,j]=min(distance[i-1,j]+1,distance[i,j-1]+1,distance[i-1,j-1]+cost)
    print(distance)
    return distance[m,n]



if __name__=='__main__':
    a='aproxiomally'
    b='approximatly'
    result = string_distance(a,b)
    print(result)

結(jié)果：

最小編輯距離

由圖可知，與我們的動態(tài)規(guī)劃表推出的結(jié)果一致。