Levenshtein Distance Algorithm: JavaScript Implementation
by Lukasz Stilger
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=Windows-1250">
<title>LD - Lukasz Stilger</title>
<script language="javascript">
var dG = new Array();
function Minimum(a, b, c) {
var mi;
mi = a;
if (b < mi)
mi = b;
if (c < mi)
mi = c;
return mi;
}
function LD(s, t) {
var d = new Array();
var n; // length of s
var m; // length of t
var i; // iterates through s
var j; // iterates through t
var s_i; // ith character of s
var t_j; // jth character of t
var cost; // cost
// Step 1
n = s.length;
m = t.length;
if (n == 0) {
return m;
}
if (m == 0) {
return n;
}
//inicjacja tablicy dwu-wymiarowej w Javascript
for(i=0; i<=n; i++)
d[i] = new Array();
// Step 2
for (i = 0; i <= n; i++) {
d[i][0] = i;
}
for (j = 0; j <= m; j++) {
d[0][j] = j;
}
// Step 3
for (i = 1; i <= n; i++) {
s_i = s.charAt(i - 1);
// Step 4
for (j = 1; j <= m; j++) {
t_j = t.charAt(j - 1);
// Step 5
if (s_i == t_j) {
cost = 0;
}
else {
cost = 1;
}
// Step 6
d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cost);
}
}
//przepisanie do tablicy globalnej
for(i=1; i<=n; i++) {
dG[i] = new Array();
for(j=1; j<=m; j++)
dG[i][j] = d[i][j];
}
// Step 7
return d[n][m];
}
function drawResult() {
//alert(LD("gumbo","gambol"));
var t1 = document.getElementById('Text1').value;
var t2 = document.getElementById('Text2').value;
var n = t1.length;
var m = t2.length;
var i,j;
LD(t1,t2);
mHTML = "<table border=1 cellpadding=5>";
for(i=0; i<=m+1; i++) {
mHTML += "<tr>";
for(j=0; j<=n+1; j++) {
//oznaczanie id komorek wypelnianych
if(i>1 && j>1) {
mHTML += "<td id=" + i + "-" + j + " align=center>";
if(i==(m+1) && j==(n+1))
mHTML += "<font color=\"red\"><b>";
mHTML += dG[j-1][i-1];
}
else
mHTML += "<td align=center>";
//wypisywanie numerow wierszy i kolumn
if(i==1 && j>0)
mHTML += "<b>" + (j-1) + "</b>";
if(j==1 && i>1)
mHTML += "<b>" + (i-1) + "</b>";
//wypisywanie literek
if(i==0 && j>1) {
mHTML += "<font color=blue size=5>" + t1.charAt(j-2) + "</font>";
} else {
if(j==0 && i>1)
mHTML += "<font color=blue size=5>" + t2.charAt(i-2) + "</font>";
else {
if(j==0 && i==0)
mHTML += "";
//else
// mHTML += "x";
}
}
mHTML += "</td>";
}
mHTML += "</tr>";
}
mHTML += "</table>";
//rysowanie tabeli
document.getElementById('result').innerHTML = mHTML;
}
</script>
</head>
<body onload="drawResult()">
<center>
Created by <a href="mailto:lukasz@semibit.com">Lukasz Stilger</a> 2003
<form ID="Form1">
<input type="text" ID="Text1" NAME="Text1" value="wyraz" onKeyUp="drawResult()" onchange="drawResult()">
<input type="text" ID="Text2" NAME="Text2" value="wyraz" onKeyUp="drawResult()" onchange="drawResult()">
<!--<input type="button" ID="Button1" NAME="Button1" value="Rysuj" onclick="drawResult()">-->
</form>
<p id="result"></p>
<a href="http://www.merriampark.com/ld.htm">Levenshtein Distance</a>
</center>
</body>
</html>