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