You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by ch...@apache.org on 2017/02/10 13:17:29 UTC
[16/25] [text] chore: update packages back to
org.apache.commons.text.*
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDetailedDistance.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDetailedDistance.java b/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDetailedDistance.java
deleted file mode 100644
index ec69f1d..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDetailedDistance.java
+++ /dev/null
@@ -1,519 +0,0 @@
-/*
- * 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.beta.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>
- *
- * @since 1.0
- */
-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);
- }
-
- /**
- * If the threshold is not null, distance calculations will be limited to a maximum length.
- *
- * <p>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}
- */
- @Override
- public LevenshteinResults apply(final CharSequence left, final CharSequence right) {
- if (threshold != null) {
- return limitedCompare(left, right, threshold);
- }
- 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,
- final int threshold) { //NOPMD
- 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
- final 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
- final 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(final CharSequence left,
- final CharSequence right,
- final int[][] matrix,
- final 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)) { // NOPMD
- columnIndex--;
- if (swapped) {
- addCount++;
- added = true;
- } else {
- delCount++;
- deleted = true;
- }
- } else if (data - 1 == dataAtTop && (data <= dataAtDiagonal && data <= dataAtLeft)
- || (dataAtDiagonal == -1 && dataAtLeft == -1)) { // NOPMD
- rowIndex--;
- if (swapped) {
- 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/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDistance.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDistance.java b/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDistance.java
deleted file mode 100644
index 1f7d9a8..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinDistance.java
+++ /dev/null
@@ -1,396 +0,0 @@
-/*
- * 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.beta.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>
- *
- * <p>
- * This code has been adapted from Apache Commons Lang 3.3.
- * </p>
- *
- * @since 1.0
- */
-public class LevenshteinDistance implements EditDistance<Integer> {
-
- /**
- * Default instance.
- */
- private static final LevenshteinDistance DEFAULT_INSTANCE = new LevenshteinDistance();
-
- /**
- * 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 LevenshteinDistance#getDefaultInstance()
- */
- public LevenshteinDistance() {
- 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 LevenshteinDistance(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}
- */
- @Override
- public Integer apply(final CharSequence left, final CharSequence right) {
- if (threshold != null) {
- return limitedCompare(left, right, threshold);
- }
- return unlimitedCompare(left, right);
- }
-
- /**
- * Gets the default instance.
- *
- * @return the default instace
- */
- public static LevenshteinDistance 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 int limitedCompare(CharSequence left, CharSequence right, final int threshold) { // NOPMD
- 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 ? m : -1;
- } else if (m == 0) {
- return n <= threshold ? n : -1;
- }
-
- if (n > m) {
- // swap the two strings to consume less memory
- final CharSequence tmp = left;
- left = right;
- right = tmp;
- n = m;
- m = right.length();
- }
-
- 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
-
- // 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 -1;
- }
-
- // 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]);
- }
- }
-
- // 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 p[n];
- }
- return -1;
- }
-
- /**
- * <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="https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm">
- * https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm</a></p>
- *
- * <p>This implementation only need one single-dimensional arrays of length s.length() + 1</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 int unlimitedCompare(CharSequence left, CharSequence right) {
- if (left == null || right == null) {
- throw new IllegalArgumentException("Strings must not be null");
- }
-
- /*
- This implementation use two variable to record the previous cost counts,
- So this implementation use less memory than previous impl.
- */
-
- int n = left.length(); // length of left
- int m = right.length(); // length of right
-
- if (n == 0) {
- return m;
- } else if (m == 0) {
- return n;
- }
-
- if (n > m) {
- // swap the input strings to consume less memory
- final CharSequence tmp = left;
- left = right;
- right = tmp;
- n = m;
- m = right.length();
- }
-
- int[] p = new int[n + 1];
-
- // indexes into strings left and right
- int i; // iterates through left
- int j; // iterates through right
- int upperLeft;
- int upper;
-
- char rightJ; // jth character of right
- int cost; // cost
-
- for (i = 0; i <= n; i++) {
- p[i] = i;
- }
-
- for (j = 1; j <= m; j++) {
- upperLeft = p[0];
- rightJ = right.charAt(j - 1);
- p[0] = j;
-
- for (i = 1; i <= n; i++) {
- upper = p[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
- p[i] = Math.min(Math.min(p[i - 1] + 1, p[i] + 1), upperLeft + cost);
- upperLeft = upper;
- }
- }
-
- return p[n];
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinResults.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinResults.java b/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinResults.java
deleted file mode 100644
index 4e0c272..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/LevenshteinResults.java
+++ /dev/null
@@ -1,125 +0,0 @@
-/*
- * 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.beta.similarity;
-
-import java.util.Objects;
-
-/**
- * Container class to store Levenshtein distance between two character sequences.
- *
- * <p>Stores the count of insert, deletion and substitute operations needed to
- * change one character sequence into another.</p>
- *
- * <p>This class is immutable.</p>
- *
- * @since 1.0
- */
-public class LevenshteinResults {
- /**
- * Edit distance.
- */
- private final Integer distance;
- /**
- * Insert character count.
- */
- private final Integer insertCount;
- /**
- * Delete character count.
- */
- private final Integer deleteCount;
- /**
- * Substitute character count.
- */
- private final Integer substituteCount;
-
- /**
- * Create the results for a detailed Levenshtein distance.
- *
- * @param distance distance between two character sequences.
- * @param insertCount insert character count
- * @param deleteCount delete character count
- * @param substituteCount substitute character count
- */
- 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;
- }
-
- /**
- * Get the distance between two character sequences.
- *
- * @return distance between two character sequence
- */
- public Integer getDistance() {
- return distance;
- }
-
- /**
- * Get the number of insertion needed to change one character sequence into another.
- *
- * @return insert character count
- */
- public Integer getInsertCount() {
- return insertCount;
- }
-
- /**
- * Get 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 into another.
- *
- * @return substitute character count
- */
- public Integer getSubstituteCount() {
- return substituteCount;
- }
-
- @Override
- public boolean equals(final Object o) {
- if (this == o) {
- return true;
- }
- if (o == null || getClass() != o.getClass()) {
- return false;
- }
- final 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);
- }
-
- @Override
- public int hashCode() {
- return Objects.hash(distance, insertCount, deleteCount, substituteCount);
- }
-
- @Override
- public String toString() {
- return "Distance: " + distance + ", Insert: " + insertCount + ", Delete: " + deleteCount + ", Substitute: "
- + substituteCount;
- }
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequence.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequence.java b/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequence.java
deleted file mode 100644
index b985a67..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequence.java
+++ /dev/null
@@ -1,144 +0,0 @@
-/*
- * 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.beta.similarity;
-
-/**
- * A similarity algorithm indicating the length of the longest common subsequence between two strings.
- *
- * <p>
- * The Longest common subsequence algorithm returns the length of the longest subsequence that two strings have in
- * common. Two strings that are entirely different, return a value of 0, and two strings that return a value
- * of the commonly shared length implies that the strings are completely the same in value and position.
- * <i>Note.</i> Generally this algorithm is fairly inefficient, as for length <i>m</i>, <i>n</i> of the input
- * <code>CharSequence</code>'s <code>left</code> and <code>right</code> respectively, the runtime of the
- * algorithm is <i>O(m*n)</i>.
- * </p>
- *
- * <p>
- * This implementation is based on the Longest Commons Substring algorithm
- * from <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem">
- * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem</a>.
- * </p>
- *
- * <p>For further reading see:</p>
- *
- * <p>Lothaire, M. <i>Applied combinatorics on words</i>. New York: Cambridge U Press, 2005. <b>12-13</b></p>
- *
- * @since 1.0
- */
-public class LongestCommonSubsequence implements SimilarityScore<Integer> {
-
- /**
- * Calculates longestCommonSubsequence similarity score of two <code>CharSequence</code>'s passed as
- * input.
- *
- * @param left first character sequence
- * @param right second character sequence
- * @return longestCommonSubsequenceLength
- * @throws IllegalArgumentException
- * if either String input {@code null}
- */
- @Override
- public Integer apply(final CharSequence left, final CharSequence right) {
- // Quick return for invalid inputs
- if (left == null || right == null) {
- throw new IllegalArgumentException("Inputs must not be null");
- }
- return logestCommonSubsequence(left, right).length();
- }
-
- /**
- *
- * Computes the longestCommonSubsequence between the two <code>CharSequence</code>'s passed as
- * input.
- *
- * <p>
- * Note, a substring and
- * subsequence are not necessarily the same thing. Indeed, <code>abcxyzqrs</code> and
- * <code>xyzghfm</code> have both the same common substring and subsequence, namely <code>xyz</code>. However,
- * <code>axbyczqrs</code> and <code>abcxyzqtv</code> have the longest common subsequence <code>xyzq</code> because a
- * subsequence need not have adjacent characters.
- * </p>
- *
- * <p>
- * For reference, we give the definition of a subsequence for the reader: a <i>subsequence</i> is a sequence that
- * can be derived from another sequence by deleting some elements without changing the order of the remaining
- * elements.
- * </p>
- *
- * @param left first character sequence
- * @param right second character sequence
- * @return lcsLengthArray
- * @throws IllegalArgumentException
- * if either String input {@code null}
- */
- public CharSequence logestCommonSubsequence(final CharSequence left, final CharSequence right) {
- // Quick return
- if (left == null || right == null) {
- throw new IllegalArgumentException("Inputs must not be null");
- }
- StringBuilder longestCommonSubstringArray = new StringBuilder(Math.max(left.length(), right.length()));
- int[][] lcsLengthArray = longestCommonSubstringLengthArray(left, right);
- int i = left.length() - 1;
- int j = right.length() - 1;
- int k = lcsLengthArray[left.length()][right.length()] - 1;
- while (k >= 0) {
- if (left.charAt(i) == right.charAt(j)) {
- longestCommonSubstringArray.append(left.charAt(i));
- i = i - 1;
- j = j - 1;
- k = k - 1;
- } else if (lcsLengthArray[i + 1][j] < lcsLengthArray[i][j + 1]) {
- i = i - 1;
- } else {
- j = j - 1;
- }
- }
- return longestCommonSubstringArray.reverse().toString();
- }
-
- /**
- *
- * Computes the lcsLengthArray for the sake of doing the actual lcs calculation. This is the
- * dynamic programming portion of the algorithm, and is the reason for the runtime complexity being
- * O(m*n), where m=left.length() and n=right.length().
- *
- * @param left first character sequence
- * @param right second character sequence
- * @return lcsLengthArray
- */
- public int[][] longestCommonSubstringLengthArray(final CharSequence left, final CharSequence right) {
- int[][] lcsLengthArray = new int[left.length() + 1][right.length() + 1];
- for (int i = 0; i < left.length(); i++) {
- for (int j = 0; j < right.length(); j++) {
- if (i == 0) {
- lcsLengthArray[i][j] = 0;
- }
- if (j == 0) {
- lcsLengthArray[i][j] = 0;
- }
- if (left.charAt(i) == right.charAt(j)) {
- lcsLengthArray[i + 1][j + 1] = lcsLengthArray[i][j] + 1;
- } else {
- lcsLengthArray[i + 1][j + 1] = Math.max(lcsLengthArray[i + 1][j], lcsLengthArray[i][j + 1]);
- }
- }
- }
- return lcsLengthArray;
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequenceDistance.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequenceDistance.java b/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequenceDistance.java
deleted file mode 100644
index 46a73a3..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/LongestCommonSubsequenceDistance.java
+++ /dev/null
@@ -1,64 +0,0 @@
-/*
- * 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.beta.similarity;
-
-/**
- * An edit distance algorithm based on the length of the longest common subsequence between two strings.
- *
- * <p>
- * This code is directly based upon the implementation in {@link LongestCommonSubsequence}.
- * </p>
- *
- * <p>
- * For reference see: <a href="https://en.wikipedia.org/wiki/Longest_common_subsequence_problem">
- * https://en.wikipedia.org/wiki/Longest_common_subsequence_problem</a>.
- * </p>
- *
- * <p>For further reading see:</p>
- *
- * <p>Lothaire, M. <i>Applied combinatorics on words</i>. New York: Cambridge U Press, 2005. <b>12-13</b></p>
- *
- * @since 1.0
- */
-public class LongestCommonSubsequenceDistance implements EditDistance<Integer> {
-
- /**
- * Object for calculating the longest common subsequence that we can then normalize in apply.
- */
- private final LongestCommonSubsequence longestCommonSubsequence = new LongestCommonSubsequence();
-
- /**
- * Calculates an edit distance between two <code>CharSequence</code>'s <code>left</code> and
- * <code>right</code> as: <code>left.length() + right.length() - 2 * LCS(left, right)</code>, where
- * <code>LCS</code> is given in {@link LongestCommonSubsequence#apply(CharSequence, CharSequence)}.
- *
- * @param left first character sequence
- * @param right second character sequence
- * @return distance
- * @throws IllegalArgumentException
- * if either String input {@code null}
- */
- @Override
- public Integer apply(final CharSequence left, final CharSequence right) {
- // Quick return for invalid inputs
- if (left == null || right == null) {
- throw new IllegalArgumentException("Inputs must not be null");
- }
- return left.length() + right.length() - 2 * longestCommonSubsequence.apply(left, right);
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/RegexTokenizer.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/RegexTokenizer.java b/src/main/java/org/apache/commons/text/beta/similarity/RegexTokenizer.java
deleted file mode 100644
index 014ace8..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/RegexTokenizer.java
+++ /dev/null
@@ -1,52 +0,0 @@
-/*
- * 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.beta.similarity;
-
-import java.util.ArrayList;
-import java.util.List;
-import java.util.regex.Matcher;
-import java.util.regex.Pattern;
-
-/**
- * A simple word tokenizer that utilizes regex to find words. It applies a regex
- * {@code}(\w)+{@code} over the input text to extract words from a given character
- * sequence.
- *
- * @since 1.0
- */
-class RegexTokenizer implements Tokenizer<CharSequence> {
-
- /**
- * {@inheritDoc}
- *
- * @throws IllegalArgumentException if the input text is blank
- */
- @Override
- public CharSequence[] tokenize(final CharSequence text) {
- if (text == null || text.toString().trim().equals("")) {
- throw new IllegalArgumentException("Invalid text");
- }
- final Pattern pattern = Pattern.compile("(\\w)+");
- final Matcher matcher = pattern.matcher(text.toString());
- final List<String> tokens = new ArrayList<>();
- while (matcher.find()) {
- tokens.add(matcher.group(0));
- }
- return tokens.toArray(new String[0]);
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScore.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScore.java b/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScore.java
deleted file mode 100644
index f92aefb..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScore.java
+++ /dev/null
@@ -1,63 +0,0 @@
-/*
- * 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.beta.similarity;
-
-/**
- * Interface for the concept of a string similarity score.
- *
- * <p>
- * A string similarity score is intended to have <i>some</i> of the properties of a metric, yet
- * allowing for exceptions, namely the Jaro-Winkler similarity score.
- * </p>
- * <p>
- * We Define a SimilarityScore to be a function <code>d: [X * X] -> [0, INFINITY)</code> with the
- * following properties:
- * </p>
- * <ul>
- * <li><code>d(x,y) >= 0</code>, non-negativity or separation axiom</li>
- * <li><code>d(x,y) == d(y,x)</code>, symmetry.</li>
- * </ul>
- *
- * <p>
- * Notice, these are two of the properties that contribute to d being a metric.
- * </p>
- *
- *
- * <p>
- * Further, this intended to be BiFunction<CharSequence, CharSequence, R>.
- * The <code>apply</code> method
- * accepts a pair of {@link CharSequence} parameters
- * and returns an <code>R</code> type similarity score. We have ommitted the explicit
- * statement of extending BiFunction due to it only being implemented in Java 1.8, and we
- * wish to maintain Java 1.7 compatibility.
- * </p>
- *
- * @param <R> The type of similarity score unit used by this EditDistance.
- * @since 1.0
- */
-public interface SimilarityScore<R> {
-
- /**
- * Compares two CharSequences.
- *
- * @param left the first CharSequence
- * @param right the second CharSequence
- * @return the similarity score between two CharSequences
- */
- R apply(CharSequence left, CharSequence right);
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScoreFrom.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScoreFrom.java b/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScoreFrom.java
deleted file mode 100644
index dd66f73..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/SimilarityScoreFrom.java
+++ /dev/null
@@ -1,112 +0,0 @@
-/*
- * 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.beta.similarity;
-
-/**
- * <p>
- * This stores a {@link SimilarityScore} implementation and a {@link CharSequence} "left" string.
- * The {@link #apply(CharSequence right)} method accepts the "right" string and invokes the
- * comparison function for the pair of strings.
- * </p>
- *
- * <p>
- * The following is an example which finds the most similar string:
- * </p>
- * <pre>
- * SimilarityScore<Integer> similarityScore = new LevenshteinDistance();
- * String target = "Apache";
- * SimilarityScoreFrom<Integer> similarityScoreFrom =
- * new SimilarityScoreFrom<Integer>(similarityScore, target);
- * String mostSimilar = null;
- * Integer shortestDistance = null;
- *
- * for (String test : new String[] { "Appaloosa", "a patchy", "apple" }) {
- * Integer distance = similarityScoreFrom.apply(test);
- * if (shortestDistance == null || distance < shortestDistance) {
- * shortestDistance = distance;
- * mostSimilar = test;
- * }
- * }
- *
- * System.out.println("The string most similar to \"" + target + "\" "
- * + "is \"" + mostSimilar + "\" because "
- * + "its distance is only " + shortestDistance + ".");
- * </pre>
- *
- * @param <R> This is the type of similarity score used by the SimilarityScore function.
- * @since 1.0
- */
-public class SimilarityScoreFrom<R> {
-
- /**
- * Similarity score.
- */
- private final SimilarityScore<R> similarityScore;
- /**
- * Left parameter used in distance function.
- */
- private final CharSequence left;
-
- /**
- * <p>This accepts the similarity score implementation and the "left" string.</p>
- *
- * @param similarityScore This may not be null.
- * @param left This may be null here,
- * but the SimilarityScore#compare(CharSequence left, CharSequence right)
- * implementation may not accept nulls.
- */
- public SimilarityScoreFrom(final SimilarityScore<R> similarityScore, final CharSequence left) {
- if (similarityScore == null) {
- throw new IllegalArgumentException("The edit distance may not be null.");
- }
-
- this.similarityScore = similarityScore;
- this.left = left;
- }
-
- /**
- * <p>
- * This compares "left" field against the "right" parameter
- * using the "similarity score" implementation.
- * </p>
- *
- * @param right the second CharSequence
- * @return the similarity score between two CharSequences
- */
- public R apply(final CharSequence right) {
- return similarityScore.apply(left, right);
- }
-
- /**
- * Gets the left parameter.
- *
- * @return the left parameter
- */
- public CharSequence getLeft() {
- return left;
- }
-
- /**
- * Gets the edit distance.
- *
- * @return the edit distance
- */
- public SimilarityScore<R> getSimilarityScore() {
- return similarityScore;
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/Tokenizer.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/Tokenizer.java b/src/main/java/org/apache/commons/text/beta/similarity/Tokenizer.java
deleted file mode 100644
index 08e1ecc..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/Tokenizer.java
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * 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.beta.similarity;
-
-/**
- * A tokenizer. Can produce arrays of tokens from a given type.
- *
- * @param <T> given type
- * @since 1.0
- */
-interface Tokenizer<T> {
-
- /**
- * Returns an array of tokens.
- *
- * @param text input text
- * @return array of tokens
- */
- T[] tokenize(CharSequence text);
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/similarity/package-info.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/similarity/package-info.java b/src/main/java/org/apache/commons/text/beta/similarity/package-info.java
deleted file mode 100644
index de5a313..0000000
--- a/src/main/java/org/apache/commons/text/beta/similarity/package-info.java
+++ /dev/null
@@ -1,44 +0,0 @@
-/*
- * 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.
- */
-/**
- * <p>Provides algorithms for string similarity.</p>
- *
- * <p>The algorithms that implement the EditDistance interface follow the same
- * simple principle: the more similar (closer) strings are, lower is the distance.
- * For example, the words house and hose are closer than house and trousers.</p>
- *
- * <p>The following algorithms are available at the moment:</p>
- *
- * <ul>
- * <li>{@link org.apache.commons.text.beta.similarity.CosineDistance Cosine Distance}</li>
- * <li>{@link org.apache.commons.text.beta.similarity.CosineSimilarity Cosine Similarity}</li>
- * <li>{@link org.apache.commons.text.beta.similarity.FuzzyScore Fuzzy Score}</li>
- * <li>{@link org.apache.commons.text.beta.similarity.HammingDistance Hamming Distance}</li>
- * <li>{@link org.apache.commons.text.beta.similarity.JaroWinklerDistance Jaro-Winkler Distance}</li>
- * <li>{@link org.apache.commons.text.beta.similarity.LevenshteinDistance Levenshtein Distance}</li>
- * <li>{@link org.apache.commons.text.beta.similarity.LongestCommonSubsequenceDistance
- * Longest Commons Subsequence Distance}</li>
- * </ul>
- *
- * <p>The {@link org.apache.commons.text.beta.similarity.CosineDistance Cosine Distance}
- * utilises a {@link org.apache.commons.text.beta.similarity.RegexTokenizer regular expression tokenizer (\w+)}.
- * And the {@link org.apache.commons.text.beta.similarity.LevenshteinDistance Levenshtein Distance}'s
- * behaviour can be changed to take into consideration a maximum throughput.</p>
- *
- * @since 1.0
- */
-package org.apache.commons.text.beta.similarity;
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/translate/AggregateTranslator.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/translate/AggregateTranslator.java b/src/main/java/org/apache/commons/text/beta/translate/AggregateTranslator.java
deleted file mode 100644
index 897790b..0000000
--- a/src/main/java/org/apache/commons/text/beta/translate/AggregateTranslator.java
+++ /dev/null
@@ -1,65 +0,0 @@
-/*
- * 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.beta.translate;
-
-import java.io.IOException;
-import java.io.Writer;
-import java.util.ArrayList;
-import java.util.List;
-
-/**
- * Executes a sequence of translators one after the other. Execution ends whenever
- * the first translator consumes codepoints from the input.
- *
- * @since 1.0
- */
-public class AggregateTranslator extends CharSequenceTranslator {
-
- private final List<CharSequenceTranslator> translators = new ArrayList<>();
-
- /**
- * Specify the translators to be used at creation time.
- *
- * @param translators CharSequenceTranslator array to aggregate
- */
- public AggregateTranslator(final CharSequenceTranslator... translators) {
- if (translators != null) {
- for (CharSequenceTranslator translator : translators) {
- if (translator != null) {
- this.translators.add(translator);
- }
- }
- }
- }
-
- /**
- * The first translator to consume codepoints from the input is the 'winner'.
- * Execution stops with the number of consumed codepoints being returned.
- * {@inheritDoc}
- */
- @Override
- public int translate(final CharSequence input, final int index, final Writer out) throws IOException {
- for (final CharSequenceTranslator translator : translators) {
- final int consumed = translator.translate(input, index, out);
- if(consumed != 0) {
- return consumed;
- }
- }
- return 0;
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/translate/CharSequenceTranslator.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/translate/CharSequenceTranslator.java b/src/main/java/org/apache/commons/text/beta/translate/CharSequenceTranslator.java
deleted file mode 100644
index 1025528..0000000
--- a/src/main/java/org/apache/commons/text/beta/translate/CharSequenceTranslator.java
+++ /dev/null
@@ -1,135 +0,0 @@
-/*
- * 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.beta.translate;
-
-import java.io.IOException;
-import java.io.StringWriter;
-import java.io.Writer;
-import java.util.Locale;
-
-/**
- * An API for translating text.
- * Its core use is to escape and unescape text. Because escaping and unescaping
- * is completely contextual, the API does not present two separate signatures.
- *
- * @since 1.0
- */
-public abstract class CharSequenceTranslator {
-
- static final char[] HEX_DIGITS = new char[] {'0','1','2','3','4','5','6','7','8','9','A','B','C','D','E','F'};
-
- /**
- * Translate a set of codepoints, represented by an int index into a CharSequence,
- * into another set of codepoints. The number of codepoints consumed must be returned,
- * and the only IOExceptions thrown must be from interacting with the Writer so that
- * the top level API may reliably ignore StringWriter IOExceptions.
- *
- * @param input CharSequence that is being translated
- * @param index int representing the current point of translation
- * @param out Writer to translate the text to
- * @return int count of codepoints consumed
- * @throws IOException if and only if the Writer produces an IOException
- */
- public abstract int translate(CharSequence input, int index, Writer out) throws IOException;
-
- /**
- * Helper for non-Writer usage.
- * @param input CharSequence to be translated
- * @return String output of translation
- */
- public final String translate(final CharSequence input) {
- if (input == null) {
- return null;
- }
- try {
- final StringWriter writer = new StringWriter(input.length() * 2);
- translate(input, writer);
- return writer.toString();
- } catch (final IOException ioe) {
- // this should never ever happen while writing to a StringWriter
- throw new RuntimeException(ioe);
- }
- }
-
- /**
- * Translate an input onto a Writer. This is intentionally final as its algorithm is
- * tightly coupled with the abstract method of this class.
- *
- * @param input CharSequence that is being translated
- * @param out Writer to translate the text to
- * @throws IOException if and only if the Writer produces an IOException
- */
- public final void translate(final CharSequence input, final Writer out) throws IOException {
- if (out == null) {
- throw new IllegalArgumentException("The Writer must not be null");
- }
- if (input == null) {
- return;
- }
- int pos = 0;
- final int len = input.length();
- while (pos < len) {
- final int consumed = translate(input, pos, out);
- if (consumed == 0) {
- // inlined implementation of Character.toChars(Character.codePointAt(input, pos))
- // avoids allocating temp char arrays and duplicate checks
- final char c1 = input.charAt(pos);
- out.write(c1);
- pos++;
- if (Character.isHighSurrogate(c1) && pos < len) {
- final char c2 = input.charAt(pos);
- if (Character.isLowSurrogate(c2)) {
- out.write(c2);
- pos++;
- }
- }
- continue;
- }
- // contract with translators is that they have to understand codepoints
- // and they just took care of a surrogate pair
- for (int pt = 0; pt < consumed; pt++) {
- pos += Character.charCount(Character.codePointAt(input, pos));
- }
- }
- }
-
- /**
- * Helper method to create a merger of this translator with another set of
- * translators. Useful in customizing the standard functionality.
- *
- * @param translators CharSequenceTranslator array of translators to merge with this one
- * @return CharSequenceTranslator merging this translator with the others
- */
- public final CharSequenceTranslator with(final CharSequenceTranslator... translators) {
- final CharSequenceTranslator[] newArray = new CharSequenceTranslator[translators.length + 1];
- newArray[0] = this;
- System.arraycopy(translators, 0, newArray, 1, translators.length);
- return new AggregateTranslator(newArray);
- }
-
- /**
- * <p>Returns an upper case hexadecimal <code>String</code> for the given
- * character.</p>
- *
- * @param codepoint The codepoint to convert.
- * @return An upper case hexadecimal <code>String</code>
- */
- public static String hex(final int codepoint) {
- return Integer.toHexString(codepoint).toUpperCase(Locale.ENGLISH);
- }
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/translate/CodePointTranslator.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/translate/CodePointTranslator.java b/src/main/java/org/apache/commons/text/beta/translate/CodePointTranslator.java
deleted file mode 100644
index 83386db..0000000
--- a/src/main/java/org/apache/commons/text/beta/translate/CodePointTranslator.java
+++ /dev/null
@@ -1,51 +0,0 @@
-/*
- * 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.beta.translate;
-
-import java.io.IOException;
-import java.io.Writer;
-
-/**
- * Helper subclass to CharSequenceTranslator to allow for translations that
- * will replace up to one character at a time.
- *
- * @since 1.0
- */
-public abstract class CodePointTranslator extends CharSequenceTranslator {
-
- /**
- * Implementation of translate that maps onto the abstract translate(int, Writer) method.
- * {@inheritDoc}
- */
- @Override
- public final int translate(final CharSequence input, final int index, final Writer out) throws IOException {
- final int codepoint = Character.codePointAt(input, index);
- final boolean consumed = translate(codepoint, out);
- return consumed ? 1 : 0;
- }
-
- /**
- * Translate the specified codepoint into another.
- *
- * @param codepoint int character input to translate
- * @param out Writer to optionally push the translated output to
- * @return boolean as to whether translation occurred or not
- * @throws IOException if and only if the Writer produces an IOException
- */
- public abstract boolean translate(int codepoint, Writer out) throws IOException;
-
-}
http://git-wip-us.apache.org/repos/asf/commons-text/blob/c7cf533d/src/main/java/org/apache/commons/text/beta/translate/CsvTranslators.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/text/beta/translate/CsvTranslators.java b/src/main/java/org/apache/commons/text/beta/translate/CsvTranslators.java
deleted file mode 100644
index e1dbf83..0000000
--- a/src/main/java/org/apache/commons/text/beta/translate/CsvTranslators.java
+++ /dev/null
@@ -1,82 +0,0 @@
-/*
- * 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.beta.translate;
-
-import org.apache.commons.lang3.CharUtils;
-import org.apache.commons.lang3.StringUtils;
-
-import java.io.IOException;
-import java.io.Writer;
-
-/**
- * This class holds inner classes for escaping/unescaping Comma Separated Values.
- */
-public class CsvTranslators {
-
- private static final char CSV_DELIMITER = ',';
- private static final char CSV_QUOTE = '"';
- private static final String CSV_QUOTE_STR = String.valueOf(CSV_QUOTE);
- private static final String CSV_ESCAPED_QUOTE_STR = CSV_QUOTE_STR + CSV_QUOTE_STR;
- private static final char[] CSV_SEARCH_CHARS =
- new char[] {CSV_DELIMITER, CSV_QUOTE, CharUtils.CR, CharUtils.LF};
-
- private CsvTranslators() { }
-
- /**
- * Translator for escaping Comma Separated Values.
- */
- public static class CsvEscaper extends SinglePassTranslator {
-
- @Override
- void translateWhole(final CharSequence input, final Writer out) throws IOException {
- final String inputSting = input.toString();
- if (StringUtils.containsNone(inputSting, CSV_SEARCH_CHARS)) {
- out.write(inputSting);
- } else {
- // input needs quoting
- out.write(CSV_QUOTE);
- out.write(StringUtils.replace(inputSting, CSV_QUOTE_STR, CSV_ESCAPED_QUOTE_STR));
- out.write(CSV_QUOTE);
- }
- }
- }
-
- /**
- * Translator for unescaping escaped Comma Separated Value entries.
- */
- public static class CsvUnescaper extends SinglePassTranslator {
-
- @Override
- void translateWhole(final CharSequence input, final Writer out) throws IOException {
- // is input not quoted?
- if (input.charAt(0) != CSV_QUOTE || input.charAt(input.length() - 1) != CSV_QUOTE) {
- out.write(input.toString());
- return;
- }
-
- // strip quotes
- final String quoteless = input.subSequence(1, input.length() - 1).toString();
-
- if (StringUtils.containsAny(quoteless, CSV_SEARCH_CHARS)) {
- // deal with escaped quotes; ie) ""
- out.write(StringUtils.replace(quoteless, CSV_ESCAPED_QUOTE_STR, CSV_QUOTE_STR));
- } else {
- out.write(input.toString());
- }
- }
- }
-}
\ No newline at end of file