Repository: commons-text Updated Branches: refs/heads/master 802258f63 -> 97d606405
Add optimization to limited levenshtein distance Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/6b85ebeb Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/6b85ebeb Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/6b85ebeb Branch: refs/heads/master Commit: 6b85ebeb0bb999d3dc158c4afb0f8ae4c6eeacac Parents: 6ad5771 Author: Luciano Quintabani <lquintab...@medallia.com> Authored: Sun Jul 15 17:10:51 2018 -0300 Committer: Luciano Quintabani <lquintab...@medallia.com> Committed: Sun Jul 15 17:10:51 2018 -0300 ---------------------------------------------------------------------- .../org/apache/commons/text/similarity/LevenshteinDistance.java | 5 +++++ 1 file changed, 5 insertions(+) ---------------------------------------------------------------------- http://git-wip-us.apache.org/repos/asf/commons-text/blob/6b85ebeb/src/main/java/org/apache/commons/text/similarity/LevenshteinDistance.java ---------------------------------------------------------------------- diff --git a/src/main/java/org/apache/commons/text/similarity/LevenshteinDistance.java b/src/main/java/org/apache/commons/text/similarity/LevenshteinDistance.java index 68c13cb..f0f2874 100644 --- a/src/main/java/org/apache/commons/text/similarity/LevenshteinDistance.java +++ b/src/main/java/org/apache/commons/text/similarity/LevenshteinDistance.java @@ -241,6 +241,11 @@ public class LevenshteinDistance implements EditDistance<Integer> { m = right.length(); } + // the edit distance cannot be less than the length difference + if (m - n > threshold) { + return -1; + } + int[] p = new int[n + 1]; // 'previous' cost array, horizontally int[] d = new int[n + 1]; // cost array, horizontally int[] tempD; // placeholder to assist in swapping p and d
