Text::Abbrev - create an abbreviation list from a table

Tie::Hash::Abbrev - a hash that can be accessed with abbreviated keys.

Tie::Hash::Abbrev::Smart - same description as the last one.

Tie::Hash::Approx - you get the idea...

String::Approx - Perl extension for approximate matching (fuzzy matching).

This might serve as a starting point.

#! perl -slw
use strict;

sub genRegex {
    my $query = shift;
    $query =~ tr[A-Za-z0-9 ][a-za-z0-9 ];
    my @words = split ' ', $query;

    my $regex = join '\W+'.$/, map{
        my $s='';
        $s = "(?:$_$s)?" for reverse split '';
        chop $s;
        "\\b$s\\b"
    } @words;
    return qr[$regex]xi;
}

my $regex;

while( my $line = <DATA>  ) {
    chomp $line;
    $regex = genRegex( $1 ) and print'' and next
        if $line =~ m[search for (.*) should match...];

    print +($line =~ $regex ?  'Matched ' : 'Failed  ' ), $line;
}

__DATA__
search for Aetna Insurance Company should match...
Aetna Insurance Company
Aetna Ins. Co.
Aetna Insurance Co.
Aetna Ins. Company
Aetna Ins Company
aetna insurance co
Aetna Ins Co
Atna Insurance Company
Aetna Ins. Ca.
Aetna Insurance Go.
Aetna Ins. Compary
search for Sam Jones should match...
Sam Jones
Sam J. Jones
Sam J Jones
S. Jones
Samuel Janes
Sam L Jones
Sam J.J. Jones
Sam J Jones
B. Jones
Manuel Jones
[download]

Results:

P:\test>junk

Matched Aetna Insurance Company
Matched Aetna Ins. Co.
Matched Aetna Insurance Co.
Matched Aetna Ins. Company
Matched Aetna Ins Company
Matched aetna insurance co
Matched Aetna Ins Co
Failed  Atna Insurance Company
Failed  Aetna Ins. Ca.
Failed  Aetna Insurance Go.
Failed  Aetna Ins. Compary

Matched Sam Jones
Matched Sam J. Jones
Matched Sam J Jones
Matched S. Jones
Failed  Samuel Janes
Failed  Sam L Jones
Matched Sam J.J. Jones
Matched Sam J Jones
Failed  B. Jones
Failed  Manuel Jones
[download]

Thanks everybody for your help. I'll try out your example BrowserUK.

Is this a perfect solution? No. But, it'll get you 80% of the way there ...

Unfortunately getting the extra 20% is an exercise in diminishing returns.

This is a very complex problem and you'll need to decide how much time (and/or money) you're prepared to spend getting as close to a complete solution as you deem necessary.

There are some pretty impressive (and very expensive) commercial solutions dedicated to this problem.

However you approach it, a machine will never get to 100% accuracy (at least not at this point).

---

If the information in this post is inaccurate, or just plain wrong, don't just downvote - please post explaining what's wrong.
That way everyone learns.

First, it helps to strip the noise from the company names, such as Inc, Co, Corp, GMBH, LTD, etc.

String::Approx finds a distance by looking at insertions, deletions, and substitutions needed to transform one string to another.

A different approach, which worked better for me, was to make lists of all the substrings of length n in the source string. I called these n-tuples. I compared the percentage overlap between the n-tuple sets for each name in one list to the n-tuples for each word in the other list. The best value for the length n of the tuples was three or four.

Very close matches could be completely automated this way. For matches that were not so close, I finished the matching task manually. I made a web user interface that had a selection list of the match candidates ranked by the closeness of the match. The closeness was determined by the percentage of n-tuples that matched. I selected the best match for each entry on the amongst these top-ranked match candidates.

A different approach, which worked better for me, was to make lists of all the substrings of length n in the source string. I called these n-tuples. I compared the percentage overlap between the n-tuple sets for each name in one list to the n-tuples for each word in the other list. The best value for the length n of the tuples was three or four.

Toma, could you give me an example of what you mean by this paragraph? I don't want you to go to the trouble of code examples, I mean an example using text so I can better understand what you mean.

Thanks...

Here is the requested example that shows how n-tuples work:

In this example, take n=3. The company names to compare are "tomacorp" and "tomarcorp". The 3-tuples of tomacorp are:

 tom
 oma
 mac
 aco
 cor
 orp
[download]

The 3-tuples of tomarcorp are:

 tom
 oma
 mar
 arc
 rco
 cor
 orp
[download]

The tuples in common are:

 tom
 oma
 cor
 orp
[download]

Four of the six 3-tuples in tomacorp appear in tomarcorp. This is a 75% match.
It should work perfectly the first time! - toma