| // 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 |
| }; |
| } |
| |
| }; |