Fuzzy Search or Approximate String Matching

[webmasterkai]

I'd like to see the ability to search tokens based on matching a substring. http://en.wikipedia.org/wiki/Approximate_string_matching

Is the ability to add this dependent on #335? I'm a little surprised this hasn't been requested before. Am I missing something totally obvious?

Thanks!

[ivadenis]

+1

I believe this was implemented in 0.9, but not the case in 0.10

[jharding]

In v0.10, typeahead.js will provide a dataset implementation out of the box. It'll also support custom implementations, so in theory you could write your own dataset that did a fuzzy search.

[yahya-uddin]

+1 on this! VERY important feature for any suggestion engine!

[yahya-uddin]

I managed to get fuzzy search working, but as this repository has been inactive for several months now I really can't be asked to do yet another pull request!

[pratik60]

Sharing the code I used

Gonna go one up, and give the code for fuzzy highlighting

function fuzzyMe(term, query) {
  var score = 0;
  var termLength = term.length;
  var queryLength = query.length;
  var highlighting = '';
  var ti = 0;
  // -1 would not work as this would break the calculations of bonus
  // points for subsequent character matches. Something like
  // Number.MIN_VALUE would be more appropriate, but unfortunately
  // Number.MIN_VALUE + 1 equals 1...
  var previousMatchingCharacter = -2;
  for (var qi = 0; qi < queryLength && ti < termLength; qi++) {
    var qc = query.charAt(qi);
    var lowerQc = qc.toLowerCase();

    for (; ti < termLength; ti++) {
      var tc = term.charAt(ti);

      if (lowerQc === tc.toLowerCase()) {
        score++;

        if ((previousMatchingCharacter + 1) === ti) {
          score += 2;
        }

        highlighting += "<em>" + tc + "</em>";
        previousMatchingCharacter = ti;
        ti++;
        break;
      } else {
        highlighting += tc;
      }
    }
  }

  highlighting += term.substring(ti, term.length);

  return {
    score: score,
    term: term,
    query: query,
    highlightedTerm: highlighting
  };
}

The above takes care of the fuzziness. Then you can just iterate over all your select 2 elements

On typeahead:change

$('#search-bar').typeahead({....}).on('change', function(e) {                     
    var query = $('#search-bar').typeahead('val'); 
     $(".tt-suggestion.tt-selectable .name").each(function() {
        var term = $(this).text();
        $(this).html(fuzzyMe(term, query).highlightedTerm);
      });
});

Credit for fuzzy code -: https://github.com/bripkens/fuzzy.js

I answered the same in stack overflow as well -: http://stackoverflow.com/questions/23226054/add-color-to-match-text-highlighting-in-twitter-typeahead/33030407#33030407