com.google.gwt.dev.util.editdistance

Class ModifiedBerghelRoachEditDistance

java.lang.Object

com.google.gwt.dev.util.editdistance.ModifiedBerghelRoachEditDistance

All Implemented Interfaces:

GeneralEditDistance

public class ModifiedBerghelRoachEditDistance
extends Object
implements GeneralEditDistance

A modified version of a string edit distance described by Berghel and Roach that uses only O(d) space and O(n*d) worst-case time, where n is the pattern string length and d is the edit distance computed. We achieve the space reduction by keeping only those sub-computations required to compute edit distance, giving up the ability to reconstruct the edit path.

Method Summary

Modifier and Type	Method and Description
ModifiedBerghelRoachEditDistance	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 targetSequence, 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.
static ModifiedBerghelRoachEditDistance	getInstance(CharSequence pattern) Creates an instance for computing edit distance from pattern.
static ModifiedBerghelRoachEditDistance	getInstance(String pattern) Creates an instance for computing edit distance from pattern.

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, toString

Method Detail

getInstance

public static ModifiedBerghelRoachEditDistance getInstance(CharSequence pattern)

Creates an instance for computing edit distance from pattern.

Parameters:

pattern - string from which distances are measured

Returns:

an instance for computing distances from the pattern

getInstance

public static ModifiedBerghelRoachEditDistance getInstance(String pattern)

Creates an instance for computing edit distance from pattern.

Parameters:

pattern - string from which distances are measured

Returns:

an instance for computing distances from the pattern

duplicate

public ModifiedBerghelRoachEditDistance 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 int getDistance(CharSequence targetSequence,
                       int limit)

Description copied from interface: GeneralEditDistance

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.

Specified by:

getDistance in interface GeneralEditDistance

Parameters:

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