    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 */
    017package org.apache.commons.text.similarity;
    018
    019import java.util.Arrays;
    020
    021/**
    022 * An algorithm for measuring the difference between two character sequences using the <a href="https://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein
    023 * Distance</a>.
    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 * <p>
    030 * This code has been adapted from Apache Commons Lang 3.3.
    031 * </p>
    032 *
    033 * @since 1.0
    034 * @see <a href="https://en.wikipedia.org/wiki/Levenshtein_distance">Levenshtein Distance on Wikipedia</a>
    035 * @see <a href="https://xlinux.nist.gov/dads/HTML/Levenshtein.html">Levenshtein Distance on NIST</a>
    036 */
    037public class LevenshteinDistance implements EditDistance<Integer> {
    038
    039    /**
    040     * The singleton instance.
    041     */
    042    private static final LevenshteinDistance INSTANCE = new LevenshteinDistance();
    043
    044    /**
    045     * Gets the default instance.
    046     *
    047     * @return The default instance.
    048     */
    049    public static LevenshteinDistance getDefaultInstance() {
    050        return INSTANCE;
    051    }
    052
    053    /**
    054     * Finds the Levenshtein distance between two CharSequences if it's less than or equal to a given threshold.
    055     *
    056     * <p>
    057     * This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield and Chas Emerick's implementation of the Levenshtein distance
    058     * algorithm from <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
    059     * </p>
    060     *
    061     * <pre>
    062     * limitedCompare(null, *, *)             = Throws {@link IllegalArgumentException}
    063     * limitedCompare(*, null, *)             = Throws {@link IllegalArgumentException}
    064     * limitedCompare(*, *, -1)               = Throws {@link IllegalArgumentException}
    065     * limitedCompare("","", 0)               = 0
    066     * limitedCompare("aaapppp", "", 8)       = 7
    067     * limitedCompare("aaapppp", "", 7)       = 7
    068     * limitedCompare("aaapppp", "", 6))      = -1
    069     * limitedCompare("elephant", "hippo", 7) = 7
    070     * limitedCompare("elephant", "hippo", 6) = -1
    071     * limitedCompare("hippo", "elephant", 7) = 7
    072     * limitedCompare("hippo", "elephant", 6) = -1
    073     * </pre>
    074     *
    075     * @param left      the first SimilarityInput, must not be null.
    076     * @param right     the second SimilarityInput, must not be null.
    077     * @param threshold the target threshold, must not be negative.
    078     * @return result distance, or -1
    079     */
    080    private static <E> int limitedCompare(SimilarityInput<E> left, SimilarityInput<E> right, final int threshold) { // NOPMD
    081        if (left == null || right == null) {
    082            throw new IllegalArgumentException("CharSequences must not be null");
    083        }
    084
    085        /*
    086         * 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
    087         * 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
    088         * 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
    089         * time until the distance is found; this is O(dm), where d is the distance.
    090         *
    091         * One subtlety comes from needing to ignore entries on the border of our stripe, for example,
    092         * p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry to the left
    093         * of the leftmost member We must ignore the entry above the rightmost member
    094         *
    095         * 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
    096         * shorter of the two, the stripe will always run off to the upper right instead of the lower left of the matrix.
    097         *
    098         * 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
    099         * matrix would look like so:
    100         *
    101         * <pre> 1 2 3 4 5 1 |#|#| | | | 2 |#|#|#| | | 3 | |#|#|#| | 4 | | |#|#|#| 5 | | | |#|#| 6 | | | | |#| 7 | | | | | | </pre>
    102         *
    103         * 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.
    104         *
    105         * Additionally, this implementation decreases memory usage by using two single-dimensional arrays and swapping them back and forth instead of
    106         * 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
    107         * the matrix and initially filling the arrays with large values so that entries we don't compute are ignored.
    108         *
    109         * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for some discussion.
    110         */
    111
    112        int n = left.length(); // length of left
    113        int m = right.length(); // length of right
    114
    115        // if one string is empty, the edit distance is necessarily the length
    116        // of the other
    117        if (n == 0) {
    118            return m <= threshold ? m : -1;
    119        }
    120        if (m == 0) {
    121            return n <= threshold ? n : -1;
    122        }
    123
    124        if (n > m) {
    125            // swap the two strings to consume less memory
    126            final SimilarityInput<E> tmp = left;
    127            left = right;
    128            right = tmp;
    129            n = m;
    130            m = right.length();
    131        }
    132
    133        // the edit distance cannot be less than the length difference
    134        if (m - n > threshold) {
    135            return -1;
    136        }
    137
    138        int[] p = new int[n + 1]; // 'previous' cost array, horizontally
    139        int[] d = new int[n + 1]; // cost array, horizontally
    140        int[] tempD; // placeholder to assist in swapping p and d
    141
    142        // fill in starting table values
    143        final int boundary = Math.min(n, threshold) + 1;
    144        for (int i = 0; i < boundary; i++) {
    145            p[i] = i;
    146        }
    147        // these fills ensure that the value above the rightmost entry of our
    148        // stripe will be ignored in following loop iterations
    149        Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
    150        Arrays.fill(d, Integer.MAX_VALUE);
    151
    152        // iterates through t
    153        for (int j = 1; j <= m; j++) {
    154            final E rightJ = right.at(j - 1); // jth character of right
    155            d[0] = j;
    156
    157            // compute stripe indices, constrain to array size
    158            final int min = Math.max(1, j - threshold);
    159            final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(n, j + threshold);
    160
    161            // ignore entry left of leftmost
    162            if (min > 1) {
    163                d[min - 1] = Integer.MAX_VALUE;
    164            }
    165
    166            int lowerBound = Integer.MAX_VALUE;
    167            // iterates through [min, max] in s
    168            for (int i = min; i <= max; i++) {
    169                if (left.at(i - 1).equals(rightJ)) {
    170                    // diagonally left and up
    171                    d[i] = p[i - 1];
    172                } else {
    173                    // 1 + minimum of cell to the left, to the top, diagonally
    174                    // left and up
    175                    d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
    176                }
    177                lowerBound = Math.min(lowerBound, d[i]);
    178            }
    179            // if the lower bound is greater than the threshold, then exit early
    180            if (lowerBound > threshold) {
    181                return -1;
    182            }
    183
    184            // copy current distance counts to 'previous row' distance counts
    185            tempD = p;
    186            p = d;
    187            d = tempD;
    188        }
    189
    190        // if p[n] is greater than the threshold, there's no guarantee on it
    191        // being the correct
    192        // distance
    193        if (p[n] <= threshold) {
    194            return p[n];
    195        }
    196        return -1;
    197    }
    198
    199    /**
    200     * Finds the Levenshtein distance between two Strings.
    201     *
    202     * <p>
    203     * A higher score indicates a greater distance.
    204     * </p>
    205     *
    206     * <p>
    207     * The previous implementation of the Levenshtein distance algorithm was from
    208     * <a href="https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm">
    209     * https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm</a>
    210     * </p>
    211     *
    212     * <p>
    213     * This implementation only need one single-dimensional arrays of length s.length() + 1
    214     * </p>
    215     *
    216     * <pre>
    217     * unlimitedCompare(null, *)             = Throws {@link IllegalArgumentException}
    218     * unlimitedCompare(*, null)             = Throws {@link IllegalArgumentException}
    219     * unlimitedCompare("","")               = 0
    220     * unlimitedCompare("","a")              = 1
    221     * unlimitedCompare("aaapppp", "")       = 7
    222     * unlimitedCompare("frog", "fog")       = 1
    223     * unlimitedCompare("fly", "ant")        = 3
    224     * unlimitedCompare("elephant", "hippo") = 7
    225     * unlimitedCompare("hippo", "elephant") = 7
    226     * unlimitedCompare("hippo", "zzzzzzzz") = 8
    227     * unlimitedCompare("hello", "hallo")    = 1
    228     * </pre>
    229     *
    230     * @param left  the first CharSequence, must not be null.
    231     * @param right the second CharSequence, must not be null.
    232     * @return result distance, or -1.
    233     * @throws IllegalArgumentException if either CharSequence input is {@code null}.
    234     */
    235    private static <E> int unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right) {
    236        if (left == null || right == null) {
    237            throw new IllegalArgumentException("CharSequences must not be null");
    238        }
    239        /*
    240         * This implementation use two variable to record the previous cost counts, So this implementation use less memory than previous impl.
    241         */
    242        int n = left.length(); // length of left
    243        int m = right.length(); // length of right
    244
    245        if (n == 0) {
    246            return m;
    247        }
    248        if (m == 0) {
    249            return n;
    250        }
    251        if (n > m) {
    252            // swap the input strings to consume less memory
    253            final SimilarityInput<E> tmp = left;
    254            left = right;
    255            right = tmp;
    256            n = m;
    257            m = right.length();
    258        }
    259        final int[] p = new int[n + 1];
    260        // indexes into strings left and right
    261        int i; // iterates through left
    262        int j; // iterates through right
    263        int upperLeft;
    264        int upper;
    265        E rightJ; // jth character of right
    266        int cost; // cost
    267        for (i = 0; i <= n; i++) {
    268            p[i] = i;
    269        }
    270        for (j = 1; j <= m; j++) {
    271            upperLeft = p[0];
    272            rightJ = right.at(j - 1);
    273            p[0] = j;
    274
    275            for (i = 1; i <= n; i++) {
    276                upper = p[i];
    277                cost = left.at(i - 1).equals(rightJ) ? 0 : 1;
    278                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
    279                p[i] = Math.min(Math.min(p[i - 1] + 1, p[i] + 1), upperLeft + cost);
    280                upperLeft = upper;
    281            }
    282        }
    283        return p[n];
    284    }
    285
    286    /**
    287     * Threshold.
    288     */
    289    private final Integer threshold;
    290
    291    /**
    292     * Constructs a default instance that uses a version of the algorithm that does not use a threshold parameter.
    293     *
    294     * @see LevenshteinDistance#getDefaultInstance()
    295     * @deprecated Use {@link #getDefaultInstance()}.
    296     */
    297    @Deprecated
    298    public LevenshteinDistance() {
    299        this(null);
    300    }
    301
    302    /**
    303     * Constructs a new instance. If the threshold is not null, distance calculations will be limited to a maximum length. If the threshold is null, the
    304     * unlimited version of the algorithm will be used.
    305     *
    306     * @param threshold If this is null then distances calculations will not be limited. This may not be negative.
    307     */
    308    public LevenshteinDistance(final Integer threshold) {
    309        if (threshold != null && threshold < 0) {
    310            throw new IllegalArgumentException("Threshold must not be negative");
    311        }
    312        this.threshold = threshold;
    313    }
    314
    315    /**
    316     * Computes the Levenshtein distance between two Strings.
    317     *
    318     * <p>
    319     * A higher score indicates a greater distance.
    320     * </p>
    321     *
    322     * <p>
    323     * The previous implementation of the Levenshtein distance algorithm was from
    324     * <a href="https://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a>
    325     * </p>
    326     *
    327     * <p>
    328     * Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large
    329     * strings.<br>
    330     * This implementation of the Levenshtein distance algorithm is from
    331     * <a href="https://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a>
    332     * </p>
    333     *
    334     * <pre>
    335     * distance.apply(null, *)             = Throws {@link IllegalArgumentException}
    336     * distance.apply(*, null)             = Throws {@link IllegalArgumentException}
    337     * distance.apply("","")               = 0
    338     * distance.apply("","a")              = 1
    339     * distance.apply("aaapppp", "")       = 7
    340     * distance.apply("frog", "fog")       = 1
    341     * distance.apply("fly", "ant")        = 3
    342     * distance.apply("elephant", "hippo") = 7
    343     * distance.apply("hippo", "elephant") = 7
    344     * distance.apply("hippo", "zzzzzzzz") = 8
    345     * distance.apply("hello", "hallo")    = 1
    346     * </pre>
    347     *
    348     * @param left  the first input, must not be null.
    349     * @param right the second input, must not be null.
    350     * @return result distance, or -1.
    351     * @throws IllegalArgumentException if either String input {@code null}.
    352     */
    353    @Override
    354    public Integer apply(final CharSequence left, final CharSequence right) {
    355        return apply(SimilarityInput.input(left), SimilarityInput.input(right));
    356    }
    357
    358    /**
    359     * Computes the Levenshtein distance between two inputs.
    360     *
    361     * <p>
    362     * A higher score indicates a greater distance.
    363     * </p>
    364     *
    365     * <pre>
    366     * distance.apply(null, *)             = Throws {@link IllegalArgumentException}
    367     * distance.apply(*, null)             = Throws {@link IllegalArgumentException}
    368     * distance.apply("","")               = 0
    369     * distance.apply("","a")              = 1
    370     * distance.apply("aaapppp", "")       = 7
    371     * distance.apply("frog", "fog")       = 1
    372     * distance.apply("fly", "ant")        = 3
    373     * distance.apply("elephant", "hippo") = 7
    374     * distance.apply("hippo", "elephant") = 7
    375     * distance.apply("hippo", "zzzzzzzz") = 8
    376     * distance.apply("hello", "hallo")    = 1
    377     * </pre>
    378     *
    379     * @param <E>   The type of similarity score unit.
    380     * @param left  the first input, must not be null.
    381     * @param right the second input, must not be null.
    382     * @return result distance, or -1.
    383     * @throws IllegalArgumentException if either String input {@code null}.
    384     * @since 1.13.0
    385     */
    386    public <E> Integer apply(final SimilarityInput<E> left, final SimilarityInput<E> right) {
    387        if (threshold != null) {
    388            return limitedCompare(left, right, threshold);
    389        }
    390        return unlimitedCompare(left, right);
    391    }
    392
    393    /**
    394     * Gets the distance threshold.
    395     *
    396     * @return The distance threshold.
    397     */
    398    public Integer getThreshold() {
    399        return threshold;
    400    }
    401
    402}