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