Debian Codegraph @

lib/util/levenshtein.scm

raw
1 ;;;
2 ;;; util.levenshtein - Calculate edit distance between two sequences
3 ;;;
4 ;;; Copyright (c) 2016-2024 Shiro Kawai <[email protected]>
5 ;;;
6 ;;; Redistribution and use in source and binary forms, with or without
7 ;;; modification, are permitted provided that the following conditions
8 ;;; are met:
9 ;;;
10 ;;; 1. Redistributions of source code must retain the above copyright
11 ;;; notice, this list of conditions and the following disclaimer.
12 ;;;
13 ;;; 2. Redistributions in binary form must reproduce the above copyright
14 ;;; notice, this list of conditions and the following disclaimer in the
15 ;;; documentation and/or other materials provided with the distribution.
16 ;;;
17 ;;; 3. Neither the name of the authors nor the names of its contributors
18 ;;; may be used to endorse or promote products derived from this
19 ;;; software without specific prior written permission.
20 ;;;
21 ;;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 ;;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 ;;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 ;;; A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 ;;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 ;;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
27 ;;; TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
28 ;;; PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
29 ;;; LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
30 ;;; NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
31 ;;; SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 ;;;
33
34 (define-module util.levenshtein
35 (use scheme.list)
36 (use scheme.vector)
37 (use gauche.array)
38 (use gauche.sequence)
39 (export l-distance l-distances
40 re-distance re-distances
41 dl-distance dl-distances))
42 (select-module util.levenshtein)
43
44 ;; Procedures to calculate Levenshtein, Damerau-Levenshtein, and
45 ;; Restricted edit distances of two sequences
46 ;; (not limited to strings).
47
48 ;; Note:
49 ;; Those widely known algorithms were extensively researched in 60s
50 ;; to 70s, and sometimes different researchers reported same or similar
51 ;; algorithms without attaching specific name. We took widely known
52 ;; names but the source we found didn't have that names.
53 ;;
54 ;; Levenshtein distance: Wagner & Fischer, The String-to-string correction
55 ;; problem, JACM 21(1), 1974, shows DP algorithm to calculate this, but
56 ;; there's no mention of "Levenshtein" in the paper.
57 ;;
58 ;; Damerau-Levenshtein-distance: Lowrance & Wagner, An extension of
59 ;; the string-to-string correction problem, JACM 22(2), 1975. Again,
60 ;; there's no mention of "Damerau" nor "Levenshtein".
61 ;;
62 ;; Restricted edit distance: Oommen & Loke, Pattern
63 ;; recognition of strings with substitutions, insertions, deletions
64 ;; and generalized transpositions, Pattern Recognition 30(5), 1997.
65 ;; This one is mentioned as Optimal string alignment distance in
66 ;; Wikipedia. The paper doesn't give itself a name, but claims it's
67 ;; "less restrictive" than Lowrance & Wagner since it removes the cost
68 ;; restriction that Lowrance & Wagner requires to work. On the other
69 ;; hand, this one restricts how transposition is applied and is not
70 ;; fully compatible to Damerau-Levenshtein.
71
72 ;; It is often explained using (N+k)x(M+k) array for dynamic programming
73 ;; (k=1 or 2), but we only need to refer to look back at most k rows,
74 ;; so we can run the algorithm with k+1 rows and rotating them.
75 ;;
76 ;; s e q u e n c e - A
77 ;; . . . . . . . . . . . .
78 ;; . . . . . . . . . . . .
79 ;; s . . . . . . . . . . . .
80 ;; e . . . . . . . . . . . .
81 ;; q . . . . . . . . . . . . "active" rows
82 ;; u . . . . . . . . . . . . < row-2
83 ;; e . . . . . . . . . . . . < row-1
84 ;; n . . . . . . . . X . . . < row-0 X @ (i,j)
85 ;; c . . . . . . . . . . . .
86 ;; e . . . . . . . . . . . .
87 ;; | . . . . . . . . . . . .
88 ;; B . . . . . . . . . . . .
89 ;;
90 ;;
91 ;; Three algorithms only differ slightly in details and it's tempting to
92 ;; factor the common part out. However such arrangement introduces overhead
93 ;; and the resulting code isn't that clean. So we decided to implement
94 ;; each separately, allowing some redundancy among their code.
95 ;;
96 ;; NB: Usually, the algorithm is described as sequences with 1-base index,
97 ;; and array index start from 0 or -1 up to the length of the sequence.
98 ;; We use 0-base vector, so the row index is offset by 1 or 2.
99 ;;
100 ;; The base implementation of every algorithm has the following signature:
101 ;;
102 ;; (base A Bs elt= cutoff)
103 ;;
104 ;; This calculates distance between sequence A and each sequence in the
105 ;; list of sequence Bs, and returns the list of distances.
106 ;; elt= is used to compare elements in the sequence. cutoff can be #f
107 ;; or a positive integer, and if it's positive integer, we stop calculating
108 ;; the distance of a particular pair as soon as the minimum distance
109 ;; exceeds the value; the distance for that pair becomes #f.
110
111 ;; Basic Levenshtein
112 (define (l-base A Bs elt= cutoff)
113 (let* ([alen (size-of A)]
114 [A (if (length>=? Bs 3)
115 (coerce-to <list> A)
116 A)]
117 [rows (circular-list (make-vector (+ alen 1))
118 (make-vector (+ alen 1)))])
119 (define (run B check)
120 (vector-unfold! identity (cadr rows) 0 (+ alen 1))
121 (for-each-with-index
122 (^[j b]
123 (let ([row-0 (car rows)]
124 [row-1 (cadr rows)]
125 [dmin (+ j 1)])
126 (vector-set! row-0 0 (+ j 1))
127 (for-each-with-index
128 (^[i a]
129 (let1 d (min (+ (vector-ref row-0 i) 1)
130 (+ (vector-ref row-1 (+ i 1)) 1)
131 (+ (vector-ref row-1 i) (if (elt= a b) 0 1)))
132 (vector-set! row-0 (+ i 1) d)
133 (when (< d dmin) (set! dmin d))))
134 A)
135 (when check (check dmin)))
136 (pop! rows))
137 B)
138 (rlet1 r (vector-ref (cadr rows) alen)
139 (when check (check r))))
140
141 (define f
142 (if cutoff
143 (^[B] (let/cc break
144 (run B (^d (if (< cutoff d) (break #f))))))
145 (cut run <> #f)))
146
147 (map f Bs)))
148
149 (define (l-distance A B :key (elt= eqv?) (cutoff #f))
150 (car (l-base A (list B) elt= cutoff)))
151
152 (define (l-distances A Bs :key (elt= eqv?) (cutoff #f))
153 (l-base A Bs elt= cutoff))
154
155 ;; Restricted Edit distance
156 ;;
157 ;; This one treats transposition as one operation, but does not allow
158 ;; editing a transposed pair afterwards.
159 ;;
160 ;; We need two columns/rows for the boundary, so when we're looking
161 ;; at A[i] and B[j], the matrix cell is (i+2, j+2) and we look at
162 ;; (i+1, j+2) - deletion
163 ;; (i+2, j+1) - insertion
164 ;; (i+1, j+1) - same or substitution
165 ;; (i, j) - transposition
166 ;; and j+2 = row-0, j+1 = row-1, j = row-2.
167
168 (define (re-base A Bs elt= cutoff)
169 (let* ([alen (size-of A)]
170 [A (if (length>=? Bs 3)
171 (coerce-to <vector> A)
172 A)]
173 [aref (cute (referencer A) A <>)]
174 [rows (circular-list (make-vector (+ alen 2))
175 (make-vector (+ alen 2))
176 (make-vector (+ alen 2)))])
177 (define (run B check)
178 (define blen (size-of B))
179 (define bref (cute (referencer B) B <>))
180 (define dmin-1 0)
181 (vector-fill! (caddr rows) (+ alen blen))
182 (vector-unfold! (^i (if (zero? i) (+ alen blen) (- i 1)))
183 (cadr rows) 0 (+ alen 2))
184 (for-each-with-index
185 (^[j b]
186 (let ([row-0 (car rows)]
187 [row-1 (cadr rows)]
188 [dmin-0 (+ j 1)])
189 (vector-set! row-0 0 (+ alen blen))
190 (vector-set! row-0 1 (+ j 1))
191 (for-each-with-index
192 (^[i a]
193 (let* ([d (min (+ (vector-ref row-0 (+ i 1)) 1)
194 (+ (vector-ref row-1 (+ i 2)) 1)
195 (+ (vector-ref row-1 (+ i 1)) (if (elt= a b) 0 1)))]
196 [d (if (and (> i 1) (> j 1)
197 (elt= (aref i) (bref (- j 1)))
198 (elt= (aref (- i 1)) (bref j)))
199 (min d (+ (vector-ref (caddr rows) i)
200 (if (elt= a b) 0 1)))
201 d)])
202 (when (< d dmin-0) (set! dmin-0 d))
203 (vector-set! row-0 (+ i 2) d)))
204 A)
205 (when check (check (min dmin-0 dmin-1)))
206 (set! dmin-1 dmin-0))
207 (pop! rows)
208 (pop! rows))
209 B)
210 (rlet1 r (vector-ref (cadr rows) (+ alen 1))
211 (when check (check r))))
212
213 (define f
214 (if cutoff
215 (^[B] (let/cc break
216 (run B (^d (if (< cutoff d) (break #f))))))
217 (cut run <> #f)))
218
219 (map f Bs)))
220
221 (define (re-distance A B :key (elt= eqv?) (cutoff #f))
222 (car (re-base A (list B) elt= cutoff)))
223
224 (define (re-distances A Bs :key (elt= eqv?) (cutoff #f))
225 (re-base A Bs elt= cutoff))
226
227 ;; Damerau-Levenshtein distance
228 ;; We need a way to look up the last character position seen in A.
229 ;; Typical DL algorithm uses an array indexed by character code, but
230 ;; that does not work with large character set or general objects.
231 ;; For the time being, we use an assoc list. It needs O(length(A))
232 ;; to look up, but in general length(A) is small and the constant
233 ;; factor is very small for alist (we could go with tree map, for
234 ;; example, if an element comparator is provided, but the constant factor
235 ;; of it could surpass the log order benefit if length(A) is small.)
236
237 (define (dl-base A Bs elt= cutoff)
238 (let* ([alen (size-of A)]
239 [A (if (length>=? Bs 3)
240 (coerce-to <list> A)
241 A)]
242 [rows (let* ([maxb (apply max (map size-of Bs))]
243 [rows (vector-tabulate (+ maxb 2)
244 (^_ (make-vector (+ alen 2))))])
245 ;; The second row is (almost) constant
246 (vector-unfold! (^i (- i 1)) (vector-ref rows 1) 0 (+ alen 2))
247 rows)])
248
249 (define (run B)
250 (define DA '()) ; alist to map element -> index in A (0-base)
251 (define blen (size-of B))
252 (vector-unfold! (^_ (+ alen blen)) (vector-ref rows 0) 0 (+ alen 2))
253 (vector-for-each-with-index (^[j v]
254 (unless (= j 0)
255 (vector-set! v 0 (+ alen blen))
256 (vector-set! v 1 (- j 1))))
257 rows)
258 (let-syntax
259 ([D (syntax-rules ()
260 [(_ i j) (vector-ref (vector-ref rows j) i)]
261 [(_ i j v) (vector-set! (vector-ref rows j) i v)])])
262 (for-each-with-index
263 (^[i a]
264 (define DB -1) ; the last j such that A[i] == B[j] (0-base)
265 (for-each-with-index
266 (^[j b]
267 (let* ([k (assoc-ref DA b -1 elt=)]
268 [l DB]
269 [cost (if (elt= a b)
270 (begin (set! DB j) 0)
271 1)]
272 [d (min (+ (D (+ i 2) (+ j 1)) 1)
273 (+ (D (+ i 1) (+ j 2)) 1)
274 (+ (D (+ i 1) (+ j 1)) cost)
275 (+ (D (+ k 1) (+ l 1))
276 (- i k)
277 (- j l 1)))])
278 (D (+ i 2) (+ j 2) d)))
279 B)
280 (push! DA (cons a i)))
281 A)
282 (D (+ alen 1) (+ blen 1))))
283
284 ;; Because of transposition propagation, early cutoff isn't trivial.
285 ;; for now, we just run the entire algorithm then check the result.
286 (define f
287 (if cutoff
288 (^[B] (let1 r (run B)
289 (and (<= r cutoff) r)))
290 run))
291
292 (map f Bs)))
293
294 (define (dl-distance A B :key (elt= eqv?) (cutoff #f))
295 (car (dl-base A (list B) elt= cutoff)))
296
297 (define (dl-distances A Bs :key (elt= eqv?) (cutoff #f))
298 (dl-base A Bs elt= cutoff))