LevenshteinDetailedDistance.java

  1. /*
  2.  * Licensed to the Apache Software Foundation (ASF) under one or more
  3.  * contributor license agreements.  See the NOTICE file distributed with
  4.  * this work for additional information regarding copyright ownership.
  5.  * The ASF licenses this file to You under the Apache License, Version 2.0
  6.  * (the "License"); you may not use this file except in compliance with
  7.  * the License.  You may obtain a copy of the License at
  8.  *
  9.  *      http://www.apache.org/licenses/LICENSE-2.0
  10.  *
  11.  * Unless required by applicable law or agreed to in writing, software
  12.  * distributed under the License is distributed on an "AS IS" BASIS,
  13.  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14.  * See the License for the specific language governing permissions and
  15.  * limitations under the License.
  16.  */
  17. package org.apache.commons.text.similarity;

  18. import java.util.Arrays;

  19. /**
  20.  * An algorithm for measuring the difference between two character sequences.
  21.  *
  22.  * <p>
  23.  * This is the number of changes needed to change one sequence into another,
  24.  * where each change is a single character modification (deletion, insertion
  25.  * or substitution).
  26.  * </p>
  27.  *
  28.  * @since 1.0
  29.  */
  30. public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResults> {

  31.     /**
  32.      * Singleton instance.
  33.      */
  34.     private static final LevenshteinDetailedDistance INSTANCE = new LevenshteinDetailedDistance();

  35.     /**
  36.      * Finds count for each of the three [insert, delete, substitute] operations
  37.      * needed. This is based on the matrix formed based on the two character
  38.      * sequence.
  39.      *
  40.      * @param <E> The type of similarity score unit.
  41.      * @param left character sequence which need to be converted from
  42.      * @param right character sequence which need to be converted to
  43.      * @param matrix two dimensional array containing
  44.      * @param swapped tells whether the value for left character sequence and right
  45.      *            character sequence were swapped to save memory
  46.      * @return result object containing the count of insert, delete and substitute and total count needed
  47.      */
  48.     private static <E> LevenshteinResults findDetailedResults(final SimilarityInput<E> left,
  49.                                                           final SimilarityInput<E> right,
  50.                                                           final int[][] matrix,
  51.                                                           final boolean swapped) {

  52.         int delCount = 0;
  53.         int addCount = 0;
  54.         int subCount = 0;

  55.         int rowIndex = right.length();
  56.         int columnIndex = left.length();

  57.         int dataAtLeft = 0;
  58.         int dataAtTop = 0;
  59.         int dataAtDiagonal = 0;
  60.         int data = 0;
  61.         boolean deleted = false;
  62.         boolean added = false;

  63.         while (rowIndex >= 0 && columnIndex >= 0) {

  64.             if (columnIndex == 0) {
  65.                 dataAtLeft = -1;
  66.             } else {
  67.                 dataAtLeft = matrix[rowIndex][columnIndex - 1];
  68.             }
  69.             if (rowIndex == 0) {
  70.                 dataAtTop = -1;
  71.             } else {
  72.                 dataAtTop = matrix[rowIndex - 1][columnIndex];
  73.             }
  74.             if (rowIndex > 0 && columnIndex > 0) {
  75.                 dataAtDiagonal = matrix[rowIndex - 1][columnIndex - 1];
  76.             } else {
  77.                 dataAtDiagonal = -1;
  78.             }
  79.             if (dataAtLeft == -1 && dataAtTop == -1 && dataAtDiagonal == -1) {
  80.                 break;
  81.             }
  82.             data = matrix[rowIndex][columnIndex];

  83.             // case in which the character at left and right are the same,
  84.             // in this case none of the counters will be incremented.
  85.             if (columnIndex > 0 && rowIndex > 0 && left.at(columnIndex - 1).equals(right.at(rowIndex - 1))) {
  86.                 columnIndex--;
  87.                 rowIndex--;
  88.                 continue;
  89.             }

  90.             // handling insert and delete cases.
  91.             deleted = false;
  92.             added = false;
  93.             if (data - 1 == dataAtLeft && data <= dataAtDiagonal && data <= dataAtTop
  94.                     || dataAtDiagonal == -1 && dataAtTop == -1) { // NOPMD
  95.                 columnIndex--;
  96.                 if (swapped) {
  97.                     addCount++;
  98.                     added = true;
  99.                 } else {
  100.                     delCount++;
  101.                     deleted = true;
  102.                 }
  103.             } else if (data - 1 == dataAtTop && data <= dataAtDiagonal && data <= dataAtLeft
  104.                     || dataAtDiagonal == -1 && dataAtLeft == -1) { // NOPMD
  105.                 rowIndex--;
  106.                 if (swapped) {
  107.                     delCount++;
  108.                     deleted = true;
  109.                 } else {
  110.                     addCount++;
  111.                     added = true;
  112.                 }
  113.             }

  114.             // substituted case
  115.             if (!added && !deleted) {
  116.                 subCount++;
  117.                 columnIndex--;
  118.                 rowIndex--;
  119.             }
  120.         }
  121.         return new LevenshteinResults(addCount + delCount + subCount, addCount, delCount, subCount);
  122.     }

  123.     /**
  124.      * Gets the default instance.
  125.      *
  126.      * @return The default instace
  127.      */
  128.     public static LevenshteinDetailedDistance getDefaultInstance() {
  129.         return INSTANCE;
  130.     }

  131.     /**
  132.      * Finds the Levenshtein distance between two CharSequences if it's less than or
  133.      * equal to a given threshold.
  134.      *
  135.      * <p>
  136.      * This implementation follows from Algorithms on Strings, Trees and
  137.      * Sequences by Dan Gusfield and Chas Emerick's implementation of the
  138.      * Levenshtein distance algorithm from <a
  139.      * href="http://www.merriampark.com/ld.htm"
  140.      * >http://www.merriampark.com/ld.htm</a>
  141.      * </p>
  142.      *
  143.      * <pre>
  144.      * limitedCompare(null, *, *)             = IllegalArgumentException
  145.      * limitedCompare(*, null, *)             = IllegalArgumentException
  146.      * limitedCompare(*, *, -1)               = IllegalArgumentException
  147.      * limitedCompare("","", 0)               = 0
  148.      * limitedCompare("aaapppp", "", 8)       = 7
  149.      * limitedCompare("aaapppp", "", 7)       = 7
  150.      * limitedCompare("aaapppp", "", 6))      = -1
  151.      * limitedCompare("elephant", "hippo", 7) = 7
  152.      * limitedCompare("elephant", "hippo", 6) = -1
  153.      * limitedCompare("hippo", "elephant", 7) = 7
  154.      * limitedCompare("hippo", "elephant", 6) = -1
  155.      * </pre>
  156.      *
  157.      * @param <E> The type of similarity score unit.
  158.      * @param left the first CharSequence, must not be null
  159.      * @param right the second CharSequence, must not be null
  160.      * @param threshold the target threshold, must not be negative
  161.      * @return result distance, or -1
  162.      */
  163.     private static <E> LevenshteinResults limitedCompare(SimilarityInput<E> left, SimilarityInput<E> right, final int threshold) { //NOPMD
  164.         if (left == null || right == null) {
  165.             throw new IllegalArgumentException("CharSequences must not be null");
  166.         }
  167.         if (threshold < 0) {
  168.             throw new IllegalArgumentException("Threshold must not be negative");
  169.         }

  170.         /*
  171.          * This implementation only computes the distance if it's less than or
  172.          * equal to the threshold value, returning -1 if it's greater. The
  173.          * advantage is performance: unbounded distance is O(nm), but a bound of
  174.          * k allows us to reduce it to O(km) time by only computing a diagonal
  175.          * stripe of width 2k + 1 of the cost table. It is also possible to use
  176.          * this to compute the unbounded Levenshtein distance by starting the
  177.          * threshold at 1 and doubling each time until the distance is found;
  178.          * this is O(dm), where d is the distance.
  179.          *
  180.          * One subtlety comes from needing to ignore entries on the border of
  181.          * our stripe eg. p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry
  182.          * to the left of the leftmost member We must ignore the entry above the
  183.          * rightmost member
  184.          *
  185.          * Another subtlety comes from our stripe running off the matrix if the
  186.          * strings aren't of the same size. Since string s is always swapped to
  187.          * be the shorter of the two, the stripe will always run off to the
  188.          * upper right instead of the lower left of the matrix.
  189.          *
  190.          * As a concrete example, suppose s is of length 5, t is of length 7,
  191.          * and our threshold is 1. In this case we're going to walk a stripe of
  192.          * length 3. The matrix would look like so:
  193.          *
  194.          * <pre>
  195.          *    1 2 3 4 5
  196.          * 1 |#|#| | | |
  197.          * 2 |#|#|#| | |
  198.          * 3 | |#|#|#| |
  199.          * 4 | | |#|#|#|
  200.          * 5 | | | |#|#|
  201.          * 6 | | | | |#|
  202.          * 7 | | | | | |
  203.          * </pre>
  204.          *
  205.          * Note how the stripe leads off the table as there is no possible way
  206.          * to turn a string of length 5 into one of length 7 in edit distance of
  207.          * 1.
  208.          *
  209.          * Additionally, this implementation decreases memory usage by using two
  210.          * single-dimensional arrays and swapping them back and forth instead of
  211.          * allocating an entire n by m matrix. This requires a few minor
  212.          * changes, such as immediately returning when it's detected that the
  213.          * stripe has run off the matrix and initially filling the arrays with
  214.          * large values so that entries we don't compute are ignored.
  215.          *
  216.          * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for
  217.          * some discussion.
  218.          */

  219.         int n = left.length(); // length of left
  220.         int m = right.length(); // length of right

  221.         // if one string is empty, the edit distance is necessarily the length of the other
  222.         if (n == 0) {
  223.             return m <= threshold ? new LevenshteinResults(m, m, 0, 0) : new LevenshteinResults(-1, 0, 0, 0);
  224.         }
  225.         if (m == 0) {
  226.             return n <= threshold ? new LevenshteinResults(n, 0, n, 0) : new LevenshteinResults(-1, 0, 0, 0);
  227.         }

  228.         boolean swapped = false;
  229.         if (n > m) {
  230.             // swap the two strings to consume less memory
  231.             final SimilarityInput<E> tmp = left;
  232.             left = right;
  233.             right = tmp;
  234.             n = m;
  235.             m = right.length();
  236.             swapped = true;
  237.         }

  238.         int[] p = new int[n + 1]; // 'previous' cost array, horizontally
  239.         int[] d = new int[n + 1]; // cost array, horizontally
  240.         int[] tempD; // placeholder to assist in swapping p and d
  241.         final int[][] matrix = new int[m + 1][n + 1];

  242.         //filling the first row and first column values in the matrix
  243.         for (int index = 0; index <= n; index++) {
  244.             matrix[0][index] = index;
  245.         }
  246.         for (int index = 0; index <= m; index++) {
  247.             matrix[index][0] = index;
  248.         }

  249.         // fill in starting table values
  250.         final int boundary = Math.min(n, threshold) + 1;
  251.         for (int i = 0; i < boundary; i++) {
  252.             p[i] = i;
  253.         }
  254.         // these fills ensure that the value above the rightmost entry of our
  255.         // stripe will be ignored in following loop iterations
  256.         Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
  257.         Arrays.fill(d, Integer.MAX_VALUE);

  258.         // iterates through t
  259.         for (int j = 1; j <= m; j++) {
  260.             final E rightJ = right.at(j - 1); // jth character of right
  261.             d[0] = j;

  262.             // compute stripe indices, constrain to array size
  263.             final int min = Math.max(1, j - threshold);
  264.             final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(
  265.                     n, j + threshold);

  266.             // the stripe may lead off of the table if s and t are of different sizes
  267.             if (min > max) {
  268.                 return new LevenshteinResults(-1, 0, 0, 0);
  269.             }

  270.             // ignore entry left of leftmost
  271.             if (min > 1) {
  272.                 d[min - 1] = Integer.MAX_VALUE;
  273.             }

  274.             // iterates through [min, max] in s
  275.             for (int i = min; i <= max; i++) {
  276.                 if (left.at(i - 1).equals(rightJ)) {
  277.                     // diagonally left and up
  278.                     d[i] = p[i - 1];
  279.                 } else {
  280.                     // 1 + minimum of cell to the left, to the top, diagonally left and up
  281.                     d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
  282.                 }
  283.                 matrix[j][i] = d[i];
  284.             }

  285.             // copy current distance counts to 'previous row' distance counts
  286.             tempD = p;
  287.             p = d;
  288.             d = tempD;
  289.         }

  290.         // if p[n] is greater than the threshold, there's no guarantee on it being the correct distance
  291.         if (p[n] <= threshold) {
  292.             return findDetailedResults(left, right, matrix, swapped);
  293.         }
  294.         return new LevenshteinResults(-1, 0, 0, 0);
  295.     }

  296.     /**
  297.      * Finds the Levenshtein distance between two Strings.
  298.      *
  299.      * <p>A higher score indicates a greater distance.</p>
  300.      *
  301.      * <p>The previous implementation of the Levenshtein distance algorithm
  302.      * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
  303.      *
  304.      * <p>Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError
  305.      * which can occur when my Java implementation is used with very large strings.<br>
  306.      * This implementation of the Levenshtein distance algorithm
  307.      * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a></p>
  308.      *
  309.      * <pre>
  310.      * unlimitedCompare(null, *)             = IllegalArgumentException
  311.      * unlimitedCompare(*, null)             = IllegalArgumentException
  312.      * unlimitedCompare("","")               = 0
  313.      * unlimitedCompare("","a")              = 1
  314.      * unlimitedCompare("aaapppp", "")       = 7
  315.      * unlimitedCompare("frog", "fog")       = 1
  316.      * unlimitedCompare("fly", "ant")        = 3
  317.      * unlimitedCompare("elephant", "hippo") = 7
  318.      * unlimitedCompare("hippo", "elephant") = 7
  319.      * unlimitedCompare("hippo", "zzzzzzzz") = 8
  320.      * unlimitedCompare("hello", "hallo")    = 1
  321.      * </pre>
  322.      *
  323.      * @param <E> The type of similarity score unit.
  324.      * @param left the first CharSequence, must not be null
  325.      * @param right the second CharSequence, must not be null
  326.      * @return result distance, or -1
  327.      * @throws IllegalArgumentException if either CharSequence input is {@code null}
  328.      */
  329.     private static <E> LevenshteinResults unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right) {
  330.         if (left == null || right == null) {
  331.             throw new IllegalArgumentException("CharSequences must not be null");
  332.         }

  333.         /*
  334.            The difference between this impl. and the previous is that, rather
  335.            than creating and retaining a matrix of size s.length() + 1 by t.length() + 1,
  336.            we maintain two single-dimensional arrays of length s.length() + 1.  The first, d,
  337.            is the 'current working' distance array that maintains the newest distance cost
  338.            counts as we iterate through the characters of String s.  Each time we increment
  339.            the index of String t we are comparing, d is copied to p, the second int[].  Doing so
  340.            allows us to retain the previous cost counts as required by the algorithm (taking
  341.            the minimum of the cost count to the left, up one, and diagonally up and to the left
  342.            of the current cost count being calculated).  (Note that the arrays aren't really
  343.            copied anymore, just switched...this is clearly much better than cloning an array
  344.            or doing a System.arraycopy() each time  through the outer loop.)

  345.            Effectively, the difference between the two implementations is this one does not
  346.            cause an out of memory condition when calculating the LD over two very large strings.
  347.          */

  348.         int n = left.length(); // length of left
  349.         int m = right.length(); // length of right

  350.         if (n == 0) {
  351.             return new LevenshteinResults(m, m, 0, 0);
  352.         }
  353.         if (m == 0) {
  354.             return new LevenshteinResults(n, 0, n, 0);
  355.         }
  356.         boolean swapped = false;
  357.         if (n > m) {
  358.             // swap the input strings to consume less memory
  359.             final SimilarityInput<E> tmp = left;
  360.             left = right;
  361.             right = tmp;
  362.             n = m;
  363.             m = right.length();
  364.             swapped = true;
  365.         }

  366.         int[] p = new int[n + 1]; // 'previous' cost array, horizontally
  367.         int[] d = new int[n + 1]; // cost array, horizontally
  368.         int[] tempD; //placeholder to assist in swapping p and d
  369.         final int[][] matrix = new int[m + 1][n + 1];

  370.         // filling the first row and first column values in the matrix
  371.         for (int index = 0; index <= n; index++) {
  372.             matrix[0][index] = index;
  373.         }
  374.         for (int index = 0; index <= m; index++) {
  375.             matrix[index][0] = index;
  376.         }

  377.         // indexes into strings left and right
  378.         int i; // iterates through left
  379.         int j; // iterates through right

  380.         E rightJ; // jth character of right

  381.         int cost; // cost
  382.         for (i = 0; i <= n; i++) {
  383.             p[i] = i;
  384.         }

  385.         for (j = 1; j <= m; j++) {
  386.             rightJ = right.at(j - 1);
  387.             d[0] = j;

  388.             for (i = 1; i <= n; i++) {
  389.                 cost = left.at(i - 1).equals(rightJ) ? 0 : 1;
  390.                 // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
  391.                 d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
  392.                 //filling the matrix
  393.                 matrix[j][i] = d[i];
  394.             }

  395.             // copy current distance counts to 'previous row' distance counts
  396.             tempD = p;
  397.             p = d;
  398.             d = tempD;
  399.         }
  400.         return findDetailedResults(left, right, matrix, swapped);
  401.     }

  402.     /**
  403.      * Threshold.
  404.      */
  405.     private final Integer threshold;

  406.     /**
  407.      * <p>
  408.      * This returns the default instance that uses a version
  409.      * of the algorithm that does not use a threshold parameter.
  410.      * </p>
  411.      *
  412.      * @see LevenshteinDetailedDistance#getDefaultInstance()
  413.      * @deprecated Use {@link #getDefaultInstance()}.
  414.      */
  415.     @Deprecated
  416.     public LevenshteinDetailedDistance() {
  417.         this(null);
  418.     }

  419.     /**
  420.      * If the threshold is not null, distance calculations will be limited to a maximum length.
  421.      *
  422.      * <p>If the threshold is null, the unlimited version of the algorithm will be used.</p>
  423.      *
  424.      * @param threshold If this is null then distances calculations will not be limited. This may not be negative.
  425.      */
  426.     public LevenshteinDetailedDistance(final Integer threshold) {
  427.         if (threshold != null && threshold < 0) {
  428.             throw new IllegalArgumentException("Threshold must not be negative");
  429.         }
  430.         this.threshold = threshold;
  431.     }

  432.     /**
  433.      * Computes the Levenshtein distance between two Strings.
  434.      *
  435.      * <p>A higher score indicates a greater distance.</p>
  436.      *
  437.      * <p>The previous implementation of the Levenshtein distance algorithm
  438.      * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
  439.      *
  440.      * <p>Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError
  441.      * which can occur when my Java implementation is used with very large strings.<br>
  442.      * This implementation of the Levenshtein distance algorithm
  443.      * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a></p>
  444.      *
  445.      * <pre>
  446.      * distance.apply(null, *)             = IllegalArgumentException
  447.      * distance.apply(*, null)             = IllegalArgumentException
  448.      * distance.apply("","")               = 0
  449.      * distance.apply("","a")              = 1
  450.      * distance.apply("aaapppp", "")       = 7
  451.      * distance.apply("frog", "fog")       = 1
  452.      * distance.apply("fly", "ant")        = 3
  453.      * distance.apply("elephant", "hippo") = 7
  454.      * distance.apply("hippo", "elephant") = 7
  455.      * distance.apply("hippo", "zzzzzzzz") = 8
  456.      * distance.apply("hello", "hallo")    = 1
  457.      * </pre>
  458.      *
  459.      * @param left the first input, must not be null
  460.      * @param right the second input, must not be null
  461.      * @return result distance, or -1
  462.      * @throws IllegalArgumentException if either String input {@code null}
  463.      */
  464.     @Override
  465.     public LevenshteinResults apply(final CharSequence left, final CharSequence right) {
  466.         return apply(SimilarityInput.input(left), SimilarityInput.input(right));
  467.     }

  468.     /**
  469.      * Computes the Levenshtein distance between two Strings.
  470.      *
  471.      * <p>A higher score indicates a greater distance.</p>
  472.      *
  473.      * <p>The previous implementation of the Levenshtein distance algorithm
  474.      * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
  475.      *
  476.      * <p>Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError
  477.      * which can occur when my Java implementation is used with very large strings.<br>
  478.      * This implementation of the Levenshtein distance algorithm
  479.      * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a></p>
  480.      *
  481.      * <pre>
  482.      * distance.apply(null, *)             = IllegalArgumentException
  483.      * distance.apply(*, null)             = IllegalArgumentException
  484.      * distance.apply("","")               = 0
  485.      * distance.apply("","a")              = 1
  486.      * distance.apply("aaapppp", "")       = 7
  487.      * distance.apply("frog", "fog")       = 1
  488.      * distance.apply("fly", "ant")        = 3
  489.      * distance.apply("elephant", "hippo") = 7
  490.      * distance.apply("hippo", "elephant") = 7
  491.      * distance.apply("hippo", "zzzzzzzz") = 8
  492.      * distance.apply("hello", "hallo")    = 1
  493.      * </pre>
  494.      *
  495.      * @param <E> The type of similarity score unit.
  496.      * @param left the first input, must not be null
  497.      * @param right the second input, must not be null
  498.      * @return result distance, or -1
  499.      * @throws IllegalArgumentException if either String input {@code null}
  500.      * @since 1.13.0
  501.      */
  502.     public <E> LevenshteinResults apply(final SimilarityInput<E> left, final SimilarityInput<E> right) {
  503.         if (threshold != null) {
  504.             return limitedCompare(left, right, threshold);
  505.         }
  506.         return unlimitedCompare(left, right);
  507.     }

  508.     /**
  509.      * Gets the distance threshold.
  510.      *
  511.      * @return The distance threshold
  512.      */
  513.     public Integer getThreshold() {
  514.         return threshold;
  515.     }
  516. }