EditDistanceMatcher - NodeJS script for doing edit distance 1 matching

05 February 2011   0 comments   Javascript

https://gist.github.com/812443

Mind That Age!

This blog post is 6 years old! Most likely, its content is outdated. Especially if it's technical.

Powered by Fusion×

I needed a very basic spell correction string matcher in my current NodeJS project so I wrote a simple class called EditDistanceMatcher that compares a string against another string and matches if it's 1 edit distance away. With it you can do things like Google search's "Did you mean: poop?" when you search for pop.

Note, this code doesn't check popularity of correct words (e.g. "pop" might appear much more often than "poop" so it'll suggest "pop" if you enter "poup"). Anyway this simple snippet from the unit tests will reveal how it works:

     /* The match() method */
     var edm = new EditDistanceMatcher(["peter"]);
     // edm.match returns an array and remember,
     // in javascript ['peter'] == ['peter'] => false
     test.equal(edm.match("petter").length, 1);
     test.equal(edm.match("petter")[0], 'peter');
     test.equal(edm.match("junk").length, 0);

     /* the is_matched() method */
     var edm = new EditDistanceMatcher(["peter"]);
     test.equal(typeof edm.is_matched('petter'), 'boolean');
     test.equal(typeof edm.is_matched('junk'), 'boolean');
     test.ok(edm.is_matched("petter"));
     test.ok(!edm.is_matched("junk"));

The most basic use case is if you have a quiz and you want to accept some spelling mistakes. "What's the capital of Sweden?; STOKHOLM; Correct!"

For the unlazy this NodeJS code can very easily be used in a browser by simply removing the exports stuff.

edit_distance.js

tests/test_edit_distance.js

Note! I wrote this in an airport lounge so I'm sure it can be improved lots more.

Follow @peterbe on Twitter

Comments

Thank you for posting a comment

Your email will never ever be published


Related posts

Previous:
DoneCal on MumbaiMirror 03 February 2011
Next:
DoneCal homepage now able to do 10,000 requests/second 13 February 2011
Related by Keyword:
Python slow-down of exception handling or condition checking 14 May 2015
"Did you mean this domain?" Auto-correction for the browser's address bar 05 April 2013
How I stopped worrying about IO blocking Tornado 18 September 2012
Slides about Kwissle from yesterdays London Python Dojo 08 July 2011
RequireJS versus HeadJS 09 January 2011
Related by Text:
Too much Python makes Peter a shit Javascript developer 13 March 2009
Major performance fix on file searches 19 November 2005
Introducing django-spellcorrector 28 May 2009
json-schema-reducer 02 August 2016
A decent Elasticsearch search engine implementation 09 April 2017