This is an automated email from the ASF dual-hosted git repository.
garydgregory 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 14657580 Compare characters by value in DamerauLevenshteinDistance
(#770)
14657580 is described below
commit 14657580972a27e504d08c1057699aaa31e0e6bc
Author: Weiki <[email protected]>
AuthorDate: Thu Sep 3 19:22:57 2026 +0800
Compare characters by value in DamerauLevenshteinDistance (#770)
calculateCost compared the boxed Character values returned by
SimilarityInput.at with ==, so it only recognized equal characters
that Character.valueOf caches. That cache covers values up to 127,
so every non-ASCII character compared unequal to itself: applying the
distance to "caf\u00e9" and "caf\u00e9" reported 1 instead of 0, and a
two-character CJK input compared against itself reported 2. The
adjacent-transposition branch never fired for non-ASCII input either,
so transposing two accented characters cost 2 instead of 1. The
limited variant was affected the same way and could return -1 for
inputs whose real distance is within the threshold.
Compare with Objects.equals instead, matching every other class in
this package: LevenshteinDistance, LevenshteinDetailedDistance,
JaroWinklerSimilarity and HammingDistance all use equals on the
values from at.
---
.../text/similarity/DamerauLevenshteinDistance.java | 8 +++++---
.../similarity/DamerauLevenshteinDistanceTest.java | 20 ++++++++++++++++++--
2 files changed, 23 insertions(+), 5 deletions(-)
diff --git
a/src/main/java/org/apache/commons/text/similarity/DamerauLevenshteinDistance.java
b/src/main/java/org/apache/commons/text/similarity/DamerauLevenshteinDistance.java
index b266c1ca..68a55f5c 100644
---
a/src/main/java/org/apache/commons/text/similarity/DamerauLevenshteinDistance.java
+++
b/src/main/java/org/apache/commons/text/similarity/DamerauLevenshteinDistance.java
@@ -16,6 +16,8 @@
*/
package org.apache.commons.text.similarity;
+import java.util.Objects;
+
/**
* An algorithm for measuring the difference between two character sequences
using the
* <a
href="https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance";>Damerau-Levenshtein
Distance</a>.
@@ -32,7 +34,7 @@ public class DamerauLevenshteinDistance implements
EditDistance<Integer> {
private static <E> int calculateCost(final SimilarityInput<E> left, final
SimilarityInput<E> right, final int leftIndex, final int rightIndex,
final int[] curr, final int[] prev, final int[] prevPrev) {
- final int cost = left.at(leftIndex - 1) == right.at(rightIndex - 1) ?
0 : 1;
+ final int cost = Objects.equals(left.at(leftIndex - 1),
right.at(rightIndex - 1)) ? 0 : 1;
// Select cheapest operation
int value = Math.min(
Math.min(
@@ -44,8 +46,8 @@ public class DamerauLevenshteinDistance implements
EditDistance<Integer> {
// Check if adjacent characters are the same -> transpose if cheaper
if (leftIndex > 1
&& rightIndex > 1
- && left.at(leftIndex - 1) == right.at(rightIndex - 2)
- && left.at(leftIndex - 2) == right.at(rightIndex - 1)) {
+ && Objects.equals(left.at(leftIndex - 1), right.at(rightIndex
- 2))
+ && Objects.equals(left.at(leftIndex - 2), right.at(rightIndex
- 1))) {
// Use cost here, to properly handle two subsequent equal letters
value = Math.min(value, prevPrev[rightIndex - 2] + cost);
}
diff --git
a/src/test/java/org/apache/commons/text/similarity/DamerauLevenshteinDistanceTest.java
b/src/test/java/org/apache/commons/text/similarity/DamerauLevenshteinDistanceTest.java
index 65f664bb..a532ba31 100644
---
a/src/test/java/org/apache/commons/text/similarity/DamerauLevenshteinDistanceTest.java
+++
b/src/test/java/org/apache/commons/text/similarity/DamerauLevenshteinDistanceTest.java
@@ -77,7 +77,14 @@ public class DamerauLevenshteinDistanceTest {
Arguments.of("xyxyxyxyxy", "yxyxyxyxyx", 4, 2),
Arguments.of("aaaaabbbbbccccc", "cccccbbbbbaaaaa", 5, -1),
Arguments.of("thequickbrownfoxjumpsoverthelazydog",
"thequickbrownfoxjumpsovrethelazydog", 1, 1),
- Arguments.of("antidisestablishmentarianism",
"antidisestablishmentarianisn", 3, 1)
+ Arguments.of("antidisestablishmentarianism",
"antidisestablishmentarianisn", 3, 1),
+ // Non-ASCII characters are outside the Character.valueOf
cache, so identical inputs must still measure zero.
+ Arguments.of("caf\u00e9", "caf\u00e9", 1, 0),
+ Arguments.of("\u4f60\u597d", "\u4f60\u597d", 1, 0),
+ Arguments.of("na\u00efve", "na\u00efve", 1, 0),
+ // Transposing two adjacent non-ASCII characters costs one
edit, exactly as it does for ASCII.
+ Arguments.of("caf\u00e9\u00e8", "caf\u00e8\u00e9", 1, 1),
+ Arguments.of("\u4f60\u597d", "\u597d\u4f60", 1, 1)
);
}
@@ -123,7 +130,16 @@ public class DamerauLevenshteinDistanceTest {
Arguments.of("xyxyxyxyxy", "yxyxyxyxyx", 2),
Arguments.of("aaaaabbbbbccccc", "cccccbbbbbaaaaa", 10),
Arguments.of("thequickbrownfoxjumpsoverthelazydog",
"thequickbrownfoxjumpsovrethelazydog", 1),
- Arguments.of("antidisestablishmentarianism",
"antidisestablishmentarianisn", 1)
+ Arguments.of("antidisestablishmentarianism",
"antidisestablishmentarianisn", 1),
+ // Non-ASCII characters are outside the Character.valueOf
cache, so identical inputs must still measure zero.
+ Arguments.of("caf\u00e9", "caf\u00e9", 0),
+ Arguments.of("\u4f60\u597d", "\u4f60\u597d", 0),
+ Arguments.of("na\u00efve", "na\u00efve", 0),
+ Arguments.of("\ud83d\ude00", "\ud83d\ude00", 0),
+ // Transposing two adjacent non-ASCII characters costs one
edit, exactly as it does for ASCII.
+ Arguments.of("caf\u00e9\u00e8", "caf\u00e8\u00e9", 1),
+ Arguments.of("\u4f60\u597d", "\u597d\u4f60", 1),
+ Arguments.of("\u00e9x", "x\u00e9", 1)
);
}
