src/js/levenshtein.js

   1 (function() {
   2   'use strict';
   3
   4   /**
   5    * Extend an Object with another Object's properties.
   6    *
   7    * The source objects are specified as additional arguments.
   8    *
   9    * @param dst Object the object to extend.
  10    *
  11    * @return Object the final object.
  12    */
  13   var _extend = function(dst) {
  14     var sources = Array.prototype.slice.call(arguments, 1);
  15     for (var i=0; i<sources.length; ++i) {
  16       var src = sources[i];
  17       for (var p in src) {
  18         if (src.hasOwnProperty(p)) dst[p] = src[p];
  19       }
  20     }
  21     return dst;
  22   };
  23
  24
  25   /**
  26    * Defer execution of given function.
  27    * @param  {Function} func
  28    */
  29   var _defer = function(func) {
  30     if (typeof setImmediate === 'function') {
  31       return setImmediate(func);
  32     } else {
  33       return setTimeout(func, 0);
  34     }
  35   };
  36
  37   /**
  38    * Based on the algorithm at http://en.wikipedia.org/wiki/Levenshtein_distance.
  39    */
  40   var Levenshtein = {
  41     /**
  42      * Calculate levenshtein distance of the two strings.
  43      *
  44      * @param str1 String the first string.
  45      * @param str2 String the second string.
  46      * @return Integer the levenshtein distance (0 and above).
  47      */
  48     get: function(str1, str2) {
  49       // base cases
  50       if (str1 === str2) return 0;
  51       if (str1.length === 0) return str2.length;
  52       if (str2.length === 0) return str1.length;
  53
  54       // two rows
  55       var prevRow  = new Array(str2.length + 1),
  56           curCol, nextCol, i, j, tmp;
  57
  58       // initialise previous row
  59       for (i=0; i<prevRow.length; ++i) {
  60         prevRow[i] = i;
  61       }
  62
  63       // calculate current row distance from previous row
  64       for (i=0; i<str1.length; ++i) {
  65         nextCol = i + 1;
  66
  67         for (j=0; j<str2.length; ++j) {
  68           curCol = nextCol;
  69
  70           // substution
  71           nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
  72           // insertion
  73           tmp = curCol + 1;
  74           if (nextCol > tmp) {
  75             nextCol = tmp;
  76           }
  77           // deletion
  78           tmp = prevRow[j + 1] + 1;
  79           if (nextCol > tmp) {
  80             nextCol = tmp;
  81           }
  82
  83           // copy current col value into previous (in preparation for next iteration)
  84           prevRow[j] = curCol;
  85         }
  86
  87         // copy last col value into previous (in preparation for next iteration)
  88         prevRow[j] = nextCol;
  89       }
  90
  91       return nextCol;
  92     },
  93
  94     /**
  95      * Asynchronously calculate levenshtein distance of the two strings.
  96      *
  97      * @param str1 String the first string.
  98      * @param str2 String the second string.
  99      * @param cb Function callback function with signature: function(Error err, int distance)
 100      * @param [options] Object additional options.
 101      * @param [options.progress] Function progress callback with signature: function(percentComplete)
 102      */
 103     getAsync: function(str1, str2, cb, options) {
 104       options = _extend({}, {
 105         progress: null
 106       }, options);
 107
 108       // base cases
 109       if (str1 === str2) return cb(null, 0);
 110       if (str1.length === 0) return cb(null, str2.length);
 111       if (str2.length === 0) return cb(null, str1.length);
 112
 113       // two rows
 114       var prevRow  = new Array(str2.length + 1),
 115           curCol, nextCol,
 116           i, j, tmp,
 117           startTime, currentTime;
 118
 119       // initialise previous row
 120       for (i=0; i<prevRow.length; ++i) {
 121         prevRow[i] = i;
 122       }
 123
 124       nextCol = 1;
 125       i = 0;
 126       j = -1;
 127
 128       var __calculate = function() {
 129         // reset timer
 130         startTime = new Date().valueOf();
 131         currentTime = startTime;
 132
 133         // keep going until one second has elapsed
 134         while (currentTime - startTime < 1000) {
 135           // reached end of current row?
 136           if (str2.length <= (++j)) {
 137             // copy current into previous (in preparation for next iteration)
 138             prevRow[j] = nextCol;
 139
 140             // if already done all chars
 141             if (str1.length <= (++i)) {
 142               return cb(null, nextCol);
 143             }
 144             // else if we have more left to do
 145             else {
 146               nextCol = i + 1;
 147               j = 0;
 148             }
 149           }
 150
 151           // calculation
 152           curCol = nextCol;
 153
 154           // substution
 155           nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
 156           // insertion
 157           tmp = curCol + 1;
 158           if (nextCol > tmp) {
 159             nextCol = tmp;
 160           }
 161           // deletion
 162           tmp = prevRow[j + 1] + 1;
 163           if (nextCol > tmp) {
 164             nextCol = tmp;
 165           }
 166
 167           // copy current into previous (in preparation for next iteration)
 168           prevRow[j] = curCol;
 169
 170           // get current time
 171           currentTime = new Date().valueOf();
 172         }
 173
 174         // send a progress update?
 175         if (null !== options.progress) {
 176           try {
 177             options.progress.call(null, (i * 100.0/ str1.length));
 178           } catch (err) {
 179             return cb('Progress callback: ' + err.toString());
 180           }
 181         }
 182
 183         // next iteration
 184         _defer(__calculate);
 185       };
 186
 187       __calculate();
 188     }
 189
 190   };
 191
 192   // amd
 193   if (typeof define !== "undefined" && define !== null && define.amd) {
 194     define(function() {
 195       return Levenshtein;
 196     });
 197   }
 198   // commonjs
 199   else if (typeof module !== "undefined" && module !== null && typeof exports !== "undefined" && module.exports === exports) {
 200     module.exports = Levenshtein;
 201   }
 202   // web worker
 203   else if (typeof self !== "undefined" && typeof self.postMessage === 'function' && typeof self.importScripts === 'function') {
 204     self.Levenshtein = Levenshtein;
 205   }
 206   // browser main thread
 207   else if (typeof window !== "undefined" && window !== null) {
 208     window.Levenshtein = Levenshtein;
 209   }
 210 }());
 211