From: Ragav Satish <ragavsatish@...>
Date: 2008-10-07T04:12:53+09:00
Subject: Re: Problem with comparing huge amount of strings

Jan Fischer wrote:
> Hello together,
> 
> I got a problem grouping rows in a Database by similarity. What I try to
> reach is the following:
> I have a table looking like (just an example):
> 
> ID   Companyname       Group
> 1    Mickeysoft Ltd.   NULL
> 2    Mickysoft LTD     NULL
> 3    Mickeysft Limited NULL
> 4    Aple Inc          NULL
> 5    APPLE INC         NULL
> 
> and so on, you get the point. Group should be 1 for the IDs 1 to 3 and 2
> for the IDs 4 and 5.
> 
> At the moment I compare two strings by making them lowercase, deleting
> dots etc., deleting the substrings 'Inc', 'Ltd' etc. and then building
> the Levenshtein-Distance of the metaphone-key of the two strings.
> Works not really good and is damn slow, but it's okay and best I could
> figure out. (Nevertheless your hints on that are welcome too.)
> 
> My problem is, that I don't know how to apply my compare-method in an
> efficient way. What I'm doing now is selecting the first row where Group
> is NULL and then selecting each row (where Group is NULL) in my database
> in a loop again, comparing with the first selected string and setting
> Group to a certain number if comapare method says they match.
> 
> That lasts a lang time and - worse - my code looks very ugly, even to a
> very beginner as I am.
> 
> So if somebody of you has a good idea how to improve that, some docs on
> how to implement such a thing or even a totally different approach to
> get the results I want, I would be very glad.
> 
> Jan

First at the minimum if you apply Lev distance for each pair of keys you 
might want to implement this as a custom database function. For eg in 
mysql you can create custom user functions 
http://dev.mysql.com/doc/refman/6.0/en/adding-functions.html

The naive implementation of comparing each key with every other is 
quadratic. You need a way of "blocking/chunking" the dataset.

1. For eg can you assume that the first letter will never be misspelled? 
Then you can group by first letters and create a smaller search space.
2. Or if you don't accept a Lev distance > 2 then maybe you can first 
sort the names by length and only compute Lev distance on those which 
differ in size < 3?
3. Perhaps the record has other fields which can be used individually or 
in combination to generate a sort key?
4. There are more complicated blocking schemes - like n-gram(chunk by N 
common continuous characters) or even sampling based ones.

A good blocking algorithm will be the key to scalability.

There is lots of literature out there on this .. search for sorted 
neighborhood, record-linkage, merge-purge, hardening soft databases.

--Cheers
--Ragav
-- 
Posted via http://www.ruby-forum.com/.