aUCBLogo Demos and Tests / testlevenshtein


to testlevenshtein
    
callLD "hallo "bellepoche
    
callLD "printer "drucker
    
callLD "paper "papier
    
callLD "Hallo World "Hello Worldy
    
callLD "Andreas "Andy
 
callLD "Levenshtein "Meilenstein
end

to callLD a b
    
(print "=> b LevenshteinDistance a b [editing operations])
end

to LevenshteinDistance s t [count s][count t] ~
[(mdarray Se n+m+1 0)][0][0][cost 0]
;    http://de.wikipedia.org/wiki/Levenshtein-Distanz
;    gives the number of editing operations between two words
    
for [n] [d.i.0=i]
    
for [m] [d.(0).j=j]
    
for [n]
    
[    for [m]
        
[    ifElse s.i==t.j
            
[    cost=0
            
][    cost=1
            
]
            
d.i.j=(min
                
1+d.(i-1).j
                
1+d.i.(j-1)
                
cost+d.(i-1).(j-1)
            
)
        
]
    
]
    
op d.n.m
end