com.google.gwt.dev.util.editdistance

Class MyersBitParallelEditDistance

java.lang.Object

com.google.gwt.dev.util.editdistance.MyersBitParallelEditDistance

All Implemented Interfaces:

GeneralEditDistance, Cloneable

public abstract class MyersBitParallelEditDistance
extends Object
implements GeneralEditDistance, Cloneable

Computes Levenshtein string-edit distance using the algorithm of Eugene Myers (see "A fast bit-vector algorithm for approximate string matching based on dynamic progamming", Journal of the ACM, 46(3): 395-415, 1999), using the reformulations of Heikki Hyyro (see "Explaining and Extending the Bit-parallel Approximate String Matching Algorithm of Myers") along with Gonzalo Navarro ("Faster Bit-Parallel Approximate String Matching", Proc. 13th Combinatorial Pattern Matching (CPM'2002)).

Constructor Summary

Constructors

Modifier	Constructor and Description
protected	MyersBitParallelEditDistance(CharSequence s) Constructs a distance calculator for a given string.

Method Summary

Methods

Modifier and Type	Method and Description
protected Object	clone()
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).
abstract int	getDistance(CharSequence s, int k) Computes distance from the pattern to a given string, bounded by a limiting distance @see(GeneralEditDistance.getDistance(CharSequence,int)).
static MyersBitParallelEditDistance	getInstance(CharSequence s) Chooses an appropriate implementation for a given pattern string.
static void	main(String[] args) Tests a computation manually.
protected void	perThreadInit() Initializes items that cannot be shared among threads.

Methods inherited from class java.lang.Object

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

Constructor Detail

MyersBitParallelEditDistance

protected MyersBitParallelEditDistance(CharSequence s)

Constructs a distance calculator for a given string.

Method Detail

getInstance

public static MyersBitParallelEditDistance getInstance(CharSequence s)

Chooses an appropriate implementation for a given pattern string.

Parameters:

s - pattern string

Returns:

distance calculator appropriate for the pattern

main

public static void main(String[] args)

Tests a computation manually.

duplicate

public GeneralEditDistance duplicate()

Description copied from interface: GeneralEditDistance

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.

Specified by:

duplicate in interface GeneralEditDistance

Returns:

a clone of this instance.

getDistance

public abstract int getDistance(CharSequence s,
              int k)

Computes distance from the pattern to a given string, bounded by a limiting distance @see(GeneralEditDistance.getDistance(CharSequence,int)).

Specified by:

getDistance in interface GeneralEditDistance

Parameters:

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

k - 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)

clone

protected Object clone()
                throws CloneNotSupportedException

Overrides:

clone in class Object

Throws:

CloneNotSupportedException

perThreadInit

protected void perThreadInit()

Initializes items that cannot be shared among threads.