de.lmu.ifi.dbs.elki.distance.distancefunction.strings

Class LevenshteinDistanceFunction

java.lang.Object

de.lmu.ifi.dbs.elki.distance.distancefunction.strings.LevenshteinDistanceFunction

All Implemented Interfaces:

DistanceFunction<java.lang.String>, PrimitiveDistanceFunction<java.lang.String>

@Description(value="Levenshtein distance.")
 @Reference(authors="V. I. Levenshtein",
           title="Binary codes capable of correcting deletions, insertions and reversals",
           booktitle="Soviet physics doklady 10",
           bibkey="journals/misc/Levenshtein66")
public class LevenshteinDistanceFunction
extends java.lang.Object
implements PrimitiveDistanceFunction<java.lang.String>

Classic Levenshtein distance on strings.

Reference:

V. I. Levenshtein
Binary codes capable of correcting deletions, insertions and reversals
Soviet physics doklady 10

TODO: add case insensitive flag.

TODO: add an API that can stop early at a maximum distance

Since:

0.6.0

Author:

Felix Stahlberg, Erich Schubert

Nested Class Summary

Nested Classes

Modifier and Type	Class and Description
static class	LevenshteinDistanceFunction.Parameterizer Parameterization class.

Field Summary

Fields

Modifier and Type	Field and Description
static LevenshteinDistanceFunction	STATIC_SENSITIVE Static instance, case sensitive.
protected static SimpleTypeInformation<? super java.lang.String>	TYPE Input data type.

Constructor Summary

Constructors

Constructor and Description
LevenshteinDistanceFunction() Deprecated.

Method Summary

Modifier and Type	Method and Description
double	distance(java.lang.String o1, java.lang.String o2) Computes the distance between two given DatabaseObjects according to this distance function.
boolean	equals(java.lang.Object obj)
SimpleTypeInformation<? super java.lang.String>	getInputTypeRestriction() Get the input data type of the function.
int	hashCode()
boolean	isMetric() Is this distance function metric (satisfy the triangle inequality)
static int	levenshteinDistance(java.lang.String o1, java.lang.String o2) Levenshtein distance for two strings.
static int	levenshteinDistance(java.lang.String o1, java.lang.String o2, int prefix, int postfix) Compute the Levenshtein distance, except for prefix and postfix.
private static int	min(int a, int b, int c) Three-way integer minimum.
private static int	postfixLen(java.lang.String o1, java.lang.String o2, int prefix) Compute the postfix length.
private static int	prefixLen(java.lang.String o1, java.lang.String o2) Compute the length of the prefix.

Methods inherited from class java.lang.Object

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

Methods inherited from interface de.lmu.ifi.dbs.elki.distance.distancefunction.PrimitiveDistanceFunction

instantiate

Methods inherited from interface de.lmu.ifi.dbs.elki.distance.distancefunction.DistanceFunction

isSquared, isSymmetric

Field Detail

STATIC_SENSITIVE

public static final LevenshteinDistanceFunction STATIC_SENSITIVE

Static instance, case sensitive.

TYPE

protected static final SimpleTypeInformation<? super java.lang.String> TYPE

Input data type.

Constructor Detail

LevenshteinDistanceFunction

@Deprecated
public LevenshteinDistanceFunction()

Deprecated.

Constructor. Use static instance instead.

Method Detail

distance

public double distance(java.lang.String o1,
                       java.lang.String o2)

Description copied from interface: PrimitiveDistanceFunction

Computes the distance between two given DatabaseObjects according to this distance function.

Specified by:

distance in interface PrimitiveDistanceFunction<java.lang.String>

Parameters:

o1 - first DatabaseObject

o2 - second DatabaseObject

Returns:

the distance between two given DatabaseObjects according to this distance function

levenshteinDistance

public static int levenshteinDistance(java.lang.String o1,
                                      java.lang.String o2)

Levenshtein distance for two strings.

Parameters:

o1 - First string

o2 - Second string

Returns:

Levenshtein distance

prefixLen

private static int prefixLen(java.lang.String o1,
                             java.lang.String o2)

Compute the length of the prefix.

Parameters:

o1 - First string

o2 - Second string

Returns:

Prefix length

postfixLen

private static int postfixLen(java.lang.String o1,
                              java.lang.String o2,
                              int prefix)

Compute the postfix length.

Parameters:

o1 - First object

o2 - Second object

prefix - Known prefix length

Returns:

Postfix length

levenshteinDistance

public static int levenshteinDistance(java.lang.String o1,
                                      java.lang.String o2,
                                      int prefix,
                                      int postfix)

Compute the Levenshtein distance, except for prefix and postfix.

Parameters:

o1 - First object

o2 - Second object

prefix - Prefix length

postfix - Postfix length

Returns:

Levenshtein distance

min

private static int min(int a,
                       int b,
                       int c)

Three-way integer minimum.

Parameters:

a - First value

b - Second value

c - Third value.

Returns:

Minimum

getInputTypeRestriction

public SimpleTypeInformation<? super java.lang.String> getInputTypeRestriction()

Description copied from interface: DistanceFunction

Get the input data type of the function.

Specified by:

getInputTypeRestriction in interface DistanceFunction<java.lang.String>

Specified by:

getInputTypeRestriction in interface PrimitiveDistanceFunction<java.lang.String>

Returns:

Type restriction

isMetric

public boolean isMetric()

Description copied from interface: DistanceFunction

Is this distance function metric (satisfy the triangle inequality)

Specified by:

isMetric in interface DistanceFunction<java.lang.String>

Returns:

true when metric.

equals

public boolean equals(java.lang.Object obj)

Overrides:

equals in class java.lang.Object

hashCode

public int hashCode()

Overrides:

hashCode in class java.lang.Object