Levenshtein distance/Alignment: Difference between revisions
→{{header|Phix}}
(Scala contribution added.) |
|||
Line 456:
<pre>ro-settac-o-de
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}}==
| |||