我知道在堆栈上和在线上都可以找到类似的答案,但是我感觉自己缺少一些东西。给定以下代码,我们需要重建导致最小编辑距离的事件序列。对于下面的代码,我们需要编写一个输出函数:
Equal, L, L
Delete, E
Equal, A, A
Substitute, D, S
Insert, T
编辑:代码已通过我的(部分正确的)解决方案更新
这是代码,还有我的部分解决方案。例如,它可以给我(“lead”->“last”),但不适用于下面的示例(“hint”->“isnt”)。我怀疑这是因为第一个字符是相等的,这使我的代码无效。正确方向上的任何提示或指示都将很棒!
def printMatrix(M):
for row in M:
print row
print
def med(s, t):
k = len(s) + 1
l = len(t) + 1
M = [[0 for i in range(k)] for j in range(l)]
MTrace = [["" for i in range(k)] for j in range(l)]
M[0][0] = 0
for i in xrange(0, k):
M[i][0] = i
MTrace[i][0] = s[i-1]
for j in xrange(0, l):
M[0][j] = j
MTrace[0][j] = t[j-1]
MTrace[0][0] = "DONE"
for i in xrange(1, k):
for j in xrange(1, l):
sub = 1
sub_op = "sub"
if s[i-1] == t[j-1]:
# equality
sub = 0
sub_op = "eq"
# deletion
min_value = M[i-1][j] + 1
op = "del"
if min_value > M[i][j-1] + 1:
# insertion
min_value = M[i][j-1] + 1
op = "ins"
if min_value > M[i-1][j-1] + sub:
# substitution
min_value = M[i-1][j-1] + sub
op = sub_op
M[i][j] = min_value
MTrace[i][j] = op
print "final Matrix"
printMatrix(M)
printMatrix(MTrace)
############ MY PARTIAL SOLUTION
def array_append(array,x,y):
ops_string = MTrace[x][y]
if ops_string == 'ins':
array.append(("Insert",MTrace[0][y]))
elif ops_string == 'sub':
array.append(("Substitute",MTrace[x][0],MTrace[0][y]))
elif ops_string == 'eq':
array.append(("Equal",MTrace[x][0],MTrace[0][y]))
elif ops_string == 'del':
array.append(("Delete",MTrace[x][0]))
i = len(s)
j = len(t)
ops_array = []
base = M[i][j]
array_append(ops_array,i,j)
while MTrace[i][j] != "DONE":
base = M[i][j]
local_min = min(M[i][j-1],M[i-1][j],M[i-1][j-1])
if base == local_min:
i = i - 1
j = j - 1
array_append(ops_array,i,j)
elif M[i][j-1] < M[i-1][j]:
j = j -1
array_append(ops_array,i,j)
elif M[i-1][j] < M[i][j-1]:
i = i - 1
array_append(ops_array,i,j)
else:
i = i - 1
j = j - 1
array_append(ops_array,i,j)
print ops_array
#########
return M[k-1][l-1]
print med('lead', 'last')
参考方案
我认为在这种情况下,更深入地了解算法很重要。除了向您提供一些伪代码外,我还将向您介绍该算法的基本步骤,并向您展示所需的数据如何在最终的矩阵中“编码”。当然,如果您不需要滚动自己的算法,那么您显然应该使用别人的算法,例如MattH suggests!
大图景
在我看来,这类似于Wagner-Fischer algorithm的实现。基本思想是计算“附近”前缀之间的距离,取最小值,然后从中计算出当前字符串对的距离。例如,假设您有两个字符串'i'
和'h'
。让我们沿着矩阵的垂直和水平轴进行布局,如下所示:
_ h
_ 0 1
i 1 1
在这里,'_'
表示一个空字符串,矩阵中的每个单元格对应于一个将输入(''
或'i'
)输入到输出(''
或'h'
)的编辑序列。
空字符串到任何长度为L的字符串的距离为L(需要插入L个字符)。从任何长度为L的字符串到空字符串的距离也为L(需要删除L个字符)。这覆盖了第一行和第一列中的值,这些值只是递增。
从那里,您可以通过从上,左和左上值中取最小值,然后加上一个值来计算任何位置的值;或者,如果字符串中该点的字母相同,则取上一个值-left值不变。对于上表中(1, 1)
的值,最小值是0
的(0, 0)
,因此(1, 1)
的值是1
,这是'i'
到'h'
的最小编辑距离(一个替换)。因此,通常,最小编辑距离始终位于矩阵的右下角。
现在让我们再做一次,比较is
和hi
。同样,矩阵中的每个单元格都对应于一个将输入(''
,'i'
或'is'
)输入到输出(''
,'h'
或'hi'
)的编辑序列。
_ h i
_ 0 1 2
i 1 1 #
s 2 # #
我们首先放大矩阵,将#
用作尚不知道的值的占位符,然后通过递增扩展第一行和第一列。这样,我们就可以开始计算上面标记为#
的位置的结果。让我们从(2, 1)
(在(行,列),即行为主的表示法)开始。在上,左上和左值中,最小值为1
。表中对应的字母不同-s
和h
-因此我们在该最小值上加一个以获得2
并继续。
_ h i
_ 0 1 2
i 1 1 #
s 2 2 #
让我们继续到(1, 2)
的值。现在情况有所不同,因为表中的对应字母相同-它们都是i
。这意味着我们可以选择在左上角的单元格中取值而不加一个。这里的直觉是我们不必增加计数,因为在此位置将相同的字母添加到两个字符串中。而且由于两根弦的长度都增加了一个,所以我们沿对角线移动。
_ h i
_ 0 1 2
i 1 1 1
s 2 2 #
在最后一个空单元格之后,一切恢复正常。对应的字母是s
和i
,因此我们再次取最小值并加一个,得到2
:
_ h i
_ 0 1 2
i 1 1 1
s 2 2 2
如果我们继续此过程以is
和hi
开头的两个更长的单词,这是我们得到的表格-isnt
(忽略标点符号)和hint
_ h i n t
_ 0 1 2 3 4
i 1 1 1 2 3
s 2 2 2 2 3
n 3 3 3 2 3
t 4 4 4 3 2
这个矩阵稍微复杂一些,但是这里的最终最小编辑距离仍然只是2
,因为这两个字符串的最后两个字母是相同的。方便!
重新创建编辑顺序
那么我们如何从该表中提取编辑类型呢?关键是要意识到桌子上的移动对应于特定的编辑类型。因此,例如,从(0, 0)
到(0, 1)
的向右移动将我们从不需要编辑的_ -> _
转到需要一个编辑,一个插入的_ -> h
。同样,从(0, 0)
到(1, 0)
的向下移动使我们从不需要编辑的_ -> _
到需要一个编辑,删除的i -> _
。最后,从(0, 0)
到(1, 1)
的对角线运动使我们从不需要编辑的_ -> _
到需要进行一次编辑的替代i -> h
。
因此,现在我们要做的就是反转步骤,从上,左和左上单元格中追踪局部最小值回到原点(0, 0)
,请记住,如果当前值与最小值相同,则我们必须转到左上方的单元格,因为这是唯一一种不会增加编辑距离的移动。
这是您可以采取的步骤的详细说明。从完成的矩阵的右下角开始,重复以下操作,直到到达左上角:
Equal
)。在这种情况下,无需编辑,因为此位置的字符相同。 把它放在一起
在上面的示例中,有两种可能的路径:
(4, 4) -> (3, 3) -> (2, 2) -> (1, 2) -> (0, 1) -> (0, 0)
和
(4, 4) -> (3, 3) -> (2, 2) -> (1, 1) -> (0, 0)
扭转它们,我们得到
(0, 0) -> (0, 1) -> (1, 2) -> (2, 2) -> (3, 3) -> (4, 4)
和
(0, 0) -> (1, 1) -> (2, 2) -> (3, 3) -> (4, 4)
因此,对于第一个版本,我们的第一个操作是向右移动,即插入。插入的字母是h
,因为我们正从isnt
移到hint
。 (这与您详细输出中的Insert, h
对应。)我们的下一个操作是对角移动,即替换或不操作。在这种情况下,这是空操作,因为两个位置的编辑距离都相同(即字母相同)。所以Equal, i, i
。然后向下移动,对应于删除。删除的字母是s
,因为我们又从isnt
移到hint
。 (通常,要插入的字母来自输出字符串,而要删除的字母来自输入字符串。)这就是Delete, s
。然后,两个对角线运动值不变:Equal, n, n
和Equal, t, t
。
结果:
Insert, h
Equal, i, i
Delete, s
Equal, n, n
Equal, t, t
在isnt
上执行以下指令:
isnt (No change)
hisnt (Insertion)
hisnt (No change)
hint (Deletion)
hint (No change)
hint (No change)
总编辑距离为2。
我将保留第二个最小路径作为练习。请记住,两条路径是完全等效的;它们可能有所不同,但是它们将导致相同的最小编辑距离2,因此可以完全互换。在向后遍历矩阵的任何时候,如果您看到两个不同的局部最小值,则可以取其中一个,并且保证最终结果是正确的
一旦您掌握了所有这些内容,就不难编写代码了。在这种情况下,关键是要首先深刻理解算法。完成此操作后,对其进行编码就很容易了。
积累与重建
最后一点,您可以选择在填充矩阵时累积编辑内容。在这种情况下,矩阵中的每个单元格都可以是一个元组:(2, ('ins', 'eq', 'del', 'eq', 'eq'))
。您将增加长度,并追加与从最小先前状态开始的移动相对应的操作。这消除了回溯,从而降低了代码的复杂性;但是会占用额外的内存。如果执行此操作,则最终编辑序列将与最终编辑距离一起出现在矩阵的右下角。
在Python 3中,要加载以前保存的json,如下所示:json.dumps(dictionary)输出是这样的{"('Hello',)": 6, "('Hi',)": 5}当我使用json.loads({"('Hello',)": 6,…
Python 3运算符>>打印到文件 - python我有以下Python代码编写项目的依赖文件。它可以在Python 2.x上正常工作,但是在使用Python 3进行测试时会报告错误。depend = None if not nmake: depend = open(".depend", "a") dependmak = open(".depend.mak…
快速返回没有Python中特定元素的列表的方法 - python如果我有任意顺序的卡片套装列表,如下所示:suits = ["h", "c", "d", "s"] 我想返回一个没有'c'的列表noclubs = ["h", "d", "s"] 有没有简单的方法可以…
Python pytz时区函数返回的时区为9分钟 - python由于某些原因,我无法从以下代码中找出原因:>>> from pytz import timezone >>> timezone('America/Chicago') 我得到:<DstTzInfo 'America/Chicago' LMT-1 day, 18:09:00 STD…
如何将Python字节字符串表示形式转换为字节? - python我在文本文件中存储了许多Python字节对象,这些Python打印的内容类似于"b'\x80\x03}q\x00.'"如何将每个对象转换回字节对象?换句话说,我正在尝试找到一个执行convert("b'\x80\x03}q\x00.'") == b'\x80\x03}q…