| var makeString = require('./helper/makeString'); |
| |
| /** |
| * Based on the implementation here: https://github.com/hiddentao/fast-levenshtein |
| */ |
| module.exports = function levenshtein(str1, str2) { |
| 'use strict'; |
| str1 = makeString(str1); |
| str2 = makeString(str2); |
| |
| // Short cut cases |
| if (str1 === str2) return 0; |
| if (!str1 || !str2) return Math.max(str1.length, str2.length); |
| |
| // two rows |
| var prevRow = new Array(str2.length + 1); |
| |
| // initialise previous row |
| for (var i = 0; i < prevRow.length; ++i) { |
| prevRow[i] = i; |
| } |
| |
| // calculate current row distance from previous row |
| for (i = 0; i < str1.length; ++i) { |
| var nextCol = i + 1; |
| |
| for (var j = 0; j < str2.length; ++j) { |
| var curCol = nextCol; |
| |
| // substution |
| nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 ); |
| // insertion |
| var tmp = curCol + 1; |
| if (nextCol > tmp) { |
| nextCol = tmp; |
| } |
| // deletion |
| tmp = prevRow[j + 1] + 1; |
| if (nextCol > tmp) { |
| nextCol = tmp; |
| } |
| |
| // copy current col value into previous (in preparation for next iteration) |
| prevRow[j] = curCol; |
| } |
| |
| // copy last col value into previous (in preparation for next iteration) |
| prevRow[j] = nextCol; |
| } |
| |
| return nextCol; |
| }; |