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:10:34 UTC
[commons-text] branch master updated (6ea79f2 -> 42c22ce)
This is an automated email from the ASF dual-hosted git repository.
kinow pushed a change to branch master
in repository https://gitbox.apache.org/repos/asf/commons-text.git.
discard 6ea79f2 TEXT-188 Speed up LevenshteinDistance with threshold by exiting early
new 2095a09 TEXT-188 Speed up LevenshteinDistance with threshold by exiting early
new 42c22ce Merge branch 'pr-174'
This update added new revisions after undoing existing revisions.
That is to say, some revisions that were in the old version of the
branch are not in the new version. This situation occurs
when a user --force pushes a change and generates a repository
containing something like this:
* -- * -- B -- O -- O -- O (6ea79f2)
\
N -- N -- N refs/heads/master (42c22ce)
You should already have received notification emails for all of the O
revisions, and so the following emails describe only the N revisions
from the common base, B.
Any revisions marked "omit" are not gone; other references still
refer to them. Any revisions marked "discard" are gone forever.
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
[commons-text] 01/02: TEXT-188 Speed up LevenshteinDistance with
threshold by exiting early
Posted by ki...@apache.org.
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
commit 2095a093ce9a73d53c3a89fe35af1ea4047f1817
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
[commons-text] 02/02: Merge branch 'pr-174'
Posted by ki...@apache.org.
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
commit 42c22ce02538e014b3f5e44368dfe75ffa445e0c
Merge: 58b1cdc 2095a09
Author: Bruno P. Kinoshita <ki...@users.noreply.github.com>
AuthorDate: Mon Oct 5 12:09:59 2020 +1300
Merge branch 'pr-174'
This closes #174
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(+)