com.bericotech.clavin.util

Class DamerauLevenshtein

java.lang.Object

com.bericotech.clavin.util.DamerauLevenshtein

public class DamerauLevenshtein
extends Object

Utility functions for calculating edit distance between strings, consistent with the Damerau-Levenshtein metric. Transposition, substitution, insertion, and deletion operations are all considered to be one edit each. Multiple substring edits (e.g., adjacent transpositions) are supported, unlike in "optimal string alignment distance" where no substring may be edited more than once.

Constructor Summary

Constructors

Constructor and Description
DamerauLevenshtein()

Method Summary

Modifier and Type	Method and Description
static int	damerauLevenshteinDistance(String str1, String str2) Computes the true Damerau–Levenshtein edit distance (with adjacent transpositions) between two given strings. Based on C# code from Wikipedia.
static int	damerauLevenshteinDistanceCaseInsensitive(String str1, String str2) Convenience method for calling damerauLevenshteinDistance(String str1, String str2) when you don't care about case sensitivity.
static boolean	isEditDistance1(String str1, String str2) Fast method for determining whether the Damerau-Levenshtein edit distance between two strings is less than 2.

Methods inherited from class java.lang.Object

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

Constructor Detail

DamerauLevenshtein

public DamerauLevenshtein()

Method Detail

damerauLevenshteinDistance

public static int damerauLevenshteinDistance(String str1,
                                             String str2)

Computes the true Damerau–Levenshtein edit distance (with adjacent transpositions) between two given strings.

Based on C# code from Wikipedia.

Parameters:

str1 - First string being compared

str2 - Second string being compared

Returns:

Edit distance between strings

damerauLevenshteinDistanceCaseInsensitive

public static int damerauLevenshteinDistanceCaseInsensitive(String str1,
                                                            String str2)

Convenience method for calling damerauLevenshteinDistance(String str1, String str2) when you don't care about case sensitivity.

Parameters:

str1 - First string being compared

str2 - Second string being compared

Returns:

Case-insensitive edit distance between strings

isEditDistance1

public static boolean isEditDistance1(String str1,
                                      String str2)

Fast method for determining whether the Damerau-Levenshtein edit distance between two strings is less than 2. Returns as quick as possibly by stopping once multiple edits are found. Significantly faster than damerauLevenshteinDistance(String str1, String str2) which explores every path between every string to get the exact edit distance. Despite the speed boost, we maintain consistency with damerauLevenshteinDistance(String str1, String str2).

Parameters:

str1 - First string being compared

str2 - Second string being compared

Returns:

True if DL edit distance < 2, false otherwise