title: Optimizing String Matching Algorithm
body: <pre><code>function levenshtein(a, b) {
    var i,j,cost,d=[];
  
    if (a.length == 0) {return b.length;}
    if (b.length == 0) {return a.length;}
  
    for ( i = 0; i &lt;= a.length; i++) {
      d[i] = new Array();
      d[ i ][0] = i;
    }
  
    for ( j = 0; j &lt;= b.length; j++) {
      d[ 0 ][j] = j;
    }
  
    for ( i = 1; i &lt;= a.length; i++) {
      for ( j = 1; j &lt;= b.length; j++) {
        if (a.charAt(i - 1) == b.charAt(j - 1)) {
          cost = 0;
        } else {
          cost = 1;
        }
  
        d[ i ][j] = Math.min(d[ i - 1 ][j] + 1, d[ i ][j - 1] + 1, d[ i - 1 ][j - 1] + cost);
  
        if (i &gt; 1 &amp;&amp; j &gt; 1 &amp;&amp; a.charAt(i - 1) == b.charAt(j - 2) &amp;&amp; a.charAt(i - 2) == b.charAt(j - 1)) {
          d[i][j] = Math.min(d[i][j], d[i - 2][j - 2] + cost)
        }
      }
    }
  
    return d[ a.length ][b.length];
  }
  
  function suggests(suggWord) {
    var sArray = [];
    for(var z = words.length;--z;) {
      if(levenshtein(words[z],suggWord) &lt; 2) { 
        sArray.push(words[z]);
      }   
    }
  }
  </code></pre>
  
  <p>Hello.</p>
  
  <p>I'm using the above implementation of Damerau-Levenshtein algorithm. Its fast enough on a normal PC browser, but on a tablet it takes ~2/3 seconds.</p>
  
  <p>Basically, I'm comparing the word sent to a suggest function to every word in my dictionary, and if the distance is less than 2 adding it to my array.</p>
  
  <p>The dic is an array of words approx size 600,000 (699KB)
  The aim of this is to make a suggest word feature for my Javascript spell checker.</p>
  
  <p>Any suggestion on how to speed this up? Or a different way of doing this?</p>