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}