src/js/levenshtein.js

   1 // source
   2 // https://github.com/hiddentao/fast-levenshtein/blob/2.0.6/levenshtein.js
   3 (function() {
   4   'use strict';
   5
   6   var collator;
   7   try {
   8     collator = (typeof Intl !== "undefined" && typeof Intl.Collator !== "undefined") ? Intl.Collator("generic", { sensitivity: "base" }) : null;
   9   } catch (err){
  10     console.log("Collator could not be initialized and wouldn't be used");
  11   }
  12   // arrays to re-use
  13   var prevRow = [],
  14     str2Char = [];
  15
  16   /**
  17    * Based on the algorithm at http://en.wikipedia.org/wiki/Levenshtein_distance.
  18    */
  19   var Levenshtein = {
  20     /**
  21      * Calculate levenshtein distance of the two strings.
  22      *
  23      * @param str1 String the first string.
  24      * @param str2 String the second string.
  25      * @param [options] Additional options.
  26      * @param [options.useCollator] Use `Intl.Collator` for locale-sensitive string comparison.
  27      * @return Integer the levenshtein distance (0 and above).
  28      */
  29     get: function(str1, str2, options) {
  30       var useCollator = (options && collator && options.useCollator);
  31
  32       var str1Len = str1.length,
  33         str2Len = str2.length;
  34
  35       // base cases
  36       if (str1Len === 0) return str2Len;
  37       if (str2Len === 0) return str1Len;
  38
  39       // two rows
  40       var curCol, nextCol, i, j, tmp;
  41
  42       // initialise previous row
  43       for (i=0; i<str2Len; ++i) {
  44         prevRow[i] = i;
  45         str2Char[i] = str2.charCodeAt(i);
  46       }
  47       prevRow[str2Len] = str2Len;
  48
  49       var strCmp;
  50       if (useCollator) {
  51         // calculate current row distance from previous row using collator
  52         for (i = 0; i < str1Len; ++i) {
  53           nextCol = i + 1;
  54
  55           for (j = 0; j < str2Len; ++j) {
  56             curCol = nextCol;
  57
  58             // substution
  59             strCmp = 0 === collator.compare(str1.charAt(i), String.fromCharCode(str2Char[j]));
  60
  61             nextCol = prevRow[j] + (strCmp ? 0 : 1);
  62
  63             // insertion
  64             tmp = curCol + 1;
  65             if (nextCol > tmp) {
  66               nextCol = tmp;
  67             }
  68             // deletion
  69             tmp = prevRow[j + 1] + 1;
  70             if (nextCol > tmp) {
  71               nextCol = tmp;
  72             }
  73
  74             // copy current col value into previous (in preparation for next iteration)
  75             prevRow[j] = curCol;
  76           }
  77
  78           // copy last col value into previous (in preparation for next iteration)
  79           prevRow[j] = nextCol;
  80         }
  81       }
  82       else {
  83         // calculate current row distance from previous row without collator
  84         for (i = 0; i < str1Len; ++i) {
  85           nextCol = i + 1;
  86
  87           for (j = 0; j < str2Len; ++j) {
  88             curCol = nextCol;
  89
  90             // substution
  91             strCmp = str1.charCodeAt(i) === str2Char[j];
  92
  93             nextCol = prevRow[j] + (strCmp ? 0 : 1);
  94
  95             // insertion
  96             tmp = curCol + 1;
  97             if (nextCol > tmp) {
  98               nextCol = tmp;
  99             }
 100             // deletion
 101             tmp = prevRow[j + 1] + 1;
 102             if (nextCol > tmp) {
 103               nextCol = tmp;
 104             }
 105
 106             // copy current col value into previous (in preparation for next iteration)
 107             prevRow[j] = curCol;
 108           }
 109
 110           // copy last col value into previous (in preparation for next iteration)
 111           prevRow[j] = nextCol;
 112         }
 113       }
 114       return nextCol;
 115     }
 116
 117   };
 118
 119   // amd
 120   if (typeof define !== "undefined" && define !== null && define.amd) {
 121     define(function() {
 122       return Levenshtein;
 123     });
 124   }
 125   // commonjs
 126   else if (typeof module !== "undefined" && module !== null && typeof exports !== "undefined" && module.exports === exports) {
 127     module.exports = Levenshtein;
 128   }
 129   // web worker
 130   else if (typeof self !== "undefined" && typeof self.postMessage === 'function' && typeof self.importScripts === 'function') {
 131     self.Levenshtein = Levenshtein;
 132   }
 133   // browser main thread
 134   else if (typeof window !== "undefined" && window !== null) {
 135     window.Levenshtein = Levenshtein;
 136   }
 137 }());
 138