Levenshtein distance: Difference between revisions
Content added Content deleted
(added RPL) |
m (→{{header|RPL}}: typo) |
||
| Line 5,658: | Line 5,658: | ||
|} |
|} |
||
"kitten" "sitting" LEV |
"kitten" "sitting" <span style="color:blue">LEV</span> |
||
"Summer" "Winter" LEV |
"Summer" "Winter" <span style="color:blue">LEV</span> |
||
"Levenshtein" "Levenshtein" LEV |
"Levenshtein" "Levenshtein" <span style="color:blue">LEV</span> |
||
{{out}} |
{{out}} |
||
<pre> |
<pre> |
||
| Line 5,670: | Line 5,670: | ||
===Iterative implementation (Wagner-Fischer algorithm)=== |
===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 |
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}} |
{{works with|HP|48}} |
||
{| class="wikitable" |
{| class="wikitable" |
||
| Line 5,697: | Line 5,697: | ||
<span style="color:blue">LEV2</span> ''( "a" "b" → distance )'' |
<span style="color:blue">LEV2</span> ''( "a" "b" → distance )'' |
||
declare int d[0..m, 0..n] and set each element in d to zero |
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> |
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> |
d[h, 0] := i <span style="color:grey>// RPL array indexes start with 1</span> |
||
for j from 1 to n: |
for j from 1 to n: |
||
d[0, j] := j |
d[0, j] := j |
||