最小編輯距離

1.定義

假設(shè)只有三種編輯方式：插入，刪除，替換。每種編輯方式對應(yīng)一次操作。按規(guī)定的編輯方式，將原始字符串變換到目標字符串所需的最少操作次數(shù)，被稱為最小編輯距離。
Levenshtein距離中定義替換對應(yīng)兩次操作。

2.推導(dǎo)

設(shè)源字符串為A，長度m，目標字符串為B，長度n。

  1. 是否存在簡單情況
    很明顯，兩字符串長度較短時情況會比較簡單。
    如，m=0時，插入n次；n=0時，刪除n次；m=n=1且A和B不同時，替換1次。

  2. 簡單情況到復(fù)雜情況的變量是什么
    是兩個字符串的長度。因此我們設(shè)最小編輯距離為D(m,n)。

  3. 是否存在簡單情況到復(fù)雜情況的遞推關(guān)系
    由1有\begin{cases}D(i,0)=i,i \in (0,m) \\ D(0,j)=j,j \in (0,n) \end{cases}
    從D(i,j)向前回溯，有三條路徑，對應(yīng)三種編輯方式，
    D(i,j) = min \begin{cases} D(i,j-1)+ins(B[j]) \\ D(i-1,j)+del(A[i]) \\ D(i-1,j-1)+sub(A[i],B[j]) \end{cases}這里，ins(x)=1，del(x)=1，sub(x,y) = \begin{cases} 1,x \neq y \\ 0,x = y \end{cases}。

  • 每一步取最短路徑，最后一定是最短路徑嗎？對于每次都歸結(jié)于一點的樹形結(jié)構(gòu)，這是必然的。
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容