    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 * @since 1.0
    031 */
    032public class LevenshteinDetailedDistance implements EditDistance<LevenshteinResults> {
    033
    034    /**
    035     * Singleton instance.
    036     */
    037    private static final LevenshteinDetailedDistance INSTANCE = new LevenshteinDetailedDistance();
    038
    039    /**
    040     * Finds count for each of the three [insert, delete, substitute] operations
    041     * needed. This is based on the matrix formed based on the two character
    042     * sequence.
    043     *
    044     * @param left character sequence which need to be converted from
    045     * @param right character sequence which need to be converted to
    046     * @param matrix two dimensional array containing
    047     * @param swapped tells whether the value for left character sequence and right
    048     *            character sequence were swapped to save memory
    049     * @return result object containing the count of insert, delete and substitute and total count needed
    050     */
    051    private static LevenshteinResults findDetailedResults(final CharSequence left,
    052                                                          final CharSequence right,
    053                                                          final int[][] matrix,
    054                                                          final boolean swapped) {
    055
    056        int delCount = 0;
    057        int addCount = 0;
    058        int subCount = 0;
    059
    060        int rowIndex = right.length();
    061        int columnIndex = left.length();
    062
    063        int dataAtLeft = 0;
    064        int dataAtTop = 0;
    065        int dataAtDiagonal = 0;
    066        int data = 0;
    067        boolean deleted = false;
    068        boolean added = false;
    069
    070        while (rowIndex >= 0 && columnIndex >= 0) {
    071
    072            if (columnIndex == 0) {
    073                dataAtLeft = -1;
    074            } else {
    075                dataAtLeft = matrix[rowIndex][columnIndex - 1];
    076            }
    077            if (rowIndex == 0) {
    078                dataAtTop = -1;
    079            } else {
    080                dataAtTop = matrix[rowIndex - 1][columnIndex];
    081            }
    082            if (rowIndex > 0 && columnIndex > 0) {
    083                dataAtDiagonal = matrix[rowIndex - 1][columnIndex - 1];
    084            } else {
    085                dataAtDiagonal = -1;
    086            }
    087            if (dataAtLeft == -1 && dataAtTop == -1 && dataAtDiagonal == -1) {
    088                break;
    089            }
    090            data = matrix[rowIndex][columnIndex];
    091
    092            // case in which the character at left and right are the same,
    093            // in this case none of the counters will be incremented.
    094            if (columnIndex > 0 && rowIndex > 0 && left.charAt(columnIndex - 1) == right.charAt(rowIndex - 1)) {
    095                columnIndex--;
    096                rowIndex--;
    097                continue;
    098            }
    099
    100            // handling insert and delete cases.
    101            deleted = false;
    102            added = false;
    103            if (data - 1 == dataAtLeft && data <= dataAtDiagonal && data <= dataAtTop
    104                    || dataAtDiagonal == -1 && dataAtTop == -1) { // NOPMD
    105                columnIndex--;
    106                if (swapped) {
    107                    addCount++;
    108                    added = true;
    109                } else {
    110                    delCount++;
    111                    deleted = true;
    112                }
    113            } else if (data - 1 == dataAtTop && data <= dataAtDiagonal && data <= dataAtLeft
    114                    || dataAtDiagonal == -1 && dataAtLeft == -1) { // NOPMD
    115                rowIndex--;
    116                if (swapped) {
    117                    delCount++;
    118                    deleted = true;
    119                } else {
    120                    addCount++;
    121                    added = true;
    122                }
    123            }
    124
    125            // substituted case
    126            if (!added && !deleted) {
    127                subCount++;
    128                columnIndex--;
    129                rowIndex--;
    130            }
    131        }
    132        return new LevenshteinResults(addCount + delCount + subCount, addCount, delCount, subCount);
    133    }
    134
    135    /**
    136     * Gets the default instance.
    137     *
    138     * @return The default instace
    139     */
    140    public static LevenshteinDetailedDistance getDefaultInstance() {
    141        return INSTANCE;
    142    }
    143
    144    /**
    145     * Finds the Levenshtein distance between two CharSequences if it's less than or
    146     * equal to a given threshold.
    147     *
    148     * <p>
    149     * This implementation follows from Algorithms on Strings, Trees and
    150     * Sequences by Dan Gusfield and Chas Emerick's implementation of the
    151     * Levenshtein distance algorithm from <a
    152     * href="http://www.merriampark.com/ld.htm"
    153     * >http://www.merriampark.com/ld.htm</a>
    154     * </p>
    155     *
    156     * <pre>
    157     * limitedCompare(null, *, *)             = IllegalArgumentException
    158     * limitedCompare(*, null, *)             = IllegalArgumentException
    159     * limitedCompare(*, *, -1)               = IllegalArgumentException
    160     * limitedCompare("","", 0)               = 0
    161     * limitedCompare("aaapppp", "", 8)       = 7
    162     * limitedCompare("aaapppp", "", 7)       = 7
    163     * limitedCompare("aaapppp", "", 6))      = -1
    164     * limitedCompare("elephant", "hippo", 7) = 7
    165     * limitedCompare("elephant", "hippo", 6) = -1
    166     * limitedCompare("hippo", "elephant", 7) = 7
    167     * limitedCompare("hippo", "elephant", 6) = -1
    168     * </pre>
    169     *
    170     * @param left the first CharSequence, must not be null
    171     * @param right the second CharSequence, must not be null
    172     * @param threshold the target threshold, must not be negative
    173     * @return result distance, or -1
    174     */
    175    private static LevenshteinResults limitedCompare(CharSequence left,
    176                                                     CharSequence right,
    177                                                     final int threshold) { //NOPMD
    178        if (left == null || right == null) {
    179            throw new IllegalArgumentException("CharSequences must not be null");
    180        }
    181        if (threshold < 0) {
    182            throw new IllegalArgumentException("Threshold must not be negative");
    183        }
    184
    185        /*
    186         * This implementation only computes the distance if it's less than or
    187         * equal to the threshold value, returning -1 if it's greater. The
    188         * advantage is performance: unbounded distance is O(nm), but a bound of
    189         * k allows us to reduce it to O(km) time by only computing a diagonal
    190         * stripe of width 2k + 1 of the cost table. It is also possible to use
    191         * this to compute the unbounded Levenshtein distance by starting the
    192         * threshold at 1 and doubling each time until the distance is found;
    193         * this is O(dm), where d is the distance.
    194         *
    195         * One subtlety comes from needing to ignore entries on the border of
    196         * our stripe eg. p[] = |#|#|#|* d[] = *|#|#|#| We must ignore the entry
    197         * to the left of the leftmost member We must ignore the entry above the
    198         * rightmost member
    199         *
    200         * Another subtlety comes from our stripe running off the matrix if the
    201         * strings aren't of the same size. Since string s is always swapped to
    202         * be the shorter of the two, the stripe will always run off to the
    203         * upper right instead of the lower left of the matrix.
    204         *
    205         * As a concrete example, suppose s is of length 5, t is of length 7,
    206         * and our threshold is 1. In this case we're going to walk a stripe of
    207         * length 3. The matrix would look like so:
    208         *
    209         * <pre>
    210         *    1 2 3 4 5
    211         * 1 |#|#| | | |
    212         * 2 |#|#|#| | |
    213         * 3 | |#|#|#| |
    214         * 4 | | |#|#|#|
    215         * 5 | | | |#|#|
    216         * 6 | | | | |#|
    217         * 7 | | | | | |
    218         * </pre>
    219         *
    220         * Note how the stripe leads off the table as there is no possible way
    221         * to turn a string of length 5 into one of length 7 in edit distance of
    222         * 1.
    223         *
    224         * Additionally, this implementation decreases memory usage by using two
    225         * single-dimensional arrays and swapping them back and forth instead of
    226         * allocating an entire n by m matrix. This requires a few minor
    227         * changes, such as immediately returning when it's detected that the
    228         * stripe has run off the matrix and initially filling the arrays with
    229         * large values so that entries we don't compute are ignored.
    230         *
    231         * See Algorithms on Strings, Trees and Sequences by Dan Gusfield for
    232         * some discussion.
    233         */
    234
    235        int n = left.length(); // length of left
    236        int m = right.length(); // length of right
    237
    238        // if one string is empty, the edit distance is necessarily the length of the other
    239        if (n == 0) {
    240            return m <= threshold ? new LevenshteinResults(m, m, 0, 0) : new LevenshteinResults(-1, 0, 0, 0);
    241        }
    242        if (m == 0) {
    243            return n <= threshold ? new LevenshteinResults(n, 0, n, 0) : new LevenshteinResults(-1, 0, 0, 0);
    244        }
    245
    246        boolean swapped = false;
    247        if (n > m) {
    248            // swap the two strings to consume less memory
    249            final CharSequence tmp = left;
    250            left = right;
    251            right = tmp;
    252            n = m;
    253            m = right.length();
    254            swapped = true;
    255        }
    256
    257        int[] p = new int[n + 1]; // 'previous' cost array, horizontally
    258        int[] d = new int[n + 1]; // cost array, horizontally
    259        int[] tempD; // placeholder to assist in swapping p and d
    260        final int[][] matrix = new int[m + 1][n + 1];
    261
    262        //filling the first row and first column values in the matrix
    263        for (int index = 0; index <= n; index++) {
    264            matrix[0][index] = index;
    265        }
    266        for (int index = 0; index <= m; index++) {
    267            matrix[index][0] = index;
    268        }
    269
    270        // fill in starting table values
    271        final int boundary = Math.min(n, threshold) + 1;
    272        for (int i = 0; i < boundary; i++) {
    273            p[i] = i;
    274        }
    275        // these fills ensure that the value above the rightmost entry of our
    276        // stripe will be ignored in following loop iterations
    277        Arrays.fill(p, boundary, p.length, Integer.MAX_VALUE);
    278        Arrays.fill(d, Integer.MAX_VALUE);
    279
    280        // iterates through t
    281        for (int j = 1; j <= m; j++) {
    282            final char rightJ = right.charAt(j - 1); // jth character of right
    283            d[0] = j;
    284
    285            // compute stripe indices, constrain to array size
    286            final int min = Math.max(1, j - threshold);
    287            final int max = j > Integer.MAX_VALUE - threshold ? n : Math.min(
    288                    n, j + threshold);
    289
    290            // the stripe may lead off of the table if s and t are of different sizes
    291            if (min > max) {
    292                return new LevenshteinResults(-1, 0, 0, 0);
    293            }
    294
    295            // ignore entry left of leftmost
    296            if (min > 1) {
    297                d[min - 1] = Integer.MAX_VALUE;
    298            }
    299
    300            // iterates through [min, max] in s
    301            for (int i = min; i <= max; i++) {
    302                if (left.charAt(i - 1) == rightJ) {
    303                    // diagonally left and up
    304                    d[i] = p[i - 1];
    305                } else {
    306                    // 1 + minimum of cell to the left, to the top, diagonally left and up
    307                    d[i] = 1 + Math.min(Math.min(d[i - 1], p[i]), p[i - 1]);
    308                }
    309                matrix[j][i] = d[i];
    310            }
    311
    312            // copy current distance counts to 'previous row' distance counts
    313            tempD = p;
    314            p = d;
    315            d = tempD;
    316        }
    317
    318        // if p[n] is greater than the threshold, there's no guarantee on it being the correct distance
    319        if (p[n] <= threshold) {
    320            return findDetailedResults(left, right, matrix, swapped);
    321        }
    322        return new LevenshteinResults(-1, 0, 0, 0);
    323    }
    324
    325    /**
    326     * Finds the Levenshtein distance between two Strings.
    327     *
    328     * <p>A higher score indicates a greater distance.</p>
    329     *
    330     * <p>The previous implementation of the Levenshtein distance algorithm
    331     * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
    332     *
    333     * <p>Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError
    334     * which can occur when my Java implementation is used with very large strings.<br>
    335     * This implementation of the Levenshtein distance algorithm
    336     * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a></p>
    337     *
    338     * <pre>
    339     * unlimitedCompare(null, *)             = IllegalArgumentException
    340     * unlimitedCompare(*, null)             = IllegalArgumentException
    341     * unlimitedCompare("","")               = 0
    342     * unlimitedCompare("","a")              = 1
    343     * unlimitedCompare("aaapppp", "")       = 7
    344     * unlimitedCompare("frog", "fog")       = 1
    345     * unlimitedCompare("fly", "ant")        = 3
    346     * unlimitedCompare("elephant", "hippo") = 7
    347     * unlimitedCompare("hippo", "elephant") = 7
    348     * unlimitedCompare("hippo", "zzzzzzzz") = 8
    349     * unlimitedCompare("hello", "hallo")    = 1
    350     * </pre>
    351     *
    352     * @param left the first CharSequence, must not be null
    353     * @param right the second CharSequence, must not be null
    354     * @return result distance, or -1
    355     * @throws IllegalArgumentException if either CharSequence input is {@code null}
    356     */
    357    private static LevenshteinResults unlimitedCompare(CharSequence left, CharSequence right) {
    358        if (left == null || right == null) {
    359            throw new IllegalArgumentException("CharSequences must not be null");
    360        }
    361
    362        /*
    363           The difference between this impl. and the previous is that, rather
    364           than creating and retaining a matrix of size s.length() + 1 by t.length() + 1,
    365           we maintain two single-dimensional arrays of length s.length() + 1.  The first, d,
    366           is the 'current working' distance array that maintains the newest distance cost
    367           counts as we iterate through the characters of String s.  Each time we increment
    368           the index of String t we are comparing, d is copied to p, the second int[].  Doing so
    369           allows us to retain the previous cost counts as required by the algorithm (taking
    370           the minimum of the cost count to the left, up one, and diagonally up and to the left
    371           of the current cost count being calculated).  (Note that the arrays aren't really
    372           copied anymore, just switched...this is clearly much better than cloning an array
    373           or doing a System.arraycopy() each time  through the outer loop.)
    374
    375           Effectively, the difference between the two implementations is this one does not
    376           cause an out of memory condition when calculating the LD over two very large strings.
    377         */
    378
    379        int n = left.length(); // length of left
    380        int m = right.length(); // length of right
    381
    382        if (n == 0) {
    383            return new LevenshteinResults(m, m, 0, 0);
    384        }
    385        if (m == 0) {
    386            return new LevenshteinResults(n, 0, n, 0);
    387        }
    388        boolean swapped = false;
    389        if (n > m) {
    390            // swap the input strings to consume less memory
    391            final CharSequence tmp = left;
    392            left = right;
    393            right = tmp;
    394            n = m;
    395            m = right.length();
    396            swapped = true;
    397        }
    398
    399        int[] p = new int[n + 1]; // 'previous' cost array, horizontally
    400        int[] d = new int[n + 1]; // cost array, horizontally
    401        int[] tempD; //placeholder to assist in swapping p and d
    402        final int[][] matrix = new int[m + 1][n + 1];
    403
    404        // filling the first row and first column values in the matrix
    405        for (int index = 0; index <= n; index++) {
    406            matrix[0][index] = index;
    407        }
    408        for (int index = 0; index <= m; index++) {
    409            matrix[index][0] = index;
    410        }
    411
    412        // indexes into strings left and right
    413        int i; // iterates through left
    414        int j; // iterates through right
    415
    416        char rightJ; // jth character of right
    417
    418        int cost; // cost
    419        for (i = 0; i <= n; i++) {
    420            p[i] = i;
    421        }
    422
    423        for (j = 1; j <= m; j++) {
    424            rightJ = right.charAt(j - 1);
    425            d[0] = j;
    426
    427            for (i = 1; i <= n; i++) {
    428                cost = left.charAt(i - 1) == rightJ ? 0 : 1;
    429                // minimum of cell to the left+1, to the top+1, diagonally left and up +cost
    430                d[i] = Math.min(Math.min(d[i - 1] + 1, p[i] + 1), p[i - 1] + cost);
    431                //filling the matrix
    432                matrix[j][i] = d[i];
    433            }
    434
    435            // copy current distance counts to 'previous row' distance counts
    436            tempD = p;
    437            p = d;
    438            d = tempD;
    439        }
    440        return findDetailedResults(left, right, matrix, swapped);
    441    }
    442
    443    /**
    444     * Threshold.
    445     */
    446    private final Integer threshold;
    447
    448    /**
    449     * <p>
    450     * This returns the default instance that uses a version
    451     * of the algorithm that does not use a threshold parameter.
    452     * </p>
    453     *
    454     * @see LevenshteinDetailedDistance#getDefaultInstance()
    455     */
    456    public LevenshteinDetailedDistance() {
    457        this(null);
    458    }
    459
    460    /**
    461     * If the threshold is not null, distance calculations will be limited to a maximum length.
    462     *
    463     * <p>If the threshold is null, the unlimited version of the algorithm will be used.</p>
    464     *
    465     * @param threshold If this is null then distances calculations will not be limited. This may not be negative.
    466     */
    467    public LevenshteinDetailedDistance(final Integer threshold) {
    468        if (threshold != null && threshold < 0) {
    469            throw new IllegalArgumentException("Threshold must not be negative");
    470        }
    471        this.threshold = threshold;
    472    }
    473
    474    /**
    475     * Finds the Levenshtein distance between two Strings.
    476     *
    477     * <p>A higher score indicates a greater distance.</p>
    478     *
    479     * <p>The previous implementation of the Levenshtein distance algorithm
    480     * was from <a href="http://www.merriampark.com/ld.htm">http://www.merriampark.com/ld.htm</a></p>
    481     *
    482     * <p>Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError
    483     * which can occur when my Java implementation is used with very large strings.<br>
    484     * This implementation of the Levenshtein distance algorithm
    485     * is from <a href="http://www.merriampark.com/ldjava.htm">http://www.merriampark.com/ldjava.htm</a></p>
    486     *
    487     * <pre>
    488     * distance.apply(null, *)             = IllegalArgumentException
    489     * distance.apply(*, null)             = IllegalArgumentException
    490     * distance.apply("","")               = 0
    491     * distance.apply("","a")              = 1
    492     * distance.apply("aaapppp", "")       = 7
    493     * distance.apply("frog", "fog")       = 1
    494     * distance.apply("fly", "ant")        = 3
    495     * distance.apply("elephant", "hippo") = 7
    496     * distance.apply("hippo", "elephant") = 7
    497     * distance.apply("hippo", "zzzzzzzz") = 8
    498     * distance.apply("hello", "hallo")    = 1
    499     * </pre>
    500     *
    501     * @param left the first string, must not be null
    502     * @param right the second string, must not be null
    503     * @return result distance, or -1
    504     * @throws IllegalArgumentException if either String input {@code null}
    505     */
    506    @Override
    507    public LevenshteinResults apply(final CharSequence left, final CharSequence right) {
    508        if (threshold != null) {
    509            return limitedCompare(left, right, threshold);
    510        }
    511        return unlimitedCompare(left, right);
    512    }
    513
    514    /**
    515     * Gets the distance threshold.
    516     *
    517     * @return The distance threshold
    518     */
    519    public Integer getThreshold() {
    520        return threshold;
    521    }
    522}