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