String::Approx(3) Perl extension for approximate matching (fuzzy matching)


use String::Approx 'amatch';
print if amatch("foobar");


String::Approx lets you match and substitute strings approximately. With this you can emulate errors: typing errors, spelling errors, closely related vocabularies (colour color), genetic mutations (GAG ACT), abbreviations (McScot, MacScot).




The measure of approximateness is the Levenshtein edit distance. It is the total number of ``edits'': insertions,

        word world


        monkey money

and substitutions

        sun fun

required to transform a string to another string. For example, to transform ``lead'' into ``gold'', you need three edits:

        lead gead goad gold

The edit distance of ``lead'' and ``gold'' is therefore three, or 75%.

String::Approx uses the Levenshtein edit distance as its measure, but String::Approx is not well-suited for comparing strings of different length, in other words, if you want a ``fuzzy eq'', see above. String::Approx is more like regular expressions or index(), it finds substrings that are close matches.>


        use String::Approx 'amatch';
        $matched     = amatch("pattern") 
        $any_matched = amatch("pattern", @inputs) 
        @match       = amatch("pattern") 
        @matches     = amatch("pattern", @inputs) 


Notice that the pattern is a string. Not a regular expression. None of the regular expression notations (^, ., *, and so on) work. They are characters just like the others. Note-on-note: some limited form of ``regular expressionism'' is planned in future: for example character classes ([abc]) and any-chars (.). But that feature will be turned on by a special modifier (just a guess: ``r''), so there should be no backward compatibility problem.



With the modifiers you can control the amount of approximateness and certain other control variables. The modifiers are one or more strings, for example ``i'', within a string optionally separated by whitespace. The modifiers are inside an anonymous array: the [ ] in the syntax are not notational, they really do mean [ ], for example [ ``i'', ``2'' ]. [``2 i''] would be identical.



Examples: ``3'', ``15%''.

Note that "0%" is not rounded up, it is equal to 0.



Examples: ``I2'', ``D20%'', ``S0''.

You can ignore case (``A'' becames equal to ``a'' and vice versa) by adding the ``i'' modifier.

For example

        [ "i 25%", "S0" ]

means ignore case, allow every fourth character to be ``an edit'', but allow no substitutions. (See NOTES about disallowing substitutions or insertions.)

NOTE: setting "I0 D0 S0" is not equivalent to using index(). If you want to use index(), use index().


        use String::Approx 'asubstitute';
                                   [ modifiers ], @inputs)

Substitute approximate pattern with replacement and return as a list <copies> of @inputs, the substitutions having been made on the elements that did match the pattern. If no inputs are given, substitute in the $_. The replacement can contain magic strings $&, $`, $' that stand for the matched string, the string before it, and the string after it, respectively. All the other arguments are as in "amatch()", plus one additional modifier, ``g'' which means substitute globally (all the matches in an element and not just the first one, as is the default).

See ``BAD NEWS'' about the unfortunate stinginess of "asubstitute()".


        use String::Approx 'aindex';
        $index   = aindex("pattern")
        @indices = aindex("pattern", @inputs)

Like "amatch()" but returns the index/indices at which the pattern matches approximately. In list context and if @inputs are used, returns a list of indices, one index for each input element. If there's no approximate match, "-1" is returned as the index.

NOTE: if there is character repetition (e.g. ``aa'') either in the pattern or in the text, the returned index might start ``too early''. This is consistent with the goal of the module of matching ``as early as possible'', just like regular expressions (that there might be a ``less approximate'' match starting later is of somewhat irrelevant).

There's also backwards-scanning "arindex()".


        use String::Approx 'aslice';



If the modifier





        use String::Approx 'adist';


        use String::Approx 'adistr';



        my %d;







To disable caching completely use





Because matching is by substrings, not by whole strings, insertions and substitutions produce often very similar results: ``abcde'' matches ``axbcde'' either by insertion or substitution of ``x''.

The maximum edit distance is also the maximum number of edits. That is, the ``I2'' in

        amatch("abcd", ["I2"])


        amatch("abcd", ["2D1S1"])

or something like that.

If you want to simulate transposes

        feet fete





or the both the modifiers


By setting the ``position_range'' to be zero you can limit (anchor) the operation to happen only once (if a match is possible) at the position.


Major release 3.



The version 3 is 2-3 times faster than version 2
No pattern length limitation
The algorithm is independent on the pattern length: its time complexity is O(kn), where k is the number of edits and n the length of the text (input). The preprocessing of the pattern will of course take some O(m) (m being the pattern length) time, but "amatch()" and "asubstitute()" cache the result of this preprocessing so that it is done only once per pattern.


You do need a C compiler to install the module
"asubstitute()" is now always stingy
The string matched and substituted is now always stingy, as short as possible. It used to be as long as possible. This is an unfortunate change stemming from switching the matching algorithm. Example: with edit distance of two and substituting for ``word'' from ``cork'' and ``wool'' previously did match ``cork'' and ``wool''. Now it does match ``or'' and ``wo''. As little as possible, or, in other words, with as much approximateness, as many edits, as possible. Because there is no need to match the ``c'' of ``cork'', it is not matched.
no more "aregex()" because regular expressions are no more used
no more "compat1" for String::Approx version 1 compatibility






Jarkko Hietaniemi <[email protected]>


Copyright 2001-2013 by Jarkko Hietaniemi

