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

public Class LevenshteinDetailedDistance

extends Object
implements EditDistance<LevenshteinResults>
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.

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).

Since
1.0

Field Summary

Modifier and TypeField and Description
private static final LevenshteinDetailedDistance
INSTANCE

The singleton instance.

private final Integer
threshold

Threshold.

Constructor Summary

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

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

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

Constructs a new instance for a threshold.

Method Summary

Modifier and TypeMethod and Description
public LevenshteinResults

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> LevenshteinResults

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 Strings.

private static <
The type of similarity score unit.
E> LevenshteinResults

Returns:

result object containing the count of insert, delete and substitute and total count needed.
findDetailedResults(final SimilarityInput<E>
character sequence which need to be converted from.
left, final SimilarityInput<E>
character sequence which need to be converted to.
right, final int[][]
two dimensional array containing.
matrix, final boolean
tells whether the value for left character sequence and right character sequence were swapped to save memory.
swapped)

Finds count for each of the three [insert, delete, substitute] operations needed.

public static LevenshteinDetailedDistance

Returns:

The default instace
getDefaultInstance()

Gets the default instance.

public Integer

Returns:

The distance threshold.
getThreshold()

Gets the distance threshold.

private static <
The type of similarity score unit.
E> LevenshteinResults

Returns:

result distance, or -1.
limitedCompare(SimilarityInput<E>
the first CharSequence, must not be null.
left, SimilarityInput<E>
the second CharSequence, 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 <
The type of similarity score unit.
E> LevenshteinResults

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 LevenshteinDetailedDistance INSTANCE

The singleton instance.

thresholdback to summary
private final Integer threshold

Threshold.

Constructor Detail

LevenshteinDetailedDistanceback to summary
public LevenshteinDetailedDistance()

Deprecated

Use getDefaultInstance().

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

Annotations
@Deprecated
See Also
LevenshteinDetailedDistance#getDefaultInstance()
LevenshteinDetailedDistanceback to summary
public LevenshteinDetailedDistance(final Integer threshold)

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

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

Method Detail

applyback to summary
public LevenshteinResults 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:LevenshteinResults

result distance, or -1.

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

Implements org.apache.commons.text.similarity.ObjectSimilarityScore.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
<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:LevenshteinResults

result distance, or -1.

Exceptions
IllegalArgumentException:
if either String input null.
Since
1.13.0
findDetailedResultsback to summary
private static <E> LevenshteinResults findDetailedResults(final SimilarityInput<E> left, final SimilarityInput<E> right, final int[][] matrix, final boolean swapped)

Finds count for each of the three [insert, delete, substitute] operations needed. This is based on the matrix formed based on the two character sequence.

Parameters
<E>
The type of similarity score unit.
left:SimilarityInput<E>

character sequence which need to be converted from.

right:SimilarityInput<E>

character sequence which need to be converted to.

matrix:int[][]

two dimensional array containing.

swapped:boolean

tells whether the value for left character sequence and right character sequence were swapped to save memory.

Returns:LevenshteinResults

result object containing the count of insert, delete and substitute and total count needed.

getDefaultInstanceback to summary
public static LevenshteinDetailedDistance getDefaultInstance()

Gets the default instance.

Returns:LevenshteinDetailedDistance

The default instace

getThresholdback to summary
public Integer getThreshold()

Gets the distance threshold.

Returns:Integer

The distance threshold.

limitedCompareback to summary
private static <E> LevenshteinResults 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
<E>
The type of similarity score unit.
left:SimilarityInput<E>

the first CharSequence, must not be null.

right:SimilarityInput<E>

the second CharSequence, must not be null.

threshold:int

the target threshold, must not be negative.

Returns:LevenshteinResults

result distance, or -1.

unlimitedCompareback to summary
private static <E> LevenshteinResults 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 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 

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
<E>
The type of similarity score unit.
left:SimilarityInput<E>

the first CharSequence, must not be null.

right:SimilarityInput<E>

the second CharSequence, must not be null.

Returns:LevenshteinResults

result distance, or -1.

Exceptions
IllegalArgumentException:
if either CharSequence input is null.