[LANG-413] Memory usage improvement for StringUtils#getLevenshteinDistance()

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 2.3
• Fix Version/s: 2.4
• Component/s: lang.*
• Assignee: Unassigned
• Reporter: Cédrik LIME
• Created: 21/Feb/08 10:34
• Updated: 16/Dec/09 08:50
• Resolved: 24/Feb/08 03:34

Description

StringUtils#getLevenshteinDistance() has recently been optimized to conserve a whole lot of memory, which is good. Since the algorithm is symmetric, we can go even further by selecting the shortest of the 2 input Strings to work upon :

Index: /Documents/workspace/commons-lang/src/java/org/apache/commons/lang/StringUtils.java
===================================================================
— /Documents/workspace/commons-lang/src/java/org/apache/commons/lang/StringUtils.java (revision 629728)
+++ /Documents/workspace/commons-lang/src/java/org/apache/commons/lang/StringUtils.java (working copy)
@@ -5737,6 +5737,15 @@
return n;
}

+ if (n > m)

{ + // swap the input strings to consume less memory in p[] and d[] + String tmp = s; + s = t; + t = tmp; + n = m; + m = t.length(); + }

+
int p[] = new int[n+1]; //'previous' cost array, horizontally
int d[] = new int[n+1]; // cost array, horizontally
int _d[]; //placeholder to assist in swapping p and d