www.aleph1.co.uk Git - yaffs-website/blob - node_modules/underscore.string/levenshtein.js

   1 var makeString = require('./helper/makeString');
   2
   3 /**
   4  * Based on the implementation here: https://github.com/hiddentao/fast-levenshtein
   5  */
   6 module.exports = function levenshtein(str1, str2) {
   7   'use strict';
   8   str1 = makeString(str1);
   9   str2 = makeString(str2);
  10
  11   // Short cut cases
  12   if (str1 === str2) return 0;
  13   if (!str1 || !str2) return Math.max(str1.length, str2.length);
  14
  15   // two rows
  16   var prevRow = new Array(str2.length + 1);
  17
  18   // initialise previous row
  19   for (var i = 0; i < prevRow.length; ++i) {
  20     prevRow[i] = i;
  21   }
  22
  23   // calculate current row distance from previous row
  24   for (i = 0; i < str1.length; ++i) {
  25     var nextCol = i + 1;
  26
  27     for (var j = 0; j < str2.length; ++j) {
  28       var curCol = nextCol;
  29
  30       // substution
  31       nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
  32       // insertion
  33       var tmp = curCol + 1;
  34       if (nextCol > tmp) {
  35         nextCol = tmp;
  36       }
  37       // deletion
  38       tmp = prevRow[j + 1] + 1;
  39       if (nextCol > tmp) {
  40         nextCol = tmp;
  41       }
  42
  43       // copy current col value into previous (in preparation for next iteration)
  44       prevRow[j] = curCol;
  45     }
  46
  47     // copy last col value into previous (in preparation for next iteration)
  48     prevRow[j] = nextCol;
  49   }
  50
  51   return nextCol;
  52 };