Naïve Levinshtein

badlevinshtein.js

// create a 2d array
function createGrid(rows, columns) {
    var grid = new Array(rows);
    for(var i = 0; i < rows; i++) {
        grid[i] = new Array(columns);
        for(var j = 0; j < columns; j++) {
            grid[i][j] = 0;
        }
    }
    return grid;
}

//levinshtein algorithm implemented using dynamic programming method from wikipedia http://en.wikipedia.org/wiki/Levenshtein_distance#Computing_Levenshtein_distance
function calculateLevinshtein(source, target, hashName){
	if(!source){
		source = [];
	}
	
	if(!target){
		target = [];
	}
	
	var grid = createGrid(source.length + 1, target.length + 1);
	for(var row=0; row<grid.length; row++){
		var ops = [];
		if(row > 0){
			ops = grid[row-1][0].ops.concat({opCode: 'delete', i: row, j: 0});
		}
		
		grid[row][0] = {num: row, ops: ops};
	}
	
	for(var col=0; col<grid[0].length; col++){
		var ops = [];
		if(col > 0){
			ops = grid[0][col-1].ops.concat({opCode: 'insert', i: 0, j: col});
		}			
		grid[0][col] = {num: col, ops: ops};
	}
	
	for(var i=1; i<source.length + 1; i++){
		for(var j=1; j< target.length + 1; j++){
			var sourceVal = (hashName ? source[i-1][hashName]() : source[i-1]);
			var targetVal = (hashName? target[j-1][hashName]() : target[j-1]);
			
			if(sourceVal === targetVal){
				grid[i][j] = grid[i-1][j-1];
			}
			else{
				var deletion = grid[i-1][j].num + 1;
				var insertion = grid[i][j-1].num + 1;
				var substitution = grid[i-1][j-1].num + 1;
				
				if(deletion < insertion && deletion < substitution){
					//delete it is
					grid[i][j] = {num: deletion, ops: grid[i-1][j].ops.concat({opCode: 'delete', i: i, j: j})};
				}
				else if(insertion < substitution){
					//insertion it is
					grid[i][j] = {num: insertion, ops: grid[i][j-1].ops.concat({opCode: 'insert', i: i, j: j})};
				}
				else{
					//that just leaves substition
					grid[i][j] = {num: substitution, ops: grid[i-1][j-1].ops.concat({opCode: 'sub', i: i, j: j})};
				}
			}
		}
	}
	
	return grid;
};