You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ki...@apache.org on 2020/10/04 23:07:23 UTC
[commons-text] branch master updated: TEXT-188 Speed up
LevenshteinDistance with threshold by exiting early
This is an automated email from the ASF dual-hosted git repository.
kinow pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/commons-text.git
The following commit(s) were added to refs/heads/master by this push:
new 6ea79f2 TEXT-188 Speed up LevenshteinDistance with threshold by exiting early
6ea79f2 is described below
commit 6ea79f2001edf5c2316597a264fba5bd97d7da1d
Author: Jakob Vesterstrøm <ja...@gmail.com>
AuthorDate: Fri Oct 2 11:45:55 2020 +0200
TEXT-188 Speed up LevenshteinDistance with threshold by exiting early
---
src/changes/changes.xml | 1 +
.../org/apache/commons/text/similarity/LevenshteinDistance.java | 6 ++++++
.../org/apache/commons/text/similarity/LevenshteinDistanceTest.java | 1 +
3 files changed, 8 insertions(+)
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 3cbce20..eca34a1 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -52,6 +52,7 @@ The <action> type attribute can be add,update,fix,remove.
<action type="fix" dev="ggregory" due-to="Gary Gregory">Update commons.jacoco.version 0.8.5 to 0.8.6; fixes Java 15 build.</action>
<action type="fix" dev="ggregory" due-to="Gary Gregory">Update spotbugs.plugin.version 4.0.4 to 4.1.3; fixes Java 16 build.</action>
<!-- ADD -->
+ <action issue="TEXT-188" type="add" dev="kinow" due-to="Jakob Vesterstrøm">Speed up LevenshteinDistance with threshold by exiting early</action>
<action issue="TEXT-185" type="add" dev="ggregory" due-to="Larry West, Gary Gregory">Release Notes page hasn't been updated for 1.9 release yet.</action>
<!-- UPDATE -->
<action type="update" dev="ggregory" due-to="Dependabot">Update checkstyle from 8.34 to 8.36.2 #141 #168.</action>
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 7814b4c..913ec24 100644
--- a/src/main/java/org/apache/commons/text/similarity/LevenshteinDistance.java
+++ b/src/main/java/org/apache/commons/text/similarity/LevenshteinDistance.java
@@ -275,6 +275,7 @@ public class LevenshteinDistance implements EditDistance<Integer> {
d[min - 1] = Integer.MAX_VALUE;
}
+ int lowerBound = Integer.MAX_VALUE;
// iterates through [min, max] in s
for (int i = min; i <= max; i++) {
if (left.charAt(i - 1) == rightJ) {
@@ -285,6 +286,11 @@ public class LevenshteinDistance implements EditDistance<Integer> {
// left and up
d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
}
+ lowerBound = Math.min(lowerBound, d[i]);
+ }
+ // if the lower bound is greater than the threshold, then exit early
+ if (lowerBound > threshold) {
+ return -1;
}
// copy current distance counts to 'previous row' distance counts
diff --git a/src/test/java/org/apache/commons/text/similarity/LevenshteinDistanceTest.java b/src/test/java/org/apache/commons/text/similarity/LevenshteinDistanceTest.java
index 22446f4..86a8251 100644
--- a/src/test/java/org/apache/commons/text/similarity/LevenshteinDistanceTest.java
+++ b/src/test/java/org/apache/commons/text/similarity/LevenshteinDistanceTest.java
@@ -114,6 +114,7 @@ public class LevenshteinDistanceTest {
assertThat(new LevenshteinDistance(Integer.MAX_VALUE).apply("hippo", "zzzzzzzz")).isEqualTo(8);
assertThat(new LevenshteinDistance(Integer.MAX_VALUE).apply("zzzzzzzz", "hippo")).isEqualTo(8);
assertThat(new LevenshteinDistance(Integer.MAX_VALUE).apply("hello", "hallo")).isEqualTo(1);
+ assertThat(new LevenshteinDistance(1).apply("abc", "acb")).isEqualTo(-1);
}
@Test