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 a "=> b LevenshteinDistance a b [editing operations])
end

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