Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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.

share|improve this question
    
Are all the variations known in advance, or do you need to be able to match a variation you've never seen before, just based on similarity? –  Karl Bielefeldt Oct 16 '12 at 20:10
    
@KarlBielefeldt Variations are not known in advance. –  That1Guy Oct 16 '12 at 20:46

2 Answers 2

up vote 3 down vote accepted

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.

share|improve this answer
2  
Nice find. Google Refine looks truly awesome. –  Steve Evers Oct 17 '12 at 19:30
1  
Looks like Google may have open sourced the project under GitHub, with a slightly different name: github.com/OpenRefine –  Joshua Burns Oct 17 '12 at 20:18

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.

share|improve this answer
    
Thanks, I think I'm goign to have to go the Hadoop route or something similar. I have several million records that need to be processed, and to add to the complexity, the trailing characters correspond to different attributes about the "Football". For example -r might mean "red", whereas -g might mean "this particular ball was only manufactured in 1987". To further add to the problem, these patters are not consistent among different football manufacturers. -r could have multiple definitions. Thanks for the help, though. –  That1Guy Oct 16 '12 at 20:05
    
@That1Guy No problem, unfortunately your situation is a little beyond my expertise though. Hopefully someone else may chime in with a better suggestion than myself. –  maple_shaft Oct 16 '12 at 22:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.