Finding Matches in Two Large Lists of Strings

See more: (untagged)

Hi,

I have two long (>50000) lists of names that must be periodically checked for possible matches between them. I've coded up several fast algorithms for computing edit distances (Eg- Levenshtein) but the size of the lists still makes it very time costly.

Is there any fast function F(S) that people compute offline on single strings that you could cluster them by, so that two strings far apart in F are also far apart in string distance, and one could reduce the size of the set that must be checked exactly? For example, if my criterion for matching is Leven(s1, s2) < N, then I know that |Length(s1) - Length(s2)| < N, and if I find a length difference >= N I won't even bother running Levenshtein.

I Googled once and came up with suggestions to use Hilbert curves or Z-ordering, and it made my head hurt. But there's gotta be something better than just length...

Thanks a million!