[Chicken-users] a levenshtein implemented in scheme

[Sunnan]

This is basically the same algorithm as the C version. It can probably
be improved further -- to use integer math, for example. But it's a
start.

Feel free to use this, or maybe you just want to change the original
to call string-ref from C?

This still doesn't work with utf-8, but it uses string-for-each-index
and string-ref, and will work with utf-8 once those are updated (if I
understood the current plans correctly).

The original returns -1 if at least one of the strings are "", I
didn't like that, but maybe it should be added anyway to keep
backwards compability.

Sunnan

(uses srfi-13 srfi-25)

(define levenshtein-distance
  (lambda (s1 s2)
    (let* ((width (add1 (string-length s1)))
           (height (add1 (string-length s2)))
           (d (do ((d (make-array (shape 0 height 0 width) 0))
                   (x 0 (add1 x)))
                  ((= x width)
                   (do ((y 0 (add1 y)))
                       ((= y height))
                     (array-set! d y 0 y))
                   d)
                (array-set! d 0 x x))))
      (string-for-each-index
       (lambda (x)
         (string-for-each-index
          (lambda (y)
            (array-set!
             d (add1 y) (add1 x)
             (min
              (add1 (array-ref d y (add1 x)))
              (add1 (array-ref d (add1 y) x))
              (+ (array-ref d y x)
                 (if (eqv? (string-ref s1 x)
                           (string-ref s2 y))
                     0
                     1)))))
          s2))
       s1)
      (array-ref d (sub1 height) (sub1 width)))))