我在 Youtube 上觀看了一段視頻，解釋了如何通過從動態規劃演算法獲得的矩陣的最后一個單元格回傳 1 來計算使用了哪些操作以及使用了多少次。雖然我理解視頻中的示例，但當我嘗試使用其他示例時，我無法做到。是否可以在矩陣上顯示每個解決方案？我還在最后添加了計算矩陣的代碼。
假設我們的詞是"apple"和"paper"。
從動態規劃演算法獲得的矩陣（我使用了 Levensthein 距離運算。）：
“apple”和“paper”的最小編輯距離為 4。
解決方案之一是 4 次替換操作。
1. a pple -> p pple（將“a”替換為“p”）
2. p p ple -> p a ple（將“p”替換為“a”）
3. pap l e -> pap e e（將“l”替換為“e”）
4. pape e -> pape r（將“e”替換為“r”）
矩陣解法：
是否可以在此矩陣上顯示其他解決方案？
例如：
1. apple -> papple（插入“p”）
2. papple -> paple（去掉“p”）
3. paple -> pape（去掉“l”）
4.紙 -> 紙（插入“r”）
代碼：
def min_edit_count(word1, word2):
word1 = ' ' word1 #
word2 = ' ' word2 # add a space before original words
len_w1 = len(word1) #
len_w2 = len(word2) # calculate the lengths of new words
edit_matrix = np.zeros((len_w2, len_w1), dtype = int)
# create a matrix with all zeros
edit_matrix[0, :] = range(len_w1)
# assign numbers from 0 to len_w1 in the first row of the edit_matrix
edit_matrix[:, 0] = range(len_w2)
# assign numbers from 0 to len_w2 in the first column of the edit_matrix
for i in range(1, len_w2):
for j in range(1, len_w1):
# edit_matrix[i-1][j] --> remove
# edit_matrix[i][j-1] --> insert
# edit_matrix[i-1][j-1] --> replace
temp1 = edit_matrix[i-1][j] 1
temp2 = edit_matrix[i][j-1] 1
# add 1 to edit_matrix[i-1][j] and edit_matrix[i][j-1]
temp3 = edit_matrix[i-1][j-1] 1 if word1[j] != word2[i] else edit_matrix[i-1][j-1]
# if last characters are same don't add 1 to edit_matrix[i-1][j-1].
# no need to replace
edit_count = min(temp1, temp2, temp3)
# find min between three numbers
edit_matrix[i][j] = edit_count
min_edit = int(edit_matrix[len_w2 - 1, len_w1 - 1])
# minimum edit count is the last number calculated
return min_edit, edit_matrix
uj5u.com熱心網友回復：
是的，您可以從最后回溯可能有助于解決方案的單元格。
復雜性是O((n m) * num_solutions).
def getSolutions(edit_matrix, word1, word2):
pos = []
def backtrack(i,j):
pos.append((i,j))
if i==0 and j==0:
# This is a solution
print(pos)
if i>0 and edit_matrix[i-1,j] 1 == edit_matrix[i,j]:
backtrack(i-1,j)
if j>0 and edit_matrix[i,j-1] 1 == edit_matrix[i,j]:
backtrack(i, j-1)
if i>0 and j>0 and (edit_matrix[i-1][j-1] 1 if word1[j] != word2[i] else edit_matrix[i-1][j-1]) == edit_matrix[i,j]:
backtrack(i,j)
pos.pop()
backtrack(len(word1) - 1,len(word2) - 1)
uj5u.com熱心網友回復：
基于 Sorin 的好回答，這里有一個稍微增強的版本，它已修復以適合您的索引，并列印在每種情況下需要完成的編輯操作：
def get_solutions(edit_matrix, word1, word2):
pos = []
sol = []
def backtrack(i,j):
pos.insert(0, (i,j))
if i==0 and j==0:
# This is a solution
print(str(pos) ": " str(sol))
if i>0 and edit_matrix[i-1,j] 1 == edit_matrix[i,j]:
sol.insert(0, "insert " word2[i])
backtrack(i-1,j)
sol.pop(0)
if j>0 and edit_matrix[i,j-1] 1 == edit_matrix[i,j]:
sol.insert(0, "remove " word1[j])
backtrack(i, j-1)
sol.pop(0);
if i>0 and j>0 and edit_matrix[i-1][j-1] 1 if word1[j] != word2[i] else edit_matrix[i-1][j-1] == edit_matrix[i,j]:
if (word1[j] != word2[i]):
sol.insert(0, "replace " word1[j] " with " word2[i])
else:
sol.insert(0, "skip")
backtrack(i-1,j-1)
sol.pop(0)
pos.pop(0)
word1 = ' ' word1
word2 = ' ' word2
backtrack(len(word2) - 1,len(word1) - 1)
示例輸出
count, matrix = min_edit_count("apple", "paper")
get_solutions(matrix, "apple", "paper")
然后看起來如下：
[(0, 0), (1, 0), (2, 1), (3, 2), (3, 3), (3, 4), (4, 5), (5, 5)]: ['insert p', 'skip', 'skip', 'remove p', 'remove l', 'skip', 'insert r']
[(0, 0), (0, 1), (1, 2), (2, 2), (3, 3), (3, 4), (4, 5), (5, 5)]: ['remove a', 'skip', 'insert a', 'skip', 'remove l', 'skip', 'insert r']
[(0, 0), (1, 0), (2, 1), (2, 2), (3, 3), (3, 4), (4, 5), (5, 5)]: ['insert p', 'skip', 'remove p', 'skip', 'remove l', 'skip', 'insert r']
[(0, 0), (1, 1), (2, 2), (3, 3), (3, 4), (4, 5), (5, 5)]: ['replace a with p', 'replace p with a', 'skip', 'remove l', 'skip', 'insert r']
[(0, 0), (0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 5)]: ['remove a', 'skip', 'replace p with a', 'replace l with p', 'skip', 'insert r']
[(0, 0), (1, 0), (2, 1), (3, 2), (4, 3), (5, 4), (5, 5)]: ['insert p', 'skip', 'skip', 'replace p with e', 'replace l with r', 'remove e']
[(0, 0), (1, 0), (2, 1), (3, 2), (4, 3), (4, 4), (5, 5)]: ['insert p', 'skip', 'skip', 'replace p with e', 'remove l', 'replace e with r']
[(0, 0), (1, 0), (2, 1), (3, 2), (3, 3), (4, 4), (5, 5)]: ['insert p', 'skip', 'skip', 'remove p', 'replace l with e', 'replace e with r']
[(0, 0), (0, 1), (1, 2), (2, 2), (3, 3), (4, 4), (5, 5)]: ['remove a', 'skip', 'insert a', 'skip', 'replace l with e', 'replace e with r']
[(0, 0), (1, 0), (2, 1), (2, 2), (3, 3), (4, 4), (5, 5)]: ['insert p', 'skip', 'remove p', 'skip', 'replace l with e', 'replace e with r']
[(0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (5, 5)]: ['replace a with p', 'replace p with a', 'skip', 'replace l with e', 'replace e with r']
//fun: 你可以試著看看為什么每一行都有相同的長度 :D
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/409394.html
標籤：
上一篇：減少陣列中不同元素的數量