Top Description Constructors Methods
info.debatty.java.stringsimilarity

public Class QGram

extends ShingleBased
implements StringDistance
Class Inheritance
All Implemented Interfaces
info.debatty.java.stringsimilarity.interfaces.StringDistance, java.io.Serializable
Annotations
@Immutable
Imports
info.debatty.java.stringsimilarity.interfaces.StringDistance, java.util.HashSet, .Map, .Set, net.jcip.annotations.Immutable
Q-gram distance, as defined by Ukkonen in "Approximate string-matching with q-grams and maximal matches". The distance between two strings is defined as the L1 norm of the difference of their profiles (the number of occurences of each n-gram): SUM( |V1_i - V2_i| ). Q-gram distance is a lower bound on Levenshtein distance, but can be computed in O(m + n), where Levenshtein requires O(m.n).
Author
Thibault Debatty

Constructor Summary

AccessConstructor and Description
public
QGram(final int k)

Q-gram similarity and distance.

public
QGram()

Q-gram similarity and distance.

Method Summary

Modifier and TypeMethod and Description
public final double

Returns:

The computed Q-gram distance.
distance(final String
The first string to compare.
s1, final String
The second string to compare.
s2)

Implements info.debatty.java.stringsimilarity.interfaces.StringDistance.distance.

The distance between two strings is defined as the L1 norm of the difference of their profiles (the number of occurence of each k-shingle).

public final double
distance(final Map<String, Integer> profile1, final Map<String, Integer> profile2)

Compute QGram distance using precomputed profiles.

Inherited from info.debatty.java.stringsimilarity.ShingleBased:
getKgetProfile

Constructor Detail

QGramback to summary
public QGram(final int k)

Q-gram similarity and distance. Defined by Ukkonen in "Approximate string-matching with q-grams and maximal matches", http://www.sciencedirect.com/science/article/pii/0304397592901434 The distance between two strings is defined as the L1 norm of the difference of their profiles (the number of occurences of each k-shingle). Q-gram distance is a lower bound on Levenshtein distance, but can be computed in O(|A| + |B|), where Levenshtein requires O(|A|.|B|)

QGramback to summary
public QGram()

Q-gram similarity and distance. Defined by Ukkonen in "Approximate string-matching with q-grams and maximal matches", http://www.sciencedirect.com/science/article/pii/0304397592901434 The distance between two strings is defined as the L1 norm of the difference of their profiles (the number of occurence of each k-shingle). Q-gram distance is a lower bound on Levenshtein distance, but can be computed in O(|A| + |B|), where Levenshtein requires O(|A|.|B|) Default k is 3.

Method Detail

distanceback to summary
public final double distance(final String s1, final String s2)

Implements info.debatty.java.stringsimilarity.interfaces.StringDistance.distance.

The distance between two strings is defined as the L1 norm of the difference of their profiles (the number of occurence of each k-shingle).

Parameters
s1:String

The first string to compare.

s2:String

The second string to compare.

Returns:double

The computed Q-gram distance.

Exceptions
NullPointerException:
if s1 or s2 is null.
distanceback to summary
public final double distance(final Map<String, Integer> profile1, final Map<String, Integer> profile2)

Compute QGram distance using precomputed profiles.