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

public Class LongestCommonSubsequence

extends Object
implements SimilarityScore<Integer>
Class Inheritance
All Implemented Interfaces
org.apache.commons.text.similarity.SimilarityScore, org.apache.commons.text.similarity.ObjectSimilarityScore, java.util.function.BiFunction
A similarity algorithm indicating the length of the longest common subsequence between two strings.

The Longest common subsequence algorithm returns the length of the longest subsequence that two strings have in common. Two strings that are entirely different, return a value of 0, and two strings that return a value of the commonly shared length implies that the strings are completely the same in value and position

Note

Generally this algorithm is fairly inefficient, as for length m, n of the input CharSequence's left and right respectively, the runtime of the algorithm is O(m*n).

As of version 1.10, a more space-efficient of the algorithm is implemented. The new algorithm has linear space complexity instead of quadratic. However, time complexity is still quadratic in the size of input strings.

The implementation is based on Hirschberg's Longest Commons Substring algorithm (cited below).

For further reading see:

Since
1.0

Field Summary

Modifier and TypeField and Description
pack-priv static final LongestCommonSubsequence
INSTANCE

The singleton instance.

Constructor Summary

AccessConstructor and Description
public
LongestCommonSubsequence()

Creates a new instance.

Method Summary

Modifier and TypeMethod and Description
private static int[]

Returns:

last row of the dynamic-programming (DP) table for calculating the LCS of left and right.
algorithmB(final CharSequence
first input sequence.
left, final CharSequence
second input sequence.
right)

An implementation of "ALG B" from Hirschberg's CACM '71 paper.

private static String

Returns:

the LCS of left and right.
algorithmC(final CharSequence
first input sequence.
left, final CharSequence
second input sequence.
right)

An implementation of "ALG C" from Hirschberg's CACM '71 paper.

public Integer

Returns:

length of the longest common subsequence of left and right.
apply(final CharSequence
first character sequence.
left, final CharSequence
second character sequence.
right)

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

Computes the longest common subsequence similarity score of two CharSequence's passed as input.

public CharSequence

Returns:

the longest common subsequence found.
logestCommonSubsequence(final CharSequence
first character sequence.
left, final CharSequence
second character sequence.
right)
Deprecated Deprecated as of 1.2 due to a typo in the method name.

Computes the longest common subsequence between the two CharSequence's passed as input.

public CharSequence

Returns:

the longest common subsequence found.
longestCommonSubsequence(final CharSequence
first character sequence.
left, final CharSequence
second character sequence.
right)

Computes the longest common subsequence between the two CharSequence's passed as input.

public int[][]

Returns:

longest common substring length array.
longestCommonSubstringLengthArray(final CharSequence
first character sequence.
left, final CharSequence
second character sequence.
right)
Deprecated Deprecated as of 1.10.

Computes the lcsLengthArray for the sake of doing the actual lcs calculation.

private static String
reverse(final CharSequence s)

Inherited from java.lang.Object:
cloneequalsfinalizegetClasshashCodenotifynotifyAlltoStringwaitwaitwait

Field Detail

INSTANCEback to summary
pack-priv static final LongestCommonSubsequence INSTANCE

The singleton instance.

Constructor Detail

LongestCommonSubsequenceback to summary
public LongestCommonSubsequence()

Creates a new instance.

Method Detail

algorithmBback to summary
private static int[] algorithmB(final CharSequence left, final CharSequence right)

An implementation of "ALG B" from Hirschberg's CACM '71 paper. Assuming the first input sequence is of size m and the second input sequence is of size n, this method returns the last row of the dynamic programming (DP) table when calculating the LCS of the two sequences in O(m*n) time and O(n) space. The last element of the returned array, is the size of the LCS of the two input sequences.

Parameters
left:CharSequence

first input sequence.

right:CharSequence

second input sequence.

Returns:int[]

last row of the dynamic-programming (DP) table for calculating the LCS of left and right.

Since
1.10.0
algorithmCback to summary
private static String algorithmC(final CharSequence left, final CharSequence right)

An implementation of "ALG C" from Hirschberg's CACM '71 paper. Assuming the first input sequence is of size m and the second input sequence is of size n, this method returns the Longest Common Subsequence (LCS) of the two sequences in O(m*n) time and O(m+n) space.

Parameters
left:CharSequence

first input sequence.

right:CharSequence

second input sequence.

Returns:String

the LCS of left and right.

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

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

Computes the longest common subsequence similarity score of two CharSequence's passed as input.

This method implements a more efficient version of LCS algorithm which has quadratic time and linear space complexity.

This method is based on newly implemented algorithmB(CharSequence, CharSequence). An evaluation using JMH revealed that this method is almost two times faster than its previous version.

Parameters
left:CharSequence

first character sequence.

right:CharSequence

second character sequence.

Returns:Integer

length of the longest common subsequence of left and right.

Annotations
@Override
Exceptions
IllegalArgumentException:
if either String input null.
logestCommonSubsequenceback to summary
public CharSequence logestCommonSubsequence(final CharSequence left, final CharSequence right)

Deprecated

Deprecated as of 1.2 due to a typo in the method name. Use longestCommonSubsequence(CharSequence, CharSequence) instead. This method will be removed in 2.0.

Computes the longest common subsequence between the two CharSequence's passed as input.

Note, a substring and subsequence are not necessarily the same thing. Indeed, abcxyzqrs and xyzghfm have both the same common substring and subsequence, namely xyz. However, axbyczqrs and abcxyzqtv have the longest common subsequence xyzq because a subsequence need not have adjacent characters.

For reference, we give the definition of a subsequence for the reader: a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Parameters
left:CharSequence

first character sequence.

right:CharSequence

second character sequence.

Returns:CharSequence

the longest common subsequence found.

Annotations
@Deprecated
Exceptions
IllegalArgumentException:
if either String input null.
longestCommonSubsequenceback to summary
public CharSequence longestCommonSubsequence(final CharSequence left, final CharSequence right)

Computes the longest common subsequence between the two CharSequence's passed as input.

This method implements a more efficient version of LCS algorithm which although has quadratic time, it has linear space complexity.

Note, a substring and subsequence are not necessarily the same thing. Indeed, abcxyzqrs and xyzghfm have both the same common substring and subsequence, namely xyz. However, axbyczqrs and abcxyzqtv have the longest common subsequence xyzq because a subsequence need not have adjacent characters.

For reference, we give the definition of a subsequence for the reader: a subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements.

Parameters
left:CharSequence

first character sequence.

right:CharSequence

second character sequence.

Returns:CharSequence

the longest common subsequence found.

Exceptions
IllegalArgumentException:
if either String input null.
Since
1.2
longestCommonSubstringLengthArrayback to summary
public int[][] longestCommonSubstringLengthArray(final CharSequence left, final CharSequence right)

Deprecated

Deprecated as of 1.10. A more efficient implementation for calculating LCS is now available. Use longestCommonSubsequence(CharSequence, CharSequence) instead to directly calculate the LCS. This method will be removed in 2.0.

Computes the lcsLengthArray for the sake of doing the actual lcs calculation. This is the dynamic programming portion of the algorithm, and is the reason for the runtime complexity being O(m*n), where m=left.length() and n=right.length().

Parameters
left:CharSequence

first character sequence.

right:CharSequence

second character sequence.

Returns:int[][]

longest common substring length array.

Annotations
@Deprecated
reverseback to summary
private static String reverse(final CharSequence s)