Levenshtein distance/Alignment: Difference between revisions
Content added Content deleted
(→{{header|Go}}: Additional output to point out edits.) |
(→{{header|Tcl}}: Added zkl) |
||
Line 509: | Line 509: | ||
r-oset-taco-de |
r-oset-taco-de |
||
raisethysword- |
raisethysword- |
||
</pre> |
|||
=={{header|zkl}}== |
|||
{{trans|Java}} |
|||
<lang zkl>fcn alignment(a,b){ |
|||
a,b = a.toLower(), b.toLower(); |
|||
costs := (a.len()+1).pump(List(),'wrap(a){ [1..b.len()].pump(List(a)) }); |
|||
foreach i,j in (a.len()+1, [1..b.len()]){ |
|||
costs[i][j] = ( 1 + costs[i-1][j].min(costs[i][j-1]) ) |
|||
.min(if(a[i-1] == b[j-1]) costs[i-1][j-1] else costs[i-1][j-1] + 1); |
|||
} |
|||
// walk back through matrix to figure out path |
|||
aPathRev,bPathRev := Data(),Data(); // byte buckets |
|||
i,j := a.len(), b.len(); |
|||
while(i!=0 and j!= 0){ |
|||
if (costs[i][j] == |
|||
( if(a[i-1]==b[j-1]) costs[i-1][j-1] else costs[i-1][j-1]+1 )){ |
|||
aPathRev.append(a[i-=1]); |
|||
bPathRev.append(b[j-=1]); |
|||
} else if(costs[i][j] == 1+costs[i-1][j]){ |
|||
aPathRev.append(a[i-=1]); |
|||
bPathRev.append("-"); |
|||
} else if (costs[i][j] == 1+costs[i][j-1]){ |
|||
aPathRev.append("-"); |
|||
bPathRev.append(b[j-=1]); |
|||
} |
|||
} |
|||
return(aPathRev.text.reverse(), bPathRev.text.reverse()) |
|||
}</lang> |
|||
<lang zkl>result := alignment("rosettacode", "raisethysword"); |
|||
println(result[0]); |
|||
println(result[1]);</lang> |
|||
{{out}} |
|||
<pre> |
|||
r-oset-tacode |
|||
raisethysword |
|||
</pre> |
</pre> |