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 2016/11/09 07:33:13 UTC
[1/5] [text] TEXT-10 A more complex Levenshtein distance
Repository: commons-text
Updated Branches:
refs/heads/master 4168de224 -> 0622f5a80
TEXT-10 A more complex 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/02168c1f
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/02168c1f
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/02168c1f
Branch: refs/heads/master
Commit: 02168c1f6c8e8c5d231203831eccea591de4c2a4
Parents: ad2c0bf
Author: drajakumar <dr...@paypal.com>
Authored: Fri Oct 14 17:48:12 2016 +0530
Committer: drajakumar <dr...@paypal.com>
Committed: Fri Oct 14 17:48:12 2016 +0530
----------------------------------------------------------------------
.../similarity/LevenshteinDetailedDistance.java | 530 +++++++++++++++++++
.../text/similarity/LevenshteinResults.java | 76 +++
.../LevenshteinDetailedDistanceTest.java | 354 +++++++++++++
3 files changed, 960 insertions(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/02168c1f/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java b/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java
new file mode 100644
index 0000000..8511058
--- /dev/null
+++ b/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java
@@ -0,0 +1,530 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.text.similarity;
+
+import java.util.Arrays;
+
+/**
+ * An algorithm for measuring the difference between two character sequences.
+ *
+ * <p>
+ * This is the number of changes needed to change one sequence into another,
+ * where each change is a single character modification (deletion, insertion
+ * or substitution).
+ * </p>
+ *
+ */
+public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResults> {
+
+
+ /**
+ * Default instance.
+ */
+ private static final LevenshteinDetailedDistance DEFAULT_INSTANCE = new LevenshteinDetailedDistance();
+
+ /**
+ * Threshold.
+ */
+ private final Integer threshold;
+
+ /**
+ * <p>
+ * This returns the default instance that uses a version
+ * of the algorithm that does not use a threshold parameter.
+ * </p>
+ *
+ * @see LevenshteinDetailedDistance#getDefaultInstance()
+ */
+ public LevenshteinDetailedDistance() {
+ this(null);
+ }
+
+ /**
+ * <p>
+ * If the threshold is not null, distance calculations will be limited to a maximum length.
+ * If the threshold is null, the unlimited version of the algorithm will be used.
+ * </p>
+ *
+ * @param threshold
+ * If this is null then distances calculations will not be limited.
+ * This may not be negative.
+ */
+ public LevenshteinDetailedDistance(final Integer threshold) {
+ if (threshold != null && threshold < 0) {
+ throw new IllegalArgumentException("Threshold must not be negative");
+ }
+ this.threshold = threshold;
+ }
+
+ /**
+ * <p>Find the Levenshtein distance between two Strings.</p>
+ *
+ * <p>A higher score indicates a greater distance.</p>
+ *
+ * <p>The previous implementation of the Levenshtein distance algorithm
+ * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
+ *
+ * <p>Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError
+ * which can occur when my Java implementation is used with very large strings.<br>
+ * This implementation of the Levenshtein distance algorithm
+ * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a></p>
+ *
+ * <pre>
+ * distance.apply(null, *) = IllegalArgumentException
+ * distance.apply(*, null) = IllegalArgumentException
+ * distance.apply("","") = 0
+ * distance.apply("","a") = 1
+ * distance.apply("aaapppp", "") = 7
+ * distance.apply("frog", "fog") = 1
+ * distance.apply("fly", "ant") = 3
+ * distance.apply("elephant", "hippo") = 7
+ * distance.apply("hippo", "elephant") = 7
+ * distance.apply("hippo", "zzzzzzzz") = 8
+ * distance.apply("hello", "hallo") = 1
+ * </pre>
+ *
+ * @param left the first string, must not be null
+ * @param right the second string, must not be null
+ * @return result distance, or -1
+ * @throws IllegalArgumentException if either String input {@code null}
+ */
+ public LevenshteinResults apply(CharSequence left, CharSequence right) {
+ if (threshold != null) {
+ return limitedCompare(left, right, threshold);
+ } else {
+ return unlimitedCompare(left, right);
+ }
+ }
+
+ /**
+ * Gets the default instance.
+ *
+ * @return the default instace
+ */
+ public static LevenshteinDetailedDistance getDefaultInstance() {
+ return DEFAULT_INSTANCE;
+ }
+
+ /**
+ * Gets the distance threshold.
+ *
+ * @return the distance threshold
+ */
+ public Integer getThreshold() {
+ return threshold;
+ }
+
+ /**
+ * Find the Levenshtein distance between two CharSequences if it's less than or
+ * equal to a given threshold.
+ *
+ * <p>
+ * This implementation follows from Algorithms on Strings, Trees and
+ * Sequences by Dan Gusfield and Chas Emerick's implementation of the
+ * Levenshtein distance algorithm from <a
+ * href="http://www.merriampark.com/ld.htm"
+ * >http://www.merriampark.com/ld.htm</a>
+ * </p>
+ *
+ * <pre>
+ * limitedCompare(null, *, *) = IllegalArgumentException
+ * limitedCompare(*, null, *) = IllegalArgumentException
+ * limitedCompare(*, *, -1) = IllegalArgumentException
+ * limitedCompare("","", 0) = 0
+ * limitedCompare("aaapppp", "", 8) = 7
+ * limitedCompare("aaapppp", "", 7) = 7
+ * limitedCompare("aaapppp", "", 6)) = -1
+ * limitedCompare("elephant", "hippo", 7) = 7
+ * limitedCompare("elephant", "hippo", 6) = -1
+ * limitedCompare("hippo", "elephant", 7) = 7
+ * limitedCompare("hippo", "elephant", 6) = -1
+ * </pre>
+ *
+ * @param left the first string, must not be null
+ * @param right the second string, must not be null
+ * @param threshold the target threshold, must not be negative
+ * @return result distance, or -1
+ */
+ private static LevenshteinResults limitedCompare(CharSequence left, CharSequence right, int threshold) {
+ if (left == null || right == null) {
+ throw new IllegalArgumentException("Strings must not be null");
+ }
+ if (threshold < 0) {
+ throw new IllegalArgumentException("Threshold must not be negative");
+ }
+
+ /*
+ * This implementation only computes the distance if it's less than or
+ * equal to the threshold value, returning -1 if it's greater. The
+ * advantage is performance: unbounded distance is O(nm), but a bound of
+ * k allows us to reduce it to O(km) time by only computing a diagonal
+ * stripe of width 2k + 1 of the cost table. It is also possible to use
+ * this to compute the unbounded Levenshtein distance by starting the
+ * threshold at 1 and doubling each time until the distance is found;
+ * this is O(dm), where d is the distance.
+ *
+ * One subtlety comes from needing to ignore entries on the border of
+ * our stripe eg. p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry
+ * to the left of the leftmost member We must ignore the entry above the
+ * rightmost member
+ *
+ * Another subtlety comes from our stripe running off the matrix if the
+ * strings aren't of the same size. Since string s is always swapped to
+ * be the shorter of the two, the stripe will always run off to the
+ * upper right instead of the lower left of the matrix.
+ *
+ * As a concrete example, suppose s is of length 5, t is of length 7,
+ * and our threshold is 1. In this case we're going to walk a stripe of
+ * length 3. The matrix would look like so:
+ *
+ * <pre>
+ * 1 2 3 4 5
+ * 1 |#|#| | | |
+ * 2 |#|#|#| | |
+ * 3 | |#|#|#| |
+ * 4 | | |#|#|#|
+ * 5 | | | |#|#|
+ * 6 | | | | |#|
+ * 7 | | | | | |
+ * </pre>
+ *
+ * Note how the stripe leads off the table as there is no possible way
+ * to turn a string of length 5 into one of length 7 in edit distance of
+ * 1.
+ *
+ * Additionally, this implementation decreases memory usage by using two
+ * single-dimensional arrays and swapping them back and forth instead of
+ * allocating an entire n by m matrix. This requires a few minor
+ * changes, such as immediately returning when it's detected that the
+ * stripe has run off the matrix and initially filling the arrays with
+ * large values so that entries we don't compute are ignored.
+ *
+ * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for
+ * some discussion.
+ */
+
+ int n = left.length(); // length of left
+ int m = right.length(); // length of right
+
+ // if one string is empty, the edit distance is necessarily the length
+ // of the other
+ if (n == 0) {
+ return m <= threshold ? new LevenshteinResults(m, m, 0, 0) : new LevenshteinResults(-1, 0, 0, 0);
+ } else if (m == 0) {
+ return n <= threshold ? new LevenshteinResults(n, 0, n, 0) : new LevenshteinResults(-1, 0, 0, 0);
+ }
+
+ boolean swapped = false;
+ if (n > m) {
+ // swap the two strings to consume less memory
+ final CharSequence tmp = left;
+ left = right;
+ right = tmp;
+ n = m;
+ m = right.length();
+ swapped = true;
+ }
+
+ 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
+ int[][] matrix = new int[m+1][n+1];
+
+ //filling the first row and first column values in the matrix
+ for(int index = 0; index <=n; index++) {
+ matrix[0][index] = index;
+ }
+ for(int index = 0; index <=m; index++) {
+ matrix[index][0] = index;
+ }
+
+ // fill in starting table values
+ final int boundary = Math.min(n, threshold) + 1;
+ for (int i = 0; i < boundary; i++) {
+ p[i] = i;
+ }
+ // these fills ensure that the value above the rightmost entry of our
+ // stripe will be ignored in following loop iterations
+ Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
+ Arrays.fill(d, Integer.MAX_VALUE);
+
+ // iterates through t
+ for (int j = 1; j <= m; j++) {
+ final char rightJ = right.charAt(j - 1); // jth character of right
+ d[0] = j;
+
+ // compute stripe indices, constrain to array size
+ final int min = Math.max(1, j - threshold);
+ final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(
+ n, j + threshold);
+
+ // the stripe may lead off of the table if s and t are of different
+ // sizes
+ if (min > max) {
+ return new LevenshteinResults(-1, 0, 0, 0);
+ }
+
+ // ignore entry left of leftmost
+ if (min > 1) {
+ d[min - 1] = Integer.MAX_VALUE;
+ }
+
+ // iterates through [min, max] in s
+ for (int i = min; i <= max; i++) {
+ if (left.charAt(i - 1) == rightJ) {
+ // diagonally left and up
+ d[i] = p[i - 1];
+ } else {
+ // 1 + minimum of cell to the left, to the top, diagonally
+ // left and up
+ d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
+ }
+ matrix[j][i] = d[i];
+ }
+
+ // copy current distance counts to 'previous row' distance counts
+ tempD = p;
+ p = d;
+ d = tempD;
+ }
+
+ // if p[n] is greater than the threshold, there's no guarantee on it
+ // being the correct
+ // distance
+ if (p[n] <= threshold) {
+ return findDetailedResults(left, right, matrix, swapped);
+ }
+ return new LevenshteinResults(-1, 0, 0, 0);
+ }
+
+ /**
+ * <p>Find the Levenshtein distance between two Strings.</p>
+ *
+ * <p>A higher score indicates a greater distance.</p>
+ *
+ * <p>The previous implementation of the Levenshtein distance algorithm
+ * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
+ *
+ * <p>Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError
+ * which can occur when my Java implementation is used with very large strings.<br>
+ * This implementation of the Levenshtein distance algorithm
+ * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a></p>
+ *
+ * <pre>
+ * unlimitedCompare(null, *) = IllegalArgumentException
+ * unlimitedCompare(*, null) = IllegalArgumentException
+ * unlimitedCompare("","") = 0
+ * unlimitedCompare("","a") = 1
+ * unlimitedCompare("aaapppp", "") = 7
+ * unlimitedCompare("frog", "fog") = 1
+ * unlimitedCompare("fly", "ant") = 3
+ * unlimitedCompare("elephant", "hippo") = 7
+ * unlimitedCompare("hippo", "elephant") = 7
+ * unlimitedCompare("hippo", "zzzzzzzz") = 8
+ * unlimitedCompare("hello", "hallo") = 1
+ * </pre>
+ *
+ * @param left the first String, must not be null
+ * @param right the second String, must not be null
+ * @return result distance, or -1
+ * @throws IllegalArgumentException if either String input {@code null}
+ */
+ private static LevenshteinResults unlimitedCompare(CharSequence left, CharSequence right) {
+ if (left == null || right == null) {
+ throw new IllegalArgumentException("Strings must not be null");
+ }
+
+ /*
+ The difference between this impl. and the previous is that, rather
+ than creating and retaining a matrix of size s.length() + 1 by t.length() + 1,
+ we maintain two single-dimensional arrays of length s.length() + 1. The first, d,
+ is the 'current working' distance array that maintains the newest distance cost
+ counts as we iterate through the characters of String s. Each time we increment
+ the index of String t we are comparing, d is copied to p, the second int[]. Doing so
+ allows us to retain the previous cost counts as required by the algorithm (taking
+ the minimum of the cost count to the left, up one, and diagonally up and to the left
+ of the current cost count being calculated). (Note that the arrays aren't really
+ copied anymore, just switched...this is clearly much better than cloning an array
+ or doing a System.arraycopy() each time through the outer loop.)
+
+ Effectively, the difference between the two implementations is this one does not
+ cause an out of memory condition when calculating the LD over two very large strings.
+ */
+
+ int n = left.length(); // length of left
+ int m = right.length(); // length of right
+
+ if (n == 0) {
+ return new LevenshteinResults(m, m, 0, 0);
+ } else if (m == 0) {
+ return new LevenshteinResults(n, 0, n, 0);
+ }
+ boolean swapped = false;
+ if (n > m) {
+ // swap the input strings to consume less memory
+ final CharSequence tmp = left;
+ left = right;
+ right = tmp;
+ n = m;
+ m = right.length();
+ swapped = true;
+ }
+
+ 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
+ int[][] matrix = new int[m+1][n+1];
+
+ //filling the first row and first column values in the matrix
+ for(int index = 0; index <=n; index++) {
+ matrix[0][index] = index;
+ }
+ for(int index = 0; index <=m; index++) {
+ matrix[index][0] = index;
+ }
+
+ // indexes into strings left and right
+ int i; // iterates through left
+ int j; // iterates through right
+
+ char rightJ; // jth character of right
+
+ int cost; // cost
+ for (i = 0; i <= n; i++) {
+ p[i] = i;
+ }
+
+ for (j = 1; j <= m; j++) {
+ rightJ = right.charAt(j - 1);
+ d[0] = j;
+
+ for (i = 1; i <= n; i++) {
+ cost = left.charAt(i - 1) == rightJ ? 0 : 1;
+ // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
+ d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
+ //filling the matrix
+ matrix[j][i] = d[i];
+ }
+
+ // copy current distance counts to 'previous row' distance counts
+ tempD = p;
+ p = d;
+ d = tempD;
+ }
+ return findDetailedResults(left, right, matrix, swapped);
+ }
+
+ /**
+ * Finds count for each of the three [insert, delete, substitute] operations
+ * needed. This is based on the matrix formed based on the two character
+ * sequence.
+ *
+ * @param left
+ * character sequence which need to be converted from.
+ * @param right
+ * character sequence which need to be converted to.
+ * @param matrix
+ * two dimensional array containing
+ * @param swapped
+ * tells whether the value for left character sequence and right
+ * character sequence were swapped to save memory
+ * @return result object containing the count of insert, delete and
+ * substitute and total count needed
+ */
+ private static LevenshteinResults findDetailedResults(CharSequence left, CharSequence right, int[][] matrix,
+ boolean swapped) {
+
+ int delCount = 0;
+ int addCount = 0;
+ int subCount = 0;
+
+ int rowIndex = right.length();
+ int columnIndex = left.length();
+
+ int dataAtLeft = 0;
+ int dataAtTop = 0;
+ int dataAtDiagonal = 0;
+ int data = 0;
+ boolean deleted = false;
+ boolean added = false;
+
+ while (rowIndex >= 0 && columnIndex >= 0) {
+
+ if (columnIndex == 0) {
+ dataAtLeft = -1;
+ } else {
+ dataAtLeft = matrix[rowIndex][columnIndex - 1];
+ }
+ if (rowIndex == 0) {
+ dataAtTop = -1;
+ } else {
+ dataAtTop = matrix[rowIndex - 1][columnIndex];
+ }
+ if (rowIndex > 0 && columnIndex > 0) {
+ dataAtDiagonal = matrix[rowIndex - 1][columnIndex - 1];
+ } else {
+ dataAtDiagonal = -1;
+ }
+ if (dataAtLeft == -1 && dataAtTop == -1 && dataAtDiagonal == -1) {
+ break;
+ }
+ data = matrix[rowIndex][columnIndex];
+
+ // case in which the character at left and right are the same,
+ // in this case none of the counters will be incremented.
+ if (columnIndex > 0 && rowIndex > 0 && left.charAt(columnIndex - 1) == right.charAt(rowIndex - 1)) {
+ columnIndex--;
+ rowIndex--;
+ continue;
+ }
+
+ // handling insert and delete cases.
+ deleted = false;
+ added = false;
+ if (data - 1 == dataAtLeft && (data <= dataAtDiagonal && data <= dataAtTop)
+ || (dataAtDiagonal == -1 && dataAtTop == -1)) {
+ columnIndex--;
+ if (swapped == true) {
+ addCount++;
+ added = true;
+ } else {
+ delCount++;
+ deleted = true;
+ }
+ }
+ else if (data - 1 == dataAtTop && (data <= dataAtDiagonal && data <= dataAtLeft)
+ || (dataAtDiagonal == -1 && dataAtLeft == -1)) {
+ rowIndex--;
+ if (swapped == true) {
+ delCount++;
+ deleted = true;
+ } else {
+ addCount++;
+ added = true;
+ }
+ }
+
+ // substituted case
+ if (!added && !deleted) {
+ subCount++;
+ columnIndex--;
+ rowIndex--;
+ }
+ }
+ return new LevenshteinResults(addCount + delCount + subCount, addCount, delCount, subCount);
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/02168c1f/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java b/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
new file mode 100644
index 0000000..69e7d32
--- /dev/null
+++ b/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
@@ -0,0 +1,76 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.text.similarity;
+
+/**
+ * Container class to store Levenshtein distance between two character sequence.
+ * It also stores the count of inserts, deletions and substitutions needed to
+ * change one character sequence to other.
+ *
+ */
+public class LevenshteinResults {
+
+ private final Integer distance;
+ private final Integer insertCount;
+ private final Integer deleteCount;
+ private final Integer substituteCount;
+
+ public LevenshteinResults (final Integer distance, final Integer insertCount, final Integer deleteCount, final Integer substituteCount) {
+ this.distance = distance;
+ this.insertCount = insertCount;
+ this.deleteCount = deleteCount;
+ this.substituteCount = substituteCount;
+ }
+
+ /**
+ * gets the distance between two character sequence.
+ * @return distance between two character sequence.
+ */
+ public Integer getDistance() {
+ return distance;
+ }
+
+ /**
+ * gets the number of insertion needed to change one character sequence to
+ * other.
+ *
+ * @return insert character count.
+ */
+ public Integer getInsertCount() {
+ return insertCount;
+ }
+
+ /**
+ * gets the number of character deletion needed to change one character
+ * sequence to other.
+ *
+ * @return delete character count.
+ */
+ public Integer getDeleteCount() {
+ return deleteCount;
+ }
+
+ /**
+ * get the number of character substitution needed to change one character
+ * sequence to other.
+ *
+ * @return substitute character count.
+ */
+ public Integer getSubstituteCount() {
+ return substituteCount;
+ }
+}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/02168c1f/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java b/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
new file mode 100644
index 0000000..7ac3f8e
--- /dev/null
+++ b/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
@@ -0,0 +1,354 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.apache.commons.text.similarity;
+
+import static org.junit.Assert.assertEquals;
+
+import org.junit.Test;
+
+public class LevenshteinDetailedDistanceTest {
+
+ private static final LevenshteinDetailedDistance UNLIMITED_DISTANCE = new LevenshteinDetailedDistance();
+
+ @Test
+ public void testGetLevenshteinDetailedDistance_StringString() {
+ LevenshteinResults result = UNLIMITED_DISTANCE.apply("", "");
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("", "a");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(1, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("aaapppp", "");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(7, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("frog", "fog");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(1, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("fly", "ant");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("elephant", "hippo");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("hippo", "zzzzzzzz");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("zzzzzzzz", "hippo");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("hello", "hallo");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGetLevenshteinDetailedDistance_NullString() throws Exception {
+ UNLIMITED_DISTANCE.apply("a", null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGetLevenshteinDetailedDistance_StringNull() throws Exception {
+ UNLIMITED_DISTANCE.apply(null, "a");
+ }
+
+ @Test
+ public void testGetLevenshteinDetailedDistance_StringStringInt() {
+
+ LevenshteinResults result = new LevenshteinDetailedDistance(0).apply("", "");
+
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("aaapppp", "");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(7, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("aaapppp", "");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(7, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("aaapppp", "");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(0).apply("b", "a");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(0).apply("a", "b");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(0).apply("aa", "aa");
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("aa", "aa");
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("aaa", "bbb");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(3).apply("aaa", "bbb");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(10).apply("aaaaaa", "b");
+ assertEquals(6, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(5, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("aaapppp", "b");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(6, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(4).apply("a", "bbb");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(2, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+
+ result = new LevenshteinDetailedDistance(7).apply("aaapppp", "b");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(6, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(3).apply("a", "bbb");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(2, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("a", "bbb");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("bbb", "a");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("aaapppp", "b");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("a", "bbb");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("bbb", "a");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("12345", "1234567");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("1234567", "12345");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("frog", "fog");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(1, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(3).apply("fly", "ant");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("elephant", "hippo");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("elephant", "hippo");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("hippo", "elephant");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("hippo", "zzzzzzzz");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("zzzzzzzz", "hippo");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("hello", "hallo");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("frog", "fog");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(1, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("fly", "ant");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("elephant", "hippo");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hippo", "zzzzzzzz");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("zzzzzzzz", "hippo");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hello", "hallo");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGetLevenshteinDetailedDistance_NullStringInt() throws Exception {
+ UNLIMITED_DISTANCE.apply(null, "a");
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testGetLevenshteinDetailedDistance_StringNullInt() throws Exception {
+ UNLIMITED_DISTANCE.apply("a", null);
+ }
+
+ @Test(expected = IllegalArgumentException.class)
+ public void testConstructorWithNegativeThreshold() throws Exception {
+ new LevenshteinDetailedDistance(-1);
+ }
+}
[2/5] [text] incorporating review comment
Posted by ki...@apache.org.
incorporating review comment
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/0443ecaa
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/0443ecaa
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/0443ecaa
Branch: refs/heads/master
Commit: 0443ecaa3e418131dd4642fc40f1cc5caaeb522a
Parents: 02168c1
Author: drajakumar <dr...@paypal.com>
Authored: Tue Oct 25 21:03:47 2016 +0530
Committer: drajakumar <dr...@paypal.com>
Committed: Tue Oct 25 21:03:47 2016 +0530
----------------------------------------------------------------------
.../similarity/LevenshteinDetailedDistance.java | 212 +++----
.../text/similarity/LevenshteinResults.java | 88 +--
.../LevenshteinDetailedDistanceTest.java | 587 +++++++++----------
3 files changed, 443 insertions(+), 444 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/0443ecaa/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java b/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java
index 8511058..555404b 100644
--- a/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java
+++ b/src/main/java/org/apache/commons/text/similarity/LevenshteinDetailedDistance.java
@@ -223,9 +223,9 @@ public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResu
// if one string is empty, the edit distance is necessarily the length
// of the other
if (n == 0) {
- return m <= threshold ? new LevenshteinResults(m, m, 0, 0) : new LevenshteinResults(-1, 0, 0, 0);
+ return m <= threshold ? new LevenshteinResults(m, m, 0, 0) : new LevenshteinResults(-1, 0, 0, 0);
} else if (m == 0) {
- return n <= threshold ? new LevenshteinResults(n, 0, n, 0) : new LevenshteinResults(-1, 0, 0, 0);
+ return n <= threshold ? new LevenshteinResults(n, 0, n, 0) : new LevenshteinResults(-1, 0, 0, 0);
}
boolean swapped = false;
@@ -246,10 +246,10 @@ public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResu
//filling the first row and first column values in the matrix
for(int index = 0; index <=n; index++) {
- matrix[0][index] = index;
+ matrix[0][index] = index;
}
for(int index = 0; index <=m; index++) {
- matrix[index][0] = index;
+ matrix[index][0] = index;
}
// fill in starting table values
@@ -381,7 +381,7 @@ public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResu
right = tmp;
n = m;
m = right.length();
- swapped = true;
+ swapped = true;
}
int[] p = new int[n + 1]; //'previous' cost array, horizontally
@@ -391,10 +391,10 @@ public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResu
//filling the first row and first column values in the matrix
for(int index = 0; index <=n; index++) {
- matrix[0][index] = index;
+ matrix[0][index] = index;
}
for(int index = 0; index <=m; index++) {
- matrix[index][0] = index;
+ matrix[index][0] = index;
}
// indexes into strings left and right
@@ -428,103 +428,103 @@ public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResu
return findDetailedResults(left, right, matrix, swapped);
}
- /**
- * Finds count for each of the three [insert, delete, substitute] operations
- * needed. This is based on the matrix formed based on the two character
- * sequence.
- *
- * @param left
- * character sequence which need to be converted from.
- * @param right
- * character sequence which need to be converted to.
- * @param matrix
- * two dimensional array containing
- * @param swapped
- * tells whether the value for left character sequence and right
- * character sequence were swapped to save memory
- * @return result object containing the count of insert, delete and
- * substitute and total count needed
- */
- private static LevenshteinResults findDetailedResults(CharSequence left, CharSequence right, int[][] matrix,
- boolean swapped) {
-
- int delCount = 0;
- int addCount = 0;
- int subCount = 0;
-
- int rowIndex = right.length();
- int columnIndex = left.length();
-
- int dataAtLeft = 0;
- int dataAtTop = 0;
- int dataAtDiagonal = 0;
- int data = 0;
- boolean deleted = false;
- boolean added = false;
-
- while (rowIndex >= 0 && columnIndex >= 0) {
-
- if (columnIndex == 0) {
- dataAtLeft = -1;
- } else {
- dataAtLeft = matrix[rowIndex][columnIndex - 1];
- }
- if (rowIndex == 0) {
- dataAtTop = -1;
- } else {
- dataAtTop = matrix[rowIndex - 1][columnIndex];
- }
- if (rowIndex > 0 && columnIndex > 0) {
- dataAtDiagonal = matrix[rowIndex - 1][columnIndex - 1];
- } else {
- dataAtDiagonal = -1;
- }
- if (dataAtLeft == -1 && dataAtTop == -1 && dataAtDiagonal == -1) {
- break;
- }
- data = matrix[rowIndex][columnIndex];
-
- // case in which the character at left and right are the same,
- // in this case none of the counters will be incremented.
- if (columnIndex > 0 && rowIndex > 0 && left.charAt(columnIndex - 1) == right.charAt(rowIndex - 1)) {
- columnIndex--;
- rowIndex--;
- continue;
- }
-
- // handling insert and delete cases.
- deleted = false;
- added = false;
- if (data - 1 == dataAtLeft && (data <= dataAtDiagonal && data <= dataAtTop)
- || (dataAtDiagonal == -1 && dataAtTop == -1)) {
- columnIndex--;
- if (swapped == true) {
- addCount++;
- added = true;
- } else {
- delCount++;
- deleted = true;
- }
- }
- else if (data - 1 == dataAtTop && (data <= dataAtDiagonal && data <= dataAtLeft)
- || (dataAtDiagonal == -1 && dataAtLeft == -1)) {
- rowIndex--;
- if (swapped == true) {
- delCount++;
- deleted = true;
- } else {
- addCount++;
- added = true;
- }
- }
-
- // substituted case
- if (!added && !deleted) {
- subCount++;
- columnIndex--;
- rowIndex--;
- }
- }
- return new LevenshteinResults(addCount + delCount + subCount, addCount, delCount, subCount);
- }
+ /**
+ * Finds count for each of the three [insert, delete, substitute] operations
+ * needed. This is based on the matrix formed based on the two character
+ * sequence.
+ *
+ * @param left
+ * character sequence which need to be converted from.
+ * @param right
+ * character sequence which need to be converted to.
+ * @param matrix
+ * two dimensional array containing
+ * @param swapped
+ * tells whether the value for left character sequence and right
+ * character sequence were swapped to save memory
+ * @return result object containing the count of insert, delete and
+ * substitute and total count needed
+ */
+ private static LevenshteinResults findDetailedResults(CharSequence left, CharSequence right, int[][] matrix,
+ boolean swapped) {
+
+ int delCount = 0;
+ int addCount = 0;
+ int subCount = 0;
+
+ int rowIndex = right.length();
+ int columnIndex = left.length();
+
+ int dataAtLeft = 0;
+ int dataAtTop = 0;
+ int dataAtDiagonal = 0;
+ int data = 0;
+ boolean deleted = false;
+ boolean added = false;
+
+ while (rowIndex >= 0 && columnIndex >= 0) {
+
+ if (columnIndex == 0) {
+ dataAtLeft = -1;
+ } else {
+ dataAtLeft = matrix[rowIndex][columnIndex - 1];
+ }
+ if (rowIndex == 0) {
+ dataAtTop = -1;
+ } else {
+ dataAtTop = matrix[rowIndex - 1][columnIndex];
+ }
+ if (rowIndex > 0 && columnIndex > 0) {
+ dataAtDiagonal = matrix[rowIndex - 1][columnIndex - 1];
+ } else {
+ dataAtDiagonal = -1;
+ }
+ if (dataAtLeft == -1 && dataAtTop == -1 && dataAtDiagonal == -1) {
+ break;
+ }
+ data = matrix[rowIndex][columnIndex];
+
+ // case in which the character at left and right are the same,
+ // in this case none of the counters will be incremented.
+ if (columnIndex > 0 && rowIndex > 0 && left.charAt(columnIndex - 1) == right.charAt(rowIndex - 1)) {
+ columnIndex--;
+ rowIndex--;
+ continue;
+ }
+
+ // handling insert and delete cases.
+ deleted = false;
+ added = false;
+ if (data - 1 == dataAtLeft && (data <= dataAtDiagonal && data <= dataAtTop)
+ || (dataAtDiagonal == -1 && dataAtTop == -1)) {
+ columnIndex--;
+ if (swapped == true) {
+ addCount++;
+ added = true;
+ } else {
+ delCount++;
+ deleted = true;
+ }
+ }
+ else if (data - 1 == dataAtTop && (data <= dataAtDiagonal && data <= dataAtLeft)
+ || (dataAtDiagonal == -1 && dataAtLeft == -1)) {
+ rowIndex--;
+ if (swapped == true) {
+ delCount++;
+ deleted = true;
+ } else {
+ addCount++;
+ added = true;
+ }
+ }
+
+ // substituted case
+ if (!added && !deleted) {
+ subCount++;
+ columnIndex--;
+ rowIndex--;
+ }
+ }
+ return new LevenshteinResults(addCount + delCount + subCount, addCount, delCount, subCount);
+ }
}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/0443ecaa/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java b/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
index 69e7d32..cb190f5 100644
--- a/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
+++ b/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
@@ -24,53 +24,53 @@ package org.apache.commons.text.similarity;
*/
public class LevenshteinResults {
- private final Integer distance;
- private final Integer insertCount;
- private final Integer deleteCount;
- private final Integer substituteCount;
+ private final Integer distance;
+ private final Integer insertCount;
+ private final Integer deleteCount;
+ private final Integer substituteCount;
- public LevenshteinResults (final Integer distance, final Integer insertCount, final Integer deleteCount, final Integer substituteCount) {
- this.distance = distance;
- this.insertCount = insertCount;
- this.deleteCount = deleteCount;
- this.substituteCount = substituteCount;
- }
+ public LevenshteinResults (final Integer distance, final Integer insertCount, final Integer deleteCount, final Integer substituteCount) {
+ this.distance = distance;
+ this.insertCount = insertCount;
+ this.deleteCount = deleteCount;
+ this.substituteCount = substituteCount;
+ }
- /**
- * gets the distance between two character sequence.
- * @return distance between two character sequence.
- */
- public Integer getDistance() {
- return distance;
- }
+ /**
+ * gets the distance between two character sequence.
+ * @return distance between two character sequence.
+ */
+ public Integer getDistance() {
+ return distance;
+ }
- /**
- * gets the number of insertion needed to change one character sequence to
- * other.
- *
- * @return insert character count.
- */
- public Integer getInsertCount() {
- return insertCount;
- }
+ /**
+ * gets the number of insertion needed to change one character sequence to
+ * other.
+ *
+ * @return insert character count.
+ */
+ public Integer getInsertCount() {
+ return insertCount;
+ }
- /**
- * gets the number of character deletion needed to change one character
- * sequence to other.
- *
- * @return delete character count.
- */
- public Integer getDeleteCount() {
- return deleteCount;
- }
+ /**
+ * gets the number of character deletion needed to change one character
+ * sequence to other.
+ *
+ * @return delete character count.
+ */
+ public Integer getDeleteCount() {
+ return deleteCount;
+ }
- /**
- * get the number of character substitution needed to change one character
- * sequence to other.
- *
- * @return substitute character count.
- */
- public Integer getSubstituteCount() {
- return substituteCount;
- }
+ /**
+ * get the number of character substitution needed to change one character
+ * sequence to other.
+ *
+ * @return substitute character count.
+ */
+ public Integer getSubstituteCount() {
+ return substituteCount;
+ }
}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/0443ecaa/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java b/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
index 7ac3f8e..72efbaa 100644
--- a/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
+++ b/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
@@ -26,65 +26,65 @@ public class LevenshteinDetailedDistanceTest {
@Test
public void testGetLevenshteinDetailedDistance_StringString() {
- LevenshteinResults result = UNLIMITED_DISTANCE.apply("", "");
- assertEquals(0, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("", "a");
- assertEquals(1, (int) result.getDistance());
- assertEquals(1, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("aaapppp", "");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(7, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("frog", "fog");
- assertEquals(1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(1, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("fly", "ant");
- assertEquals(3, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(3, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("elephant", "hippo");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(3, (int) result.getDeleteCount());
- assertEquals(4, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("hippo", "elephant");
- assertEquals(7, (int) result.getDistance());
- assertEquals(3, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(4, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("hippo", "zzzzzzzz");
- assertEquals(8, (int) result.getDistance());
- assertEquals(3, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(5, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("zzzzzzzz", "hippo");
- assertEquals(8, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(3, (int) result.getDeleteCount());
- assertEquals(5, (int) result.getSubstituteCount());
-
- result = UNLIMITED_DISTANCE.apply("hello", "hallo");
- assertEquals(1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
+ LevenshteinResults result = UNLIMITED_DISTANCE.apply("", "");
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("", "a");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(1, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("aaapppp", "");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(7, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("frog", "fog");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(1, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("fly", "ant");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("elephant", "hippo");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("hippo", "zzzzzzzz");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("zzzzzzzz", "hippo");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = UNLIMITED_DISTANCE.apply("hello", "hallo");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
}
@Test(expected = IllegalArgumentException.class)
@@ -100,241 +100,240 @@ public class LevenshteinDetailedDistanceTest {
@Test
public void testGetLevenshteinDetailedDistance_StringStringInt() {
- LevenshteinResults result = new LevenshteinDetailedDistance(0).apply("", "");
-
- assertEquals(0, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(8).apply("aaapppp", "");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(7, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(7).apply("aaapppp", "");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(7, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(6).apply("aaapppp", "");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(0).apply("b", "a");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(0).apply("a", "b");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(0).apply("aa", "aa");
- assertEquals(0, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(2).apply("aa", "aa");
- assertEquals(0, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(2).apply("aaa", "bbb");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(3).apply("aaa", "bbb");
- assertEquals(3, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(3, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(10).apply("aaaaaa", "b");
- assertEquals(6, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(5, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(8).apply("aaapppp", "b");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(6, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(4).apply("a", "bbb");
- assertEquals(3, (int) result.getDistance());
- assertEquals(2, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
-
-
- result = new LevenshteinDetailedDistance(7).apply("aaapppp", "b");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(6, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(3).apply("a", "bbb");
- assertEquals(3, (int) result.getDistance());
- assertEquals(2, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(2).apply("a", "bbb");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(2).apply("bbb", "a");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(6).apply("aaapppp", "b");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(1).apply("a", "bbb");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(1).apply("bbb", "a");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(1).apply("12345", "1234567");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(1).apply("1234567", "12345");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(1).apply("frog", "fog");
- assertEquals(1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(1, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(3).apply("fly", "ant");
- assertEquals(3, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(3, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(7).apply("elephant", "hippo");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(3, (int) result.getDeleteCount());
- assertEquals(4, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(6).apply("elephant", "hippo");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(7).apply("hippo", "elephant");
- assertEquals(7, (int) result.getDistance());
- assertEquals(3, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(4, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(7).apply("hippo", "elephant");
- assertEquals(7, (int) result.getDistance());
- assertEquals(3, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(4, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(6).apply("hippo", "elephant");
- assertEquals(-1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(8).apply("hippo", "zzzzzzzz");
- assertEquals(8, (int) result.getDistance());
- assertEquals(3, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(5, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(8).apply("zzzzzzzz", "hippo");
- assertEquals(8, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(3, (int) result.getDeleteCount());
- assertEquals(5, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(1).apply("hello", "hallo");
- assertEquals(1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("frog", "fog");
- assertEquals(1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(1, (int) result.getDeleteCount());
- assertEquals(0, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("fly", "ant");
- assertEquals(3, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(3, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("elephant", "hippo");
- assertEquals(7, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(3, (int) result.getDeleteCount());
- assertEquals(4, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hippo", "elephant");
- assertEquals(7, (int) result.getDistance());
- assertEquals(3, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(4, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hippo", "zzzzzzzz");
- assertEquals(8, (int) result.getDistance());
- assertEquals(3, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(5, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("zzzzzzzz", "hippo");
- assertEquals(8, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(3, (int) result.getDeleteCount());
- assertEquals(5, (int) result.getSubstituteCount());
-
- result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hello", "hallo");
- assertEquals(1, (int) result.getDistance());
- assertEquals(0, (int) result.getInsertCount());
- assertEquals(0, (int) result.getDeleteCount());
- assertEquals(1, (int) result.getSubstituteCount());
+ LevenshteinResults result = new LevenshteinDetailedDistance(0).apply("", "");
+
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("aaapppp", "");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(7, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("aaapppp", "");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(7, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("aaapppp", "");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(0).apply("b", "a");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(0).apply("a", "b");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(0).apply("aa", "aa");
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("aa", "aa");
+ assertEquals(0, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("aaa", "bbb");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(3).apply("aaa", "bbb");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(10).apply("aaaaaa", "b");
+ assertEquals(6, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(5, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("aaapppp", "b");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(6, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(4).apply("a", "bbb");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(2, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("aaapppp", "b");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(6, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(3).apply("a", "bbb");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(2, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("a", "bbb");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(2).apply("bbb", "a");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("aaapppp", "b");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("a", "bbb");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("bbb", "a");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("12345", "1234567");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("1234567", "12345");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("frog", "fog");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(1, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(3).apply("fly", "ant");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("elephant", "hippo");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("elephant", "hippo");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(7).apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(6).apply("hippo", "elephant");
+ assertEquals(-1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("hippo", "zzzzzzzz");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(8).apply("zzzzzzzz", "hippo");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(1).apply("hello", "hallo");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("frog", "fog");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(1, (int) result.getDeleteCount());
+ assertEquals(0, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("fly", "ant");
+ assertEquals(3, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(3, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("elephant", "hippo");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hippo", "elephant");
+ assertEquals(7, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(4, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hippo", "zzzzzzzz");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(3, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("zzzzzzzz", "hippo");
+ assertEquals(8, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(3, (int) result.getDeleteCount());
+ assertEquals(5, (int) result.getSubstituteCount());
+
+ result = new LevenshteinDetailedDistance(Integer.MAX_VALUE).apply("hello", "hallo");
+ assertEquals(1, (int) result.getDistance());
+ assertEquals(0, (int) result.getInsertCount());
+ assertEquals(0, (int) result.getDeleteCount());
+ assertEquals(1, (int) result.getSubstituteCount());
}
@Test(expected = IllegalArgumentException.class)
[4/5] [text] Merge branch 'add-detailed-levenshtein-distance'
Posted by ki...@apache.org.
Merge branch 'add-detailed-levenshtein-distance'
TEXT-10: A more complex Levenshtein distance
This closes #6 from github. Thanks to Don Jeba.
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/25b07671
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/25b07671
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/25b07671
Branch: refs/heads/master
Commit: 25b07671c3e253a8b5bf80f6cc87f35690269735
Parents: 4168de2 930c07d
Author: Bruno P. Kinoshita <br...@yahoo.com.br>
Authored: Wed Nov 9 20:27:59 2016 +1300
Committer: Bruno P. Kinoshita <br...@yahoo.com.br>
Committed: Wed Nov 9 20:27:59 2016 +1300
----------------------------------------------------------------------
.../similarity/LevenshteinDetailedDistance.java | 530 +++++++++++++++++++
.../text/similarity/LevenshteinResults.java | 126 +++++
.../LevenshteinDetailedDistanceTest.java | 402 ++++++++++++++
3 files changed, 1058 insertions(+)
----------------------------------------------------------------------
[3/5] [text] incorporating review comments,
adding overloaded functions in result container class
Posted by ki...@apache.org.
incorporating review comments, adding overloaded functions in result container class
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/930c07d6
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/930c07d6
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/930c07d6
Branch: refs/heads/master
Commit: 930c07d6d7a165b1c16d2eaba702bc2074580899
Parents: 0443eca
Author: drajakumar <dr...@paypal.com>
Authored: Tue Nov 8 21:38:02 2016 +0530
Committer: drajakumar <dr...@paypal.com>
Committed: Tue Nov 8 21:38:02 2016 +0530
----------------------------------------------------------------------
.../text/similarity/LevenshteinResults.java | 52 +++++++++++++++++++-
.../LevenshteinDetailedDistanceTest.java | 49 ++++++++++++++++++
2 files changed, 100 insertions(+), 1 deletion(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/930c07d6/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java b/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
index cb190f5..12043da 100644
--- a/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
+++ b/src/main/java/org/apache/commons/text/similarity/LevenshteinResults.java
@@ -16,6 +16,8 @@
*/
package org.apache.commons.text.similarity;
+import java.util.Objects;
+
/**
* Container class to store Levenshtein distance between two character sequence.
* It also stores the count of inserts, deletions and substitutions needed to
@@ -29,7 +31,8 @@ public class LevenshteinResults {
private final Integer deleteCount;
private final Integer substituteCount;
- public LevenshteinResults (final Integer distance, final Integer insertCount, final Integer deleteCount, final Integer substituteCount) {
+ public LevenshteinResults(final Integer distance, final Integer insertCount, final Integer deleteCount,
+ final Integer substituteCount) {
this.distance = distance;
this.insertCount = insertCount;
this.deleteCount = deleteCount;
@@ -38,6 +41,7 @@ public class LevenshteinResults {
/**
* gets the distance between two character sequence.
+ *
* @return distance between two character sequence.
*/
public Integer getDistance() {
@@ -73,4 +77,50 @@ public class LevenshteinResults {
public Integer getSubstituteCount() {
return substituteCount;
}
+
+ /**
+ * indicates whether this object is equal to the object passed. It checks
+ * whether each of the individual attributes of both the objects are equal.
+ *
+ * @param o
+ * - the object to which this object needs to be compared.
+ *
+ * @return - true if this object is same as the one passed as argument,
+ * false otherwise.
+ */
+ @Override
+ public boolean equals(Object o) {
+ if (this == o)
+ return true;
+ if (o == null || getClass() != o.getClass())
+ return false;
+ LevenshteinResults result = (LevenshteinResults) o;
+ return Objects.equals(distance, result.distance) && Objects.equals(insertCount, result.insertCount)
+ && Objects.equals(deleteCount, result.deleteCount)
+ && Objects.equals(substituteCount, result.substituteCount);
+ }
+
+ /**
+ * gets the hash code value for this object. This hash code is made from
+ * individual attributes of this object.
+ *
+ * @return - hash code value of this object.
+ */
+ @Override
+ public int hashCode() {
+ return Objects.hash(distance, insertCount, deleteCount, substituteCount);
+ }
+
+ /**
+ * returns the textual representation of this object, its formed using
+ * individual attributes of this object.
+ *
+ * @return - textual representation of this object.
+ */
+ @Override
+ public String toString() {
+ return "Distance: " + distance + ", Insert: " + insertCount + ", Delete: " + deleteCount + ", Substitute: "
+ + substituteCount;
+
+ }
}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/930c07d6/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
----------------------------------------------------------------------
diff --git a/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java b/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
index 72efbaa..90d4a20 100644
--- a/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
+++ b/src/test/java/org/apache/commons/text/similarity/LevenshteinDetailedDistanceTest.java
@@ -86,6 +86,55 @@ public class LevenshteinDetailedDistanceTest {
assertEquals(0, (int) result.getDeleteCount());
assertEquals(1, (int) result.getSubstituteCount());
}
+
+ @Test
+ public void testEquals() {
+ LevenshteinDetailedDistance classBeingTested = new LevenshteinDetailedDistance();
+ LevenshteinResults actualResult = classBeingTested.apply("hello", "hallo");
+ LevenshteinResults expectedResult = new LevenshteinResults(1, 0, 0, 1);
+ assertEquals(actualResult, expectedResult);
+
+ actualResult = classBeingTested.apply("zzzzzzzz", "hippo");
+ expectedResult = new LevenshteinResults(8, 0, 3, 5);
+ assertEquals(actualResult, expectedResult);
+ assertEquals(actualResult, actualResult); //intentionally added
+
+ actualResult = classBeingTested.apply("", "");
+ expectedResult = new LevenshteinResults(0, 0, 0, 0);
+ assertEquals(actualResult, expectedResult);
+ }
+
+ @Test
+ public void testHashCode() {
+ LevenshteinDetailedDistance classBeingTested = new LevenshteinDetailedDistance();
+ LevenshteinResults actualResult = classBeingTested.apply("aaapppp", "");
+ LevenshteinResults expectedResult = new LevenshteinResults(7, 0, 7, 0);
+ assertEquals(actualResult.hashCode(), expectedResult.hashCode());
+
+ actualResult = classBeingTested.apply("frog", "fog");
+ expectedResult = new LevenshteinResults(1, 0, 1, 0);
+ assertEquals(actualResult.hashCode(), expectedResult.hashCode());
+
+ actualResult = classBeingTested.apply("elephant", "hippo");
+ expectedResult = new LevenshteinResults(7, 0, 3, 4);
+ assertEquals(actualResult.hashCode(), expectedResult.hashCode());
+ }
+
+ @Test
+ public void testToString() {
+ LevenshteinDetailedDistance classBeingTested = new LevenshteinDetailedDistance();
+ LevenshteinResults actualResult = classBeingTested.apply("fly", "ant");
+ LevenshteinResults expectedResult = new LevenshteinResults(3, 0, 0, 3);
+ assertEquals(actualResult.toString(), expectedResult.toString());
+
+ actualResult = classBeingTested.apply("hippo", "elephant");
+ expectedResult = new LevenshteinResults(7, 3, 0, 4);
+ assertEquals(actualResult.toString(), expectedResult.toString());
+
+ actualResult = classBeingTested.apply("", "a");
+ expectedResult = new LevenshteinResults(1, 1, 0, 0);
+ assertEquals(actualResult.toString(), expectedResult.toString());
+ }
@Test(expected = IllegalArgumentException.class)
public void testGetLevenshteinDetailedDistance_NullString() throws Exception {
[5/5] [text] TEXT-10 add entry in changes.xml
Posted by ki...@apache.org.
TEXT-10 add entry in changes.xml
Project: http://git-wip-us.apache.org/repos/asf/commons-text/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-text/commit/0622f5a8
Tree: http://git-wip-us.apache.org/repos/asf/commons-text/tree/0622f5a8
Diff: http://git-wip-us.apache.org/repos/asf/commons-text/diff/0622f5a8
Branch: refs/heads/master
Commit: 0622f5a8010a7ccfc18dff65c12e67501f3118a7
Parents: 25b0767
Author: Bruno P. Kinoshita <br...@yahoo.com.br>
Authored: Wed Nov 9 20:32:53 2016 +1300
Committer: Bruno P. Kinoshita <br...@yahoo.com.br>
Committed: Wed Nov 9 20:32:53 2016 +1300
----------------------------------------------------------------------
src/changes/changes.xml | 1 +
1 file changed, 1 insertion(+)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-text/blob/0622f5a8/src/changes/changes.xml
----------------------------------------------------------------------
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 05f0bb6..45825e7 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -22,6 +22,7 @@
<body>
<release version="1.0" date="tba" description="tba">
+ <action issue="TEXT-10" type="add" dev="kinow" due-to="Don Jeba">A more complex Levenshtein distance</action>
<action issue="TEXT-24" type="add" dev="chtompki">Add coveralls and Travis.ci integration</action>
<action issue="TEXT-19" type="add" dev="kinow" due-to="Eyal Allweil">Add alphabet converter</action>
<action issue="TEXT-13" type="add" dev="kinow">Create Commons Text logo</action>