Grammalecte  Check-in [300e9c7d3d]

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: 300e9c7d3d6a4d155f236b4705b1692258ee8b9c91e61496876b8d2689248bb6
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
8

9
10
11
12
13
14
15
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 = {

    distanceDamerauLevenshtein: function (s1, s2) {
    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
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)})`);