Levenshtein distance: Difference between revisions
Add bruijn
(added RPL) |
(Add bruijn) |
||
| (2 intermediate revisions by one other user 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,658 ⟶ 5,675:
|}
"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>
Line 5,670 ⟶ 5,687:
===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
{{works with|HP|48}}
{| class="wikitable"
Line 5,680 ⟶ 5,697:
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
Line 5,697 ⟶ 5,713:
<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>
d[h, 0] := i <span style="color:grey>
for j from 1 to n:
d[0, j] := j
for j from 1 to n:
for h from 1 to m:
| |||