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
|
// list of similar chars
// useful for suggestion mechanism
${map}
var char_player = {
distanceDamerauLevenshtein: function (s1, s2) {
// distance of Damerau-Levenshtein between <s1> and <s2>
// https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
try {
let d = new Map();
for (let i = -1; i <= nLen1; i++) {
d.set([i, -1], i + 1);
}
for (let j = -1; j <= nLen2; j++) {
d.set([-1, j], j + 1);
}
for (let i = 0; i < nLen1; i++) {
for (let j = 0; j < nLen2; j++) {
let nCost = (s1[i] === s2[j]) ? 0 : 1;
d.set([i, j], Math.min(
d.get([i-1, j]) + 1, // Deletion
d.get([i, j-1]) + 1, // Insertion
d.get([i-1, j-1]) + nCost, // Substitution
));
if (i && j && s1[i] == s2[j-1] && s1[i-1] == s2[j]) {
d.set([i, j], Math.min(d.get([i, j]), d.get([i-2, j-2]) + nCost)); // Transposition
}
}
}
return d.get([nLen1-1, nLen2-1]);
}
catch (e) {
helpers.logerror(e);
}
},
|
<
>
|
|
>
>
>
|
|
|
|
|
|
|
|
|
|
|
>
|
|
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
|
// list of similar chars
// useful for suggestion mechanism
${map}
var char_player = {
distanceDamerauLevenshtein: function (s1, s2) {
// distance of Damerau-Levenshtein between <s1> and <s2>
// https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
try {
let nLen1 = s1.length;
let nLen2 = s2.length;
let matrix = [];
for (let i = 0; i <= nLen1; i++) {
matrix[i] = new Array(nLen2 + 1);
}
for (let i = 0; i <= nLen1; i++) {
matrix[i][0] = i;
}
for (let j = 0; j <= nLen2; j++) {
matrix[0][j] = j;
}
for (let i = 1; i <= nLen1; i++) {
for (let j = 1; j <= nLen2; j++) {
let nCost = (s1[i] === s2[j]) ? 0 : 1;
matrix[i][j] = Math.min(
matrix[i-1][j] + 1, // Deletion
matrix[i][j-1] + 1, // Insertion
matrix[i-1][j-1] + nCost // Substitution
);
if (i > 1 && j > 1 && s1[i] == s2[j-1] && s1[i-1] == s2[j]) {
matrix[i][j] = Math.min(matrix[i][j], matrix[i-2][j-2] + nCost); // Transposition
}
}
}
console.log(s2 + ": " + matrix[nLen1][nLen2]);
return matrix[nLen1][nLen2];
}
catch (e) {
helpers.logerror(e);
}
},
|