title: Javascript fuzzy search that makes sense
body: <p>I'm looking for a fuzzy search JavaScript library to filter an array. I've tried using <a href="http://glench.github.io/fuzzyset.js/" rel="noreferrer">fuzzyset.js</a> and <a href="https://fusejs.io/" rel="noreferrer">fuse.js</a>, but the results are terrible (there are demos you can try on the linked pages).</p>
  <p>After doing some reading on Levenshtein distance, it strikes me as a poor approximation of what users are looking for when they type. For those who don't know, the system calculates how many <strong>insertions</strong>, <strong>deletions</strong>, and <strong>substitutions</strong> are needed to make two strings match.</p>
  <p>One obvious flaw, which is fixed in the Levenshtein-Demerau model, is that both <em>blub</em> and <em>boob</em> are considered equally similar to <em>bulb</em> (each requiring two substitutions). It is clear, however, that <em>bulb</em> is more similar to <em>blub</em> than <em>boob</em> is, and the model I just mentioned recognizes that by allowing for <strong>transpositions</strong>.</p>
  <p>I want to use this in the context of text completion, so if I have an array <code>['international', 'splint', 'tinder']</code>, and my query is <em>int</em>, I think <em>international</em> ought to rank more highly than <em>splint</em>, even though the former has a score (higher=worse) of 10 versus the latter's 3.</p>
  <p>So what I'm looking for (and will create if it doesn't exist), is a library that does the following:</p>
  <ul>
  <li>Weights the different text manipulations</li>
  <li>Weights each manipulation differently depending on where they appear in a word (early manipulations being more costly than late manipulations)</li>
  <li>Returns a list of results sorted by relevance</li>
  </ul>
  <p>Has anyone come across anything like this? I realize that StackOverflow isn't the place to be asking for software recommendations, but implicit (not anymore!) in the above is: am I thinking about this the right way?</p>
  <hr />
  <h2>Edit</h2>
  <p>I found a <a href="https://web.archive.org/web/20160804043501/https://www.cs.cmu.edu/%7Epradeepr/papers/ijcai03.pdf" rel="noreferrer">good paper (pdf)</a> on the subject. Some notes and excerpts:</p>
  <blockquote>
  <p>Affine edit-distance functions assign a relatively lower cost to a sequence of insertions or deletions</p>
  </blockquote>
  <blockquote>
  <p>the Monger-Elkan distance function (Monge &amp; Elkan 1996), which is an affine variant of the Smith-Waterman distance function (Durban et al. 1998) with particular cost parameters</p>
  </blockquote>
  <p>For the <a href="http://en.wikipedia.org/wiki/Smith%E2%80%93Waterman_algorithm" rel="noreferrer">Smith-Waterman distance (wikipedia)</a>, &quot;Instead of looking at the total sequence, the Smith–Waterman algorithm compares segments of all possible lengths and optimizes the similarity measure.&quot; It's the n-gram approach.</p>
  <blockquote>
  <p>A broadly similar metric, which is not based on an edit-distance model, is the
  Jaro metric (Jaro 1995; 1989; Winkler
  1999). In the record-linkage literature, good results have been obtained using variants of this method, which is based on the number and order of the common characters between two strings.</p>
  </blockquote>
  <blockquote>
  <p>A variant of this due to Winkler (1999) also uses the length P of the longest common prefix</p>
  </blockquote>
  <blockquote>
  <p>(seem to be intended primarily for short strings)</p>
  </blockquote>
  <p>For text completion purposes, the Monger-Elkan and Jaro-Winkler approaches seem to make the most sense. Winkler's addition to the Jaro metric effectively weights the beginnings of words more heavily. And the affine aspect of Monger-Elkan means that the necessity to complete a word (which is simply a sequence of additions) won't disfavor it too heavily.</p>
  <p>Conclusion:</p>
  <blockquote>
  <p>the TFIDF
  ranking performed best among several token-based distance
  metrics, and a tuned affine-gap edit-distance metric proposed by Monge and Elkan performed best among several
  string edit-distance metrics. A surprisingly good distance
  metric is a fast heuristic scheme, proposed by Jaro and later extended by Winkler.
  This works almost as well as the Monge-Elkan scheme, but
  is an order of magnitude faster.
  One simple way of combining the TFIDF method and the
  Jaro-Winkler is to replace the exact token matches used in
  TFIDF with approximate token matches based on the Jaro-
  Winkler scheme. This combination performs slightly better than either Jaro-Winkler or TFIDF on average, and occasionally performs much better. It is also close in performance to a learned combination of several of the best metrics
  considered in this paper.</p>
  </blockquote>