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 }