我将如何去显示单词之间的详细距离。 例如,程序的输出可能是:单词之间的详细距离
Words are "car" and "cure":
Replace "a" with "u".
Add "e".
的Levenshtein距离不符合我的需要(我认为)。
我将如何去显示单词之间的详细距离。 例如,程序的输出可能是:单词之间的详细距离
Words are "car" and "cure":
Replace "a" with "u".
Add "e".
的Levenshtein距离不符合我的需要(我认为)。
请尝试以下操作。该算法大致遵循Wikipedia (Levenshtein distance)。下面所使用的语言是红宝石
使用作为一个例子,改变s
的情况下进入t
如下:
s = 'Sunday'
t = 'Saturday'
首先,s
和t
都变成阵列,以及一个空字符串被插入在开始时。 m
最终将成为算法中使用的矩阵。
s = ['', *s.split('')]
t = ['', *t.split('')]
m = Array.new(s.length){[]}
m
这里,然而,是从在维基百科如果算法给出的事实,不同的矩阵,每个单元不仅包括Levenshtein距离,而且(非)操作(开始 ,无为,缺失,插入,或取代),其用于获取对来自相邻(左,上,或左上)单元该单元格。它还可能包括描述操作参数的字符串。即,每个单元格的格式是:
[Levenshtein距离,操作(字符串)]
这里是主程序。它在m
算法后的细胞填充:
s.each_with_index{|a, i| t.each_with_index{|b, j|
m[i][j] =
if i.zero?
[j, "started"]
elsif j.zero?
[i, "started"]
elsif a == b
[m[i-1][j-1][0], "did nothing"]
else
del, ins, subs = m[i-1][j][0], m[i][j-1][0], m[i-1][j-1][0]
case [del, ins, subs].min
when del
[del+1, "deleted", "'#{a}' at position #{i-1}"]
when ins
[ins+1, "inserted", "'#{b}' at position #{j-1}"]
when subs
[subs+1, "substituted", "'#{a}' at position #{i-1} with '#{b}'"]
end
end
}}
现在,我们设置i
,j
到m
的右下角,然后按照步骤倒退,因为我们不印字的单元格的内容转换成一种叫做阵列steps
,直到我们开始。
i, j = s.length-1, t.length-1
steps = []
loop do
case m[i][j][1]
when "started"
break
when "did nothing", "substituted"
steps.unshift(m[i-=1][j-=1])
when "deleted"
steps.unshift(m[i-=1][j])
when "inserted"
steps.unshift(m[i][j-=1])
end
end
然后我们打印操作和每个步骤的字符串,除非这是非操作。
steps.each do |d, op, str=''|
puts "#{op} #{str}" unless op == "did nothing" or op == "started"
end
有了这个特殊的例子,它会输出:
inserted 'a' at position 1
inserted 't' at position 2
substituted 'n' at position 2 with 'r'
这是我尝试的第一件事,但我一定有什么不对。我结束了一些bruteforcing。 – SuprDewd 2011-03-12 18:31:18
我想的话,你需要给“距离”的一个更精确的定义,在您使用它的方式。 – FrustratedWithFormsDesigner 2011-03-10 15:33:12
Levenshtein距离有什么问题? – sawa 2011-03-10 15:35:34
我需要输出在后台执行的操作。 – SuprDewd 2011-03-10 15:54:33