org.apache.commons.text.similarity

## Class LevenshteinDistance

- java.lang.Object
- - org.apache.commons.text.similarity.LevenshteinDistance

- All Implemented Interfaces:
    EditDistance<Integer>, SimilarityScore<Integer>

      public class LevenshteinDistance
      extends Object
      implements EditDistance<Integer>

  An algorithm for measuring the difference between two character sequences.

  This is the number of changes needed to change one sequence into another, where each change is a single character modification (deletion, insertion or substitution).

  This code has been adapted from Apache Commons Lang 3.3.

  Since:
    1.0

- - ### Constructor Summary

    Constructors
    Constructor and Description
    `LevenshteinDistance()` This returns the default instance that uses a version of the algorithm that does not use a threshold parameter.
    `LevenshteinDistance(Integer threshold)` If the threshold is not null, distance calculations will be limited to a maximum length.

  - ### Method Summary

    All Methods Static Methods Instance Methods Concrete Methods
    Modifier and Type | Method and Description
    --- | ---
    `Integer` | `apply(CharSequence left, CharSequence right)` Find the Levenshtein distance between two Strings.
    `static LevenshteinDistance` | `getDefaultInstance()` Gets the default instance.
    `Integer` | `getThreshold()` Gets the distance threshold.

    - ### Methods inherited from class java.lang.Object

      `clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

- - ### Constructor Detail

    - #### LevenshteinDistance

          public LevenshteinDistance()

      This returns the default instance that uses a version of the algorithm that does not use a threshold parameter.

      See Also:
        `getDefaultInstance()`

    - #### LevenshteinDistance

          public LevenshteinDistance(Integer threshold)

      If the threshold is not null, distance calculations will be limited to a maximum length. If the threshold is null, the unlimited version of the algorithm will be used.

      Parameters:
        `threshold` - If this is null then distances calculations will not be limited. This may not be negative.

  - ### Method Detail

    - #### apply

          public Integer apply(CharSequence left,
                               CharSequence right)

      Find the Levenshtein distance between two Strings.

      A higher score indicates a greater distance.

      The previous implementation of the Levenshtein distance algorithm was from http://www.merriampark.com/ld.htm

      Chas Emerick has written an implementation in Java, which avoids an OutOfMemoryError which can occur when my Java implementation is used with very large strings.
      This implementation of the Levenshtein distance algorithm is from http://www.merriampark.com/ldjava.htm

           distance.apply(null, *)             = IllegalArgumentException
           distance.apply(*, null)             = IllegalArgumentException
           distance.apply("","")               = 0
           distance.apply("","a")              = 1
           distance.apply("aaapppp", "")       = 7
           distance.apply("frog", "fog")       = 1
           distance.apply("fly", "ant")        = 3
           distance.apply("elephant", "hippo") = 7
           distance.apply("hippo", "elephant") = 7
           distance.apply("hippo", "zzzzzzzz") = 8
           distance.apply("hello", "hallo")    = 1

      Specified by:
        `apply` in interface `EditDistance<Integer>`
      Specified by:
        `apply` in interface `SimilarityScore<Integer>`
      Parameters:
        `left` - the first string, must not be null
        `right` - the second string, must not be null
      Returns:
        result distance, or -1
      Throws:
        `IllegalArgumentException` - if either String input `null`

    - #### getDefaultInstance

          public static LevenshteinDistance getDefaultInstance()

      Gets the default instance.
      Returns:
        the default instance

    - #### getThreshold

          public Integer getThreshold()

      Gets the distance threshold.
      Returns:
        the distance threshold

Copyright © 2014–2018 The Apache Software Foundation. All rights reserved.