com.google.gwt.dev.util.editdistance

Interface GeneralEditDistance

All Known Implementing Classes:

ModifiedBerghelRoachEditDistance, MyersBitParallelEditDistance

public interface GeneralEditDistance

An engine definition for computing string edit distances, and implementation generators. Generally, edit distance is the minimum number of edit operations required to transform one string into another. Being a minimum transform, it forms a metric space (one that is non-negative, symmetric, and obeys triangle inequality). The most common form is Levenshtein distance, where the set of operations consists of: deleting one character; inserting one character; or, substituting one character for another, each having a "cost" of 1. Another common form is Damerau-Levenshtein distance, which adds transpose two adjacent characters to the set of operations. Note that many implementations of Damerau distance do not account for insertion after transposition; this "restricted" Damerau distance does not obey triangle inequality, but is substantially easier to compute than the unrestricted metric. Another variation is to apply differential costs for the various operations. For example, substitutions could be weighted by character type (e.g., vowel<=>vowel being a cheaper edit than vowel<=>consonant). This class defines an engine for computing edit distance from a fixed ("pattern") string to other ("target") strings. The pattern is fixed at instantiation time; this allows an implementation to perform precomputations to make individual target computations faster. To allow further performance optimization, the GeneralEditDistance contract does not require thread-safety. A duplicate method is defined to allow additional equivalent instances to be created for separate threads; it is essentially a type-knowledgeable clone.

Method Summary

Modifier and Type	Method and Description
GeneralEditDistance	duplicate() Creates a duplicate (clone) of this distance engine, typically in order to use it in another thread (as the GeneralEditDistance contract does not specify thread safety).
int	getDistance(CharSequence target, int limit) Computes edit distance from the pattern string (used to construct this GeneralEditDistance instance) to a given target string, bounded by a limit of interest.

Method Detail

duplicate

GeneralEditDistance duplicate()

Creates a duplicate (clone) of this distance engine, typically in order to use it in another thread (as the GeneralEditDistance contract does not specify thread safety). This method differs from Object.clone() in two ways: it is typed (to GeneralEditDistance); and, it must not throw an exception.

Returns:

a clone of this instance.

getDistance

int getDistance(CharSequence target,
                int limit)

Computes edit distance from the pattern string (used to construct this GeneralEditDistance instance) to a given target string, bounded by a limit of interest. The specified limit must be non-negative. If the actual distance exceeds the limit, this method may return *any* value above the limit; it need not be the actual distance. The behavior of illegal limit values is undefined; an implementation may return an incorrect result or raise a runtime exception.

Parameters:

target - string for which distance is to be compared against a predefined pattern

limit - maximum distance for which exact result is required (and beyond which any over-limit result can be returned)

Returns:

edit distance from the predefined pattern to the target (or any value above limit, if the actual distance exceeds the prescribed limit)