{"id":1517,"date":"2015-01-16T15:46:45","date_gmt":"2015-01-16T14:46:45","guid":{"rendered":"http:\/\/www.andrewj.com\/blog\/?p=1517"},"modified":"2015-01-16T15:46:45","modified_gmt":"2015-01-16T14:46:45","slug":"efficient-fuzzy-matching-at-word-level","status":"publish","type":"post","link":"https:\/\/www.andrewj.com\/blog\/2015\/efficient-fuzzy-matching-at-word-level\/","title":{"rendered":"Efficient Fuzzy Matching at Word Level"},"content":{"rendered":"

I’ve just solved a tricky problem with what I think is quite an elegant solution, and thought it would be interesting to share it.<\/p>\n

I’m building a system in which I have to process fault data. Sometimes this comes with a standard fault code (hallelujah!), but quite often it comes with the manufacturer’s own fault code and a description which may (or may not) be quite close to the description against one of the standard faults. If I can match the description up, I can treat the fault as standard.<\/p>\n

The problem is that the description matching is not exact. Variations in punctuation are common, but the wording can also change so that, for example, “Evaporative emission system incorrect purge flow” in one system is “Evaporative emission control <\/em>system incorrect purge flow” in another. To a human reader this is fine, but eliminates simplistic exact matching.<\/p>\n

I spent some time Googling fuzzy matching, but most of the available literature focuses on character or even bit-level matching and looks both complex and compute-intensive. However finally I found the Jaccard similarity coefficient<\/b>. This is designed for establishing the “similarity” between two objects with similar lists of attributes, and I had a “lights on” moment and realised I could apply a similar algorithm, but to the set of words used in the pair of descriptions.<\/p>\n

The algorithm to calculate the coefficient for a given pair is actually very simple:<\/p>\n

    \n
  1. Convert Text1 to a list of words\/tokens, excluding spaces and punctuation. In VB.NET the string.split() function does this very neatly and you can specify exactly what counts as punctuation or white space. For simplicity it’s a good idea to convert both strings to uppercase to eliminate capitalisation variations.<\/li>\n
  2. Convert Text2 to a list of tokens on the same basis.<\/li>\n
  3. For each token from Text1, see if it appears in the list of tokens from Text2. If so, increment a counter M<\/li>\n
  4. For each token from Text2, see if it appears in the list of tokens from Text1. If so, increment M<\/li>\n
  5. Calculate the coefficient as M \/ (total number of tokens from both lists)<\/li>\n<\/ol>\n

    This produces a very intuitive result: 1 if the token sets are an exact match, 0 if they are completely disjoint, and a linearly varying value between. The process does, however, ignore transpositions, so that “Fuel rail pressure low” equates to “Fuel rail low pressure”. In my context this matches what a human assessor would do.<\/p>\n

    Now I simply have to repeat steps 2-5 above for each standard error description, and pick the one which produces the highest coefficient. If the value is below about 80% I treat the string as “matched”, and I can quote the coefficient to give a feel for “how good” the match is.<\/p>\n

    Hopefully that’s useful.<\/p>\n","protected":false},"excerpt":{"rendered":"

    I’ve just solved a tricky problem with what I think is quite an elegant solution, and thought it would be interesting to share it. I’m building a system in which I have to process fault data. Sometimes this comes with … Continue reading →<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7,9],"tags":[],"_links":{"self":[{"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/posts\/1517"}],"collection":[{"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/comments?post=1517"}],"version-history":[{"count":0,"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/posts\/1517\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/media?parent=1517"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/categories?post=1517"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.andrewj.com\/blog\/wp-json\/wp\/v2\/tags?post=1517"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}