<p>尝试基于<a href="https://web.stanford.edu/class/cs124/lec/med.pdf" rel="nofollow">Minimum Edit Distance</a>的解决方案,在本例中,我使用<a href="http://nbviewer.ipython.org/github/BenLangmead/comp-genomics-class/blob/master/notebooks/CG_DP_EditDist.ipynb" rel="nofollow">this algorithm</a>来计算距离矩阵。在那之后,矩阵上的迭代返回到前进,以确定字符串中包含或删除的字符,因为我需要反转结果</p>
<p>要给终端上色,我使用colorama模块</p>
<pre><code>#!/bin/python
import sys
from colorama import *
from numpy import zeros
init()
inv_WHITE = Fore.WHITE[::-1]
inv_RED = Fore.RED[::-1]
inv_GREEN = Fore.GREEN[::-1]
def edDistDp(y, x):
res = inv_WHITE
D = zeros((len(x)+1, len(y)+1), dtype=int)
D[0, 1:] = range(1, len(y)+1)
D[1:, 0] = range(1, len(x)+1)
for i in xrange(1, len(x)+1):
for j in xrange(1, len(y)+1):
delt = 1 if x[i-1] != y[j-1] else 0
D[i, j] = min(D[i-1, j-1]+delt, D[i-1, j]+1, D[i, j-1]+1)
#print D
# iterate the matrix's values from back to forward
i = len(x)
j = len(y)
while i > 0 and j > 0:
diagonal = D[i-1, j-1]
upper = D[i, j-1]
left = D[i-1, j]
# check back direction
direction = "\\" if diagonal <= upper and diagonal <= left else "<-" if left < diagonal and left <= upper else "^"
#print "(",i,j,")",diagonal, upper, left, direction
i = i-1 if direction == "<-" or direction == "\\" else i
j = j-1 if direction == "^" or direction == "\\" else j
# Colorize caracters
if (direction == "\\"):
if D[i+1, j+1] == diagonal:
res += x[i] + inv_WHITE
elif D[i+1, j+1] > diagonal:
res += y[j] + inv_RED
res += x[i] + inv_GREEN
else:
res += x[i] + inv_GREEN
res += y[j] + inv_RED
elif (direction == "<-"):
res += x[i] + inv_GREEN
elif (direction == "^"):
res += y[j] + inv_RED
return res[::-1]
one_string = "beep boop"
other_string = "beep boob blah"
print ("'%s'-'%s'='%s'" % (one_string, other_string, edDistDp(one_string, other_string)))
print ("'%s'-'%s'='%s'" % (other_string, one_string, edDistDp(other_string, one_string)))
other_string = "hola nacho"
one_string = "hola naco"
print ("'%s'-'%s'='%s'" % (one_string, other_string, edDistDp(one_string, other_string)))
print ("'%s'-'%s'='%s'" % (other_string, one_string, edDistDp(other_string, one_string)))
</code></pre>