Overview
| Comment: | [core][js] Damerau-Levenshtein distance buggy: can’t find out why -> another version |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | trunk | core |
| Files: | files | file ages | folders |
| SHA3-256: |
300e9c7d3d6a4d155f236b4705b16922 |
| User & Date: | olr on 2017-11-22 14:58:41 |
| Other Links: | manifest | tags |
Context
|
2017-11-23
| ||
| 08:08 | [fr] réversion: apostrophe typographique suivant <t> check-in: 997694fa93 user: olr tags: trunk, fr | |
|
2017-11-22
| ||
| 14:58 | [core][js] Damerau-Levenshtein distance buggy: can’t find out why -> another version check-in: 300e9c7d3d user: olr tags: trunk, core | |
| 14:57 | [core] ibdawg: bug fixed and code cleaning check-in: fbf59c7547 user: olr tags: trunk, core | |
Changes
Modified gc_core/js/str_transform.js from [9dddadeae1] to [aaa0b82c6b].
1 2 3 4 5 6 7 |
//// STRING TRANSFORMATION
/*jslint esversion: 6*/
// Note: 48 is the ASCII code for "0"
var str_transform = {
| | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
//// STRING TRANSFORMATION
/*jslint esversion: 6*/
// Note: 48 is the ASCII code for "0"
var str_transform = {
distanceDamerauLevenshtein2: 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++) {
|
| ︙ | ︙ | |||
32 33 34 35 36 37 38 39 40 41 42 43 44 45 |
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
}
}
}
return matrix[nLen1][nLen2];
}
catch (e) {
helpers.logerror(e);
}
},
showDistance (s1, s2) {
console.log(`Distance: ${s1} / ${s2} = ${this.distanceDamerauLevenshtein(s1, s2)})`);
| > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > | 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 |
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
}
}
}
return matrix[nLen1][nLen2];
}
catch (e) {
helpers.logerror(e);
}
},
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 INF = nLen1 + nLen2;
let matrix = [];
let sd = {};
for (let i = 0; i < nLen1+2; i++) {
matrix[i] = new Array(nLen2+2);
}
matrix[0][0] = INF;
for (let i = 0; i <= nLen1; i++) {
matrix[i+1][1] = i;
matrix[i+1][0] = INF;
sd[s1[i]] = 0;
}
for (let j = 0; j <= nLen2; j++) {
matrix[1][j+1] = j;
matrix[0][j+1] = INF;
sd[s2[j]] = 0;
}
for (let i = 1; i <= nLen1; i++) {
let DB = 0;
for (let j = 1; j <= nLen2; j++) {
let i1 = sd[s2[j-1]];
let j1 = DB;
if (s1[i-1] === s2[j-1]) {
matrix[i+1][j+1] = matrix[i][j];
DB = j;
}
else {
matrix[i+1][j+1] = Math.min(matrix[i][j], Math.min(matrix[i+1][j], matrix[i][j+1])) + 1;
}
matrix[i+1][j+1] = Math.min(matrix[i+1][j+1], matrix[i1] ? matrix[i1][j1] + (i-i1-1) + 1 + (j-j1-1) : Infinity);
}
sd[s1[i-1]] = i;
}
return matrix[nLen1+1][nLen2+1];
}
catch (e) {
helpers.logerror(e);
}
},
showDistance (s1, s2) {
console.log(`Distance: ${s1} / ${s2} = ${this.distanceDamerauLevenshtein(s1, s2)})`);
|
| ︙ | ︙ |