i am dustin diaz

Autocomplete Fuzzy Matching

Autocomplete widgets live in nearly all systems that requires filtering items via input against large amounts of data. This includes address books, email contacts, restaurants, even social graphs. However, in most matching algorithms, Engineers don't take into account that people don't know how to spell AND/OR are lazy. Thus here is a really simple solution to work around this problem, and in my own opinion, will vastly improve the user experience.

Look ahead matching

Let's say you have five people. Daniel, Dustin, David, Damarcus, and Russ. Now let's say a user types in dus. We would match Dustin and Damarcus. Likewise, if we typed in us, we would get an output of Dustin, Damarcus, and Russ.

Enter RegExp

At this point, it's sort of a no-brainer. Your input-based regular expression can be created as such:

var people = ['Daniel', 'Dustin', 'David', 'Damarcus', 'Russ'];



function matchPeople(input) {

  var reg = new RegExp(input.split('').join('\\w*').replace(/\W/, ""), 'i');

  return people.filter(function(person) {

    if (person.match(reg)) {

      return person;

    }

  });

}

Voila! Now you never have to type another vowel again! (At least in spirit... you know what I mean). In addition to this, you can do further post-process sorting based on Levenshtein distance which will graduate better matches to the top.

An Aside: Caching

Since this tends to do be heavy on regular expression construction, a good idea would be to cache your compiled expressions. This can easily be done using my Cache Provider as such:

var regCache = new CacheProvider;



function matchPeople(input) {

  var reg = regCache.get(input) || regCache.set(input, new RegExp(input.split('').join('\\w*').replace(/\W/, ""), 'i'));

  // etc...

}

Now any subsequent calls to the same input will run against a pre-compiled expression. And that folks, is all I got for the night. Cheers.