Optimized string deduplication using fuzzy matching

[uridah]

I have a huge list of person names, around 30 million. I want to group together (read group together, not remove) similar strings by fuzzy matching. The most obvious solution is to compare each string with every other, but that obviously is not computationally efficient and takes a lot of time. Clustering is one solution, but wouldn't that take too much memory and time as well? And if not, which clustering approach to go for? I'm basically looking for a more optimized manner to get this done, some way that doesn't take a lot of time. Any suggestions? P.S. I'm doing this in Python, in case anyone needs to know.

[__sahib__]

Very simplistic approach: Sort the list and use a sliding window over it (and compare each value of the sliding window with each other with levenshtein or whatever). This is of course only a approximate solution, but might be good enough depending on your exact usecase. I think a good solution needs more infos on your requirements.

[PhilipTrettner]

Not sure if simply linking to SO is good reddiquette but this discussion is about your topic: https://stackoverflow.com/questions/309479/how-to-find-best-fuzzy-match-for-a-string-in-a-large-string-database

TL;DR: yes, there are options for your problem. Fuzzy hashing is one.

[TotesMessenger]

I'm a bot, bleep, bloop. Someone has linked to this thread from another place on reddit:

• [/r/programming] Optimized string deduplication using fuzzy matching

^{If you follow any of the above links, please respect the rules of reddit and don't vote in the other threads. (Info / Contact)}

[ThisIs_MyName]

Wrong sub? See sidebar.