{"id":215,"date":"2012-04-16T19:37:19","date_gmt":"2012-04-17T02:37:19","guid":{"rendered":"http:\/\/adam.yanalunas.com\/blog\/?p=215"},"modified":"2012-04-16T19:37:19","modified_gmt":"2012-04-17T02:37:19","slug":"calculating-levenshtein-distance-for-fun-and-profit","status":"publish","type":"post","link":"http:\/\/adam.yanalunas.com\/blog\/archives\/215","title":{"rendered":"Calculating Levenshtein distance for fun and profit"},"content":{"rendered":"

JavaScript has some pretty weak tools for strings. What method would you use to compare simliar-but-different strings? Say, for example, you have a signup form and when someone is typing in their email address you want to be helpful and check to see if they may have typed “gmial.com” instead of “gmail.com” or “em.com” instead of “me.com”. I give you the Levenshtein distance<\/a>!<\/p>\n

The Levenshtein distance is an oft-used algorithm for determining the similarity of two strings, measured in the number of changes you’d have to make to one string to make it into the other. So strings a distance of 5 would require five letter changes to be the same, a distance of 7 would need seven edits and so on. <\/p>\n

For reference, I have used Carlos Rodrigues’ implementation of the Levenshtein distance<\/a> in previous projects with great success. Yes, it is attached to the String prototype. No, I don’t have a problem with that, nor should you. Arguments about prototype purity will be saved for another day.<\/p>\n

Levenshtein, how does it work?<\/h2>\n

In practice finding the distance between two strings is easy. Just do this:<\/p>\n

\r\nvar barDiff = 'bar'.levenshtein('baz');\r\nconsole.log('difference: ' + barDiff);\r\n\/\/Outputs: "difference: 1"\r\nvar jsDiff = 'javascript'.levenshtein('JavaScript');\r\nconsole.log('difference: ' + jsDiff);\r\n\/\/Outputs: "difference: 2"\r\n<\/pre>\n
Did you see that? Yes, Levenshtein is a case-sensitive comparison, just like the rest of JavaScript. Keep that in mind and sanitize\/mutate your comparisons accordingly.<\/p>\n
That’s it! Take this information and go write something clever and useful for your users. Also, keep an eye on my GitHub account<\/a> for a Backbone extension that will automatically suggest proper email provider spellings for you users.<\/p>\n","protected":false},"excerpt":{"rendered":"
JavaScript has some pretty weak tools for strings. What method would you use to compare simliar-but-different strings? Say, for example, you have a signup form and when someone is typing in their email address you want to be helpful and check to see if they may have typed “gmial.com” instead of “gmail.com” or “em.com” instead […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[6],"tags":[],"_links":{"self":[{"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/posts\/215"}],"collection":[{"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/comments?post=215"}],"version-history":[{"count":3,"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/posts\/215\/revisions"}],"predecessor-version":[{"id":218,"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/posts\/215\/revisions\/218"}],"wp:attachment":[{"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/media?parent=215"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/categories?post=215"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/adam.yanalunas.com\/blog\/wp-json\/wp\/v2\/tags?post=215"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}