    001/*
    002 * Licensed to the Apache Software Foundation (ASF) under one or more
    003 * contributor license agreements.  See the NOTICE file distributed with
    004 * this work for additional information regarding copyright ownership.
    005 * The ASF licenses this file to You under the Apache License, Version 2.0
    006 * (the "License"); you may not use this file except in compliance with
    007 * the License.  You may obtain a copy of the License at
    008 *
    009 *      https://www.apache.org/licenses/LICENSE-2.0
    010 *
    011 * Unless required by applicable law or agreed to in writing, software
    012 * distributed under the License is distributed on an "AS IS" BASIS,
    013 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    014 * See the License for the specific language governing permissions and
    015 * limitations under the License.
    016 */
    017
    018package org.apache.commons.text.similarity;
    019
    020import java.util.Arrays;
    021
    022/**
    023 * An algorithm for measuring the difference between two character sequences.
    024 *
    025 * <p>
    026 * This is the number of changes needed to change one sequence into another, where each change is a single character modification (deletion, insertion or
    027 * substitution).
    028 * </p>
    029 *
    030 * @since 1.0
    031 */
    032public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResults> {
    033
    034    /**
    035     * The singleton instance.
    036     */
    037    private static final LevenshteinDetailedDistance INSTANCE = new LevenshteinDetailedDistance();
    038
    039    /**
    040     * 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.
    041     *
    042     * @param <E>     The type of similarity score unit.
    043     * @param left    character sequence which need to be converted from.
    044     * @param right   character sequence which need to be converted to.
    045     * @param matrix  two dimensional array containing.
    046     * @param swapped tells whether the value for left character sequence and right character sequence were swapped to save memory.
    047     * @return result object containing the count of insert, delete and substitute and total count needed.
    048     */
    049    private static <E> LevenshteinResults findDetailedResults(final SimilarityInput<E> left, final SimilarityInput<E> right, final int[][] matrix,
    050            final boolean swapped) {
    051        int delCount = 0;
    052        int addCount = 0;
    053        int subCount = 0;
    054        int rowIndex = right.length();
    055        int columnIndex = left.length();
    056        int dataAtLeft = 0;
    057        int dataAtTop = 0;
    058        int dataAtDiagonal = 0;
    059        int data = 0;
    060        boolean deleted = false;
    061        boolean added = false;
    062        while (rowIndex >= 0 && columnIndex >= 0) {
    063            if (columnIndex == 0) {
    064                dataAtLeft = -1;
    065            } else {
    066                dataAtLeft = matrix[rowIndex][columnIndex - 1];
    067            }
    068            if (rowIndex == 0) {
    069                dataAtTop = -1;
    070            } else {
    071                dataAtTop = matrix[rowIndex - 1][columnIndex];
    072            }
    073            if (rowIndex > 0 && columnIndex > 0) {
    074                dataAtDiagonal = matrix[rowIndex - 1][columnIndex - 1];
    075            } else {
    076                dataAtDiagonal = -1;
    077            }
    078            if (dataAtLeft == -1 && dataAtTop == -1 && dataAtDiagonal == -1) {
    079                break;
    080            }
    081            data = matrix[rowIndex][columnIndex];
    082            // case in which the character at left and right are the same,
    083            // in this case none of the counters will be incremented.
    084            if (columnIndex > 0 && rowIndex > 0 && left.at(columnIndex - 1).equals(right.at(rowIndex - 1))) {
    085                columnIndex--;
    086                rowIndex--;
    087                continue;
    088            }
    089            // handling insert and delete cases.
    090            deleted = false;
    091            added = false;
    092            if (data - 1 == dataAtLeft && data <= dataAtDiagonal && data <= dataAtTop || dataAtDiagonal == -1 && dataAtTop == -1) { // NOPMD
    093                columnIndex--;
    094                if (swapped) {
    095                    addCount++;
    096                    added = true;
    097                } else {
    098                    delCount++;
    099                    deleted = true;
    100                }
    101            } else if (data - 1 == dataAtTop && data <= dataAtDiagonal && data <= dataAtLeft || dataAtDiagonal == -1 && dataAtLeft == -1) { // NOPMD
    102                rowIndex--;
    103                if (swapped) {
    104                    delCount++;
    105                    deleted = true;
    106                } else {
    107                    addCount++;
    108                    added = true;
    109                }
    110            }
    111            // substituted case
    112            if (!added && !deleted) {
    113                subCount++;
    114                columnIndex--;
    115                rowIndex--;
    116            }
    117        }
    118        return new LevenshteinResults(addCount + delCount + subCount, addCount, delCount, subCount);
    119    }
    120
    121    /**
    122     * Gets the default instance.
    123     *
    124     * @return The default instace
    125     */
    126    public static LevenshteinDetailedDistance getDefaultInstance() {
    127        return INSTANCE;
    128    }
    129
    130    /**
    131     * Finds the Levenshtein distance between two CharSequences if it's less than or equal to a given threshold.
    132     *
    133     * <p>
    134     * This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield and Chas Emerick's implementation of the Levenshtein distance
    135     * algorithm from <a href="https://www.merriampark.com/ld.htm" >http://www.merriampark.com/ld.htm</a>
    136     * </p>
    137     *
    138     * <pre>
    139     * limitedCompare(null, *, *)             = Throws {@link IllegalArgumentException}
    140     * limitedCompare(*, null, *)             = Throws {@link IllegalArgumentException}
    141     * limitedCompare(*, *, -1)               = Throws {@link IllegalArgumentException}
    142     * limitedCompare("","", 0)               = 0
    143     * limitedCompare("aaapppp", "", 8)       = 7
    144     * limitedCompare("aaapppp", "", 7)       = 7
    145     * limitedCompare("aaapppp", "", 6))      = -1
    146     * limitedCompare("elephant", "hippo", 7) = 7
    147     * limitedCompare("elephant", "hippo", 6) = -1
    148     * limitedCompare("hippo", "elephant", 7) = 7
    149     * limitedCompare("hippo", "elephant", 6) = -1
    150     * </pre>
    151     *
    152     * @param <E>       The type of similarity score unit.
    153     * @param left      the first CharSequence, must not be null.
    154     * @param right     the second CharSequence, must not be null.
    155     * @param threshold the target threshold, must not be negative.
    156     * @return result distance, or -1.
    157     */
    158    private static <E> LevenshteinResults limitedCompare(SimilarityInput<E> left, SimilarityInput<E> right, final int threshold) { // NOPMD
    159        if (left == null || right == null) {
    160            throw new IllegalArgumentException("CharSequences must not be null");
    161        }
    162
    163        /*
    164         * 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
    165         * 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
    166         * 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
    167         * time until the distance is found; this is O(dm), where d is the distance.
    168         *
    169         * One subtlety comes from needing to ignore entries on the border of our stripe, for example,
    170         * p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry to the left
    171         * of the leftmost member We must ignore the entry above the rightmost member
    172         *
    173         * 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
    174         * shorter of the two, the stripe will always run off to the upper right instead of the lower left of the matrix.
    175         *
    176         * 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
    177         * matrix would look like so:
    178         *
    179         * <pre> 1 2 3 4 5 1 |#|#| | | | 2 |#|#|#| | | 3 | |#|#|#| | 4 | | |#|#|#| 5 | | | |#|#| 6 | | | | |#| 7 | | | | | | </pre>
    180         *
    181         * 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.
    182         *
    183         * Additionally, this implementation decreases memory usage by using two single-dimensional arrays and swapping them back and forth instead of
    184         * 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
    185         * the matrix and initially filling the arrays with large values so that entries we don't compute are ignored.
    186         *
    187         * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for some discussion.
    188         */
    189        int n = left.length(); // length of left
    190        int m = right.length(); // length of right
    191        // if one string is empty, the edit distance is necessarily the length of the other
    192        if (n == 0) {
    193            return m <= threshold ? new LevenshteinResults(m, m, 0, 0) : new LevenshteinResults(-1, 0, 0, 0);
    194        }
    195        if (m == 0) {
    196            return n <= threshold ? new LevenshteinResults(n, 0, n, 0) : new LevenshteinResults(-1, 0, 0, 0);
    197        }
    198        boolean swapped = false;
    199        if (n > m) {
    200            // swap the two strings to consume less memory
    201            final SimilarityInput<E> tmp = left;
    202            left = right;
    203            right = tmp;
    204            n = m;
    205            m = right.length();
    206            swapped = true;
    207        }
    208        int[] p = new int[n + 1]; // 'previous' cost array, horizontally
    209        int[] d = new int[n + 1]; // cost array, horizontally
    210        int[] tempD; // placeholder to assist in swapping p and d
    211        final int[][] matrix = new int[m + 1][n + 1];
    212        // filling the first row and first column values in the matrix
    213        for (int index = 0; index <= n; index++) {
    214            matrix[0][index] = index;
    215        }
    216        for (int index = 0; index <= m; index++) {
    217            matrix[index][0] = index;
    218        }
    219        // fill in starting table values
    220        final int boundary = Math.min(n, threshold) + 1;
    221        for (int i = 0; i < boundary; i++) {
    222            p[i] = i;
    223        }
    224        // these fills ensure that the value above the rightmost entry of our
    225        // stripe will be ignored in following loop iterations
    226        Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
    227        Arrays.fill(d, Integer.MAX_VALUE);
    228        // iterates through t
    229        for (int j = 1; j <= m; j++) {
    230            final E rightJ = right.at(j - 1); // jth character of right
    231            d[0] = j;
    232            // compute stripe indices, constrain to array size
    233            final int min = Math.max(1, j - threshold);
    234            final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(n, j + threshold);
    235            // the stripe may lead off of the table if s and t are of different sizes
    236            if (min > max) {
    237                return new LevenshteinResults(-1, 0, 0, 0);
    238            }
    239            // ignore entry left of leftmost
    240            if (min > 1) {
    241                d[min - 1] = Integer.MAX_VALUE;
    242            }
    243            // iterates through [min, max] in s
    244            for (int i = min; i <= max; i++) {
    245                if (left.at(i - 1).equals(rightJ)) {
    246                    // diagonally left and up
    247                    d[i] = p[i - 1];
    248                } else {
    249                    // 1 + minimum of cell to the left, to the top, diagonally left and up
    250                    d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
    251                }
    252                matrix[j][i] = d[i];
    253            }
    254            // copy current distance counts to 'previous row' distance counts
    255            tempD = p;
    256            p = d;
    257            d = tempD;
    258        }
    259        // if p[n] is greater than the threshold, there's no guarantee on it being the correct distance
    260        if (p[n] <= threshold) {
    261            return findDetailedResults(left, right, matrix, swapped);
    262        }
    263        return new LevenshteinResults(-1, 0, 0, 0);
    264    }
    265
    266    /**
    267     * Finds the Levenshtein distance between two Strings.
    268     *
    269     * <p>
    270     * A higher score indicates a greater distance.
    271     * </p>
    272     *
    273     * <p>
    274     * The previous implementation of the Levenshtein distance algorithm was from
    275     * <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
    276     * </p>
    277     *
    278     * <p>
    279     * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
    280     * strings.<br>
    281     * This implementation of the Levenshtein distance algorithm is from
    282     * <a href="https://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
    283     * </p>
    284     *
    285     * <pre>
    286     * unlimitedCompare(null, *)             = Throws {@link IllegalArgumentException}
    287     * unlimitedCompare(*, null)             = Throws {@link IllegalArgumentException}
    288     * unlimitedCompare("","")               = 0
    289     * unlimitedCompare("","a")              = 1
    290     * unlimitedCompare("aaapppp", "")       = 7
    291     * unlimitedCompare("frog", "fog")       = 1
    292     * unlimitedCompare("fly", "ant")        = 3
    293     * unlimitedCompare("elephant", "hippo") = 7
    294     * unlimitedCompare("hippo", "elephant") = 7
    295     * unlimitedCompare("hippo", "zzzzzzzz") = 8
    296     * unlimitedCompare("hello", "hallo")    = 1
    297     * </pre>
    298     *
    299     * @param <E>   The type of similarity score unit.
    300     * @param left  the first CharSequence, must not be null.
    301     * @param right the second CharSequence, must not be null.
    302     * @return result distance, or -1.
    303     * @throws IllegalArgumentException if either CharSequence input is {@code null}.
    304     */
    305    private static <E> LevenshteinResults unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right) {
    306        if (left == null || right == null) {
    307            throw new IllegalArgumentException("CharSequences must not be null");
    308        }
    309        /*
    310         * 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
    311         * maintain two single-dimensional arrays of length s.length() + 1. The first, d, is the 'current working' distance array that maintains the newest
    312         * 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
    313         * 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
    314         * 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
    315         * switched...this is clearly much better than cloning an array or doing a System.arraycopy() each time through the outer loop.)
    316         *
    317         * Effectively, the difference between the two implementations is this one does not cause an out of memory condition when calculating the LD over two
    318         * very large strings.
    319         */
    320        int n = left.length(); // length of left
    321        int m = right.length(); // length of right
    322        if (n == 0) {
    323            return new LevenshteinResults(m, m, 0, 0);
    324        }
    325        if (m == 0) {
    326            return new LevenshteinResults(n, 0, n, 0);
    327        }
    328        boolean swapped = false;
    329        if (n > m) {
    330            // swap the input strings to consume less memory
    331            final SimilarityInput<E> tmp = left;
    332            left = right;
    333            right = tmp;
    334            n = m;
    335            m = right.length();
    336            swapped = true;
    337        }
    338        int[] p = new int[n + 1]; // 'previous' cost array, horizontally
    339        int[] d = new int[n + 1]; // cost array, horizontally
    340        int[] tempD; // placeholder to assist in swapping p and d
    341        final int[][] matrix = new int[m + 1][n + 1];
    342        // filling the first row and first column values in the matrix
    343        for (int index = 0; index <= n; index++) {
    344            matrix[0][index] = index;
    345        }
    346        for (int index = 0; index <= m; index++) {
    347            matrix[index][0] = index;
    348        }
    349        // indexes into strings left and right
    350        int i; // iterates through left
    351        int j; // iterates through right
    352        E rightJ; // jth character of right
    353        int cost; // cost
    354        for (i = 0; i <= n; i++) {
    355            p[i] = i;
    356        }
    357        for (j = 1; j <= m; j++) {
    358            rightJ = right.at(j - 1);
    359            d[0] = j;
    360            for (i = 1; i <= n; i++) {
    361                cost = left.at(i - 1).equals(rightJ) ? 0 : 1;
    362                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
    363                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
    364                // filling the matrix
    365                matrix[j][i] = d[i];
    366            }
    367            // copy current distance counts to 'previous row' distance counts
    368            tempD = p;
    369            p = d;
    370            d = tempD;
    371        }
    372        return findDetailedResults(left, right, matrix, swapped);
    373    }
    374
    375    /**
    376     * Threshold.
    377     */
    378    private final Integer threshold;
    379
    380    /**
    381     * Constructs a new instance that uses a version of the algorithm that does not use a threshold parameter.
    382     *
    383     * @see LevenshteinDetailedDistance#getDefaultInstance()
    384     * @deprecated Use {@link #getDefaultInstance()}.
    385     */
    386    @Deprecated
    387    public LevenshteinDetailedDistance() {
    388        this(null);
    389    }
    390
    391    /**
    392     * Constructs a new instance for a threshold.
    393     * <p>
    394     * If the threshold is not null, distance calculations will be limited to a maximum length.
    395     * </p>
    396     * <p>
    397     * If the threshold is null, the unlimited version of the algorithm will be used.
    398     * </p>
    399     *
    400     * @param threshold If this is null then distances calculations will not be limited. This may not be negative.
    401     */
    402    public LevenshteinDetailedDistance(final Integer threshold) {
    403        if (threshold != null && threshold < 0) {
    404            throw new IllegalArgumentException("Threshold must not be negative");
    405        }
    406        this.threshold = threshold;
    407    }
    408
    409    /**
    410     * Computes the Levenshtein distance between two Strings.
    411     *
    412     * <p>
    413     * A higher score indicates a greater distance.
    414     * </p>
    415     *
    416     * <p>
    417     * The previous implementation of the Levenshtein distance algorithm was from
    418     * <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
    419     * </p>
    420     *
    421     * <p>
    422     * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
    423     * strings.<br>
    424     * This implementation of the Levenshtein distance algorithm is from
    425     * <a href="https://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
    426     * </p>
    427     *
    428     * <pre>
    429     * distance.apply(null, *)             = Throws {@link IllegalArgumentException}
    430     * distance.apply(*, null)             = Throws {@link IllegalArgumentException}
    431     * distance.apply("","")               = 0
    432     * distance.apply("","a")              = 1
    433     * distance.apply("aaapppp", "")       = 7
    434     * distance.apply("frog", "fog")       = 1
    435     * distance.apply("fly", "ant")        = 3
    436     * distance.apply("elephant", "hippo") = 7
    437     * distance.apply("hippo", "elephant") = 7
    438     * distance.apply("hippo", "zzzzzzzz") = 8
    439     * distance.apply("hello", "hallo")    = 1
    440     * </pre>
    441     *
    442     * @param left  the first input, must not be null.
    443     * @param right the second input, must not be null.
    444     * @return result distance, or -1.
    445     * @throws IllegalArgumentException if either String input {@code null}.
    446     */
    447    @Override
    448    public LevenshteinResults apply(final CharSequence left, final CharSequence right) {
    449        return apply(SimilarityInput.input(left), SimilarityInput.input(right));
    450    }
    451
    452    /**
    453     * Computes the Levenshtein distance between two Strings.
    454     *
    455     * <p>
    456     * A higher score indicates a greater distance.
    457     * </p>
    458     *
    459     * <p>
    460     * The previous implementation of the Levenshtein distance algorithm was from
    461     * <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
    462     * </p>
    463     *
    464     * <p>
    465     * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
    466     * strings.<br>
    467     * This implementation of the Levenshtein distance algorithm is from
    468     * <a href="https://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
    469     * </p>
    470     *
    471     * <pre>
    472     * distance.apply(null, *)             = Throws {@link IllegalArgumentException}
    473     * distance.apply(*, null)             = Throws {@link IllegalArgumentException}
    474     * distance.apply("","")               = 0
    475     * distance.apply("","a")              = 1
    476     * distance.apply("aaapppp", "")       = 7
    477     * distance.apply("frog", "fog")       = 1
    478     * distance.apply("fly", "ant")        = 3
    479     * distance.apply("elephant", "hippo") = 7
    480     * distance.apply("hippo", "elephant") = 7
    481     * distance.apply("hippo", "zzzzzzzz") = 8
    482     * distance.apply("hello", "hallo")    = 1
    483     * </pre>
    484     *
    485     * @param <E>   The type of similarity score unit.
    486     * @param left  the first input, must not be null.
    487     * @param right the second input, must not be null.
    488     * @return result distance, or -1.
    489     * @throws IllegalArgumentException if either String input {@code null}.
    490     * @since 1.13.0
    491     */
    492    public <E> LevenshteinResults apply(final SimilarityInput<E> left, final SimilarityInput<E> right) {
    493        if (threshold != null) {
    494            return limitedCompare(left, right, threshold);
    495        }
    496        return unlimitedCompare(left, right);
    497    }
    498
    499    /**
    500     * Gets the distance threshold.
    501     *
    502     * @return The distance threshold.
    503     */
    504    public Integer getThreshold() {
    505        return threshold;
    506    }
    507}