javascript Approximate string matching

gistfile1.js

// http://en.wikipedia.org/wiki/Approximate_string_matching
function fuzzySearch(t, p) { // returns minimum edit distance between substring of t and p
  var a = [], // current row
      b = [], // previous row
      pa = [], // from
      pb = [],
      s, i, j;
  for (i = 0; i <= p.length; i++) {
    s = b;
    b = a;
    a = s;
    s = pb;
    pb = pa;
    pa = s;
    for (j = 0; j <= t.length; j++) {
      if (i && j) {
        a[j] = a[j - 1] + 1;
        pa[j] = pa[j - 1];

        s = b[j - 1] + (t[j - 1] === p[i - 1] ? 0 : 1);
        if (a[j] > s) {
          a[j] = s;
          pa[j] = pb[j - 1];
        }

        if (a[j] > b[j] + 1) {
          a[j] = b[j] + 1;
          pa[j] = pb[j];
        }
      } else {
        a[j] = i;
        pa[j] = j;
      }
    }
  }

  s = 0;
  for (j = a.length - 1; j >= 1; j--) {
    if (a[j] < a[s]) {
      s = j;
    }
  }

  return {
    distance: a[s],
    substring: t.slice(pa[s], s)
  };
}

var tt = 'tdest';
var pp = 'test';
alert(fuzzySearch(tt, pp).substring + ' ! ' + fuzzySearch(tt, pp).distance);
/*
0,0,0,0,0,0
1,0,1,1,1,0
2,1,0,1,2,1
3,2,1,1,1,2
4,3,2,2,2,1
5,4,3,3,3,2
*/

var x = 'Госпожа горничная История любви пуэрториканской горничной шикарного а'.slice(0, 70);
var y = 'Гdоспожа горничная История любви пуэрториканской горничной шикарного а'.slice(0, 70);
var t = 0, i, n = 5000;
t = +new Date;
for(i = 0;i< n;i++)
  fuzzySearch(x.split(''), y.split(''));
t = +new Date - t;

alert(t);