LANG-1277: StringUtils#getLevenshteinDistance reduce memory consumption minimal clean-up
add changes.xml entry Project: http://git-wip-us.apache.org/repos/asf/commons-lang/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-lang/commit/6423a766 Tree: http://git-wip-us.apache.org/repos/asf/commons-lang/tree/6423a766 Diff: http://git-wip-us.apache.org/repos/asf/commons-lang/diff/6423a766 Branch: refs/heads/master Commit: 6423a7665516d738ae50d272e3b4ca72cdb89a9d Parents: 103b64a Author: pascalschumacher <pascalschumac...@gmx.net> Authored: Thu Oct 20 21:51:01 2016 +0200 Committer: pascalschumacher <pascalschumac...@gmx.net> Committed: Thu Oct 20 21:52:09 2016 +0200 ---------------------------------------------------------------------- src/changes/changes.xml | 1 + .../org/apache/commons/lang3/StringUtils.java | 23 +++++++------------- 2 files changed, 9 insertions(+), 15 deletions(-) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-lang/blob/6423a766/src/changes/changes.xml ---------------------------------------------------------------------- diff --git a/src/changes/changes.xml b/src/changes/changes.xml index b3f4b00..4d31ea2 100644 --- a/src/changes/changes.xml +++ b/src/changes/changes.xml @@ -46,6 +46,7 @@ The <action> type attribute can be add,update,fix,remove. <body> <release version="3.6" date="tba" description="tba"> + <action issue="LANG-1277" type="update" dev="pschumacher" due-to="yufcuy">StringUtils#getLevenshteinDistance reduce memory consumption</action> <action issue="LANG-1070" type="fix" dev="pschumacher" due-to="Paul Pogonyshev">ArrayUtils#add confusing example in javadoc</action> <action issue="LANG-1271" type="fix" dev="pschumacher" due-to="Pierre Templier">StringUtils#isAnyEmpty and #isAnyBlank should return false for an empty array</action> <action issue="LANG-1270" type="add" dev="pschumacher" due-to="Pierre Templier">Add StringUtils#isAnyNotEmpty and #isAnyNotBlank</action> http://git-wip-us.apache.org/repos/asf/commons-lang/blob/6423a766/src/main/java/org/apache/commons/lang3/StringUtils.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/lang3/StringUtils.java b/src/main/java/org/apache/commons/lang3/StringUtils.java index d06d60c..559444d 100644 --- a/src/main/java/org/apache/commons/lang3/StringUtils.java +++ b/src/main/java/org/apache/commons/lang3/StringUtils.java @@ -7736,11 +7736,9 @@ public class StringUtils { * another, where each change is a single character modification (deletion, * insertion or substitution).</p> * - * <p>The previous implementation of the Levenshtein distance algorithm - * was from <a href="https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm";> - * https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm</a></p> - * - * <p>This implementation only need one single-dimensional arrays of length s.length() + 1</p> + * <p>The implementation uses a single-dimensional array of length s.length() + 1. See + * <a href="http://blog.softwx.net/2014/12/optimizing-levenshtein-algorithm-in-c.html";> + * http://blog.softwx.net/2014/12/optimizing-levenshtein-algorithm-in-c.html</a> for details.</p> * * <pre> * StringUtils.getLevenshteinDistance(null, *) = IllegalArgumentException @@ -7768,13 +7766,8 @@ public class StringUtils { throw new IllegalArgumentException("Strings must not be null"); } - /* - This implementation use two variable to record the previous cost counts, - So this implementation use less memory than previous impl. - */ - - int n = s.length(); // length of s - int m = t.length(); // length of t + int n = s.length(); + int m = t.length(); if (n == 0) { return m; @@ -7799,19 +7792,19 @@ public class StringUtils { int upper; char t_j; // jth character of t - int cost; // cost + int cost; for (i = 0; i <= n; i++) { p[i] = i; } for (j = 1; j <= m; j++) { - upper_left = p[0]; + upper_left = p[0]; t_j = t.charAt(j - 1); p[0] = j; for (i = 1; i <= n; i++) { - upper = p[i]; + upper = p[i]; cost = s.charAt(i - 1) == t_j ? 0 : 1; // minimum of cell to the left+1, to the top+1, diagonally left and up +cost p[i] = Math.min(Math.min(p[i - 1] + 1, p[i] + 1), upper_left + cost);
