Top Description Fields Constructors Methods
org.apache.commons.text.similarity

public Class LevenshteinDistance

extends Object
implements EditDistance<Integer>
Class Inheritance
All Implemented Interfaces
org.apache.commons.text.similarity.EditDistance, org.apache.commons.text.similarity.SimilarityScore, org.apache.commons.text.similarity.ObjectSimilarityScore, java.util.function.BiFunction
Imports
java.util.Arrays
An algorithm for measuring the difference between two character sequences using the Levenshtein Distance.

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
See Also
Levenshtein Distance on Wikipedia, Levenshtein Distance on NIST

Field Summary

Modifier and TypeField and Description
private static final LevenshteinDistance
INSTANCE

The singleton instance.

private final Integer
threshold

Threshold.

Constructor Summary

AccessConstructor and Description
public
LevenshteinDistance()
Deprecated Use getDefaultInstance().

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

public
LevenshteinDistance(final Integer
If this is null then distances calculations will not be limited. This may not be negative.
threshold)

Constructs a new instance.

Method Summary

Modifier and TypeMethod and Description
public Integer

Returns:

result distance, or -1.
apply(final CharSequence
the first input, must not be null.
left, final CharSequence
the second input, must not be null.
right)

Implements org.apache.commons.text.similarity.SimilarityScore.apply.

Computes the Levenshtein distance between two Strings.

public <
The type of similarity score unit.
E> Integer

Returns:

result distance, or -1.
apply(final SimilarityInput<E>
the first input, must not be null.
left, final SimilarityInput<E>
the second input, must not be null.
right)

Implements org.apache.commons.text.similarity.ObjectSimilarityScore.apply.

Computes the Levenshtein distance between two inputs.

public static LevenshteinDistance

Returns:

The default instance.
getDefaultInstance()

Gets the default instance.

public Integer

Returns:

The distance threshold.
getThreshold()

Gets the distance threshold.

private static <E> int

Returns:

result distance, or -1
limitedCompare(SimilarityInput<E>
the first SimilarityInput, must not be null.
left, SimilarityInput<E>
the second SimilarityInput, must not be null.
right, final int
the target threshold, must not be negative.
threshold)

Finds the Levenshtein distance between two CharSequences if it's less than or equal to a given threshold.

private static <E> int

Returns:

result distance, or -1.
unlimitedCompare(SimilarityInput<E>
the first CharSequence, must not be null.
left, SimilarityInput<E>
the second CharSequence, must not be null.
right)

Finds the Levenshtein distance between two Strings.

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

INSTANCEback to summary
private static final LevenshteinDistance INSTANCE

The singleton instance.

thresholdback to summary
private final Integer threshold

Threshold.

Constructor Detail

LevenshteinDistanceback to summary
public LevenshteinDistance()

Deprecated

Use getDefaultInstance().

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

Annotations
@Deprecated
See Also
LevenshteinDistance#getDefaultInstance()
LevenshteinDistanceback to summary
public LevenshteinDistance(final Integer threshold)

Constructs a new instance. 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:Integer

If this is null then distances calculations will not be limited. This may not be negative.

Method Detail

applyback to summary
public Integer apply(final CharSequence left, final CharSequence right)

Implements org.apache.commons.text.similarity.SimilarityScore.apply.

Computes 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, *)             = Throws IllegalArgumentException
distance.apply(*, null)             = Throws 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
Parameters
left:CharSequence

the first input, must not be null.

right:CharSequence

the second input, must not be null.

Returns:Integer

result distance, or -1.

Annotations
@Override
Exceptions
IllegalArgumentException:
if either String input null.
applyback to summary
public <E> Integer apply(final SimilarityInput<E> left, final SimilarityInput<E> right)

Implements org.apache.commons.text.similarity.ObjectSimilarityScore.apply.

Computes the Levenshtein distance between two inputs.

A higher score indicates a greater distance. 

distance.apply(null, *)             = Throws IllegalArgumentException
distance.apply(*, null)             = Throws 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
Parameters
<E>
The type of similarity score unit.
left:SimilarityInput<E>

the first input, must not be null.

right:SimilarityInput<E>

the second input, must not be null.

Returns:Integer

result distance, or -1.

Exceptions
IllegalArgumentException:
if either String input null.
Since
1.13.0
getDefaultInstanceback to summary
public static LevenshteinDistance getDefaultInstance()

Gets the default instance.

Returns:LevenshteinDistance

The default instance.

getThresholdback to summary
public Integer getThreshold()

Gets the distance threshold.

Returns:Integer

The distance threshold.

limitedCompareback to summary
private static <E> int limitedCompare(SimilarityInput<E> left, SimilarityInput<E> right, final int threshold)

Finds the Levenshtein distance between two CharSequences if it's less than or equal to a given threshold.

This implementation follows from Algorithms on Strings, Trees and Sequences by Dan Gusfield and Chas Emerick's implementation of the Levenshtein distance algorithm from http://www.merriampark.com/ld.htm 

limitedCompare(null, *, *)             = Throws IllegalArgumentException
limitedCompare(*, null, *)             = Throws IllegalArgumentException
limitedCompare(*, *, -1)               = Throws IllegalArgumentException
limitedCompare("","", 0)               = 0
limitedCompare("aaapppp", "", 8)       = 7
limitedCompare("aaapppp", "", 7)       = 7
limitedCompare("aaapppp", "", 6))      = -1
limitedCompare("elephant", "hippo", 7) = 7
limitedCompare("elephant", "hippo", 6) = -1
limitedCompare("hippo", "elephant", 7) = 7
limitedCompare("hippo", "elephant", 6) = -1
Parameters
left:SimilarityInput<E>

the first SimilarityInput, must not be null.

right:SimilarityInput<E>

the second SimilarityInput, must not be null.

threshold:int

the target threshold, must not be negative.

Returns:int

result distance, or -1

unlimitedCompareback to summary
private static <E> int unlimitedCompare(SimilarityInput<E> left, SimilarityInput<E> right)

Finds the Levenshtein distance between two Strings.

A higher score indicates a greater distance.

The previous implementation of the Levenshtein distance algorithm was from https://web.archive.org/web/20120526085419/http://www.merriampark.com/ldjava.htm

This implementation only need one single-dimensional arrays of length s.length() + 1 

unlimitedCompare(null, *)             = Throws IllegalArgumentException
unlimitedCompare(*, null)             = Throws IllegalArgumentException
unlimitedCompare("","")               = 0
unlimitedCompare("","a")              = 1
unlimitedCompare("aaapppp", "")       = 7
unlimitedCompare("frog", "fog")       = 1
unlimitedCompare("fly", "ant")        = 3
unlimitedCompare("elephant", "hippo") = 7
unlimitedCompare("hippo", "elephant") = 7
unlimitedCompare("hippo", "zzzzzzzz") = 8
unlimitedCompare("hello", "hallo")    = 1
Parameters
left:SimilarityInput<E>

the first CharSequence, must not be null.

right:SimilarityInput<E>

the second CharSequence, must not be null.

Returns:int

result distance, or -1.

Exceptions
IllegalArgumentException:
if either CharSequence input is null.