Levenshtein distance: Difference between revisions
added RPL
Not a robot (talk | contribs) (Add Refal) |
(added RPL) |
||
Line 5,625:
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" LEV
"Summer" "Winter" LEV
"Levenshtein" "Levenshtein" LEV
{{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 HP-28S (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
h 1 + 1 2 →LIST h PUT '''NEXT'''
1 b SIZE '''FOR''' j
1 j 1 + 2 →LIST j PUT '''NEXT'''
'd' STO
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
<span style="color:grey>// transfer d from stack to a variable to speed up execution</span>
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>
| |||