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 * https://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
18 package org.apache.commons.text.similarity;
19
20 import java.util.Arrays;
21
22 /**
23 * An algorithm for measuring the difference between two character sequences.
24 *
25 * <p>
26 * This is the number of changes needed to change one sequence into another, where each change is a single character modification (deletion, insertion or
27 * substitution).
28 * </p>
29 *
30 * @since 1.0
31 */
32 public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResults> {
33
34 /**
35 * The singleton instance.
36 */
37 private static final LevenshteinDetailedDistance INSTANCE = new LevenshteinDetailedDistance();
38
39 /**
40 * Finds count for each of the three [insert, delete, substitute] operations needed. This is based on the matrix formed based on the two character sequence.
41 *
42 * @param <E> The type of similarity score unit.
43 * @param left character sequence which need to be converted from.
44 * @param right character sequence which need to be converted to.
45 * @param matrix two dimensional array containing.
46 * @param swapped tells whether the value for left character sequence and right character sequence were swapped to save memory.
47 * @return result object containing the count of insert, delete and substitute and total count needed.
48 */
49 private static <E> LevenshteinResults findDetailedResults(final SimilarityInput<E> left, final SimilarityInput<E> right, final int[][] matrix,
50 final boolean swapped) {
51 int delCount = 0;
52 int addCount = 0;
53 int subCount = 0;
54 int rowIndex = right.length();
55 int columnIndex = left.length();
56 int dataAtLeft = 0;
57 int dataAtTop = 0;
58 int dataAtDiagonal = 0;
59 int data = 0;
60 boolean deleted = false;
61 boolean added = false;
62 while (rowIndex >= 0 && columnIndex >= 0) {
63 if (columnIndex == 0) {
64 dataAtLeft = -1;
65 } else {
66 dataAtLeft = matrix[rowIndex][columnIndex - 1];
67 }
68 if (rowIndex == 0) {
69 dataAtTop = -1;
70 } else {
71 dataAtTop = matrix[rowIndex - 1][columnIndex];
72 }
73 if (rowIndex > 0 && columnIndex > 0) {
74 dataAtDiagonal = matrix[rowIndex - 1][columnIndex - 1];
75 } else {
76 dataAtDiagonal = -1;
77 }
78 if (dataAtLeft == -1 && dataAtTop == -1 && dataAtDiagonal == -1) {
79 break;
80 }
81 data = matrix[rowIndex][columnIndex];
82 // case in which the character at left and right are the same,
83 // in this case none of the counters will be incremented.
84 if (columnIndex > 0 && rowIndex > 0 && left.at(columnIndex - 1).equals(right.at(rowIndex - 1))) {
85 columnIndex--;
86 rowIndex--;
87 continue;
88 }
89 // handling insert and delete cases.
90 deleted = false;
91 added = false;
92 if (data - 1 == dataAtLeft && data <= dataAtDiagonal && data <= dataAtTop || dataAtDiagonal == -1 && dataAtTop == -1) { // NOPMD
93 columnIndex--;
94 if (swapped) {
95 addCount++;
96 added = true;
97 } else {
98 delCount++;
99 deleted = true;
100 }
101 } else if (data - 1 == dataAtTop && data <= dataAtDiagonal && data <= dataAtLeft || dataAtDiagonal == -1 && dataAtLeft == -1) { // NOPMD
102 rowIndex--;
103 if (swapped) {
104 delCount++;
105 deleted = true;
106 } else {
107 addCount++;
108 added = true;
109 }
110 }
111 // substituted case
112 if (!added && !deleted) {
113 subCount++;
114 columnIndex--;
115 rowIndex--;
116 }
117 }
118 return new LevenshteinResults(addCount + delCount + subCount, addCount, delCount, subCount);
119 }
120
121 /**
122 * Gets the default instance.
123 *
124 * @return The default instace
125 */
126 public static LevenshteinDetailedDistance getDefaultInstance() {
127 return INSTANCE;
128 }
129
130 /**
131 * Finds the Levenshtein distance between two CharSequences if it's less than or equal to a given threshold.
132 *
133 * <p>
134 * This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield and Chas Emerick's implementation of the Levenshtein distance
135 * algorithm from <a href="https://www.merriampark.com/ld.htm" >http://www.merriampark.com/ld.htm</a>
136 * </p>
137 *
138 * <pre>
139 * limitedCompare(null, *, *) = Throws {@link IllegalArgumentException}
140 * limitedCompare(*, null, *) = Throws {@link IllegalArgumentException}
141 * limitedCompare(*, *, -1) = Throws {@link IllegalArgumentException}
142 * limitedCompare("","", 0) = 0
143 * limitedCompare("aaapppp", "", 8) = 7
144 * limitedCompare("aaapppp", "", 7) = 7
145 * limitedCompare("aaapppp", "", 6)) = -1
146 * limitedCompare("elephant", "hippo", 7) = 7
147 * limitedCompare("elephant", "hippo", 6) = -1
148 * limitedCompare("hippo", "elephant", 7) = 7
149 * limitedCompare("hippo", "elephant", 6) = -1
150 * </pre>
151 *
152 * @param <E> The type of similarity score unit.
153 * @param left the first CharSequence, must not be null.
154 * @param right the second CharSequence, must not be null.
155 * @param threshold the target threshold, must not be negative.
156 * @return result distance, or -1.
157 */
158 private static <E> LevenshteinResults limitedCompare(SimilarityInput<E> left, SimilarityInput<E> right, final int threshold) { // NOPMD
159 if (left == null || right == null) {
160 throw new IllegalArgumentException("CharSequences must not be null");
161 }
162
163 /*
164 * 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
165 * 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
166 * 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
167 * time until the distance is found; this is O(dm), where d is the distance.
168 *
169 * One subtlety comes from needing to ignore entries on the border of our stripe, for example,
170 * p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry to the left
171 * of the leftmost member We must ignore the entry above the rightmost member
172 *
173 * 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
174 * shorter of the two, the stripe will always run off to the upper right instead of the lower left of the matrix.
175 *
176 * 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
177 * matrix would look like so:
178 *
179 * <pre> 1 2 3 4 5 1 |#|#| | | | 2 |#|#|#| | | 3 | |#|#|#| | 4 | | |#|#|#| 5 | | | |#|#| 6 | | | | |#| 7 | | | | | | </pre>
180 *
181 * 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.
182 *
183 * Additionally, this implementation decreases memory usage by using two single-dimensional arrays and swapping them back and forth instead of
184 * 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
185 * the matrix and initially filling the arrays with large values so that entries we don't compute are ignored.
186 *
187 * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for some discussion.
188 */
189 int n = left.length(); // length of left
190 int m = right.length(); // length of right
191 // if one string is empty, the edit distance is necessarily the length of the other
192 if (n == 0) {
193 return m <= threshold ? new LevenshteinResults(m, m, 0, 0) : new LevenshteinResults(-1, 0, 0, 0);
194 }
195 if (m == 0) {
196 return n <= threshold ? new LevenshteinResults(n, 0, n, 0) : new LevenshteinResults(-1, 0, 0, 0);
197 }
198 boolean swapped = false;
199 if (n > m) {
200 // swap the two strings to consume less memory
201 final SimilarityInput<E> tmp = left;
202 left = right;
203 right = tmp;
204 n = m;
205 m = right.length();
206 swapped = true;
207 }
208 int[] p = new int[n + 1]; // 'previous' cost array, horizontally
209 int[] d = new int[n + 1]; // cost array, horizontally
210 int[] tempD; // placeholder to assist in swapping p and d
211 final int[][] matrix = new int[m + 1][n + 1];
212 // filling the first row and first column values in the matrix
213 for (int index = 0; index <= n; index++) {
214 matrix[0][index] = index;
215 }
216 for (int index = 0; index <= m; index++) {
217 matrix[index][0] = index;
218 }
219 // fill in starting table values
220 final int boundary = Math.min(n, threshold) + 1;
221 for (int i = 0; i < boundary; i++) {
222 p[i] = i;
223 }
224 // these fills ensure that the value above the rightmost entry of our
225 // stripe will be ignored in following loop iterations
226 Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
227 Arrays.fill(d, Integer.MAX_VALUE);
228 // iterates through t
229 for (int j = 1; j <= m; j++) {
230 final E rightJ = right.at(j - 1); // jth character of right
231 d[0] = j;
232 // compute stripe indices, constrain to array size
233 final int min = Math.max(1, j - threshold);
234 final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(n, j + threshold);
235 // the stripe may lead off of the table if s and t are of different sizes
236 if (min > max) {
237 return new LevenshteinResults(-1, 0, 0, 0);
238 }
239 // ignore entry left of leftmost
240 if (min > 1) {
241 d[min - 1] = Integer.MAX_VALUE;
242 }
243 // iterates through [min, max] in s
244 for (int i = min; i <= max; i++) {
245 if (left.at(i - 1).equals(rightJ)) {
246 // diagonally left and up
247 d[i] = p[i - 1];
248 } else {
249 // 1 + minimum of cell to the left, to the top, diagonally left and up
250 d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
251 }
252 matrix[j][i] = d[i];
253 }
254 // copy current distance counts to 'previous row' distance counts
255 tempD = p;
256 p = d;
257 d = tempD;
258 }
259 // if p[n] is greater than the threshold, there's no guarantee on it being the correct distance
260 if (p[n] <= threshold) {
261 return findDetailedResults(left, right, matrix, swapped);
262 }
263 return new LevenshteinResults(-1, 0, 0, 0);
264 }
265
266 /**
267 * Finds the Levenshtein distance between two Strings.
268 *
269 * <p>
270 * A higher score indicates a greater distance.
271 * </p>
272 *
273 * <p>
274 * The previous implementation of the Levenshtein distance algorithm was from
275 * <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
276 * </p>
277 *
278 * <p>
279 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
280 * strings.<br>
281 * This implementation of the Levenshtein distance algorithm is from
282 * <a href="https://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
283 * </p>
284 *
285 * <pre>
286 * unlimitedCompare(null, *) = Throws {@link IllegalArgumentException}
287 * unlimitedCompare(*, null) = Throws {@link IllegalArgumentException}
288 * unlimitedCompare("","") = 0
289 * unlimitedCompare("","a") = 1
290 * unlimitedCompare("aaapppp", "") = 7
291 * unlimitedCompare("frog", "fog") = 1
292 * unlimitedCompare("fly", "ant") = 3
293 * unlimitedCompare("elephant", "hippo") = 7
294 * unlimitedCompare("hippo", "elephant") = 7
295 * unlimitedCompare("hippo", "zzzzzzzz") = 8
296 * unlimitedCompare("hello", "hallo") = 1
297 * </pre>
298 *
299 * @param <E> The type of similarity score unit.
300 * @param left the first CharSequence, must not be null.
301 * @param right the second CharSequence, must not be null.
302 * @return result distance, or -1.
303 * @throws IllegalArgumentException if either CharSequence input is {@code null}.
304 */
305 private static <E> LevenshteinResults unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right) {
306 if (left == null || right == null) {
307 throw new IllegalArgumentException("CharSequences must not be null");
308 }
309 /*
310 * The difference between this impl. and the previous is that, rather than creating and retaining a matrix of size s.length() + 1 by t.length() + 1, we
311 * maintain two single-dimensional arrays of length s.length() + 1. The first, d, is the 'current working' distance array that maintains the newest
312 * distance cost counts as we iterate through the characters of String s. Each time we increment the index of String t we are comparing, d is copied to
313 * p, the second int[]. Doing so allows us to retain the previous cost counts as required by the algorithm (taking the minimum of the cost count to the
314 * left, up one, and diagonally up and to the left of the current cost count being calculated). (Note that the arrays aren't really copied anymore, just
315 * switched...this is clearly much better than cloning an array or doing a System.arraycopy() each time through the outer loop.)
316 *
317 * Effectively, the difference between the two implementations is this one does not cause an out of memory condition when calculating the LD over two
318 * very large strings.
319 */
320 int n = left.length(); // length of left
321 int m = right.length(); // length of right
322 if (n == 0) {
323 return new LevenshteinResults(m, m, 0, 0);
324 }
325 if (m == 0) {
326 return new LevenshteinResults(n, 0, n, 0);
327 }
328 boolean swapped = false;
329 if (n > m) {
330 // swap the input strings to consume less memory
331 final SimilarityInput<E> tmp = left;
332 left = right;
333 right = tmp;
334 n = m;
335 m = right.length();
336 swapped = true;
337 }
338 int[] p = new int[n + 1]; // 'previous' cost array, horizontally
339 int[] d = new int[n + 1]; // cost array, horizontally
340 int[] tempD; // placeholder to assist in swapping p and d
341 final int[][] matrix = new int[m + 1][n + 1];
342 // filling the first row and first column values in the matrix
343 for (int index = 0; index <= n; index++) {
344 matrix[0][index] = index;
345 }
346 for (int index = 0; index <= m; index++) {
347 matrix[index][0] = index;
348 }
349 // indexes into strings left and right
350 int i; // iterates through left
351 int j; // iterates through right
352 E rightJ; // jth character of right
353 int cost; // cost
354 for (i = 0; i <= n; i++) {
355 p[i] = i;
356 }
357 for (j = 1; j <= m; j++) {
358 rightJ = right.at(j - 1);
359 d[0] = j;
360 for (i = 1; i <= n; i++) {
361 cost = left.at(i - 1).equals(rightJ) ? 0 : 1;
362 // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
363 d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
364 // filling the matrix
365 matrix[j][i] = d[i];
366 }
367 // copy current distance counts to 'previous row' distance counts
368 tempD = p;
369 p = d;
370 d = tempD;
371 }
372 return findDetailedResults(left, right, matrix, swapped);
373 }
374
375 /**
376 * Threshold.
377 */
378 private final Integer threshold;
379
380 /**
381 * Constructs a new instance that uses a version of the algorithm that does not use a threshold parameter.
382 *
383 * @see LevenshteinDetailedDistance#getDefaultInstance()
384 * @deprecated Use {@link #getDefaultInstance()}.
385 */
386 @Deprecated
387 public LevenshteinDetailedDistance() {
388 this(null);
389 }
390
391 /**
392 * Constructs a new instance for a threshold.
393 * <p>
394 * If the threshold is not null, distance calculations will be limited to a maximum length.
395 * </p>
396 * <p>
397 * If the threshold is null, the unlimited version of the algorithm will be used.
398 * </p>
399 *
400 * @param threshold If this is null then distances calculations will not be limited. This may not be negative.
401 */
402 public LevenshteinDetailedDistance(final Integer threshold) {
403 if (threshold != null && threshold < 0) {
404 throw new IllegalArgumentException("Threshold must not be negative");
405 }
406 this.threshold = threshold;
407 }
408
409 /**
410 * Computes the Levenshtein distance between two Strings.
411 *
412 * <p>
413 * A higher score indicates a greater distance.
414 * </p>
415 *
416 * <p>
417 * The previous implementation of the Levenshtein distance algorithm was from
418 * <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
419 * </p>
420 *
421 * <p>
422 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
423 * strings.<br>
424 * This implementation of the Levenshtein distance algorithm is from
425 * <a href="https://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
426 * </p>
427 *
428 * <pre>
429 * distance.apply(null, *) = Throws {@link IllegalArgumentException}
430 * distance.apply(*, null) = Throws {@link IllegalArgumentException}
431 * distance.apply("","") = 0
432 * distance.apply("","a") = 1
433 * distance.apply("aaapppp", "") = 7
434 * distance.apply("frog", "fog") = 1
435 * distance.apply("fly", "ant") = 3
436 * distance.apply("elephant", "hippo") = 7
437 * distance.apply("hippo", "elephant") = 7
438 * distance.apply("hippo", "zzzzzzzz") = 8
439 * distance.apply("hello", "hallo") = 1
440 * </pre>
441 *
442 * @param left the first input, must not be null.
443 * @param right the second input, must not be null.
444 * @return result distance, or -1.
445 * @throws IllegalArgumentException if either String input {@code null}.
446 */
447 @Override
448 public LevenshteinResults apply(final CharSequence left, final CharSequence right) {
449 return apply(SimilarityInput.input(left), SimilarityInput.input(right));
450 }
451
452 /**
453 * Computes the Levenshtein distance between two Strings.
454 *
455 * <p>
456 * A higher score indicates a greater distance.
457 * </p>
458 *
459 * <p>
460 * The previous implementation of the Levenshtein distance algorithm was from
461 * <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
462 * </p>
463 *
464 * <p>
465 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
466 * strings.<br>
467 * This implementation of the Levenshtein distance algorithm is from
468 * <a href="https://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
469 * </p>
470 *
471 * <pre>
472 * distance.apply(null, *) = Throws {@link IllegalArgumentException}
473 * distance.apply(*, null) = Throws {@link IllegalArgumentException}
474 * distance.apply("","") = 0
475 * distance.apply("","a") = 1
476 * distance.apply("aaapppp", "") = 7
477 * distance.apply("frog", "fog") = 1
478 * distance.apply("fly", "ant") = 3
479 * distance.apply("elephant", "hippo") = 7
480 * distance.apply("hippo", "elephant") = 7
481 * distance.apply("hippo", "zzzzzzzz") = 8
482 * distance.apply("hello", "hallo") = 1
483 * </pre>
484 *
485 * @param <E> The type of similarity score unit.
486 * @param left the first input, must not be null.
487 * @param right the second input, must not be null.
488 * @return result distance, or -1.
489 * @throws IllegalArgumentException if either String input {@code null}.
490 * @since 1.13.0
491 */
492 public <E> LevenshteinResults apply(final SimilarityInput<E> left, final SimilarityInput<E> right) {
493 if (threshold != null) {
494 return limitedCompare(left, right, threshold);
495 }
496 return unlimitedCompare(left, right);
497 }
498
499 /**
500 * Gets the distance threshold.
501 *
502 * @return The distance threshold.
503 */
504 public Integer getThreshold() {
505 return threshold;
506 }
507 }