Levenshtein distance: Difference between revisions
m
→{{header|Phix}}: reworked/tidied, added alternative
(Added generic ISO C++ solution) |
m (→{{header|Phix}}: reworked/tidied, added alternative) |
||
Line 3,768:
=={{header|Phix}}==
<lang Phix>requires("0.8.2")
function levenshtein(
integer n = length(
m = length(
if
sequence d =
▲ return n-1
end if▼
sequence d = repeat(repeat(0, m), n)▼
for i=1 to n do
d[i+1][1] = i
-- next := min({ prev +substitution, deletion, or insertion }):
for j=1 to m do▼
d[i+1][j+1] = min({d[i][j
end for▼
for i=2 to n do▼
▲ d[i][j] = min({
d[i-1][j]+1,▼
end for
end for
▲ return d[n][m]
end function
Line 3,833 ⟶ 3,816:
"" <== 0 ==> ""
</pre>
=== alternative ===
(modelled after the Processing code, uses a single/smaller array, passes the same tests as above)
<lang Phix>function levenshtein(string a, b)
costs[1] = i
integer newcost = i-1, pj = i, cj
pj = min({pj+1, cj+1, newcost+(a[i]!=b[j])})
{costs[j+1],newcost} = {pj,cj}
▲ end for
return costs[$-1]
end function</lang>
=={{header|PHP}}==
|