Package com.sk89q.worldedit.util.function

Class LevenshteinDistance

java.lang.Object
com.sk89q.worldedit.util.function.LevenshteinDistance
All Implemented Interfaces:
com.google.common.base.Function<String,Integer>, Function<String,Integer>
public class LevenshteinDistance extends Object implements com.google.common.base.Function<String,Integer>
Provides a Levenshtein distance between a given string and each string that this function is applied to.

  • Field Details

    • STANDARD_CHARS

      public static final Pattern STANDARD_CHARS

  • Constructor Details

    • LevenshteinDistance

      public LevenshteinDistance(String baseString, boolean caseSensitive)
      Create a new instance.
      Parameters:
      baseString - the string to compare to
      caseSensitive - true to make case sensitive comparisons

    • LevenshteinDistance

      public LevenshteinDistance(String baseString, boolean caseSensitive, @Nullable Pattern replacePattern)
      Create a new instance.
      Parameters:
      baseString - the string to compare to
      caseSensitive - true to make case sensitive comparisons
      replacePattern - pattern to match characters to be removed in both the input and test strings (may be null)

  • Method Details

    • apply

      @Nullable public Integer apply(String input)
      Specified by:
      apply in interface com.google.common.base.Function<String,Integer>
      Specified by:
      apply in interface Function<String,Integer>

    • distance

      public static int distance(String s, String t)

      Find the Levenshtein distance between two Strings.

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

      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(null, *)             = IllegalArgumentException
 distance(*, null)             = IllegalArgumentException
 distance("","")               = 0
 distance("","a")              = 1
 distance("aaapppp", "")       = 7
 distance("frog", "fog")       = 1
 distance("fly", "ant")        = 3
 distance("elephant", "hippo") = 7
 distance("hippo", "elephant") = 7
 distance("hippo", "zzzzzzzz") = 8
 distance("hello", "hallo")    = 1
      Parameters:
      s - the first String, must not be null
      t - the second String, must not be null
      Returns:
      result distance
      Throws:
      IllegalArgumentException - if either String input null