Grammalecte  Check-in [4486055937]

Overview
Comment:[core][js] fix Damerau-Levenshtein distance
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk | core
Files: files | file ages | folders
SHA3-256: 448605593771fe35938aaefd090d7c41dfc653b60caebbef146c6eeadfbc0422
User & Date: olr on 2017-09-15 13:12:42
Other Links: manifest | tags
Context
2017-09-15
13:33
[core][js] calculate Damerau-Levenshtein distance only once check-in: ecae0c75b7 user: olr tags: trunk, core
13:12
[core][js] fix Damerau-Levenshtein distance check-in: 4486055937 user: olr tags: trunk, core
10:01
[core][js] fix spell suggestion engine check-in: 4b57907a81 user: olr tags: trunk, core
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified gc_core/js/char_player.js from [b60b89aafe] to [6d45a56753]. 

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();
            let nLen1 = s1.length;
            let nLen2 = s2.length;

            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);
        }
    },
︙︙

Modified gc_core/js/ibdawg.js from [da811a4bb4] to [8f764d2989].

︙︙
188
189
190
191
192
193
194

195

196
197
198
199
200
201
202

        }
        // Set to Array
        aSugg = Array.from(aSugg);
        aSugg = aSugg.filter((sSugg) => { return !sSugg.endsWith("è") && !sSugg.endsWith("È"); }); // fr language 
        if (sWord.gl_isTitle()) {
            aSugg = aSugg.map((sSugg) => { return sSugg.gl_toCapitalize(); });
        }

        return aSugg.sort((sSugg) => { return char_player.distanceDamerauLevenshtein(sWord, sSugg); }).slice(0, nMaxSugg);

    }

    _suggest (sRemain, nMaxDel=0, nDeep=0, iAddr=0, sNewWord="", bAvoidLoop=false) {
        // returns a set of suggestions
        // recursive function
        //show(nDeep, sNewWord + ":" + sRemain)
        let aSugg = new Set();








>
|
>








188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

        }
        // Set to Array
        aSugg = Array.from(aSugg);
        aSugg = aSugg.filter((sSugg) => { return !sSugg.endsWith("è") && !sSugg.endsWith("È"); }); // fr language 
        if (sWord.gl_isTitle()) {
            aSugg = aSugg.map((sSugg) => { return sSugg.gl_toCapitalize(); });
        }
        return aSugg.sort((sA, sB) => {
            return char_player.distanceDamerauLevenshtein(sWord, sA) - char_player.distanceDamerauLevenshtein(sWord, sB);
        }).slice(0, nMaxSugg);
    }

    _suggest (sRemain, nMaxDel=0, nDeep=0, iAddr=0, sNewWord="", bAvoidLoop=false) {
        // returns a set of suggestions
        // recursive function
        //show(nDeep, sNewWord + ":" + sRemain)
        let aSugg = new Set();
︙︙

Fossil 2.20 [210e89a059] 2022-11-16 18:46:32
This page was generated in about 0.005s