Topic: Levenshtein Distance

[crux]

I wasn't able to find a Levensthein Distance function done in autolisp / visual lisp anywhere so I put one together.  Sharing for anyone else that looks.

Code - Auto/Visual Lisp: [Select]

1. (defun levenshtein (a b / m n d i j)
2.   (setq m (strlen a))
3.   (setq n (strlen b))
4.   (setq d (vlax-make-safearray vlax-vbInteger (cons 0 m) (cons 0 n)))
5.  
6.   (setq i 0)
7.   (while (<= i m)
8.     (vlax-safearray-put-element d i 0 i)
9.     (setq i (1+ i))
10.   )
11.  
12.   (setq j 0)
13.   (while (<= j n)
14.     (vlax-safearray-put-element d 0 j j)
15.     (setq j (1+ j))
16.   )
17.  
18.   (setq j 1)
19.   (while (<= j n)
20.     (setq i 1)
21.     (while (<= i m)
22.  
23.       (if (= (substr a i 1) (substr b j 1))
24.         (vlax-safearray-put-element d i j (vlax-safearray-get-element d (1- i) (1- j)))
25.         (progn
26.           (vlax-safearray-put-element d i j
27.             (min
28.               (1+ (vlax-safearray-get-element d (1- i) j))
29.               (1+ (vlax-safearray-get-element d i (1- j)))
30.               (1+ (vlax-safearray-get-element d (1- i) (1- j)))
31.             )
32.           )
33.         )
34.       )
35.  
36.       (setq i (1+ i))
37.     )    
38.     (setq j (1+ j))
39.   )
40.  
41.   (cond
42.     ((= n 0) m)
43.     ((= m 0) n)
44.     (T (vlax-safearray-get-element d m n))
45.   )  
46. )
47.  
48.  

Code - Auto/Visual Lisp: [Select]

1.  
2.   ;;For viewing/debugging the matrix:
3.   (mapcar 'print (vlax-safearray->list d))
4.  
5.   ;;Test cases:
6.   (list (= 6 (levenshtein "" "Sunday"))
7.       (= 8 (levenshtein "Saturday" ""))
8.       (= 3 (levenshtein "Saturday" "Sunday"))
9.       (= 3 (levenshtein "sitting" "kitten"))
10.       (= 2 (levenshtein "sitting" "kittin"))
11.       (= 8 (levenshtein "rosettacode" "raisethysword")))
12.  
13.  

[d2010]

I wasn't able to find a Levensthein Distance function done in auto Sharing for anyone else that looks.[/code]
1)First I define list of test

Code - Auto/Visual Lisp: [Select]

1.   (setq atc_readable
2.          (list
3.            (list "0" "kitten" "sitting" "=>3\n")
4.            (list "1" "stop" "tops" "=>2\n")
5.            (list "2" "mississippi" "swiss miss" "=>8\n")
6.            (list "3" "Saturday" "Sunday" "=>3\n")
7.            (list "4" "mist" "dist" "=>1\n")
8.            (list "5" "I don't drink tea in the morning."  "I don't normally drink in the morning."  "=>7\n")
9.            (list "6" "They  don't go to France for their holidays"
10.              "They don't often go to France for their holidays" "=>5\n"
11.          ))
12.  

02)I need help. Why the function "str_Levenshtein" have infinite-loop?

03)My son quite often goes to the stadium.

Code: [Select]

package main

func levenshtein(s, t string) int {
    if s == "" { return len(t) }
    if t == "" { return len(s) }
    if s[0] == t[0] {
        return levenshtein(s[1:], t[1:])
    }
    a := levenshtein(s[1:], t[1:])
    b := levenshtein(s,     t[1:])
    c := levenshtein(s[1:], t)
    if a > b { a = b }
    if a > c { a = c }
    return a + 1
}
 
func main() {
    s1 := "After lunch, they go to bed."
    s2 := "After lunch, they almost always go to bed."
    fmt.Printf("distance between %s and %s: %d\n", s1, s2,
        levenshtein(s1, s2))}