-
Notifications
You must be signed in to change notification settings - Fork 0
/
search.js
116 lines (99 loc) · 2.58 KB
/
search.js
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
// ============== Source: https://github.com/gustf/js-levenshtein; License: MIT (Expat) ============
const levenshtein = (function () {
function _min(d0, d1, d2, bx, ay) {
return d0 < d1 || d2 < d1
? d0 > d2
? d2 + 1
: d0 + 1
: bx === ay
? d1
: d1 + 1;
}
return function (a, b) {
if (a === b) {
return 0;
}
if (a.length > b.length) {
var tmp = a;
a = b;
b = tmp;
}
var la = a.length;
var lb = b.length;
while (la > 0 && a.charCodeAt(la - 1) === b.charCodeAt(lb - 1)) {
la--;
lb--;
}
var offset = 0;
while (offset < la && a.charCodeAt(offset) === b.charCodeAt(offset)) {
offset++;
}
la -= offset;
lb -= offset;
if (la === 0 || lb < 3) {
return lb;
}
var x = 0;
var y;
var d0;
var d1;
var d2;
var d3;
var dd;
var dy;
var ay;
var bx0;
var bx1;
var bx2;
var bx3;
var vector = [];
for (y = 0; y < la; y++) {
vector.push(y + 1);
vector.push(a.charCodeAt(offset + y));
}
var len = vector.length - 1;
for (; x < lb - 3; ) {
bx0 = b.charCodeAt(offset + (d0 = x));
bx1 = b.charCodeAt(offset + (d1 = x + 1));
bx2 = b.charCodeAt(offset + (d2 = x + 2));
bx3 = b.charCodeAt(offset + (d3 = x + 3));
dd = x += 4;
for (y = 0; y < len; y += 2) {
dy = vector[y];
ay = vector[y + 1];
d0 = _min(dy, d0, d1, bx0, ay);
d1 = _min(d0, d1, d2, bx1, ay);
d2 = _min(d1, d2, d3, bx2, ay);
dd = _min(d2, d3, dd, bx3, ay);
vector[y] = dd;
d3 = d2;
d2 = d1;
d1 = d0;
d0 = dy;
}
}
for (; x < lb; ) {
bx0 = b.charCodeAt(offset + (d0 = x));
dd = ++x;
for (y = 0; y < len; y += 2) {
dy = vector[y];
vector[y] = dd = _min(dy, d0, dd, bx0, vector[y + 1]);
d0 = dy;
}
}
return dd;
};
})();
//========= END ===============
function searchWithLevenshteinDist(query, dist, dictionary) {
var results = [];
for(var elem of dictionaries[dictionary]) {
console.log("Checking " + elem.phrase + "\n");
if(levenshtein(query, elem.phrase) <= dist) {
results.push(elem.phrase);
console.log("Found a result: " + elem.phrase + "\n");
}
}
console.log("searchWithLevenshteinDist(): dictionary = " + dictionary + "\n");
return {dict: dictionary, res: results};
}