org.simmetrics.metrics

Class LongestCommonSubsequence

java.lang.Object

org.simmetrics.metrics.LongestCommonSubsequence

All Implemented Interfaces:

Distance<String>, Metric<String>, StringDistance, StringMetric

public final class LongestCommonSubsequence
extends Object
implements StringMetric, StringDistance

Applies the longest common subsequence algorithm to calculate the similarity and distance between two strings.

similarity(a,b) = ∣lcs(a,b)∣ / max{∣a∣, ∣b∣}
distance(a,b) = ∣a∣ + ∣b∣ - 2 * ∣lcs(a,b)∣

This class is immutable and thread-safe.

See Also:

Wikipedia - Longest common subsequence problem

Constructor Summary

Constructors

Constructor and Description
LongestCommonSubsequence()

Method Summary

Modifier and Type	Method and Description
float	compare(String a, String b) Measures the similarity between strings a and b.
float	distance(String a, String b) Measures the distance between string a and b.
String	toString()

Methods inherited from class java.lang.Object

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

Constructor Detail

LongestCommonSubsequence

public LongestCommonSubsequence()

Method Detail

compare

public float compare(String a,
                     String b)

Description copied from interface: StringMetric

Measures the similarity between strings a and b. The measurement results in a value between 0 and 1 (inclusive). A value of zero indicates that the strings are dissimilar, a value of 1 indicates they are similar.

Specified by:

compare in interface Metric<String>

Specified by:

compare in interface StringMetric

Parameters:

a - string a to compare

b - string b to compare

Returns:

a value between 0 and 1 inclusive indicating similarity

distance

public float distance(String a,
                      String b)

Description copied from interface: StringDistance

Measures the distance between string a and b. The measurement results in a non-negative value. A value of 0.0 indicates that a and b are similar.

Specified by:

distance in interface Distance<String>

Specified by:

distance in interface StringDistance

Parameters:

a - string a to compare

b - string b to compare

Returns:

a non-negative value

toString

public String toString()

Overrides:

toString in class Object