Complex string matching with fuzzywuzzy

Question

I'm attempting to write a process that matches obscure strings to a single 'master string' for further processing. I have a lot of data that looks something like this:

Basketball
Basket Ball
Football
BasketBallR
BBall
BBall - r
FootB

...and so on. These need to be mapped to a master record like so:

Basketball       = Basket Ball, BBall
Basketball - R   = BasketBallR, BBall - r

I also have instances of data resembling this format:

Football -r
FootBall - r-g/H,Q,HH

These situations need to be separated into different categories before being mapped. For example FootBall - r-g/H,Q,HH should be:

Football - r
Football - g
Football - H
Football - Q
Football - HH

At this point, it still needs to be mapped to a master record...

I've tried several different combinations of fuzzywuzzy matching methods, Levenshtein Distance measurements, regex, etc. and can't seem to find a reliable method to logically associate different naming styles of a single item with a master name.

I'm throwing my hands up in desperation. Are there any existing python resources than can help sort out my problem? Are there other options? Can anybody point out an obvious option that I might have overlooked?

Basically, any suggestion, solution, resource or alternative method is greatly appreciated.

Answer 1

Fortunately, I'm not one to give up easily. Through reaching out to other sources/communities I found Google Refine which (amazingly) completely resolves my matching issues 90% of the time, and leaves the remaining 10% incredibly manageable and easy to manually resolve. I hope this might help other people facing similar issues.

Answer 2

I wrote something very similar at one time where I needed to write business logic to do a reasonably good job with matching various nick names and diminutive first names to person records with their full legal name. Eg. (James Smith = Jim Smith = Jimmy Smith etc...)

I resolved the problem by essentially compiling and slowly building a CSV file that had a proper name, and each comma delimited value after the first value on a line represented every known diminutive name I could think of. For purposes of memory consumption and processing time I preloaded the data of the CSV file into a map of string sets.

I created a unique key for each map entry for every single first name, proper and diminutive. Why? So that I could easily and quickly fetch *every possible proper and diminutive name by any given proper or dimunitive name. I used the singleton pattern because obviously this object is expensive to build and consumes quite a deal of memory, however once this object is constructed it is insanely quick to fetch not only the proper name from a diminutive name, but also to fetch other possible diminutive names.

As the system encounters new dimunitive names it will proceed to slowly add new matches and increase the success rate.

If the data set in question is relatively manageable, and memory is cheap for your scenario, you might find this to be an excellent design idea.

Unfortunately I don't think you are going to find a catch all regex pattern that is going to arbitrarily find matches like this in a data set. Their are no clear rules to how any two words can compare in your situation. The best way to do this is to pre-associate the data once, or to pre associate manageable or indexed chunks of the data all at once.

EDIT:

If you are dealing with an enormous set of data then obviously the above will not work. In this case I advise looking into a massively parallel solution utilizing a Map Reduce algorithm. Apache Hadoop is a great open source project that manages a lot of the complexity of these kinds of applications for JVM based languages. I am not sure if such a project exists for Python.