1 | (function() {
|
2 | 'use strict';
|
3 |
|
4 | |
5 |
|
6 |
|
7 |
|
8 |
|
9 |
|
10 |
|
11 |
|
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 |
|
27 | var Levenshtein = {
|
28 | |
29 |
|
30 |
|
31 |
|
32 |
|
33 |
|
34 |
|
35 | get: function(str1, str2) {
|
36 |
|
37 | if (str1 === str2) return 0;
|
38 | if (str1.length === 0) return str2.length;
|
39 | if (str2.length === 0) return str1.length;
|
40 |
|
41 |
|
42 | var prevRow = new Array(str2.length + 1),
|
43 | curCol, nextCol, i, j, tmp;
|
44 |
|
45 |
|
46 | for (i=0; i<prevRow.length; ++i) {
|
47 | prevRow[i] = i;
|
48 | }
|
49 |
|
50 |
|
51 | for (i=0; i<str1.length; ++i) {
|
52 | nextCol = i + 1;
|
53 |
|
54 | for (j=0; j<str2.length; ++j) {
|
55 | curCol = nextCol;
|
56 |
|
57 |
|
58 | nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
|
59 |
|
60 | tmp = curCol + 1;
|
61 | if (nextCol > tmp) {
|
62 | nextCol = tmp;
|
63 | }
|
64 |
|
65 | tmp = prevRow[j + 1] + 1;
|
66 | if (nextCol > tmp) {
|
67 | nextCol = tmp;
|
68 | }
|
69 |
|
70 |
|
71 | prevRow[j] = curCol;
|
72 | }
|
73 |
|
74 |
|
75 | prevRow[j] = nextCol;
|
76 | }
|
77 |
|
78 | return nextCol;
|
79 | },
|
80 |
|
81 | |
82 |
|
83 |
|
84 |
|
85 |
|
86 |
|
87 |
|
88 |
|
89 |
|
90 | getAsync: function(str1, str2, cb, options) {
|
91 | options = _extend({}, {
|
92 | progress: null
|
93 | }, options);
|
94 |
|
95 |
|
96 | if (str1 === str2) return cb(null, 0);
|
97 | if (str1.length === 0) return cb(null, str2.length);
|
98 | if (str2.length === 0) return cb(null, str1.length);
|
99 |
|
100 |
|
101 | var prevRow = new Array(str2.length + 1),
|
102 | curCol, nextCol,
|
103 | i, j, tmp,
|
104 | startTime, currentTime;
|
105 |
|
106 |
|
107 | for (i=0; i<prevRow.length; ++i) {
|
108 | prevRow[i] = i;
|
109 | }
|
110 |
|
111 | nextCol = 1;
|
112 | i = 0;
|
113 | j = -1;
|
114 |
|
115 | var __calculate = function() {
|
116 |
|
117 | startTime = new Date().valueOf();
|
118 | currentTime = startTime;
|
119 |
|
120 |
|
121 | while (currentTime - startTime < 1000) {
|
122 |
|
123 | if (str2.length <= (++j)) {
|
124 |
|
125 | prevRow[j] = nextCol;
|
126 |
|
127 |
|
128 | if (str1.length <= (++i)) {
|
129 | return cb(null, nextCol);
|
130 | }
|
131 |
|
132 | else {
|
133 | nextCol = i + 1;
|
134 | j = 0;
|
135 | }
|
136 | }
|
137 |
|
138 |
|
139 | curCol = nextCol;
|
140 |
|
141 |
|
142 | nextCol = prevRow[j] + ( (str1.charAt(i) === str2.charAt(j)) ? 0 : 1 );
|
143 |
|
144 | tmp = curCol + 1;
|
145 | if (nextCol > tmp) {
|
146 | nextCol = tmp;
|
147 | }
|
148 |
|
149 | tmp = prevRow[j + 1] + 1;
|
150 | if (nextCol > tmp) {
|
151 | nextCol = tmp;
|
152 | }
|
153 |
|
154 |
|
155 | prevRow[j] = curCol;
|
156 |
|
157 |
|
158 | currentTime = new Date().valueOf();
|
159 | }
|
160 |
|
161 |
|
162 | if (null !== options.progress) {
|
163 | try {
|
164 | options.progress.call(null, (i * 100.0/ str1.length));
|
165 | } catch (err) {
|
166 | return cb('Progress callback: ' + err.toString());
|
167 | }
|
168 | }
|
169 |
|
170 |
|
171 | setTimeout(__calculate(), 0);
|
172 | };
|
173 |
|
174 | __calculate();
|
175 | }
|
176 |
|
177 | };
|
178 |
|
179 | if(typeof self !== "undefined"){
|
180 | self.Levenshtein = Levenshtein;
|
181 | }
|
182 | else if (typeof define !== "undefined" && define !== null && define.amd) {
|
183 | define(function() {
|
184 | return Levenshtein;
|
185 | });
|
186 | } else if (typeof module !== "undefined" && module !== null) {
|
187 | module.exports = Levenshtein;
|
188 | } else {
|
189 | if (typeof window !== "undefined" && window !== null) {
|
190 | window.Levenshtein = Levenshtein;
|
191 | }
|
192 | }
|
193 | }());
|
194 |
|