Levenshtein distance: Difference between revisions
→{{header|Picat}}: Split into subsections. Added {{out}}
(→{{header|Picat}}: Split into subsections. Added {{out}}) |
|||
Line 4,102:
=={{header|Picat}}==
==Iterative==
<lang Picat>levenshtein(S,T) = Dist =>▼
<lang Picat>go =>▼
S = [▼
["kitten","sitting"],▼
["rosettacode","raisethysword"],▼
["levenshtein","levenstein"], ▼
["saturday", "sunday"],▼
["stop", "tops"],▼
["saturday", "sunday"]▼
],▼
foreach([W1,W2] in S)▼
% clear the table cache ▼
initialize_table,▼
println(iter=[W1,W2,levenshtein(W1,W2)]),▼
println(recu=[W1,W2,levenshtein_rec(W1,W2)]),▼
println(mode=[W1,W2,levenshtein_mode(W1,W2)]), ▼
nl▼
end,▼
nl.▼
▲levenshtein(S,T) = Dist =>
M = 1+S.length,
N = 1+T.length,
Line 4,156 ⟶ 4,129:
end,
Dist = D[M,N].</lang>
<lang Picat>table
▲% Tabled recursive version.
levenshtein_rec(S,T) = Dist =>
Dist1 = 0,
Line 4,179 ⟶ 4,149:
Dist1 := A + 1
end,
Dist = Dist1.</lang>
===Mode-directed tabling===
{{trans|Prolog}}
<lang Picat>
levenshtein_mode(S,T) = Dist =>
lev(S, T, Dist).
Line 4,194 ⟶ 4,164:
lev(L, [_|R], D) :- lev(L, R, H), D is H+1.</lang>
===Test===
▲<lang Picat>go =>
▲ S = [
▲ ["kitten","sitting"],
▲ ["rosettacode","raisethysword"],
▲ ["levenshtein","levenstein"],
▲ ["saturday", "sunday"],
▲ ["stop", "tops"],
▲ ["saturday", "sunday"]
▲ ],
▲ foreach([W1,W2] in S)
▲ % clear the table cache
▲ initialize_table,
▲ println(iter=[W1,W2,levenshtein(W1,W2)]),
▲ println(recu=[W1,W2,levenshtein_rec(W1,W2)]),
▲ println(mode=[W1,W2,levenshtein_mode(W1,W2)]),
▲ nl
▲ end,
▲ nl.</lang>
{{out}}
<pre>goal = go
iter = [kitten,sitting,3]
Line 4,220 ⟶ 4,212:
mode = [saturday,sunday,3]</pre>
===Benchmark on larger strings===
Benchmarking the methods with larger strings of random lengths (between 1 and 2000).
<lang Picat>go2 =>
Line 4,237 ⟶ 4,231:
println(distances=[iter=L1,rec=L2,mode=L3]),
nl.
%
Line 4,247 ⟶ 4,240:
S := [Alpha[random(1,Len)] : _ in 1..random(1,MaxLen)].</lang>
Here is sample run. The
{{out}}
<pre>len_s1 = 1968
len_s2 = 1529
Line 4,260 ⟶ 4,254:
CPU time 1.402 seconds.
distances=[iter = 1607,rec = 1607,mode = 1607]</pre>
=={{header|PicoLisp}}==
| |||