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