73 lines
1.9 KiB
JavaScript
73 lines
1.9 KiB
JavaScript
|
// TheSpanishInquisition
|
||
|
|
|
||
|
|
// Cache the matrix. Note that if you not pass a limit this implementation will use a dynamically calculate one.
|
||
|
|
|
||
|
|
module.exports = function(__this, that, limit) {
|
||
|
|
|
||
|
|
var thisLength = __this.length,
|
||
|
|
thatLength = that.length,
|
||
|
|
matrix = [];
|
||
|
|
|
||
|
|
// If the limit is not defined it will be calculate from this and that args.
|
||
|
|
limit = (limit || ((thatLength > thisLength ? thatLength : thisLength)))+1;
|
||
|
|
|
||
|
|
for (var i = 0; i < limit; i++) {
|
||
|
|
matrix[i] = [i];
|
||
|
|
matrix[i].length = limit;
|
||
|
|
}
|
||
|
|
for (i = 0; i < limit; i++) {
|
||
|
|
matrix[0][i] = i;
|
||
|
|
}
|
||
|
|
|
||
|
|
if (Math.abs(thisLength - thatLength) > (limit || 100)){
|
||
|
|
return prepare (limit || 100);
|
||
|
|
}
|
||
|
|
if (thisLength === 0){
|
||
|
|
return prepare (thatLength);
|
||
|
|
}
|
||
|
|
if (thatLength === 0){
|
||
|
|
return prepare (thisLength);
|
||
|
|
}
|
||
|
|
|
||
|
|
// Calculate matrix.
|
||
|
|
var j, this_i, that_j, cost, min, t;
|
||
|
|
for (i = 1; i <= thisLength; ++i) {
|
||
|
|
this_i = __this[i-1];
|
||
|
|
|
||
|
|
// Step 4
|
||
|
|
for (j = 1; j <= thatLength; ++j) {
|
||
|
|
// Check the jagged ld total so far
|
||
|
|
if (i === j && matrix[i][j] > 4) return prepare (thisLength);
|
||
|
|
|
||
|
|
that_j = that[j-1];
|
||
|
|
cost = (this_i === that_j) ? 0 : 1; // Step 5
|
||
|
|
// Calculate the minimum (much faster than Math.min(...)).
|
||
|
|
min = matrix[i - 1][j ] + 1; // Deletion.
|
||
|
|
if ((t = matrix[i ][j - 1] + 1 ) < min) min = t; // Insertion.
|
||
|
|
if ((t = matrix[i - 1][j - 1] + cost) < min) min = t; // Substitution.
|
||
|
|
|
||
|
|
// Update matrix.
|
||
|
|
matrix[i][j] = (i > 1 && j > 1 && this_i === that[j-2] && __this[i-2] === that_j && (t = matrix[i-2][j-2]+cost) < min) ? t : min; // Transposition.
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
return prepare (matrix[thisLength][thatLength]);
|
||
|
|
|
||
|
|
/**
|
||
|
|
*
|
||
|
|
*/
|
||
|
|
function prepare(steps) {
|
||
|
|
var length = Math.max(thisLength, thatLength)
|
||
|
|
var relative = length === 0
|
||
|
|
? 0
|
||
|
|
: (steps / length);
|
||
|
|
var similarity = 1 - relative
|
||
|
|
return {
|
||
|
|
steps: steps,
|
||
|
|
relative: relative,
|
||
|
|
similarity: similarity
|
||
|
|
};
|
||
|
|
}
|
||
|
|
|
||
|
|
};
|