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