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