Skip to content

Instantly share code, notes, and snippets.

@omarstreak
Created July 9, 2012 20:29
Show Gist options
  • Save omarstreak/3078704 to your computer and use it in GitHub Desktop.
Save omarstreak/3078704 to your computer and use it in GitHub Desktop.
Fast non-optimal one step lookahead Levinshtein
// 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;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment