Source code

Return-Path: X-Original-To: apmail-commons-notifications-archive@minotaur.apache.org Delivered-To: apmail-commons-notifications-archive@minotaur.apache.org Received: from mail.apache.org (hermes.apache.org [140.211.11.3]) by minotaur.apache.org (Postfix) with SMTP id 64C4B172CA for ; Sun, 26 Apr 2015 10:18:33 +0000 (UTC) Received: (qmail 52138 invoked by uid 500); 26 Apr 2015 10:18:33 -0000 Delivered-To: apmail-commons-notifications-archive@commons.apache.org Received: (qmail 52091 invoked by uid 500); 26 Apr 2015 10:18:33 -0000 Mailing-List: contact notifications-help@commons.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: dev@commons.apache.org Delivered-To: mailing list notifications@commons.apache.org Received: (qmail 51905 invoked by uid 99); 26 Apr 2015 10:18:33 -0000 Received: from eris.apache.org (HELO hades.apache.org) (140.211.11.105) by apache.org (qpsmtpd/0.29) with ESMTP; Sun, 26 Apr 2015 10:18:33 +0000 Received: from hades.apache.org (localhost [127.0.0.1]) by hades.apache.org (ASF Mail Server at hades.apache.org) with ESMTP id 19728AC1435 for ; Sun, 26 Apr 2015 10:18:33 +0000 (UTC) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r949214 [17/35] - in /websites/production/commons/content/sandbox/commons-text: ./ apidocs/ apidocs/org/apache/commons/text/diff/ apidocs/org/apache/commons/text/diff/class-use/ apidocs/org/apache/commons/text/names/ apidocs/org/apache/comm... Date: Sun, 26 Apr 2015 10:18:28 -0000 To: notifications@commons.apache.org From: britter@apache.org X-Mailer: svnmailer-1.0.9 Message-Id: <20150426101833.19728AC1435@hades.apache.org> Modified: websites/production/commons/content/sandbox/commons-text/apidocs/src-html/org/apache/commons/text/similarity/LevenshteinDistance.html ============================================================================== --- websites/production/commons/content/sandbox/commons-text/apidocs/src-html/org/apache/commons/text/similarity/LevenshteinDistance.html (original) +++ websites/production/commons/content/sandbox/commons-text/apidocs/src-html/org/apache/commons/text/similarity/LevenshteinDistance.html Sun Apr 26 10:18:25 2015 @@ -1,5 +1,5 @@ - + Source code @@ -38,389 +38,387 @@ 030 * 031 * This code has been adapted from Apache Commons Lang 3.3. 032 * -033 * -034 * @since 1.0 -035 */ -036public class LevenshteinDistance implements EditDistance<Integer> { -037 -038 /** -039 * Default instance. -040 */ -041 private static final LevenshteinDistance DEFAULT_INSTANCE = new LevenshteinDistance(); -042 -043 /** -044 * Threshold. -045 */ -046 private final Integer threshold; -047 -048 /** -049 * -050 * This returns the default instance that uses a version -051 * of the algorithm that does not use a threshold parameter. -052 * -053 * -054 * @see LevenshteinDistance#getDefaultInstance() -055 */ -056 public LevenshteinDistance() { -057 this(null); -058 } -059 -060 /** -061 * -062 * If the threshold is not null, distance calculations will be limited to a maximum length. -063 * If the threshold is null, the unlimited version of the algorithm will be used. -064 * -065 * -066 * @param threshold -067 * If this is null then distances calculations will not be limited. -068 * This may not be negative. -069 */ -070 public LevenshteinDistance(final Integer threshold) { -071 if (threshold != null && threshold < 0) { -072 throw new IllegalArgumentException("Threshold must not be negative"); -073 } -074 this.threshold = threshold; -075 } -076 -077 /** -078 * Find the Levenshtein distance between two Strings. +033 */ +034public class LevenshteinDistance implements EditDistance<Integer> { +035 +036 /** +037 * Default instance. +038 */ +039 private static final LevenshteinDistance DEFAULT_INSTANCE = new LevenshteinDistance(); +040 +041 /** +042 * Threshold. +043 */ +044 private final Integer threshold; +045 +046 /** +047 * +048 * This returns the default instance that uses a version +049 * of the algorithm that does not use a threshold parameter. +050 * +051 * +052 * @see LevenshteinDistance#getDefaultInstance() +053 */ +054 public LevenshteinDistance() { +055 this(null); +056 } +057 +058 /** +059 * +060 * If the threshold is not null, distance calculations will be limited to a maximum length. +061 * If the threshold is null, the unlimited version of the algorithm will be used. +062 * +063 * +064 * @param threshold +065 * If this is null then distances calculations will not be limited. +066 * This may not be negative. +067 */ +068 public LevenshteinDistance(final Integer threshold) { +069 if (threshold != null && threshold < 0) { +070 throw new IllegalArgumentException("Threshold must not be negative"); +071 } +072 this.threshold = threshold; +073 } +074 +075 /** +076 * Find the Levenshtein distance between two Strings. +077 * +078 * A higher score indicates a greater distance. 079 * -080 * A higher score indicates a greater distance. -081 * -082 * The previous implementation of the Levenshtein distance algorithm -083 * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a> -084 * -085 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError -086 * which can occur when my Java implementation is used with very large strings. -087 * This implementation of the Levenshtein distance algorithm -088 * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a> -089 * -090 * <pre> -091 * distance.apply(null, *) = IllegalArgumentException -092 * distance.apply(*, null) = IllegalArgumentException -093 * distance.apply("","") = 0 -094 * distance.apply("","a") = 1 -095 * distance.apply("aaapppp", "") = 7 -096 * distance.apply("frog", "fog") = 1 -097 * distance.apply("fly", "ant") = 3 -098 * distance.apply("elephant", "hippo") = 7 -099 * distance.apply("hippo", "elephant") = 7 -100 * distance.apply("hippo", "zzzzzzzz") = 8 -101 * distance.apply("hello", "hallo") = 1 -102 * </pre> -103 * -104 * @param left the first string, must not be null -105 * @param right the second string, must not be null -106 * @return result distance, or -1 -107 * @throws IllegalArgumentException if either String input {@code null} -108 */ -109 public Integer apply(CharSequence left, CharSequence right) { -110 if (threshold != null) { -111 return limitedCompare(left, right, threshold); -112 } else { -113 return unlimitedCompare(left, right); -114 } -115 } -116 -117 /** -118 * Gets the default instance. -119 * -120 * @return the default instace -121 */ -122 public static LevenshteinDistance getDefaultInstance() { -123 return DEFAULT_INSTANCE; -124 } -125 -126 /** -127 * Gets the distance threshold. -128 * -129 * @return the distance threshold -130 */ -131 public Integer getThreshold() { -132 return threshold; -133 } -134 -135 /** -136 * Find the Levenshtein distance between two CharSequences if it's less than or -137 * equal to a given threshold. -138 * -139 * -140 * This implementation follows from Algorithms on Strings, Trees and -141 * Sequences by Dan Gusfield and Chas Emerick's implementation of the -142 * Levenshtein distance algorithm from <a -143 * href="http://www.merriampark.com/ld.htm" -144 * >http://www.merriampark.com/ld.htm</a> -145 * -146 * -147 * <pre> -148 * limitedCompare(null, *, *) = IllegalArgumentException -149 * limitedCompare(*, null, *) = IllegalArgumentException -150 * limitedCompare(*, *, -1) = IllegalArgumentException -151 * limitedCompare("","", 0) = 0 -152 * limitedCompare("aaapppp", "", 8) = 7 -153 * limitedCompare("aaapppp", "", 7) = 7 -154 * limitedCompare("aaapppp", "", 6)) = -1 -155 * limitedCompare("elephant", "hippo", 7) = 7 -156 * limitedCompare("elephant", "hippo", 6) = -1 -157 * limitedCompare("hippo", "elephant", 7) = 7 -158 * limitedCompare("hippo", "elephant", 6) = -1 -159 * </pre> -160 * -161 * @param left the first string, must not be null -162 * @param right the second string, must not be null -163 * @param threshold the target threshold, must not be negative -164 * @return result distance, or -1 -165 */ -166 private static int limitedCompare(CharSequence left, CharSequence right, int threshold) { -167 if (left == null || right == null) { -168 throw new IllegalArgumentException("Strings must not be null"); -169 } -170 if (threshold < 0) { -171 throw new IllegalArgumentException("Threshold must not be negative"); -172 } -173 -174 /* -175 * This implementation only computes the distance if it's less than or -176 * equal to the threshold value, returning -1 if it's greater. The -177 * advantage is performance: unbounded distance is O(nm), but a bound of -178 * k allows us to reduce it to O(km) time by only computing a diagonal -179 * stripe of width 2k + 1 of the cost table. It is also possible to use -180 * this to compute the unbounded Levenshtein distance by starting the -181 * threshold at 1 and doubling each time until the distance is found; -182 * this is O(dm), where d is the distance. -183 * -184 * One subtlety comes from needing to ignore entries on the border of -185 * our stripe eg. p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry -186 * to the left of the leftmost member We must ignore the entry above the -187 * rightmost member -188 * -189 * Another subtlety comes from our stripe running off the matrix if the -190 * strings aren't of the same size. Since string s is always swapped to -191 * be the shorter of the two, the stripe will always run off to the -192 * upper right instead of the lower left of the matrix. -193 * -194 * As a concrete example, suppose s is of length 5, t is of length 7, -195 * and our threshold is 1. In this case we're going to walk a stripe of -196 * length 3. The matrix would look like so: -197 * -198 * <pre> -199 * 1 2 3 4 5 -200 * 1 |#|#| | | | -201 * 2 |#|#|#| | | -202 * 3 | |#|#|#| | -203 * 4 | | |#|#|#| -204 * 5 | | | |#|#| -205 * 6 | | | | |#| -206 * 7 | | | | | | -207 * </pre> -208 * -209 * Note how the stripe leads off the table as there is no possible way -210 * to turn a string of length 5 into one of length 7 in edit distance of -211 * 1. -212 * -213 * Additionally, this implementation decreases memory usage by using two -214 * single-dimensional arrays and swapping them back and forth instead of -215 * allocating an entire n by m matrix. This requires a few minor -216 * changes, such as immediately returning when it's detected that the -217 * stripe has run off the matrix and initially filling the arrays with -218 * large values so that entries we don't compute are ignored. -219 * -220 * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for -221 * some discussion. -222 */ -223 -224 int n = left.length(); // length of left -225 int m = right.length(); // length of right -226 -227 // if one string is empty, the edit distance is necessarily the length -228 // of the other -229 if (n == 0) { -230 return m <= threshold ? m : -1; -231 } else if (m == 0) { -232 return n <= threshold ? n : -1; -233 } -234 -235 if (n > m) { -236 // swap the two strings to consume less memory -237 final CharSequence tmp = left; -238 left = right; -239 right = tmp; -240 n = m; -241 m = right.length(); -242 } -243 -244 int[] p = new int[n + 1]; // 'previous' cost array, horizontally -245 int[] d = new int[n + 1]; // cost array, horizontally -246 int[] tempD; // placeholder to assist in swapping p and d -247 -248 // fill in starting table values -249 final int boundary = Math.min(n, threshold) + 1; -250 for (int i = 0; i < boundary; i++) { -251 p[i] = i; -252 } -253 // these fills ensure that the value above the rightmost entry of our -254 // stripe will be ignored in following loop iterations -255 Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE); -256 Arrays.fill(d, Integer.MAX_VALUE); -257 -258 // iterates through t -259 for (int j = 1; j <= m; j++) { -260 final char rightJ = right.charAt(j - 1); // jth character of right -261 d[0] = j; -262 -263 // compute stripe indices, constrain to array size -264 final int min = Math.max(1, j - threshold); -265 final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min( -266 n, j + threshold); -267 -268 // the stripe may lead off of the table if s and t are of different -269 // sizes -270 if (min > max) { -271 return -1; -272 } -273 -274 // ignore entry left of leftmost -275 if (min > 1) { -276 d[min - 1] = Integer.MAX_VALUE; -277 } -278 -279 // iterates through [min, max] in s -280 for (int i = min; i <= max; i++) { -281 if (left.charAt(i - 1) == rightJ) { -282 // diagonally left and up -283 d[i] = p[i - 1]; -284 } else { -285 // 1 + minimum of cell to the left, to the top, diagonally -286 // left and up -287 d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]); -288 } -289 } -290 -291 // copy current distance counts to 'previous row' distance counts -292 tempD = p; -293 p = d; -294 d = tempD; -295 } -296 -297 // if p[n] is greater than the threshold, there's no guarantee on it -298 // being the correct -299 // distance -300 if (p[n] <= threshold) { -301 return p[n]; -302 } -303 return -1; -304 } -305 -306 /** -307 * Find the Levenshtein distance between two Strings. +080 * The previous implementation of the Levenshtein distance algorithm +081 * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a> +082 * +083 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError +084 * which can occur when my Java implementation is used with very large strings. +085 * This implementation of the Levenshtein distance algorithm +086 * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a> +087 * +088 * <pre> +089 * distance.apply(null, *) = IllegalArgumentException +090 * distance.apply(*, null) = IllegalArgumentException +091 * distance.apply("","") = 0 +092 * distance.apply("","a") = 1 +093 * distance.apply("aaapppp", "") = 7 +094 * distance.apply("frog", "fog") = 1 +095 * distance.apply("fly", "ant") = 3 +096 * distance.apply("elephant", "hippo") = 7 +097 * distance.apply("hippo", "elephant") = 7 +098 * distance.apply("hippo", "zzzzzzzz") = 8 +099 * distance.apply("hello", "hallo") = 1 +100 * </pre> +101 * +102 * @param left the first string, must not be null +103 * @param right the second string, must not be null +104 * @return result distance, or -1 +105 * @throws IllegalArgumentException if either String input {@code null} +106 */ +107 public Integer apply(CharSequence left, CharSequence right) { +108 if (threshold != null) { +109 return limitedCompare(left, right, threshold); +110 } else { +111 return unlimitedCompare(left, right); +112 } +113 } +114 +115 /** +116 * Gets the default instance. +117 * +118 * @return the default instace +119 */ +120 public static LevenshteinDistance getDefaultInstance() { +121 return DEFAULT_INSTANCE; +122 } +123 +124 /** +125 * Gets the distance threshold. +126 * +127 * @return the distance threshold +128 */ +129 public Integer getThreshold() { +130 return threshold; +131 } +132 +133 /** +134 * Find the Levenshtein distance between two CharSequences if it's less than or +135 * equal to a given threshold. +136 * +137 * +138 * This implementation follows from Algorithms on Strings, Trees and +139 * Sequences by Dan Gusfield and Chas Emerick's implementation of the +140 * Levenshtein distance algorithm from <a +141 * href="http://www.merriampark.com/ld.htm" +142 * >http://www.merriampark.com/ld.htm</a> +143 * +144 * +145 * <pre> +146 * limitedCompare(null, *, *) = IllegalArgumentException +147 * limitedCompare(*, null, *) = IllegalArgumentException +148 * limitedCompare(*, *, -1) = IllegalArgumentException +149 * limitedCompare("","", 0) = 0 +150 * limitedCompare("aaapppp", "", 8) = 7 +151 * limitedCompare("aaapppp", "", 7) = 7 +152 * limitedCompare("aaapppp", "", 6)) = -1 +153 * limitedCompare("elephant", "hippo", 7) = 7 +154 * limitedCompare("elephant", "hippo", 6) = -1 +155 * limitedCompare("hippo", "elephant", 7) = 7 +156 * limitedCompare("hippo", "elephant", 6) = -1 +157 * </pre> +158 * +159 * @param left the first string, must not be null +160 * @param right the second string, must not be null +161 * @param threshold the target threshold, must not be negative +162 * @return result distance, or -1 +163 */ +164 private static int limitedCompare(CharSequence left, CharSequence right, int threshold) { +165 if (left == null || right == null) { +166 throw new IllegalArgumentException("Strings must not be null"); +167 } +168 if (threshold < 0) { +169 throw new IllegalArgumentException("Threshold must not be negative"); +170 } +171 +172 /* +173 * This implementation only computes the distance if it's less than or +174 * equal to the threshold value, returning -1 if it's greater. The +175 * advantage is performance: unbounded distance is O(nm), but a bound of +176 * k allows us to reduce it to O(km) time by only computing a diagonal +177 * stripe of width 2k + 1 of the cost table. It is also possible to use +178 * this to compute the unbounded Levenshtein distance by starting the +179 * threshold at 1 and doubling each time until the distance is found; +180 * this is O(dm), where d is the distance. +181 * +182 * One subtlety comes from needing to ignore entries on the border of +183 * our stripe eg. p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry +184 * to the left of the leftmost member We must ignore the entry above the +185 * rightmost member +186 * +187 * Another subtlety comes from our stripe running off the matrix if the +188 * strings aren't of the same size. Since string s is always swapped to +189 * be the shorter of the two, the stripe will always run off to the +190 * upper right instead of the lower left of the matrix. +191 * +192 * As a concrete example, suppose s is of length 5, t is of length 7, +193 * and our threshold is 1. In this case we're going to walk a stripe of +194 * length 3. The matrix would look like so: +195 * +196 * <pre> +197 * 1 2 3 4 5 +198 * 1 |#|#| | | | +199 * 2 |#|#|#| | | +200 * 3 | |#|#|#| | +201 * 4 | | |#|#|#| +202 * 5 | | | |#|#| +203 * 6 | | | | |#| +204 * 7 | | | | | | +205 * </pre> +206 * +207 * Note how the stripe leads off the table as there is no possible way +208 * to turn a string of length 5 into one of length 7 in edit distance of +209 * 1. +210 * +211 * Additionally, this implementation decreases memory usage by using two +212 * single-dimensional arrays and swapping them back and forth instead of +213 * allocating an entire n by m matrix. This requires a few minor +214 * changes, such as immediately returning when it's detected that the +215 * stripe has run off the matrix and initially filling the arrays with +216 * large values so that entries we don't compute are ignored. +217 * +218 * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for +219 * some discussion. +220 */ +221 +222 int n = left.length(); // length of left +223 int m = right.length(); // length of right +224 +225 // if one string is empty, the edit distance is necessarily the length +226 // of the other +227 if (n == 0) { +228 return m <= threshold ? m : -1; +229 } else if (m == 0) { +230 return n <= threshold ? n : -1; +231 } +232 +233 if (n > m) { +234 // swap the two strings to consume less memory +235 final CharSequence tmp = left; +236 left = right; +237 right = tmp; +238 n = m; +239 m = right.length(); +240 } +241 +242 int[] p = new int[n + 1]; // 'previous' cost array, horizontally +243 int[] d = new int[n + 1]; // cost array, horizontally +244 int[] tempD; // placeholder to assist in swapping p and d +245 +246 // fill in starting table values +247 final int boundary = Math.min(n, threshold) + 1; +248 for (int i = 0; i < boundary; i++) { +249 p[i] = i; +250 } +251 // these fills ensure that the value above the rightmost entry of our +252 // stripe will be ignored in following loop iterations +253 Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE); +254 Arrays.fill(d, Integer.MAX_VALUE); +255 +256 // iterates through t +257 for (int j = 1; j <= m; j++) { +258 final char rightJ = right.charAt(j - 1); // jth character of right +259 d[0] = j; +260 +261 // compute stripe indices, constrain to array size +262 final int min = Math.max(1, j - threshold); +263 final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min( +264 n, j + threshold); +265 +266 // the stripe may lead off of the table if s and t are of different +267 // sizes +268 if (min > max) { +269 return -1; +270 } +271 +272 // ignore entry left of leftmost +273 if (min > 1) { +274 d[min - 1] = Integer.MAX_VALUE; +275 } +276 +277 // iterates through [min, max] in s +278 for (int i = min; i <= max; i++) { +279 if (left.charAt(i - 1) == rightJ) { +280 // diagonally left and up +281 d[i] = p[i - 1]; +282 } else { +283 // 1 + minimum of cell to the left, to the top, diagonally +284 // left and up +285 d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]); +286 } +287 } +288 +289 // copy current distance counts to 'previous row' distance counts +290 tempD = p; +291 p = d; +292 d = tempD; +293 } +294 +295 // if p[n] is greater than the threshold, there's no guarantee on it +296 // being the correct +297 // distance +298 if (p[n] <= threshold) { +299 return p[n]; +300 } +301 return -1; +302 } +303 +304 /** +305 * Find the Levenshtein distance between two Strings. +306 * +307 * A higher score indicates a greater distance. 308 * -309 * A higher score indicates a greater distance. -310 * -311 * The previous implementation of the Levenshtein distance algorithm -312 * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a> -313 * -314 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError -315 * which can occur when my Java implementation is used with very large strings. -316 * This implementation of the Levenshtein distance algorithm -317 * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a> -318 * -319 * <pre> -320 * unlimitedCompare(null, *) = IllegalArgumentException -321 * unlimitedCompare(*, null) = IllegalArgumentException -322 * unlimitedCompare("","") = 0 -323 * unlimitedCompare("","a") = 1 -324 * unlimitedCompare("aaapppp", "") = 7 -325 * unlimitedCompare("frog", "fog") = 1 -326 * unlimitedCompare("fly", "ant") = 3 -327 * unlimitedCompare("elephant", "hippo") = 7 -328 * unlimitedCompare("hippo", "elephant") = 7 -329 * unlimitedCompare("hippo", "zzzzzzzz") = 8 -330 * unlimitedCompare("hello", "hallo") = 1 -331 * </pre> -332 * -333 * @param left the first String, must not be null -334 * @param right the second String, must not be null -335 * @return result distance, or -1 -336 * @throws IllegalArgumentException if either String input {@code null} -337 */ -338 private static int unlimitedCompare(CharSequence left, CharSequence right) { -339 if (left == null || right == null) { -340 throw new IllegalArgumentException("Strings must not be null"); -341 } -342 -343 /* -344 The difference between this impl. and the previous is that, rather -345 than creating and retaining a matrix of size s.length() + 1 by t.length() + 1, -346 we maintain two single-dimensional arrays of length s.length() + 1. The first, d, -347 is the 'current working' distance array that maintains the newest distance cost -348 counts as we iterate through the characters of String s. Each time we increment -349 the index of String t we are comparing, d is copied to p, the second int[]. Doing so -350 allows us to retain the previous cost counts as required by the algorithm (taking -351 the minimum of the cost count to the left, up one, and diagonally up and to the left -352 of the current cost count being calculated). (Note that the arrays aren't really -353 copied anymore, just switched...this is clearly much better than cloning an array -354 or doing a System.arraycopy() each time through the outer loop.) -355 -356 Effectively, the difference between the two implementations is this one does not -357 cause an out of memory condition when calculating the LD over two very large strings. -358 */ -359 -360 int n = left.length(); // length of left -361 int m = right.length(); // length of right -362 -363 if (n == 0) { -364 return m; -365 } else if (m == 0) { -366 return n; -367 } -368 -369 if (n > m) { -370 // swap the input strings to consume less memory -371 final CharSequence tmp = left; -372 left = right; -373 right = tmp; -374 n = m; -375 m = right.length(); -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 -382 // indexes into strings left and right -383 int i; // iterates through left -384 int j; // iterates through right +309 * The previous implementation of the Levenshtein distance algorithm +310 * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a> +311 * +312 * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError +313 * which can occur when my Java implementation is used with very large strings. +314 * This implementation of the Levenshtein distance algorithm +315 * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a> +316 * +317 * <pre> +318 * unlimitedCompare(null, *) = IllegalArgumentException +319 * unlimitedCompare(*, null) = IllegalArgumentException +320 * unlimitedCompare("","") = 0 +321 * unlimitedCompare("","a") = 1 +322 * unlimitedCompare("aaapppp", "") = 7 +323 * unlimitedCompare("frog", "fog") = 1 +324 * unlimitedCompare("fly", "ant") = 3 +325 * unlimitedCompare("elephant", "hippo") = 7 +326 * unlimitedCompare("hippo", "elephant") = 7 +327 * unlimitedCompare("hippo", "zzzzzzzz") = 8 +328 * unlimitedCompare("hello", "hallo") = 1 +329 * </pre> +330 * +331 * @param left the first String, must not be null +332 * @param right the second String, must not be null +333 * @return result distance, or -1 +334 * @throws IllegalArgumentException if either String input {@code null} +335 */ +336 private static int unlimitedCompare(CharSequence left, CharSequence right) { +337 if (left == null || right == null) { +338 throw new IllegalArgumentException("Strings must not be null"); +339 } +340 +341 /* +342 The difference between this impl. and the previous is that, rather +343 than creating and retaining a matrix of size s.length() + 1 by t.length() + 1, +344 we maintain two single-dimensional arrays of length s.length() + 1. The first, d, +345 is the 'current working' distance array that maintains the newest distance cost +346 counts as we iterate through the characters of String s. Each time we increment +347 the index of String t we are comparing, d is copied to p, the second int[]. Doing so +348 allows us to retain the previous cost counts as required by the algorithm (taking +349 the minimum of the cost count to the left, up one, and diagonally up and to the left +350 of the current cost count being calculated). (Note that the arrays aren't really +351 copied anymore, just switched...this is clearly much better than cloning an array +352 or doing a System.arraycopy() each time through the outer loop.) +353 +354 Effectively, the difference between the two implementations is this one does not +355 cause an out of memory condition when calculating the LD over two very large strings. +356 */ +357 +358 int n = left.length(); // length of left +359 int m = right.length(); // length of right +360 +361 if (n == 0) { +362 return m; +363 } else if (m == 0) { +364 return n; +365 } +366 +367 if (n > m) { +368 // swap the input strings to consume less memory +369 final CharSequence tmp = left; +370 left = right; +371 right = tmp; +372 n = m; +373 m = right.length(); +374 } +375 +376 int[] p = new int[n + 1]; //'previous' cost array, horizontally +377 int[] d = new int[n + 1]; // cost array, horizontally +378 int[] tempD; //placeholder to assist in swapping p and d +379 +380 // indexes into strings left and right +381 int i; // iterates through left +382 int j; // iterates through right +383 +384 char rightJ; // jth character of right 385 -386 char rightJ; // jth character of right +386 int cost; // cost 387 -388 int cost; // cost -389 -390 for (i = 0; i <= n; i++) { -391 p[i] = i; -392 } -393 -394 for (j = 1; j <= m; j++) { -395 rightJ = right.charAt(j - 1); -396 d[0] = j; -397 -398 for (i = 1; i <= n; i++) { -399 cost = left.charAt(i - 1) == rightJ ? 0 : 1; -400 // minimum of cell to the left+1, to the top+1, diagonally left and up +cost -401 d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost); -402 } -403 -404 // copy current distance counts to 'previous row' distance counts -405 tempD = p; -406 p = d; -407 d = tempD; -408 } -409 -410 // our last action in the above loop was to switch d and p, so p now -411 // actually has the most recent cost counts -412 return p[n]; -413 } -414 -415} +388 for (i = 0; i <= n; i++) { +389 p[i] = i; +390 } +391 +392 for (j = 1; j <= m; j++) { +393 rightJ = right.charAt(j - 1); +394 d[0] = j; +395 +396 for (i = 1; i <= n; i++) { +397 cost = left.charAt(i - 1) == rightJ ? 0 : 1; +398 // minimum of cell to the left+1, to the top+1, diagonally left and up +cost +399 d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost); +400 } +401 +402 // copy current distance counts to 'previous row' distance counts +403 tempD = p; +404 p = d; +405 d = tempD; +406 } +407 +408 // our last action in the above loop was to switch d and p, so p now +409 // actually has the most recent cost counts +410 return p[n]; +411 } +412 +413} @@ -484,4 +482,4 @@ - + \ No newline at end of file