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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
|
/**
* match utility;
* includes fuzzy and partial match functions too;
* many of them return a match-rate
*/
// fuzzy match
////////////////////////////////////////////////////////////////////////////////
/** Ngram fuzzy match algorithm
* (simple and fast)
*/
const createNgram = (word, n) => { // Ngram creation
if (word.length <3) return word;
const vector = [];
for (let i = 0; i < word.length-n+1; ++i) {
vector.push(word.slice(i, i + n));
}
return vector;
};
/** similarity
* rates similarity between 2 words
* based on Ngram matches of N = n letters;
* implements a 2-dim check (all a-Ngrams vs all all b-Ngrams)
*
* @param {string} a : first word
* @param {string} b : second word
* @param {int} n : Ngram base
* @returns {float} : match percentage as a float in [0, 1]
*/
const similarity = (a, b, n) => { // Ngram match score
if (a.length > 0 && b.length > 0) {
const aNgram = createNgram(a, n);
const bNgram = createNgram(b, n);
let hits = 0;
for (let x = 0; x < aNgram.length; ++x) {
for (let y = 0; y < bNgram.length; ++y) {
if (aNgram[x] === bNgram[y]) {
hits += 1;
}
}
}
if (hits > 0) {
const union = aNgram.length + bNgram.length;
return (2.0 * hits) / union;
}
}
return 0;
};
/** resemblance
* is an alternative similarity rating;
* implements an 1-dim Ngram similarity check
* and it's much faster than similarity()
*/
const resemblance = (a, b, n) => {
if (a.length > n && b.length >= a.length) {
const aNgram = createNgram(a, n);
let hits = 0;
for (let i = 0; i < aNgram.length; ++i) {
if (b.includes(aNgram[i])) {
hits++;
}
}
if (hits > 0) {
// rate resemblance based on hits and length-similarity
return (hits / aNgram.length) * (a.length / b.length);
}
}
return 0;
}
// exact and partial match
////////////////////////////////////////////////////////////////////////////////
/** is_exact_match
* check if a searching string -> query (string/latin in kb-format)
* matches exactly an item of the array of synonyms -> chkArr (array of utf-8/strings)
*
* @param {string} query: searching string; string/latin in kb-format
* @param {array} chkArr: array of synonyms; (array of utf-8/strings)
* @return {boolean}: true|false
*/
function exact( query, chkArr ) {
found = false;
chkArr.forEach( w => { if (w == query) found = true });
return found;
}
function partial( query, chkArr ) {
found = false;
chkArr.forEach( w => { if (w.includes(query)) found = true });
return found;
}
/** is exact match + weight rating
* @returns {float} weight rates depth of array when a match is found
*/
function weighted_exact( query, chkArr ) {
let weight = 0; // closer to left/begin rating
let len = chkArr.length;
for(let i = 0; i < len ; i++) { // i ~ depth
if (chkArr[i] == query) {
// weights array depth
weight = (len - i + 1.0) / len;
break;
}
}
return weight;
}
/** is partial match + weight rating
*
* @param query (string): searching string; string/latin in kb-format
* @param chkArr (array): array of synonyms; (array of utf-8/strings)
* @returns {float} weight rates both match position and depth of match
*
* (*) optimization NOTE:
* Given the weight `W` and the depth `i`,
* the best weight for next `i` shall be: `(L - (i+1)) / L`
* To be imposibbe to have a better weight, should:
* W > (L - (i+1)) / L => ... => i > (L - L*W - 1)
*/
function weighted_partial( query, chkArr ) {
let rate = 0;
let weight = 0;
let len = chkArr.length;
for( let i = 0 ; i < len ; i++ ) {
let chk = chkArr[i].indexOf(query)
if (chk != -1) {
rate = (len - i) / (len + 2.0 * chk);
weight = rate > weight ? rate : weight;
}
if (i > (len - len * weight - 1)) {
break; // better rating is not possible (*)
}
}
return weight;
}
// exports
module.exports = {
exact,
partial,
weighted_exact,
weighted_partial,
similarity,
resemblance
}
|
