Levenshtein distance/Alignment: Difference between revisions
Content added Content deleted
m (Made Racket sub-sections appear as sub-sections) |
(Added Ruby) |
||
Line 356: | Line 356: | ||
r-oset-taco-de |
r-oset-taco-de |
||
raisethysword-</pre> |
raisethysword-</pre> |
||
=={{header|Ruby}}== |
|||
{{trans|Tcl}} |
|||
uses "lcs" from [[Longest common subsequence#Ruby]] |
|||
<lang ruby>require 'lcs' |
|||
def levenshtein_align(a, b) |
|||
apos = LCS.new(a, b).backtrack |
|||
bpos = LCS.new(b, a).backtrack |
|||
c = "" |
|||
d = "" |
|||
x0 = y0 = -1 |
|||
dx = dy = 0 |
|||
apos.zip(bpos) do |x,y| |
|||
if x+dx < y+dy |
|||
n = (y+dy)-(x+dx) |
|||
dx += n |
|||
c += "-" * n |
|||
elsif x+dx > y+dy |
|||
n = (x+dx)-(y+dy) |
|||
dy += n |
|||
d += "-" * n |
|||
end |
|||
c += a[x0+1..x] |
|||
x0 = x |
|||
d += b[y0+1..y] |
|||
y0 = y |
|||
end |
|||
c += a[x0+1..-1] |
|||
d += b[y0+1..-1] |
|||
al = a.length |
|||
bl = b.length |
|||
if al+y0 < bl+x0 |
|||
c += "-" * (bl+x0-y0-al) |
|||
elsif bl+x0 < al+y0 |
|||
d += "-" * (al+y0-x0-bl) |
|||
end |
|||
[c, d] |
|||
end |
|||
puts levenshtein_align("rosettacode", "raisethysword")</lang> |
|||
{{out}} |
|||
<pre> |
|||
r-oset-taco-de |
|||
raisethysword- |
|||
</pre> |
|||
=={{header|Tcl}}== |
=={{header|Tcl}}== |