1 /*
2 * Licensed to the Apache Software Foundation (ASF) under one or more
3 * contributor license agreements. See the NOTICE file distributed with
4 * this work for additional information regarding copyright ownership.
5 * The ASF licenses this file to You under the Apache License, Version 2.0
6 * (the "License"); you may not use this file except in compliance with
7 * the License. You may obtain a copy of the License at
8 *
9 * http://www.apache.org/licenses/LICENSE-2.0
10 *
11 * Unless required by applicable law or agreed to in writing, software
12 * distributed under the License is distributed on an "AS IS" BASIS,
13 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 * See the License for the specific language governing permissions and
15 * limitations under the License.
16 */
17 package org.apache.commons.text.similarity;
18
19 import java.util.Arrays;
20
21 /**
22 * An algorithm for measuring the difference between two character sequences.
23 *
24 * <p>
25 * This is the number of changes needed to change one sequence into another, where each change is a single character modification (deletion, insertion or
26 * substitution).
27 * </p>
28 * <p>
29 * This code has been adapted from Apache Commons Lang 3.3.
30 * </p>
31 *
32 * @since 1.0
33 */
34 public class LevenshteinDistance implements EditDistance<Integer> {
35
36 /**
37 * Singleton instance.
38 */
39 private static final LevenshteinDistance INSTANCE = new LevenshteinDistance();
40
41 /**
42 * Gets the default instance.
43 *
44 * @return The default instance
45 */
46 public static LevenshteinDistance getDefaultInstance() {
47 return INSTANCE;
48 }
49
50 /**
51 * Find the Levenshtein distance between two CharSequences if it's less than or equal to a given threshold.
52 *
53 * <p>
54 * This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield and Chas Emerick's implementation of the Levenshtein distance
55 * algorithm from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
56 * </p>
57 *
58 * <pre>
59 * limitedCompare(null, *, *) = IllegalArgumentException
60 * limitedCompare(*, null, *) = IllegalArgumentException
61 * limitedCompare(*, *, -1) = IllegalArgumentException
62 * limitedCompare("","", 0) = 0
63 * limitedCompare("aaapppp", "", 8) = 7
64 * limitedCompare("aaapppp", "", 7) = 7
65 * limitedCompare("aaapppp", "", 6)) = -1
66 * limitedCompare("elephant", "hippo", 7) = 7
67 * limitedCompare("elephant", "hippo", 6) = -1
68 * limitedCompare("hippo", "elephant", 7) = 7
69 * limitedCompare("hippo", "elephant", 6) = -1
70 * </pre>
71 *
72 * @param left the first SimilarityInput, must not be null
73 * @param right the second SimilarityInput, must not be null
74 * @param threshold the target threshold, must not be negative
75 * @return result distance, or -1
76 */
77 private static <E> int limitedCompare(SimilarityInput<E> left, SimilarityInput<E> right, final int threshold) { // NOPMD
78 if (left == null || right == null) {
79 throw new IllegalArgumentException("CharSequences must not be null");
80 }
81 if (threshold < 0) {
82 throw new IllegalArgumentException("Threshold must not be negative");
83 }
84
85 /*
86 * This implementation only computes the distance if it's less than or equal to the threshold value, returning -1 if it's greater. The advantage is
87 * performance: unbounded distance is O(nm), but a bound of k allows us to reduce it to O(km) time by only computing a diagonal stripe of width 2k + 1
88 * of the cost table. It is also possible to use this to compute the unbounded Levenshtein distance by starting the threshold at 1 and doubling each
89 * time until the distance is found; this is O(dm), where d is the distance.
90 *
91 * One subtlety comes from needing to ignore entries on the border of our stripe eg. p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry to the left
92 * of the leftmost member We must ignore the entry above the rightmost member
93 *
94 * Another subtlety comes from our stripe running off the matrix if the strings aren't of the same size. Since string s is always swapped to be the
95 * shorter of the two, the stripe will always run off to the upper right instead of the lower left of the matrix.
96 *
97 * As a concrete example, suppose s is of length 5, t is of length 7, and our threshold is 1. In this case we're going to walk a stripe of length 3. The
98 * matrix would look like so:
99 *
100 * <pre> 1 2 3 4 5 1 |#|#| | | | 2 |#|#|#| | | 3 | |#|#|#| | 4 | | |#|#|#| 5 | | | |#|#| 6 | | | | |#| 7 | | | | | | </pre>
101 *
102 * Note how the stripe leads off the table as there is no possible way to turn a string of length 5 into one of length 7 in edit distance of 1.
103 *
104 * Additionally, this implementation decreases memory usage by using two single-dimensional arrays and swapping them back and forth instead of
105 * allocating an entire n by m matrix. This requires a few minor changes, such as immediately returning when it's detected that the stripe has run off
106 * the matrix and initially filling the arrays with large values so that entries we don't compute are ignored.
107 *
108 * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for some discussion.
109 */
110
111 int n = left.length(); // length of left
112 int m = right.length(); // length of right
113
114 // if one string is empty, the edit distance is necessarily the length
115 // of the other
116 if (n == 0) {
117 return m <= threshold ? m : -1;
118 }
119 if (m == 0) {
120 return n <= threshold ? n : -1;
121 }
122
123 if (n > m) {
124 // swap the two strings to consume less memory
125 final SimilarityInput<E> tmp = left;
126 left = right;
127 right = tmp;
128 n = m;
129 m = right.length();
130 }
131
132 // the edit distance cannot be less than the length difference
133 if (m - n > threshold) {
134 return -1;
135 }
136
137 int[] p = new int[n + 1]; // 'previous' cost array, horizontally
138 int[] d = new int[n + 1]; // cost array, horizontally
139 int[] tempD; // placeholder to assist in swapping p and d
140
141 // fill in starting table values
142 final int boundary = Math.min(n, threshold) + 1;
143 for (int i = 0; i < boundary; i++) {
144 p[i] = i;
145 }
146 // these fills ensure that the value above the rightmost entry of our
147 // stripe will be ignored in following loop iterations
148 Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
149 Arrays.fill(d, Integer.MAX_VALUE);
150
151 // iterates through t
152 for (int j = 1; j <= m; j++) {
153 final E rightJ = right.at(j - 1); // jth character of right
154 d[0] = j;
155
156 // compute stripe indices, constrain to array size
157 final int min = Math.max(1, j - threshold);
158 final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(n, j + threshold);
159
160 // ignore entry left of leftmost
161 if (min > 1) {
162 d[min - 1] = Integer.MAX_VALUE;
163 }
164
165 int lowerBound = Integer.MAX_VALUE;
166 // iterates through [min, max] in s
167 for (int i = min; i <= max; i++) {
168 if (left.at(i - 1).equals(rightJ)) {
169 // diagonally left and up
170 d[i] = p[i - 1];
171 } else {
172 // 1 + minimum of cell to the left, to the top, diagonally
173 // left and up
174 d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
175 }
176 lowerBound = Math.min(lowerBound, d[i]);
177 }
178 // if the lower bound is greater than the threshold, then exit early
179 if (lowerBound > threshold) {
180 return -1;
181 }
182
183 // copy current distance counts to 'previous row' distance counts
184 tempD = p;
185 p = d;
186 d = tempD;
187 }
188
189 // if p[n] is greater than the threshold, there's no guarantee on it
190 // being the correct
191 // distance
192 if (p[n] <= threshold) {
193 return p[n];
194 }
195 return -1;
196 }
197
198 /**
199 * Finds the Levenshtein distance between two Strings.
200 *
201 * <p>
202 * A higher score indicates a greater distance.
203 * </p>
204 *
205 * <p>
206 * The previous implementation of the Levenshtein distance algorithm was from
207 * <a href="https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm">
208 * https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm</a>
209 * </p>
210 *
211 * <p>
212 * This implementation only need one single-dimensional arrays of length s.length() + 1
213 * </p>
214 *
215 * <pre>
216 * unlimitedCompare(null, *) = IllegalArgumentException
217 * unlimitedCompare(*, null) = IllegalArgumentException
218 * unlimitedCompare("","") = 0
219 * unlimitedCompare("","a") = 1
220 * unlimitedCompare("aaapppp", "") = 7
221 * unlimitedCompare("frog", "fog") = 1
222 * unlimitedCompare("fly", "ant") = 3
223 * unlimitedCompare("elephant", "hippo") = 7
224 * unlimitedCompare("hippo", "elephant") = 7
225 * unlimitedCompare("hippo", "zzzzzzzz") = 8
226 * unlimitedCompare("hello", "hallo") = 1
227 * </pre>
228 *
229 * @param left the first CharSequence, must not be null
230 * @param right the second CharSequence, must not be null
231 * @return result distance, or -1
232 * @throws IllegalArgumentException if either CharSequence input is {@code null}
233 */
234 private static <E> int unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right) {
235 if (left == null || right == null) {
236 throw new IllegalArgumentException("CharSequences must not be null");
237 }
238 /*
239 * This implementation use two variable to record the previous cost counts, So this implementation use less memory than previous impl.
240 */
241 int n = left.length(); // length of left
242 int m = right.length(); // length of right
243
244 if (n == 0) {
245 return m;
246 }
247 if (m == 0) {
248 return n;
249 }
250 if (n > m) {
251 // swap the input strings to consume less memory
252 final SimilarityInput<E> tmp = left;
253 left = right;
254 right = tmp;
255 n = m;
256 m = right.length();
257 }
258 final int[] p = new int[n + 1];
259 // indexes into strings left and right
260 int i; // iterates through left
261 int j; // iterates through right
262 int upperLeft;
263 int upper;
264 E rightJ; // jth character of right
265 int cost; // cost
266 for (i = 0; i <= n; i++) {
267 p[i] = i;
268 }
269 for (j = 1; j <= m; j++) {
270 upperLeft = p[0];
271 rightJ = right.at(j - 1);
272 p[0] = j;
273
274 for (i = 1; i <= n; i++) {
275 upper = p[i];
276 cost = left.at(i - 1).equals(rightJ) ? 0 : 1;
277 // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
278 p[i] = Math.min(Math.min(p[i - 1] + 1, p[i] + 1), upperLeft + cost);
279 upperLeft = upper;
280 }
281 }
282 return p[n];
283 }
284
285 /**
286 * Threshold.
287 */
288 private final Integer threshold;
289
290 /**
291 * This returns the default instance that uses a version of the algorithm that does not use a threshold parameter.
292 *
293 * @see LevenshteinDistance#getDefaultInstance()
294 * @deprecated Use {@link #getDefaultInstance()}.
295 */
296 @Deprecated
297 public LevenshteinDistance() {
298 this(null);
299 }
300
301 /**
302 * If the threshold is not null, distance calculations will be limited to a maximum length. If the threshold is null, the unlimited version of the algorithm
303 * will be used.
304 *
305 * @param threshold If this is null then distances calculations will not be limited. This may not be negative.
306 */
307 public LevenshteinDistance(final Integer threshold) {
308 if (threshold != null && threshold < 0) {
309 throw new IllegalArgumentException("Threshold must not be negative");
310 }
311 this.threshold = threshold;
312 }
313
314 /**
315 * Computes the Levenshtein distance between two Strings.
316 *
317 * <p>
318 * A higher score indicates a greater distance.
319 * </p>
320 *
321 * <p>
322 * The previous implementation of the Levenshtein distance algorithm was from
323 * <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
324 * </p>
325 *
326 * <p>
327 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
328 * strings.<br>
329 * This implementation of the Levenshtein distance algorithm is from
330 * <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
331 * </p>
332 *
333 * <pre>
334 * distance.apply(null, *) = IllegalArgumentException
335 * distance.apply(*, null) = IllegalArgumentException
336 * distance.apply("","") = 0
337 * distance.apply("","a") = 1
338 * distance.apply("aaapppp", "") = 7
339 * distance.apply("frog", "fog") = 1
340 * distance.apply("fly", "ant") = 3
341 * distance.apply("elephant", "hippo") = 7
342 * distance.apply("hippo", "elephant") = 7
343 * distance.apply("hippo", "zzzzzzzz") = 8
344 * distance.apply("hello", "hallo") = 1
345 * </pre>
346 *
347 * @param left the first input, must not be null
348 * @param right the second input, must not be null
349 * @return result distance, or -1
350 * @throws IllegalArgumentException if either String input {@code null}
351 */
352 @Override
353 public Integer apply(final CharSequence left, final CharSequence right) {
354 return apply(SimilarityInput.input(left), SimilarityInput.input(right));
355 }
356
357 /**
358 * Computes the Levenshtein distance between two inputs.
359 *
360 * <p>
361 * A higher score indicates a greater distance.
362 * </p>
363 *
364 * <pre>
365 * distance.apply(null, *) = IllegalArgumentException
366 * distance.apply(*, null) = IllegalArgumentException
367 * distance.apply("","") = 0
368 * distance.apply("","a") = 1
369 * distance.apply("aaapppp", "") = 7
370 * distance.apply("frog", "fog") = 1
371 * distance.apply("fly", "ant") = 3
372 * distance.apply("elephant", "hippo") = 7
373 * distance.apply("hippo", "elephant") = 7
374 * distance.apply("hippo", "zzzzzzzz") = 8
375 * distance.apply("hello", "hallo") = 1
376 * </pre>
377 *
378 * @param <E> The type of similarity score unit.
379 * @param left the first input, must not be null.
380 * @param right the second input, must not be null.
381 * @return result distance, or -1.
382 * @throws IllegalArgumentException if either String input {@code null}.
383 * @since 1.13.0
384 */
385 public <E> Integer apply(final SimilarityInput<E> left, final SimilarityInput<E> right) {
386 if (threshold != null) {
387 return limitedCompare(left, right, threshold);
388 }
389 return unlimitedCompare(left, right);
390 }
391
392 /**
393 * Gets the distance threshold.
394 *
395 * @return The distance threshold
396 */
397 public Integer getThreshold() {
398 return threshold;
399 }
400
401 }