[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Chicken-users] a levenshtein implemented in scheme

From: Sunnan
Subject: [Chicken-users] a levenshtein implemented in scheme
Date: Wed, 15 Dec 2004 13:44:13 +0100
User-agent: Gnus/5.1006 (Gnus v5.10.6) Emacs/21.3.50 (gnu/linux)

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

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.


(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))
                (array-set! d 0 x x))))
       (lambda (x)
          (lambda (y)
             d (add1 y) (add1 x)
              (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))
      (array-ref d (sub1 height) (sub1 width)))))

reply via email to

[Prev in Thread] Current Thread [Next in Thread]