NAME

String::Levenshtein - Compute the Levenshtein distance between two strings

SYNOPSIS

  use String::Levenshtein qw(distance prefix_distance);
  $d = distance       ("abcd", "abxc")
  $d = prefix_distance("Smith", "Smithson")

DESCRIPTION

String::Levenshtein computes the Levenshtein distance between two strings. The Levenshtein distance is defined as the minimum number of characters that must be added, removed, or changed in order to transform one string into another.

The Levenshtein distance is also called the edit distance.

FUNCTIONS

$d = distance($string1, $string2)

Returns the Levenshtein distance between $string1 and $string2.

Returns -1 on error.

$d = prefix_distance($string1, $string2)

Returns the smallest number of characters that must be added, removed or changed in order to transform the shorter of $string1 and $string2 into a prefix of the longer.

Returns -1 on error.

EXAMPLES

                           Levenshtein prefix
    String1   String2 	   distance    distance
    <empty>   <empty> 	   0  	       0
    abc       <empty> 	   3  	       0
    <empty>   xyz     	   3  	       0
    abc       abc     	   0  	       0
    abc       xyz     	   3  	       3
    abc       abd     	   1  	       1
    gumbo     gambol  	   2  	       1
    aaaa      bbbbbbb 	   7  	       4
    McDougall MacDougal    2  	       2
    Smith     Smithson     3  	       0
    Smithson  Smith        3  	       0

EXPORTS

@EXPORT

Nothing

@EXPORT_OK

DIAGNOSTICS

distance and prefix_distance return -1 on error. The only error is memory allocation failure.

SEE ALSO

AUTHOR

Steven W. McDougall, <swmcd@world.std.com>

COPYRIGHT

Copyright 2002 by Steven W. McDougall. This module is free software; you can redistribute it and/or modify it under the same terms as Perl itself.