| 1 |
root |
1.1 |
=head1 NAME |
| 2 |
|
|
|
| 3 |
|
|
String::Similarity - calculate the similarity of two strings |
| 4 |
|
|
|
| 5 |
|
|
=head1 SYNOPSIS |
| 6 |
|
|
|
| 7 |
|
|
use String::Similarity; |
| 8 |
|
|
|
| 9 |
|
|
$similarity = similarity $string1, $string2; |
| 10 |
|
|
$similarity = similarity $string1, $string2, $limit; |
| 11 |
|
|
|
| 12 |
|
|
=head1 DESCRIPTION |
| 13 |
|
|
|
| 14 |
|
|
=over 4 |
| 15 |
|
|
|
| 16 |
|
|
=cut |
| 17 |
|
|
|
| 18 |
|
|
package String::Similarity; |
| 19 |
|
|
|
| 20 |
root |
1.2 |
use Exporter; |
| 21 |
|
|
use DynaLoader; |
| 22 |
root |
1.1 |
|
| 23 |
root |
1.2 |
$VERSION = '1.04'; |
| 24 |
root |
1.1 |
@ISA = qw/Exporter DynaLoader/; |
| 25 |
|
|
@EXPORT = qw(similarity); |
| 26 |
|
|
@EXPORT_OK = qw(fstrcmp); |
| 27 |
|
|
|
| 28 |
|
|
bootstrap String::Similarity $VERSION; |
| 29 |
|
|
|
| 30 |
|
|
=item $factor = similarity $string1, $string2, [$limit] |
| 31 |
|
|
|
| 32 |
|
|
The C<similarity>-function calculates the similarity index of |
| 33 |
|
|
its two arguments. A value of C<0> means that the strings are |
| 34 |
|
|
entirely different. A value of C<1> means that the strings are |
| 35 |
|
|
identical. Everything else lies between 0 and 1 and describes the amount |
| 36 |
|
|
of similarity between the strings. |
| 37 |
|
|
|
| 38 |
|
|
It roughly works by looking at the smallest number of edits to change one |
| 39 |
|
|
string into the other. |
| 40 |
|
|
|
| 41 |
|
|
You can add an optional argument C<$limit> (default 0) that gives the |
| 42 |
|
|
minimum similarity the two strings must satisfy. C<similarity> stops |
| 43 |
|
|
analyzing the string as soon as the result drops below the given limit, |
| 44 |
|
|
in which case the result will be invalid but lower than the given |
| 45 |
|
|
C<$limit>. You can use this to speed up the common case of searching for |
| 46 |
root |
1.3 |
the most similar string from a set by specifying the maximum similarity |
| 47 |
root |
1.1 |
found so far. |
| 48 |
|
|
|
| 49 |
|
|
=cut |
| 50 |
|
|
|
| 51 |
|
|
# out of historical reasons, I prefer "fstrcmp" as the original name. |
| 52 |
|
|
*similarity = *fstrcmp; |
| 53 |
|
|
|
| 54 |
|
|
1; |
| 55 |
|
|
|
| 56 |
|
|
=back |
| 57 |
|
|
|
| 58 |
|
|
=head1 SEE ALSO |
| 59 |
|
|
|
| 60 |
|
|
The basic algorithm is described in: |
| 61 |
|
|
"An O(ND) Difference Algorithm and its Variations", Eugene Myers, |
| 62 |
|
|
Algorithmica Vol. 1 No. 2, 1986, pp. 251-266; |
| 63 |
|
|
see especially section 4.2, which describes the variation used below. |
| 64 |
|
|
|
| 65 |
|
|
The basic algorithm was independently discovered as described in: |
| 66 |
|
|
"Algorithms for Approximate String Matching", E. Ukkonen, |
| 67 |
|
|
Information and Control Vol. 64, 1985, pp. 100-118. |
| 68 |
|
|
|
| 69 |
|
|
=head1 AUTHOR |
| 70 |
|
|
|
| 71 |
|
|
Marc Lehmann <schmorp@schmorp.de> |
| 72 |
|
|
http://home.schmorp.de/ |
| 73 |
|
|
|
| 74 |
|
|
(the underlying fstrcmp function was taken from gnu diffutils and |
| 75 |
|
|
modified by Peter Miller <pmiller@agso.gov.au> and Marc Lehmann |
| 76 |
|
|
<schmorp@schmorp.de>). |
| 77 |
|
|
|
| 78 |
|
|
|
| 79 |
|
|
|
