Levenshtein distance/Alignment: Difference between revisions
Content added Content deleted
(Scala contribution added.) |
|||
Line 456: | Line 456: | ||
<pre>ro-settac-o-de |
<pre>ro-settac-o-de |
||
raisethysword-</pre> |
raisethysword-</pre> |
||
=={{header|Phix}}== |
|||
{{trans|Kotlin}} plus the indicator from Go |
|||
<lang Phix>function LevenshteinAlignment(string a, b) |
|||
integer la = length(a)+1, |
|||
lb = length(b)+1 |
|||
sequence costs = repeat(repeat(0,lb),la) |
|||
for j=1 to lb do |
|||
costs[1][j] = j |
|||
end for |
|||
for i=2 to la do |
|||
costs[i][1] = i |
|||
for j=2 to lb do |
|||
integer tmp1 = 1+min(costs[i-1][j], costs[i][j-1]), |
|||
tmp2 = costs[i-1][j-1] + (a[i-1]!=b[j-1]) |
|||
costs[i][j] = min(tmp1, tmp2) |
|||
end for |
|||
end for |
|||
-- walk back through matrix to figure out the path |
|||
string arev = "", |
|||
brev = "" |
|||
integer i = la, j = lb |
|||
while i>1 and j>1 do |
|||
integer tmp = costs[i-1][j-1] + (a[i-1]!=b[j-1]) |
|||
switch costs[i][j] do |
|||
case tmp: i -= 1; arev &= a[i] |
|||
j -= 1; brev &= b[j] |
|||
case 1 + costs[i-1][j]: i -= 1; arev &= a[i] |
|||
brev &= '-' |
|||
case 1 + costs[i][j-1]: arev &= '-' |
|||
j -= 1; brev &= b[j] |
|||
end switch |
|||
end while |
|||
return {reverse(arev),reverse(brev)} |
|||
end function |
|||
procedure test(string a,b) |
|||
{a,b} = LevenshteinAlignment(a,b) |
|||
string c = sq_add(repeat(' ',length(a)),sq_mul(sq_ne(a,b),'|'-' ')) |
|||
printf(1,"%s\n%s\n%s\n\n",{a,b,c}) |
|||
end procedure |
|||
test("rosettacode", "raisethysword") |
|||
test("place", "palace")</lang> |
|||
{{out}} |
|||
<pre> |
|||
r-oset-tacode |
|||
raisethysword |
|||
|| |||| || |
|||
p-lace |
|||
palace |
|||
| |
|||
</pre> |
|||
=={{header|Racket}}== |
=={{header|Racket}}== |