Levenshtein distance: Difference between revisions
Add bruijn
imported>Lacika7 No edit summary |
(Add bruijn) |
||
| (8 intermediate revisions by 4 users not shown) | |||
Line 927:
levenshtein$(rosettacode,raisethysword)
8</pre>
=={{header|Bruijn}}==
{{trans|Haskell}}
Recursive and non-memoized method:
<syntaxhighlight lang="bruijn>
:import std/Combinator .
:import std/Char C
:import std/List .
:import std/Math .
levenshtein y [[[∅?1 ∀0 (∅?0 ∀1 (0 (1 [[[[go]]]])))]]]
go (C.eq? 3 1) (6 2 0) ++(lmin ((6 2 0) : ((6 5 0) : {}(6 2 4))))
:test ((levenshtein "rosettacode" "raisethysword") =? (+8)) ([[1]])
:test ((levenshtein "kitten" "sitting") =? (+3)) ([[1]])
</syntaxhighlight>
=={{header|C}}==
Line 5,243 ⟶ 5,260:
Levenshtein distance('saturday', 'sunday') == 3
Levenshtein distance('rosettacode', 'raisethysword') == 8</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
= <Show ('kitten') ('sitting')>
<Show ('rosettacode') ('raisethysword')>;
};
Show {
(e.A) (e.B) = <Prout e.A ' -> ' e.B ': ' <Lev (e.A) (e.B)>>;
};
Lev {
(e.A) (), <Lenw e.A>: s.L e.A = s.L;
() (e.B), <Lenw e.B>: s.L e.B = s.L;
(s.C e.A) (s.C e.B) = <Lev (e.A) (e.B)>;
(e.A) (e.B), e.A: s.HA e.LA, e.B: s.HB e.LB =
<+ 1 <Min <Lev (e.LA) (e.B)>
<Lev (e.A) (e.LB)>
<Lev (e.LA) (e.LB)>>>;
}
Min {
s.N = s.N;
s.M s.N e.X, <Compare s.M s.N>: {
'-' = <Min s.M e.X>;
s.X = <Min s.N e.X>;
};
};</syntaxhighlight>
{{out}}
<pre>kitten -> sitting: 3
rosettacode -> raisethysword: 8</pre>
=={{header|REXX}}==
Line 5,594 ⟶ 5,642:
distance(saturday, sunday) = 3
distance(rosettacode, raisethysword) = 8
</pre>
=={{header|RPL}}==
{{works with|HP|28}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪ DUP2 SIZE SWAP SIZE → a b lb la
≪ '''IF''' la lb * NOT '''THEN''' la lb +
'''ELSE'''
a 2 la SUB b 2 lb SUB DUP2 <span style="color:blue">LEV</span>
'''IF''' a 1 1 SUB b 1 1 SUB == '''THEN'''
ROT ROT DROP2
'''ELSE'''
a ROT <span style="color:blue">LEV</span> ROT b <span style="color:blue">LEV</span>
MIN MIN 1 +
'''END END'''
≫ ≫ '<span style="color:blue">LEV</span>' STO
|
<span style="color:blue">LEV</span> ''( "a" "b" → distance )''
if |a|=0 or [b|=0 then return resp. [b| or |a|
else
put tail(a), tail(b) and lev(tail(a),tail(b)) in stack
if a[1]=b[1} then
clean stack and return lev(tail(a),tail(b))
else
put lev(a,tail(b)) and lev(tail(a),b) in stack
return min of the 3 values in stack and add 1
|}
"kitten" "sitting" <span style="color:blue">LEV</span>
"Summer" "Winter" <span style="color:blue">LEV</span>
"Levenshtein" "Levenshtein" <span style="color:blue">LEV</span>
{{out}}
<pre>
3: 3
2: 4
1: 0
</pre>
===Iterative implementation (Wagner-Fischer algorithm)===
index of arrays and strings start with 1 in RPL, so the main trick in translating the algorithm given by Wikipedia was to manage the offsets properly. The distance between "rosettacode" and "raisethysword" is within the reach of a calculator (emulated or not), unlike the above recursive approach.
{{works with|HP|48}}
{| class="wikitable"
! RPL code
! Comment
|-
|
≪
DUP2 { } + + ≪ SIZE ≫ DOLIST 1 ADD 0 CON → a b d
≪ 1 a SIZE '''FOR''' h
'd' h 1 + 1 2 →LIST h PUT '''NEXT'''
1 b SIZE '''FOR''' j
'd' 1 j 1 + 2 →LIST j PUT '''NEXT'''
1 b SIZE '''FOR''' j
1 a SIZE '''FOR''' h
a h DUP SUB b j DUP SUB ≠
'd' h j 2 →LIST GET +
'd' h j 1 + 2 →LIST GET 1 +
'd' h 1 + j 2 →LIST GET 1 +
MIN MIN 'd' h 1 + j 1 + 2 →LIST ROT PUT
'''NEXT NEXT'''
'd' DUP SIZE GET
≫ ≫ '<span style="color:blue">LEV2</span>' STO
|
<span style="color:blue">LEV2</span> ''( "a" "b" → distance )''
declare int d[0..m, 0..n] and set each element in d to zero
for h from 1 to m: <span style="color:grey>// h replaces i, which is √-1 in RPL</span>
d[h, 0] := i <span style="color:grey>// RPL array indexes start with 1</span>
for j from 1 to n:
d[0, j] := j
for j from 1 to n:
for h from 1 to m:
substitutionCost := ( s[h] <> t[j] )
d[h, j] := minimum(d[h-1, j-1] + substitutionCost,
d[h-1, j] + 1,
d[h, j-1] + 1)
return d[m, n]
|}
"rosettacode" "raisethysword" <span style="color:blue">LEV2</span>
{{out}}
<pre>
1: 8
</pre>
Line 6,214 ⟶ 6,352:
}
</syntaxhighlight>
=={{header|uBasic/4tH}}==
{{trans|FreeBASIC}}
<syntaxhighlight lang="ubasic-4th">
' Uses the "iterative with two matrix rows" algorithm
' referred to in the Wikipedia article.
' create two integer arrays of distances
Dim @u(128) ' previous
Dim @v(128) ' current
Print "'kitten' to 'sitting' => ";
Print FUNC(_Levenshtein ("kitten", "sitting"))
Print "'rosettacode' to 'raisethysword' => ";
Print FUNC(_Levenshtein ("rosettacode", "raisethysword"))
Print "'sleep' to 'fleeting' => ";
Print FUNC(_Levenshtein ("sleep", "fleeting"))
End
_Levenshtein
Param (2)
Local (3)
' degenerate cases
If Comp(a@, b@) = 0 Then Return (0)
If Len(a@) = 0 Then Return (Len(b@))
If Len(b@) = 0 Then Return (Len(a@))
' initialize v0
For c@ = 0 To Len(b@)
@u(c@) = c@
Next
For c@ = 0 To Len(a@) - 1
' calculate @v() from @u()
@v(0) = c@ + 1
For d@ = 0 To Len(b@) - 1
e@ = IIf(Peek (a@, c@) = Peek (b@, d@), 0, 1)
@v(d@ + 1) = min(@v(d@) + 1, Min(@u(d@ + 1) + 1, @u(d@) + e@))
Next
' copy @v() to @u() for next iteration
For d@ = 0 To Len(b@)
@u(d@) = @v(d@)
Next
Next
Return (@v(Len(b@)))
</syntaxhighlight>
Line 6,460 ⟶ 6,651:
=={{header|Wren}}==
{{trans|Go}}
<syntaxhighlight lang="
var ls = s.count
var lt = t.count
| |||