I have two datasets that I wish to relate together using the company name.
The problem is the same company may have a slightly different name in each
the two datasets.

What I want to do is for each company name in dataset A, find the 'nearest'
n matches to it in dataset B.

e.g. If I have 'Alkool Inc.', the nearest matches could be:

Alcool
Alcool inc
AlKool Partners
KB Alkoool
Akool Ltd.
etc....

I've looked into SOUNDEX but this doesn't work as the initial letters may be
different. A variation of SOUNDEX could work if it always returned n
'closest' matches though.... Is such a thing possible?

MySQL full-text searching is out as I'm using InnoDB tables.

Does anyone have any suggestions?

Thanks!
Edward