]>
Commit | Line | Data |
---|---|---|
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 |