org.opends.server.util
Class LevenshteinDistance

java.lang.Object
  extended by org.opends.server.util.LevenshteinDistance

@PublicAPI(stability=UNCOMMITTED,
           mayInstantiate=false,
           mayExtend=false,
           mayInvoke=true)
public final class LevenshteinDistance
extends java.lang.Object

This class provides an implementation of the Levenshtein distance algorithm, which may be used to determine the minimum number of changes required to transform one string into another. For the purpose of this algorithm, a change is defined as replacing one character with another, inserting a new character, or removing an existing character.

The basic algorithm works as follows for a source string S of length X and a target string T of length Y:

  1. Create a matrix M with dimensions of X+1, Y+1.
  2. Fill the first row with sequentially-increasing values 0 through X.
  3. Fill the first column with sequentially-increasing values 0 through Y.
  4. Create a nested loop iterating over the characters in the strings. In the outer loop, iterate through characters in S from 0 to X-1 using an iteration counter I. In the inner loop, iterate through the characters in T from 0 to Y-1 using an iterator counter J. Calculate the following three things and place the smallest value in the matrix in row I+1 column J+1:
  5. The Levenshtein distance value, which is the least number of changes needed to transform the source string into the target string, will be the value in the bottom right corner of the matrix (i.e., M[X][Y]).


Note that this is a completely "clean room" implementation, developed from a description of the algorithm, rather than copying an existing implementation. Doing it in this way eliminates copyright and licensing concerns associated with using an existing implementation.


Constructor Summary
LevenshteinDistance()
           
 
Method Summary
static int calculate(java.lang.String source, java.lang.String target)
          Calculates the Levenshtein distance between the provided string values.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

LevenshteinDistance

public LevenshteinDistance()
Method Detail

calculate

public static int calculate(java.lang.String source,
                            java.lang.String target)
Calculates the Levenshtein distance between the provided string values.

Parameters:
source - The source string to compare. It must not be null.
target - The target string to compare. It must not be null.
Returns:
The minimum number of changes required to turn the source string into the target string.