1# Copyright (C) 2006-2009, Parrot Foundation.
2#
3# Levenshtein distance
4#
5# implementation based on http://www.merriampark.com/ld.htm
6# First implementation by Alberto Simões (ambs <at> cpan.org)
7#
8
9# .sub main :main
10#         $S1 = "purl"
11#         $S2 = "perl"
12
13#         $I1 = levenshtein($S1,$S2)
14
15#         print $I1
16#         print "\n"
17#         end
18# .end
19
20# Levenshtein distance. Pass two strings in
21.sub levenshtein
22        .param string s
23        .param string t
24
25        .local int n # s size
26        .local int m # t size
27
28        .local pmc matrix
29        .local int i
30        .local int j
31
32        .local string schar
33        .local string tchar
34
35        .local int cost
36        .local int a
37        .local int b
38        .local int c
39
40        n = length s
41        m = length t
42
43        if n == 0 goto return_m
44        if m == 0 goto return_n
45
46        new matrix, 'ResizablePMCArray'
47        i = 0
48init_matrix:
49        new $P0, 'ResizableIntegerArray'
50        matrix[i] = $P0
51        i += 1
52        if i <= m goto init_matrix
53
54        i = 0
55init_matrix_1:
56        matrix[i;0] = i
57        i += 1
58        if i <= m goto init_matrix_1
59
60        i = 0
61init_matrix_2:
62        matrix[0;i] = i
63        i += 1
64        if i <= n goto init_matrix_2
65
66init_matrix_done:
67        i = 1
68
69cycle:
70        j = 1
71inner_cycle:
72        $I0 = i - 1
73        $I1 = j - 1
74        schar = substr s, $I1, 1
75        tchar = substr t, $I0, 1
76
77        cost = calculate_cost(schar, tchar)
78
79        # calculate a
80        a = matrix[$I0;j]
81        a += 1
82        # calculate b
83        b = matrix[i;$I1]
84        b += 1
85        # calculate c
86        c = matrix[$I0;$I1]
87        c += cost
88
89        cost = minimum(a,b,c)
90        matrix[i;j] = cost
91
92        j += 1
93        if j <= n goto inner_cycle
94        i += 1
95        if i <= m goto cycle
96
97        cost = matrix[m;n]
98        .return(cost)
99
100return_m:
101        .return(m)
102
103return_n:
104        .return(n)
105.end
106
107# return (first==second)?1:0
108.sub calculate_cost
109        .param string first
110        .param string second
111
112        if first == second goto zero
113        .return(1)
114zero:
115        .return(0)
116.end
117
118# return minimum(a,b,c)
119.sub minimum
120        .param int a
121        .param int b
122        .param int c
123
124        if a < b goto other
125        if b < c goto b_label
126c_label:
127        .return(c)
128a_label:
129        .return(a)
130b_label:
131        .return(b)
132other:
133        if a < c goto a_label
134        goto c_label
135
136.end
137
138# Local Variables:
139#   mode: pir
140#   fill-column: 100
141# End:
142# vim: expandtab shiftwidth=4 ft=pir:
143