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