http://blog.csdn.net/pipisorry/article/details/46383947

編輯距離Edit distance/Levenshtein distance-序列之間的距離

X 和Y 的編輯距離定義為：從字元串strings X轉換到 Y 需要的插入、删除、替換兩個相鄰的基本機關(字元)的最小個數。

給定 2 個字元串 a, b. 編輯距離是将 a 轉換為 b 的最少操作次數，操作隻允許如下 3 種：

插入一個字元，例如：fj -> fxj
删除一個字元，例如：fxj -> fj
替換一個字元，例如：fxj -> fyj

如：

ed (recoginze, recognize) = 1

ed (sailn, failing) = 3

編輯距離是一個動态規劃的問題。

編輯距離常用在英語單詞拼寫檢查中，可以使用有限自動機實作[宗成慶:《自然語言處理》講義：第03章形式語言與自動機及其在自然語言進行中的應用NLP-03+FL_and_ItsApp.pdf]。

編輯距離與最長公共子序列LCS

編輯距離Edit distance編輯距離的動态規劃解

子串的定義：one string is a sub-sequence of another if we can get the first by deleting 0 or more positions from the second.the positions of the deleted characters did not have to be consecutive.

計算x,y編輯距離的兩種方式

編輯距離Edit distance編輯距離的動态規劃解

第一種方式中我們可以逆向編輯：we can get from y to x by doing the same edits in reverse.delete u and v,and then we insert a to get x.

[海量資料挖掘Mining Massive Datasets(MMDs) -Jure Leskovec courses學習筆記之局部敏感哈希LSH的距離度量方法]

Note: lz代碼證明了，并沒有這種關系，這裡隻是一個特例碰巧而已，不知道是不是lcs定義不同還是怎麼回事。如"bedaacbade"和 "dccaeedbeb"的lcs為5，而編輯距離為10，并沒有以上關系。

擴充的編輯距離(Damerau-Levenshtein Distance)

擴充的編輯距離在思想上與編輯距離一樣，隻是除插入、删除和替換操作外，還支援相鄰字元的交換這樣一個操作，增加這個操作的考慮是人們在計算機上輸入文檔時的錯誤情況中，因為快速敲擊而前後兩個字元的順序被輸錯的情況很常見。

皮皮blog

編輯距離的動态規劃解

思路

用分治的思想解決比較簡單，将複雜的問題分解成相似的子問題。

假設字元串 a, 共 m 位，從

a[1]

到

a[m]，

字元串 b, 共 n 位，從

b[1]

到

b[n]

d[i][j]

表示字元串

a[1]-a[i]

轉換為

b[1]-b[j]

的編輯距離。

那麼有如下遞歸規律（

a[i]

和

b[j]

分别是目前要計算編輯距離的子字元串 a 和 b 的最後一位）：

