NAME
Text::Levenshtein::Flexible - XS Levenshtein distance calculation with bounds and costs
SYNOPSIS
use Text::Levenshtein::Flexible;DESCRIPTION
Yet another Levenshtein module written in C, but a tad more flexible than the rest.
This module uses code from PostgreSQL's levenshtein distance function to provide the following features on top of plain distance calculation as it is done by Levenshtein::XS and others:
- Distance-limited calculation: if a certain maximum distance is exceeded, the algorithm aborts without result. This helps performance in situations where it is clear that results over a certain maximum are not useful.
- Configurable costs for insert, delete ans substitute operations. The traditional Levenshtein algorithm assumes equal cost for insertion and deletion but modifying these allows preferential correction of certain errors.
EXPORT
Nothing is exported by default.
Exportable
The following functions can be exported upon request, e.g.:
use Text::Levenshtein::Flexible qw( levenshtein levenshtein_l_all );levenshteinlevenshtein_clevenshtein_llevenshtein_lclevenshtein_l_alllevenshtein_lc_all
Procedural interface
The functions listed under "Exportable" consitute the module's procedural API. Neither the names nor the huge parameter lists are particularly pretty so the OO interface is usually recommended.
levenshtein($src, $dst)
Plain Levenshtein distance calculation between the two strings $src and $dst. Always returns an integer. If the strings are too long (currently there is a hard-coded limit of 255 characters), the function may die(), so call it in an eval block if this is a possibility.
levenshtein_c($src, $dst, $cost_ins, $cost_del, $cost_sub)
Distance between the two strings $src and $dst using the specified costs for insertion, deletion and substitution respectively. Always returns an integer unless it dies.
levenshtein_l($src, $dst, $max_distance)
Distance between $src and $dst unless it is bigger than $max_distance (think _limit!), in which case undef is returned. May die just like the other functions.
levenshtein_lc($src, $dst, $max_distance, $cost_ins, $cost_del, $cost_sub)
Distance between $src and $dst using the specified costs, up to $max_distance,
levenshtein_l_all($max_distance, $src, @dst)
For an array @dst of strings, return all that are up to $max_distance from $src. The result is a list of 2-element arrays consisting of string-distance pairs. To get a list of strings sorted by distance:
map { $_->[0] }
sort { $a->[1] <=> $b->[1] }
levenshtein_l_all(2, "bar", "foo", "blah", "baz");Note that since the *_all functions were converted to XS as well, this function delegates to the OO version internally to avoid too much XS code duplication, so the OO interface is preferable for this in any case.
levenshtein_lc_all($max_distance, $cost_ins, $cost_del, $cost_sub, $src, @dst)
For an array @dst of strings, return all that are up to $max_distance from $src when using the specified costs as in levenshtein_c. The result is the same as for levenshtein_l_all and the remark about the OO version applies equally here.
Note that there is no levenshtein_all() function because it is trivial to write using map.
Object-oriented interface
The OO API will usually be more convenient except for trivial calculations because it allows to specify limits and costs once and pass only variable data to object methods. Being implemented in C/XS it is just as fast as the procedural one, or faster in the case of the list functions.
new($max_distance, $cost_ins, $cost_del, $cost_sub)
All four constructor arguments are optional but must be defined if they are used, i.e. you have to specify a number for $max_distance if you want to use the costs. Pass 1 for costs and some number over 255 times the largest of the cost values for $max_distance (passing something significantly bigger doesn't hurt, in case the hardcoded limit for calculations should grow some day) if you don't care.
distance($src, $dst)
Just for orthogonality, this does the same as levenshtein().
distance_c($src, $dst)
Just like levenshtein_c() but using the previously specified costs.
distance_l($src, $dst)
levenshtein_l()'s modern brother.
distance_lc($src, $dst, $max_distance, $cost_ins, $cost_del, $cost_sub)
The nicer variant of levenshtein_lc().
distance_l_all($src, @dst)
Not quite as ugly but otherwise equivalent to levenshtein_l_all().
distance_lc_all($src, @dst)
Where levenshtein_lc_all() gets really nasty, this does the same in a saner way.
Of course there's no distance_all() method either.
Speed
According to a few completely made-up benchmarks, Text::Levenshtein::Flexible is at least as fast as either Text::Levenshtein::XS, Text::LevenshteinXS or Text::Fuzzy (Core i7 920) and between 25% and 48% faster on some systems (Phenom II X6 1090T). A small benchmark script is included to test on your system, I'd be interested to hear about any unexpectedly good or bad performance.
SEE ALSO
Dont even bother with anything else unless you're more interested in the algorithm than in practical applications as the algorithm is one of the better examples for something reasonably efficient in C that Perl is terrible at.
To find this module's lastest updates that are not on CPAN yet, check https://github.com/mbethke/Text-Levenshtein-Flexible
ACKNOWLEDGEMENTS
All the credit for speed and algorithmic cleverness goes to Joe Conway and Volkan Yazici who wrote the bulk of this module's code, originally for PostgreSQL.
AUTHOR
Matthias Bethke, <matthias@towiski.de>
COPYRIGHT AND LICENSE
Copyright (C) 2014 by Matthias Bethke
This library is free software; you can redistribute it and/or modify it under the same terms as Perl itself, either Perl version 5.14.2 or, at your option, any later version of Perl 5 you may have available. Significant portions of the code are (C) PostgreSQL Global Development Group and The Regents of the University of California. All modified versions must retain the file COPYRIGHT included in the distribution.