FasterLevinshtein.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;
}

//calculate faster levinschtein
function calculateFastLevinshtein(source, target){
	var ops = [];
	
	var sourceIndex = 0;
	var targetIndex = 0;
	
	//helper functions
	var deleteChainLength = function(){
		if(source[sourceIndex+1] === target[targetIndex]){
			return 1;
		}
		else{
			return -1;
		}								
	};
	
	var insertChainLength = function(){
		if(source[sourceIndex] === target[targetIndex +1]){
			return 1;
		}
		else{
			return -1;
		}						
	};
	
	
	for(var sourceIndex=0; sourceIndex<source.length;){
		if(targetIndex >= target.length){
			break;
		}
		
		if(source[sourceIndex] === target[targetIndex]){
			targetIndex++;
			sourceIndex++;
		}
		else{
			//mismatch, need to check now for a delete chain, or an insert chain
			var deleteChain = deleteChainLength();
			if(deleteChain > 0){
				for(var i=0; i<deleteChain; i++){
					ops.push({opCode: 'delete', i: sourceIndex, j: targetIndex});
					sourceIndex++;
				}
			}
			else{
				var insertChain = insertChainLength();
				if(insertChain > 0){
					for(var i=0; i<insertChain; i++){
						ops.push({opCode: 'insert', i: sourceIndex, j: targetIndex});
						targetIndex++;
					}
				}
				else{
					ops.push({opCode: 'sub', i: sourceIndex, j: targetIndex});
					targetIndex++;
					sourceIndex++;
				}
			}				
		}
	}	
	
	for(; targetIndex<target.length; targetIndex++){
		ops.push({opCode: 'insert', i: sourceIndex, j: targetIndex});
	}
	
	for(; sourceIndex < source.length; sourceIndex++){
		ops.push({opCode: 'delete', i: sourceIndex, j: Math.min(targetIndex, target.length-1)});
	}
	
	return ops;
};