當 a[i] 等于 b[j] 時， d[i][j] = d[i-1][j-1] , 比如 fxy -> fay 的編輯距離等于 fx -> fa 的編輯距離
當 a[i] 不等于 b[j] 時， d[i][j] 等于如下 3 項的最小值：
- d[i-1][j] + 1（删除 a[i] （删除等價于插入操作，相當于插入b中插入a[i[）），比如 fxy -> fab 的編輯距離 = fx -> fab 的編輯距離 + 1
- d[i][j-1] + 1（删除 b[j]或者插入b[j] )，比如 fxy -> fab 的編輯距離 = fxyb -> fab 的編輯距離 + 1 = fxy -> fa 的編輯距離 + 1
- d[i-1][j-1] + 1（ 将a[i]b[j]同時删除 （等價于交換操作）），比如 fxy -> fab 的編輯距離 = fxb -> fab 的編輯距離 + 1 = fx -> fa 的編輯距離 + 1

遞歸邊界：

a[i][0] = i , b 字元串為空，表示将 a[1]-a[i] 全部删除，是以編輯距離為 i
a[0][j] = j , a 字元串為空，表示 a 插入 b[1]-b[j] ，是以編輯距離為 j

遞歸思路代碼

按照上面的思路将代碼寫下來

int edit_distance(char *a, char *b, int i, int j)
{
    if (j == 0) {
        return i;
    } else if (i == 0) {
        return j;
    // 算法中 a, b 字元串下标從 1 開始，c 語言從 0 開始，是以 -1
    } else if (a[i-1] == b[j-1]) {
        return edit_distance(a, b, i - 1, j - 1);
    } else {
        return min_of_three(edit_distance(a, b, i - 1, j) + 1,
                            edit_distance(a, b, i, j - 1) + 1,
                            edit_distance(a, b, i - 1, j - 1) + 1);
    }
}

edit_distance(stra, strb, strlen(stra), strlen(strb));

但是這個代碼的性能很低下，時間複雜度是指數增長的，很多相同的子問題其實是經過了多次求解。

解決這類問題的辦法是1 使用記憶

ins = dict()
def edit_distance(w1, w2, i, j):
    if (i, j) in ins:
        return ins[(i, j)]
    if len(w1) <= i:
        return len(w2) - j
    if len(w2) <= j:
        return len(w1) - i

    if w1[i] == w2[j]:
        minl = edit_distance(w1, w2, i + 1, j + 1)
    else:
        minl = min(edit_distance(w1, w2, i + 1, j + 1), edit_distance(w1, w2, i, j + 1)
                   , edit_distance(w1, w2, i + 1, j)) + 1
    ins[(i, j)] = minl
    return minl

2 使用動态規劃。

用動态規劃思想優化時間複雜度

以上解決思路是從後往前算的，想知道

edit_distance(a, b, i, j)

就需要知道

edit_distance(a, b, i-1, j-1)。

如果從前往後算，先算出各個子問題，然後根據子問題，計算出原問題。

例如以字元串 a = "ace", b = "abcdef" 為例：

首先建立一個矩陣，用來存放子問題及原問題的編輯距離，并将遞歸邊界在矩陣中填好，如下：

a	b	c	d	e	f
1	2	3	4	5	6
a	1
c	2
e	3

然後計算 i = 1, j = 1 所對應的編輯距離：比較

a[i]

和

b[j]

是否相等然後根據遞歸規律算出這個值

比如在這種情況下

a[i] = a

和

b[j] = a

, 那麼

d[i][j]

就等于

d[i-1][j-1]

等于 0

然後計算 i = 1, j = 2 直到算出 i = 3, j = 6, 原問題的編輯距離就等于

d[3][6]

最終矩陣如下：

a	b	c	d	e	f
1	2	3	4	5	6
a	1	1	2	3	4	5
c	2	1	1	1	2	3	4
e	3	2	2	2	2	2	3

即要計算

d[i][j]

隻需要知道3個位置上的值。

代碼如下：

int edit_distance(char *a, char *b){
    int lena = strlen(a);
    int lenb = strlen(b);
    int d[lena+1][lenb+1];
    int i, j;

    for (i = 0; i <= lena; i++) {
        d[i][0] = i;
    }
    for (j = 0; j <= lenb; j++) {
        d[0][j] = j;
    }

    for (i = 1; i <= lena; i++) {
        for (j = 1; j <= lenb; j++) {
            // 算法中 a, b 字元串下标從 1 開始，c 語言從 0 開始，是以 -1
            if (a[i-1] == b[j-1]) {
                d[i][j] = d[i-1][j-1];
            } else {
                d[i][j] = min_of_three(d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1]+1);
            }
        }
    }

    return d[lena][lenb];
}

def edit_distance(w1, w2):
    len1 = len(w1)
    len2 = len(w2)
    matrix = [[0 for _ in range(len2 + 1)] for _ in range(len1 + 1)]
    for j in range(len2):
        matrix[0][j + 1] = j + 1
    for i in range(len1):
        matrix[i + 1][0] = i + 1

    for i in range(1, len1 + 1):
        for j in range(1, len2 + 1):
            if w1[i - 1] == w2[j - 1]:
                matrix[i][j] = matrix[i - 1][j - 1]
            else:
                matrix[i][j] = min(matrix[i - 1][j], matrix[i - 1][j - 1], matrix[i][j - 1]) + 1
    return matrix[len1][len2]

這個算法的時間複雜度為O(mn)。

空間複雜度為 O(mn)，空間複雜度可以繼續優化，因為計算矩陣某位置值的時候總是需要有限的量，同一時間并不需要所有矩陣的值。

根據具體問題優化空間複雜度

還是以 a = "fxy", b = "fab" 為例，例如計算

d[1][3]

, 也就是下圖中的綠色方塊，我們需要知道的值隻需 3 個，下圖中藍色方塊的值

編輯距離Edit distance編輯距離的動态規劃解

進一步分析，我們知道，當計算

d[1]

這行的時候，我們隻需知道

d[0]

這行的值，同理我們計算目前行的時候隻需知道上一行就可以了。

再進一步分析，其實我們隻需要一行就可以了，每次計算的時候我們需要的 3 個值，其中上邊和左邊的值我們可以直接得到，坐上角的值需要臨時變量（如下代碼使用 old）來記錄。

代碼如下：

