http://www.perlmonks.org?node_id=225388


in reply to Comparing Approximate Items

You could use Text::Levenshtein

It is an edit distance, i.e. it is a measure of the degree of proximity between two strings.
So for example, distance("foo","four") is 2 because you need an edit "SUBSTITUTE" and an edit "INSERT".

As algorithm I suggest the 'Stable Marriage Problem', a matching algorithm to best fit the "marriage preferences" of two sets.

Replies are listed 'Best First'.
Re: Re: Comparing Approximate Items
by tall_man (Parson) on Jan 09, 2003 at 01:31 UTC
    I think you are right. Text::Levenshtein is better in this case because String::Approx will match substrings of the input. Here is one more thing. If substitutions are not allowed, only inserts and deletes, you could use Text::WagnerFischer to set the cost of substitution so high that it will not be used.
    use Text::Levenshtein; use Text::WagnerFischer; my $pat = 'AAB'; my @lst = qw(ABAB ABBA ABB ABABAAB); my @dist1 = Text::Levenshtein::distance($pat, @lst); my @dist2 = Text::WagnerFischer::distance([0, 1, 100], $pat, @lst); my ($i, $item); $i = 0; foreach $item (@lst) { print "Levenshtein distance of $item to $pat is ",$dist1[$i],"\n"; print "WagnerFischer distance of $item to $pat is ",$dist2[$i],"\n" +; $i++; }