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 have two lists of data, A and B. These lists are themselves aggregated from multiple sources, and contain typos, abbreviations not found in the other, and also lack a 1-1 mapping, but will never have a value in A that maps to two values in B and vice-versa.

Right now, we're doing a naive (string comparison) match to create a map between the two lists. That has about 80% accuracy. I'd like to get that accuracy to at least 90% (95% would be incredible).

Are there any software tools that can be used for something like this? I'd like some sort of tool that could traverse both lists and suggest matches.

Update from comments:

Right now, we only produce a hit if A[x] == B[y]. That gives us matches for 80% of the data in the data sets (which contain roughly fifty thousand rows each). What I'd like to do is find a tool or develop one based on an algorithm that will allow me to suggest a match for two values that are likely to have the same meaning, e.g. KING ROAD and KG RD. These potential matches would then be provided to a human to review and approve or ignore. Generally, I'd use something like Levenshtein, but this is somewhat parametrized data (think addresses) and I don't know how to apply something like Levenshtein to structured data.

share|improve this question
    
can you please show us some string example? –  Jean-François Côté May 2 '13 at 12:56
3  
If you ask for tools, your are on the wrong site. Algorithms and suggestions: of course, try to find the string/strings with the smallest edit-distance (en.wikipedia.org/wiki/Edit_distance), or use Soundex (en.wikipedia.org/wiki/Soundex) –  Doc Brown May 2 '13 at 12:57
    
You must first define your "match" criteria accurately. I second @Doc Brown in his recommendations. –  Emmad Kareem May 2 '13 at 13:29
1  
@JonathanRich then you may have historical evidence of "KG RD", 2009, Pennsylvania from A, and now have "King Road", 2009, Pennsylvania, and be able to use that historical KG RD trusted from A to have a match in B, with the similarity with the current "King Road"s other elements in A and have that trip it over to saying they're the same. That's based on edit distance to begin with though, and the year can give you a conclusive exclusion where edit distance might otherwise say they're close enough. –  Jimmy Hoffa May 2 '13 at 16:46
1  
For addresses you could establish a set of rules how to unify certain fields of the address. In the "street", it makes sense to replace "RD" by "road" like you've mentioned. Other unification examples: &=and Comp=Company. Convert all characters to lowercase and eliminate/replace foreign characters á=a ä=ae ... In the "first name" you could sort multiple names alphabetically. Fields like postcode or phonenumbers are typically more meaningful than others. You could estimate a fuzzy similarity measure and define a threshold for "equal" candidates –  Axel Kemper May 5 '13 at 19:02
show 6 more comments

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.