int edit_distance(char *a, char *b){
    int lena = strlen(a);
    int lenb = strlen(b);
    int d[lenb+1];
    int i, j, old, tnmp;

    for (j = 0; j <= lenb; j++) {
        d[j] = j;
    }

    for (i = 1; i <= lena; i++) {
        old = i - 1;
        d[0] = i;
        for (j = 1; j <= lenb; j++) {
            temp = d[j];
            // 算法中 a, b 字元串下标從 1 開始，c 語言從 0 開始，是以 -1
            if (a[i-1] == b[j-1]) {
                d[j] = old;
            } else {
                d[j] = min_of_three(d[j] + 1, d[j-1] + 1, old + 1);
            }
            old = temp;
        }
    }

    return d[lenb];
}

寫代碼的過程中需要注意的一點就是，當一行計算好之後開始下一行的時候，要初始化

old

和

d[0]

的值

優化過後時間複雜度還是 O(mn), 空間複雜度 O(min(m,n))。

皮皮blog

DTW 距離（Dynamic Time Warp）

時間序列是序列之間距離的另外一個例子。DTW 距離（Dynamic Time Warp）是序列信号在時間或者速度上不比對的時候一種衡量相似度的方法。舉個例子，兩份原本一樣聲音樣本A、B都說了“你好”，A在時間上發生了扭曲，“你”這個音延長了幾秒。最後A:“你~~好”，B：“你好”。DTW正是這樣一種可以用來比對A、B之間的最短距離的算法。DTW 距離在保持信号先後順序的限制下對時間信号進行“膨脹”或者“收縮”，找到最優的比對，與編輯距離相似，這其實也是一個動态規劃的問題。

實作代碼

import sys
 
distance = lambda a,b : 0 if a==b else 1
 
def dtw(sa,sb):
    '''
    >>>dtw(u"幹啦今今今今今天天氣氣氣氣氣好好好好啊啊啊", u"今天天氣好好啊")
    2
    '''
    MAX_COST = 1<<32
    #初始化一個len(sb) 行(i)，len(sa)列(j)的二維矩陣
    len_sa = len(sa)
    len_sb = len(sb)
    # BUG:這樣是錯誤的(淺拷貝): dtw_array = [[MAX_COST]*len(sa)]*len(sb)
    dtw_array = [[MAX_COST for i in range(len_sa)] for j in range(len_sb)]
    dtw_array[0][0] = distance(sa[0],sb[0])
    for i in xrange(0, len_sb):
        for j in xrange(0, len_sa):
            if i+j==0:
                continue
            nb = []
            if i > 0: nb.append(dtw_array[i-1][j])
            if j > 0: nb.append(dtw_array[i][j-1])
            if i > 0 and j > 0: nb.append(dtw_array[i-1][j-1])
            min_route = min(nb)
            cost = distance(sa[j],sb[i])
            dtw_array[i][j] = cost + min_route
    return dtw_array[len_sb-1][len_sa-1]
 
 
def main(argv):
    s1 = u'幹啦今今今今今天天氣氣氣氣氣好好好好啊啊啊'
    s2 = u'今天天氣好好啊'
    d = dtw(s1, s2)
    print d
    return 0
 
if __name__ == '__main__':
    sys.exit(main(sys.argv))

[動态時間歸整 | DTW | Dynamic Time Warping]

from: http://blog.csdn.net/pipisorry/article/details/46383947

ref: [編輯距離 (Edit distance)]

[leetcode位址https://leetcode-cn.com/problems/edit-distance/]

編輯距離Edit distance編輯距離的動态規劃解

編輯距離Edit distance/Levenshtein distance-序列之間的距離

編輯距離與最長公共子序列LCS

擴充的編輯距離(Damerau-Levenshtein Distance)

編輯距離的動态規劃解

思路

遞歸思路代碼

用動态規劃思想優化時間複雜度

根據具體問題優化空間複雜度

DTW 距離（Dynamic Time Warp）

繼續閱讀

POJ3628 Bookshelf2

程式員的算法趣題Q09: 落單的男女1. 問題描述2. 解題分析3. 代碼及測試4. 思考

ZOJ 3216 Compositions（矩陣優化DP）

HDOJ.1114-Piggy-Bank

【bzoj1419】Red is good（機率期望dp）1419: Red is good

746.使用最小花費爬樓梯 Min Cost Climing Stairs

[LeetCode]（面試題 17.21）直方圖的水量

LeetCode刷題系列——編輯距離

HDU 5119 Happy Matt Friends（01背包）

HDU 5119 Happy Matt Friends（dp） Happy Matt Friends

Codeforces Round #319 (Div. 2) B C D

nyoj712 雙程動态規劃

NYOJ 269--VF

NYOJ - 252 - 01串(動态規劃)

一個小小的算法題

HDU 1160 FatMouse's Speed （記錄路徑的最長上升子序列）