最小編輯距離

1.定義

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

2.推導(dǎo)

設(shè)源字符串為A，長(zhǎng)度m，目標(biāo)字符串為B，長(zhǎng)度n。

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

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

  3. 是否存在簡(jiǎn)單情況到復(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)向前回溯，有三條路徑，對(duì)應(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}。

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

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

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