Damerau-Levenshtein Distance

HTML

<label for="input">Comparison Term</label>
<input type="text" id="input"/>
<label for="checkbox">Use Damerau-Levenschtein</label>
<input type="checkbox" id="checkbox" checked="true"/>
<ol id="words">
    <li>Feed</li>
    <li>Flee</li>
    <li>File</li>
    <li>Flier</li>
</ol>

CSS

html, body {
    font-family: "Helvetica Neue", Arial, sans-serif;
    font-size: 14px;
    color: #222;
}

label {
    margin: 4px;
}

input {
    border: 1px solid #999;
    padding: 4px;
}

ol {
    list-style-type: decimal;
    list-style-position: inside;
    margin-top: 20px;
}

li {
    background: #f2f2f2;
    margin-bottom: 1px;
    padding: 4px;
}

JavaScript

var list = $('#words');
var items = list.find('li');
var damerau = true;
var words = [];
items.each(function(){
    words.push($(this).text());
});

function levenshtein(a, b, d) {
    var x = a.length, y = b.length;
    var i, j, c, m = [];
    for(i = 0; i <= x; i++) {
        m[i] = [];
        m[i][0] = i;
    }
    for(i = 0; i <= y; i++) {
        m[0][i] = i;
    }
    for(i = 1; i <= x; i++) {
      for(j = 1; j <= y; j++) {
          c = (a[i - 1] === b[j - 1] ? 0 : 1);
          m[i][j] = Math.min(m[i - 1][j] + 1, m[i][j - 1] + 1, m[i - 1][j - 1] + c);
          if(d && i > 1 && j > 1 && a[i] === b[j - 1] && a[i - 1] === b[j]) {
              d[i, j] = Math.min(m[i, j], d[i - 2, j - 2] + c);
          }
      }  
    }
    return m[x][y];
}

function sort(w) {
    var i, d, item, index = [];
    for(i = 0, n = words.length; i < n; i++) {
        d = levenshtein(w, words[i], damerau);
        index.push({
            dist: d / w.length,
            word: words[i]
        });
    }
    index.sort(function(a,b){
        return a.dist - b.dist;
    });
    list.children().remove();
    for(i = 0, n = index.length; i < n; i++) {
        item = $('<li>').text(index[i].word + ' (' + index[i].dist.toFixed(3) + ')');
        list.append(item);
    }
}

$('#input').keyup(function(){
    var s = $('#input').val();
    sort(s);
});