Levenshtein distance: Difference between revisions
Content added Content deleted
(add Ada) |
No edit summary |
||
Line 252: | Line 252: | ||
Output: |
Output: |
||
<pre>3</pre> |
<pre>3</pre> |
||
=={{header|Icon}} and {{header|Unicon}}== |
|||
<lang unicon>procedure main() |
|||
every process(!&input) |
|||
end |
|||
procedure process(s) |
|||
s ? { |
|||
s1 := tab(upto(' \t')) | fail |
|||
s2 := (tab(many(' \t')), tab(0)) |
|||
write("'",s1,"' -> '",s2,"' = ", levenshtein(s1,s2)) |
|||
} |
|||
end |
|||
procedure levenshtein(s, t) |
|||
if *s = 0 then return *t |
|||
if *t = 0 then return *s |
|||
n := *s+1 |
|||
m := *t+1 |
|||
every !(d := list(n,0)) := list(m, 0) |
|||
every i := 1 to max(n,m) do d[i,1] := d[1,i] := i |
|||
every d[1(i := 2 to n, s_i := s[iM1 := i-1]), j := 2 to m] := |
|||
min(d[iM1,j], d[i,jM1:=j-1], |
|||
d[iM1,jM1] + if s_i == t[jM1] then -1 else 0) + 1 |
|||
return d[n,m]-1 |
|||
end</lang> |
|||
<pre> |
|||
->leven |
|||
kitten sitting |
|||
'kitten' -> 'sitting' = 3 |
|||
-> |
|||
</pre> |
|||
=={{header|J}}== |
=={{header|J}}== |