commons-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From pascalschumac...@apache.org
Subject [2/2] [lang] LANG-1277: StringUtils#getLevenshteinDistance reduce memory consumption
Date Thu, 20 Oct 2016 19:52:57 GMT
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 <pascalschumacher@gmx.net>
Authored: Thu Oct 20 21:51:01 2016 +0200
Committer: pascalschumacher <pascalschumacher@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);


Mime
View raw message