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