Fuzzy String Matching

They’re not equal!How the <<expletive>> do you expect me to find a match?kyle.burton@gmail.comhttp://asymmetrical-view.com/PLUG August 6th 2008How Do You Spell ...?• De Morgan• Di Morgen• D’Morgun• Demorgyn• De Murgen• Dy MoreganEr, So How Can You • Dy MurganFind a Match?• Da MyrgnFuzzy Matching, That’s how•Partial Matching•Phonetic Encodings•String Similarity MetricsHow’d We Get Here?•US Census Bureau• William Winkler (not the Fonz)How’d We Get Here?• Record Linkage, aka Duplicate Detection• My Company Does This! (it’s a complex problem domain)• DNA Comparison and Sequence Alignment• (I don’t do this, but it sounds cool on Tv)•Partial Matching•Phonetic Encodings•String Similarity MetricsPartial Matching• ‘False’ Fuzziness: prefix, suffix, infix• SQL’s ‘%’ operator• n-grams (bi-grams, tri-grams)• foobar => foo, oob, oba, bar• This is infix in disguisePartial Matching• Indexable - fast lookup / search• Fixed Degree of ‘Fuzziness’• Doesn’t scale based on difference• Any hit and you have a match• Can’t Measure Quality of the match• Not going into any detail...you get it.•Partial Matching•Phonetic Encodings•String Similarity MetricsPhonetic Encodings• Soundex, NYSIIS, Double Metaphone• ‘hash’ of input• Fixed fuzziness, one or two degrees