]>
Commit | Line | Data |
---|---|---|
079635cb IC |
1 | // source |
2 | // https://github.com/hiddentao/fast-levenshtein/blob/2.0.6/levenshtein.js | |
563e401a IC |
3 | (function() { |
4 | 'use strict'; | |
5 | ||
079635cb IC |
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 = []; | |
563e401a IC |
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. | |
079635cb IC |
25 | * @param [options] Additional options. |
26 | * @param [options.useCollator] Use `Intl.Collator` for locale-sensitive string comparison. | |
563e401a IC |
27 | * @return Integer the levenshtein distance (0 and above). |
28 | */ | |
079635cb IC |
29 | get: function(str1, str2, options) { |
30 | var useCollator = (options && collator && options.useCollator); | |
31 | ||
32 | var str1Len = str1.length, | |
33 | str2Len = str2.length; | |
34 | ||
563e401a | 35 | // base cases |
079635cb IC |
36 | if (str1Len === 0) return str2Len; |
37 | if (str2Len === 0) return str1Len; | |
563e401a IC |
38 | |
39 | // two rows | |
079635cb | 40 | var curCol, nextCol, i, j, tmp; |
563e401a IC |
41 | |
42 | // initialise previous row | |
079635cb | 43 | for (i=0; i<str2Len; ++i) { |
563e401a | 44 | prevRow[i] = i; |
079635cb | 45 | str2Char[i] = str2.charCodeAt(i); |
563e401a | 46 | } |
079635cb | 47 | prevRow[str2Len] = str2Len; |
563e401a | 48 | |
079635cb IC |
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; | |
563e401a | 54 | |
079635cb IC |
55 | for (j = 0; j < str2Len; ++j) { |
56 | curCol = nextCol; | |
563e401a | 57 | |
079635cb IC |
58 | // substution |
59 | strCmp = 0 === collator.compare(str1.charAt(i), String.fromCharCode(str2Char[j])); | |
563e401a | 60 | |
079635cb | 61 | nextCol = prevRow[j] + (strCmp ? 0 : 1); |
563e401a | 62 | |
079635cb IC |
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 | } | |
563e401a | 73 | |
079635cb IC |
74 | // copy current col value into previous (in preparation for next iteration) |
75 | prevRow[j] = curCol; | |
76 | } | |
563e401a | 77 | |
079635cb IC |
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; | |
563e401a | 86 | |
079635cb IC |
87 | for (j = 0; j < str2Len; ++j) { |
88 | curCol = nextCol; | |
563e401a | 89 | |
079635cb IC |
90 | // substution |
91 | strCmp = str1.charCodeAt(i) === str2Char[j]; | |
563e401a | 92 | |
079635cb | 93 | nextCol = prevRow[j] + (strCmp ? 0 : 1); |
563e401a | 94 | |
079635cb IC |
95 | // insertion |
96 | tmp = curCol + 1; | |
97 | if (nextCol > tmp) { | |
98 | nextCol = tmp; | |
563e401a | 99 | } |
079635cb IC |
100 | // deletion |
101 | tmp = prevRow[j + 1] + 1; | |
102 | if (nextCol > tmp) { | |
103 | nextCol = tmp; | |
563e401a | 104 | } |
563e401a | 105 | |
079635cb IC |
106 | // copy current col value into previous (in preparation for next iteration) |
107 | prevRow[j] = curCol; | |
563e401a IC |
108 | } |
109 | ||
079635cb IC |
110 | // copy last col value into previous (in preparation for next iteration) |
111 | prevRow[j] = nextCol; | |
563e401a | 112 | } |
079635cb IC |
113 | } |
114 | return nextCol; | |
563e401a IC |
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 |