Grammalecte  Check-in [6c7fd16428]

Overview
Comment:[graphspell] suggestion mechanism improvement: Damerau-Levenshtein extension
Downloads: Tarball | ZIP archive | SQL archive
Timelines: family | ancestors | descendants | both | trunk | major_change | graphspell
Files: files | file ages | folders
SHA3-256: 6c7fd16428098930ca2746b240ed9937efcf9dff5734c09c31d994262e1c77f4
User & Date: olr on 2025-09-18 12:39:06
Other Links: manifest | tags
Context
2025-09-18
13:12
[graphspell][js] suggestion mechanism improvement: Damerau-Levenshtein extension Leaf check-in: 504e22f37f user: olr tags: trunk, major_change, graphspell
12:39
[graphspell] suggestion mechanism improvement: Damerau-Levenshtein extension check-in: 6c7fd16428 user: olr tags: trunk, major_change, graphspell
12:35
[core] label clarity check-in: d2dbd35eb8 user: olr tags: trunk, core
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Modified grammalecte-cli.py from [885831172a] to [0dcc4aa5f2].

︙︙
270
271
272
273
274
275
276

277
278
279
280
281
282
283
284

285
286
287
288




289

290
291

292
293
294
295
296
297
298
299
300
301
302

303
304
305
306
307
308
309
310
311
312
313

                        print("Error. This error doesn’t exist.")
    else:
        # pseudo-console
        sInputText = "\n~==========~ Enter your text [/h /q] ~==========~\n"
        sText = _getText(sInputText)
        while True:
            if sText.startswith("?"):

                for sWord in sText[1:].strip().split():
                    if sWord:
                        echo("* " + sWord)
                        for sElem, aRes in oSpellChecker.analyze(sWord):
                            echo("  - " + sElem)
                            for sMorph, sMeaning in aRes:
                                echo("      {:<40}  {}".format(sMorph, sMeaning))
            elif sText.startswith("!"):

                for sWord in sText[1:].strip().split():
                    if sWord:
                        for lSugg in oSpellChecker.suggest(sWord):
                            echo(" | ".join(lSugg))




            elif sText.startswith(">"):

                oSpellChecker.drawPath(sText[1:].strip())
            elif sText.startswith("="):

                sSearch = sText[1:].strip()
                if "=" in sSearch:
                    nCut = sSearch.find("=")
                    sFlexPattern = sSearch[0:nCut]
                    sTagsPattern = sSearch[nCut+1:]
                else:
                    sFlexPattern = sSearch
                    sTagsPattern = ""
                for aRes in oSpellChecker.select(sFlexPattern, sTagsPattern):
                    echo("{:<30} {:<30} {}".format(*aRes))
            elif sText.startswith("≠"):

                lWords = sText[1:].split("|")
                for s1, s2 in itertools.combinations(lWords, 2):
                    nDist = strt.distanceDamerauLevenshtein(s1, s2)
                    print(f"{s1} ≠ {s2}: {nDist}")
            elif sText.startswith("/o+ "):
                oGrammarChecker.gce.setOptions({ opt:True  for opt in sText[3:].strip().split()  if opt in oGrammarChecker.gce.getOptions() })
                echo("done")
            elif sText.startswith("/o- "):
                oGrammarChecker.gce.setOptions({ opt:False  for opt in sText[3:].strip().split()  if opt in oGrammarChecker.gce.getOptions() })
                echo("done")
            elif sText.startswith("/r- "):








>








>




>
>
>
>

>


>











>


|
<








270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314

315
316
317
318
319
320
321

                        print("Error. This error doesn’t exist.")
    else:
        # pseudo-console
        sInputText = "\n~==========~ Enter your text [/h /q] ~==========~\n"
        sText = _getText(sInputText)
        while True:
            if sText.startswith("?"):
                # morphologies
                for sWord in sText[1:].strip().split():
                    if sWord:
                        echo("* " + sWord)
                        for sElem, aRes in oSpellChecker.analyze(sWord):
                            echo("  - " + sElem)
                            for sMorph, sMeaning in aRes:
                                echo("      {:<40}  {}".format(sMorph, sMeaning))
            elif sText.startswith("!"):
                # spelling suggestions
                for sWord in sText[1:].strip().split():
                    if sWord:
                        for lSugg in oSpellChecker.suggest(sWord):
                            echo(" | ".join(lSugg))
                            if xArgs.debug:
                                for sSugg in lSugg:
                                    nDist = strt.distanceDamerauLevenshteinX(sWord, sSugg)
                                    echo(f"{sSugg:30} {nDist}")
            elif sText.startswith(">"):
                # path in the word graph
                oSpellChecker.drawPath(sText[1:].strip())
            elif sText.startswith("="):
                # search in dictionnary
                sSearch = sText[1:].strip()
                if "=" in sSearch:
                    nCut = sSearch.find("=")
                    sFlexPattern = sSearch[0:nCut]
                    sTagsPattern = sSearch[nCut+1:]
                else:
                    sFlexPattern = sSearch
                    sTagsPattern = ""
                for aRes in oSpellChecker.select(sFlexPattern, sTagsPattern):
                    echo("{:<30} {:<30} {}".format(*aRes))
            elif sText.startswith("≠"):
                # distances calculation
                lWords = sText[1:].split("|")
                for s1, s2 in itertools.combinations(lWords, 2):
                    strt.showDistance(s1, s2)

            elif sText.startswith("/o+ "):
                oGrammarChecker.gce.setOptions({ opt:True  for opt in sText[3:].strip().split()  if opt in oGrammarChecker.gce.getOptions() })
                echo("done")
            elif sText.startswith("/o- "):
                oGrammarChecker.gce.setOptions({ opt:False  for opt in sText[3:].strip().split()  if opt in oGrammarChecker.gce.getOptions() })
                echo("done")
            elif sText.startswith("/r- "):
︙︙

Modified graphspell/char_player.py from [9efc586374] to [fdeaf568a0]. 

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

"""
List of similar chars
useful for suggestion mechanism
"""


dDistanceBetweenChars = {
    # dDistanceBetweenChars:

    # - with Jaro-Winkler, values between 1 and 10






    # - with Damerau-Levenshtein, values / 10 (between 0 and 1: 0.1, 0.2 ... 0.9)
    #"a": {},
    "e": {"é": 5},



    "é": {"e": 5},
    "i": {"y": 2},
    #"o": {},
    #"u": {},
    "y": {"i": 3},

    "b": {"d": 8, "h": 9},





    "c": {"ç": 1, "k": 5, "q": 5, "s": 5, "x": 5, "z": 8},
    "d": {"b": 8},
    "f": {"v": 8},
    "g": {"j": 5},
    "h": {"b": 9},

    "j": {"g": 5, "i": 9},





    "k": {"c": 5, "q": 1, "x": 5},










    "l": {"i": 9},
    "m": {"n": 8},
    "n": {"m": 8, "r": 9},
    "p": {"q": 9},
    "q": {"c": 5, "k": 1, "p": 9},
    "r": {"n": 9, "j": 9},
    "s": {"c": 5, "ç": 1, "x": 5, "z": 5},
    "t": {"d": 9},
    "v": {"f": 8, "w": 1},
    "w": {"v": 1},
    "x": {"c": 5, "k": 5, "q": 5, "s": 5},
    "z": {"s": 5}
}


def distanceBetweenChars (c1, c2):
    "returns a float between 0 and 1"
    if c1 == c2:
        return 0






<

<
>

>
>
>
>
>
>
|
|
|
>
>
>
|
|
|
|
|
>
|
>
>
>
>
>
|
|
|
|
|
>
|
>
>
>
>
>
|
>
>
>
>
>
>
>
>
>
>
|
|
|
|
|
|
|
|
|
|
|
|








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

"""
List of similar chars
useful for suggestion mechanism
"""


dDistanceBetweenChars = {

    # - with Damerau-Levenshtein, values / 10 (between 0 and 1: 0.1, 0.2 ... 0.9)
    # - with Jaro-Winkler, values between 1 and 10
    # voyelles
    "a": { "a": 0,  "á": .1, "à": .1, "â": .1, "ã": .1 },
    "á": { "a": .1, "á": 0,  "à": .1, "â": .1, "ã": .1 },
    "à": { "a": .1, "á": .1, "à": 0,  "â": .1, "ã": .1 },
    "â": { "a": .1, "á": .1, "à": .1, "â": 0,  "ã": .1 },
    "ã": { "a": .1, "á": .1, "à": .1, "â": .1, "ã": 0  },

    "e": { "e": 0,  "é": .1, "è": .1, "ê": .1, "ẽ": .1 },
    "é": { "e": .1, "é": 0,  "è": .1, "ê": .1, "ẽ": .1 },
    "è": { "e": .1, "é": .1, "è": 0,  "ê": .1, "ẽ": .1 },
    "ê": { "e": .1, "é": .1, "è": .1, "ê": 0,  "ẽ": .1 },
    "ẽ": { "e": .1, "é": .1, "è": .1, "ê": .1, "ẽ": 0  },

    "i": { "i": 0,  "í": .1, "ì": .1, "î": .1, "ĩ": .1 },
    "í": { "i": .1, "í": 0,  "ì": .1, "î": .1, "ĩ": .1 },
    "ì": { "i": .1, "í": .1, "ì": 0,  "î": .1, "ĩ": .1 },
    "î": { "i": .1, "í": .1, "ì": .1, "î": 0,  "ĩ": .1 },
    "ĩ": { "i": .1, "í": .1, "ì": .1, "î": .1, "ĩ": 0  },

    "o": { "o": 0,  "ó": .1, "ò": .1, "ô": .1, "õ": .1 },
    "ó": { "o": .1, "ó": 0,  "ò": .1, "ô": .1, "õ": .1 },
    "ò": { "o": .1, "ó": .1, "ò": 0,  "ô": .1, "õ": .1 },
    "ô": { "o": .1, "ó": .1, "ò": .1, "ô": 0,  "õ": .1 },
    "õ": { "o": .1, "ó": .1, "ò": .1, "ô": .1, "õ": 0  },

    "u": { "u": 0,  "ú": .1, "ù": .1, "û": .1, "ũ": .1 },
    "ú": { "u": .1, "ú": 0,  "ù": .1, "û": .1, "ũ": .1 },
    "ù": { "u": .1, "ú": .1, "ù": 0,  "û": .1, "ũ": .1 },
    "û": { "u": .1, "ú": .1, "ù": .1, "û": 0,  "ũ": .1 },
    "ũ": { "u": .1, "ú": .1, "ù": .1, "û": .1, "ũ": 0  },

    "y": { "y": 0,  "ý": .1, "ỳ": .1, "ŷ": .1, "ỹ": .1 },
    "ý": { "y": .1, "ý": 0,  "ỳ": .1, "ŷ": .1, "ỹ": .1 },
    "ỳ": { "y": .1, "ý": .1, "ỳ": 0,  "ŷ": .1, "ỹ": .1 },
    "ŷ": { "y": .1, "ý": .1, "ỳ": .1, "ŷ": 0,  "ỹ": .1 },
    "ỹ": { "y": .1, "ý": .1, "ỳ": .1, "ŷ": .1, "ỹ": 0  },

    ## consonnes
    "b": { "b": 0, "d": .8, "h": .9 },
    "c": { "c": 0, "ç": .1, "k": .5, "q": .5, "s": .5, "x": .5, "z": .8 },
    "ç": { "c": .1, "ç": 0, "k": .5, "q": .5, "s": .5, "x": .5, "z": .8 },
    "d": { "d": 0, "b": .8 },
    "f": { "f": 0, "v": .8 },
    "g": { "g": 0, "j": .5, "q": .8 },
    "h": { "h": 0, "b": .9 },
    "j": { "j": 0, "g": .5, "i": .8 },
    "k": { "k": 0, "c": .5, "q": .1, "x": .5 },
    "l": { "l": 0, "i": .8 },
    "m": { "m": 0, "n": .6 },
    "n": { "n": 0, "ñ": .1, "m": .6, "r": .8 },
    "p": { "p": 0, "q": .8 },
    "q": { "q": 0, "c": .5, "k": .1, "p": .8, "g": .8 },
    "r": { "r": 0, "n": .8, "j": .9 },
    "s": { "s": 0, "c": .5, "ç": .1, "x": .5, "z": .5 },
    "t": { "t": 0, "d": .9 },
    "v": { "v": 0, "f": .8, "w": .2 },
    "w": { "w": 0, "v": .2 },
    "x": { "x": 0, "c": .5, "k": .5, "q": .5, "s": .5 },
    "z": { "z": 0, "s": .5 }
}


def distanceBetweenChars (c1, c2):
    "returns a float between 0 and 1"
    if c1 == c2:
        return 0
︙︙

Modified graphspell/ibdawg.py from [a6af4bb96b] to [b0bfbd049d].

︙︙
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

            return
        self.aAllSugg.add(sSugg)
        nSimDist = st.distanceSift4(self.sSimplifiedWord, st.simplifyWord(sSugg))
        #st.showDistance(self.sSimplifiedWord, st.simplifyWord(sSugg))
        if nSimDist < self.nMinDist:
            self.nMinDist = nSimDist
        if nSimDist <= (self.nMinDist + 1):
            nDist = min(st.distanceDamerauLevenshtein(self.sWord, sSugg), st.distanceDamerauLevenshtein(self.sSimplifiedWord, st.simplifyWord(sSugg)))
            #print(">", end="")
            #st.showDistance(self.sWord, sSugg)
            self.dAccSugg[sSugg] = min(nDist, nSimDist+1)
            if len(self.dAccSugg) > self.nTempSuggLimit:
                self.nDistLimit = -1  # suggest() ends searching when this variable = -1
        self.nDistLimit = min(self.nDistLimit, self.nMinDist+1)

    def getSuggestions (self):
        "return a list of suggestions"
        # sort according to distance
        lRes = []
        lResTmp = sorted(self.dAccSugg.items(), key=lambda x: (x[1], x[0]))

        for i in range(min(self.nSuggLimit, len(lResTmp))):
            lRes.append(lResTmp[i][0])
            #st.showDistance(self.sWord, lResTmp[i][0])
        # casing
        if self.sWord.isupper():
            lRes = list(dict.fromkeys(map(lambda sSugg: sSugg.upper(), lRes)))
        elif self.sWord[0:1].isupper():








|


|









>








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

            return
        self.aAllSugg.add(sSugg)
        nSimDist = st.distanceSift4(self.sSimplifiedWord, st.simplifyWord(sSugg))
        #st.showDistance(self.sSimplifiedWord, st.simplifyWord(sSugg))
        if nSimDist < self.nMinDist:
            self.nMinDist = nSimDist
        if nSimDist <= (self.nMinDist + 1):
            nDist = min(st.distanceDamerauLevenshteinX(self.sWord, sSugg), st.distanceDamerauLevenshteinX(self.sSimplifiedWord, st.simplifyWord(sSugg)))
            #print(">", end="")
            #st.showDistance(self.sWord, sSugg)
            self.dAccSugg[sSugg] = nDist  if " " not in sSugg  else nDist+1
            if len(self.dAccSugg) > self.nTempSuggLimit:
                self.nDistLimit = -1  # suggest() ends searching when this variable = -1
        self.nDistLimit = min(self.nDistLimit, self.nMinDist+1)

    def getSuggestions (self):
        "return a list of suggestions"
        # sort according to distance
        lRes = []
        lResTmp = sorted(self.dAccSugg.items(), key=lambda x: (x[1], x[0]))
        #print("\n>", lResTmp)
        for i in range(min(self.nSuggLimit, len(lResTmp))):
            lRes.append(lResTmp[i][0])
            #st.showDistance(self.sWord, lResTmp[i][0])
        # casing
        if self.sWord.isupper():
            lRes = list(dict.fromkeys(map(lambda sSugg: sSugg.upper(), lRes)))
        elif self.sWord[0:1].isupper():
︙︙

Modified graphspell/str_transform.py from [5e51d32779] to [947dc593c6]. 

1
2
3
4
5
6
7
8
9
10
11
12
















13
14
15
16
17
18
19

"""
Operations on strings:
- calculate distance between two strings
- transform strings with transformation codes
"""

import unicodedata
import re

from .char_player import distanceBetweenChars, dDistanceBetweenChars
from .echo import echo


















#### N-GRAMS

def getNgrams (sWord, n=2):
    "return a list of Ngrams strings"
    return [ sWord[i:i+n]  for i in range(len(sWord)-n+1) ]














>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>








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

"""
Operations on strings:
- calculate distance between two strings
- transform strings with transformation codes
"""

import unicodedata
import re

from .char_player import distanceBetweenChars, dDistanceBetweenChars
from .echo import echo


# import time
# from functools import wraps
#
# def timethis (func):
#     "decorator for the execution time"
#     @wraps(func)
#     def wrapper (*args, **kwargs):
#         "something to prevent pylint whining"
#         fStart = time.perf_counter_ns()
#         result = func(*args, **kwargs)
#         fEnd = time.perf_counter_ns()
#         print(func.__name__, fEnd - fStart)
#         return result
#     return wrapper


#### N-GRAMS

def getNgrams (sWord, n=2):
    "return a list of Ngrams strings"
    return [ sWord[i:i+n]  for i in range(len(sWord)-n+1) ]
︙︙
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

                    nLongest = lMatrix[x][y]
                    nLongestX = x
            else:
                lMatrix[x][y] = 0
    return s1[nLongestX-nLongest : nLongestX]








































































def distanceDamerauLevenshtein (s1, s2):
    "distance of Damerau-Levenshtein between <s1> and <s2>"
    # https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
    d = {}
    nLen1 = len(s1)
    nLen2 = len(s2)
    for i in range(-1, nLen1+1):
        d[i, -1] = i + 1
    for j in range(-1, nLen2+1):
        d[-1, j] = j + 1
    for i in range(nLen1):
        for j in range(nLen2):
            nCost = 0  if s1[i] == s2[j]  else 1
            #nCost = distanceBetweenChars(s1[i], s2[j])



            d[i, j] = min(
                d[i-1, j]   + 1,        # Deletion
                d[i,   j-1] + 1,        # Insertion
                d[i-1, j-1] + nCost,    # Substitution
            )
            if i and j and s1[i] == s2[j-1] and s1[i-1] == s2[j]:
                d[i, j] = min(d[i, j], d[i-2, j-2] + nCost)     # Transposition

    return d[nLen1-1, nLen2-1]































def distanceJaroWinkler (sWord1, sWord2, fBoost = .666):
    "distance of Jaro-Winkler between <sWord1> and <sWord2>, returns a float"
    # https://github.com/thsig/jaro-winkler-JS
    #if (sWord1 == sWord2): return 1.0

    nLen1 = len(sWord1)
    nLen2 = len(sWord2)
    nMax = max(nLen1, nLen2)
    aFlags1 = [ None for _ in range(nMax) ]
    aFlags2 = [ None for _ in range(nMax) ]
    nSearchRange = (max(nLen1, nLen2) // 2) - 1
    nMinLen = min(nLen1, nLen2)








>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>












<

>
>
>



|



>


>
>
>
>
>
>
>
>
>
>
>
>
>

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



|
>








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
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191

192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247

                    nLongest = lMatrix[x][y]
                    nLongestX = x
            else:
                lMatrix[x][y] = 0
    return s1[nLongestX-nLongest : nLongestX]


llMatrix = [
    [  0,  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 ],
    [  1,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  2,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  3,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  4,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  5,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  6,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  7,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  8,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [  9,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 10,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 11,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 12,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 13,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 14,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 15,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 16,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 17,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 18,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 19,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 20,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 21,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 22,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 23,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 24,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 25,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 26,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 27,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 28,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 29,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 30,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 31,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 32,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 33,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 34,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 35,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 36,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 37,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 38,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 39,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 40,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ],
    [ 41,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0 ]
]

#@timethis
def distanceDamerauLevenshteinX (s1, s2):
    "distance of Damerau-Levenshtein between <s1> and <s2>"
    # https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
    if s1 == s2:
        return 0
    nLen1 = len(s1)
    nLen2 = len(s2)
    if nLen1 > 40 or nLen2 > 40:
        return distanceDamerauLevenshtein(s1, s2)
    for i in range(1, nLen1+1):
        for j in range(1, nLen2+1):
            #nCost = 0  if s1[i-1] == s2[j-1]  else 1
            nCost = distanceBetweenChars(s1[i-1], s2[j-1])
            llMatrix[i][j] = min(
                llMatrix[i-1][j]   + 1,        # Deletion
                llMatrix[i][j-1]   + 1,        # Insertion
                llMatrix[i-1][j-1] + nCost,    # Substitution
            )
            if i > 1 and j > 1 and s1[i-1] == s2[j-2] and s1[i-2] == s2[j-1]:
                llMatrix[i][j] = min(llMatrix[i][j], llMatrix[i-2][j-2] + nCost)     # Transposition
    #_showLLMatrix(s1, s2)
    return llMatrix[nLen1][nLen2]

#@timethis
def distanceDamerauLevenshtein (s1, s2):
    "distance of Damerau-Levenshtein between <s1> and <s2>"
    # https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein
    d = {}
    nLen1 = len(s1)
    nLen2 = len(s2)
    for i in range(-1, nLen1+1):
        d[i, -1] = i + 1
    for j in range(-1, nLen2+1):
        d[-1, j] = j + 1
    for i in range(nLen1):
        for j in range(nLen2):

            #nCost = distanceBetweenChars(s1[i], s2[j])
            # We don’t use distanceBetweenChars to speed up the calc,
            # as we use this function only for very long words.
            nCost = 0  if s1[i] == s2[j]  else 1
            d[i, j] = min(
                d[i-1, j]   + 1,        # Deletion
                d[i,   j-1] + 1,        # Insertion
                d[i-1, j-1] + nCost     # Substitution
            )
            if i and j and s1[i] == s2[j-1] and s1[i-1] == s2[j]:
                d[i, j] = min(d[i, j], d[i-2, j-2] + nCost)     # Transposition
    #_showMatrix(s1, s2, d)
    return d[nLen1-1, nLen2-1]

def _showMatrix (s1, s2, dMatrix):
    "display the matrix for Damerau-Levenshtein distance calculation"
    nLen1 = len(s1)
    nLen2 = len(s2)
    print("\n  ", end="")
    for j in range(-1, nLen2+1):
        print(f"{s2[j:j+1]:>4}", end="")
    print("")
    for i in range(-1, nLen1+1):
        print(f"{s1[i:i+1]:2}", end="")
        for j in range(-1, nLen2+1):
            print(f"{dMatrix.get((i, j),'   ·'):4}", end="")
        print("")

def _showLLMatrix (s1, s2):
    "display the matrix for fast Damerau-Levenshtein distance calculation"
    nLen1 = len(s1)
    nLen2 = len(s2)
    print("\n  ", end="")
    for j in range(-1, nLen2+1):
        print(f"{s2[j:j+1]:>4}", end="")
    print("")
    for i in range(0, nLen1+2):
        print(f"{s1[i-1:i]:2}", end="")
        for v in llMatrix[i][:nLen2+2]:
            print(f"{v:4}", end="")
        print("")


#@timethis
def distanceJaroWinkler (sWord1, sWord2, fBoost = .666):
    "distance of Jaro-Winkler between <sWord1> and <sWord2>, returns a float"
    # https://github.com/thsig/jaro-winkler-JS
    if (sWord1 == sWord2):
        return 1.0
    nLen1 = len(sWord1)
    nLen2 = len(sWord2)
    nMax = max(nLen1, nLen2)
    aFlags1 = [ None for _ in range(nMax) ]
    aFlags2 = [ None for _ in range(nMax) ]
    nSearchRange = (max(nLen1, nLen2) // 2) - 1
    nMinLen = min(nLen1, nLen2)
︙︙
189
190
191
192
193
194
195

196
197
198
199
200
201
202

        # and the agreeing characters must be more than half of the
        # remaining characters.
        if nMinLen > 4  and  nCommon > i + 1  and  2 * nCommon >= nMinLen + i:
            fWeight += (1 - fWeight) * ((nCommon - i - 1) / (nLen1 * nLen2 - i*2 + 2))
    return fWeight



def distanceSift4 (s1, s2, nMaxOffset=5):
    "implementation of general Sift4."
    # faster than Damerau-Levenshtein and Jaro-Winkler
    # https://siderite.dev/blog/super-fast-and-accurate-string-distance.html
    if not s1:
        return len(s2)
    if not s2:








>








308
309
310
311
312
313
314
315
316
317
318
319
320
321
322

        # and the agreeing characters must be more than half of the
        # remaining characters.
        if nMinLen > 4  and  nCommon > i + 1  and  2 * nCommon >= nMinLen + i:
            fWeight += (1 - fWeight) * ((nCommon - i - 1) / (nLen1 * nLen2 - i*2 + 2))
    return fWeight


#@timethis
def distanceSift4 (s1, s2, nMaxOffset=5):
    "implementation of general Sift4."
    # faster than Damerau-Levenshtein and Jaro-Winkler
    # https://siderite.dev/blog/super-fast-and-accurate-string-distance.html
    if not s1:
        return len(s2)
    if not s2:
︙︙
252
253
254
255
256
257
258
259
260

261
262
263
264
265
266
267
268
269
270

            nLocalCS = 0
            i1 = i2 = min(i1, i2)
    nLargestCS += nLocalCS
    return round(max(nLen1, nLen2) - nLargestCS + nTrans)


def showDistance (s1, s2):
    "display Damerau-Levenshtein distance and Sift4 distance between <s1> and <s2>"
    nDL = distanceDamerauLevenshtein(s1, s2)

    nS4 = distanceSift4(s1, s2)
    fJW = distanceJaroWinkler(s1, s2)
    echo(f"{s1:22} ≠ {s2:22} \tDL: {nDL}\tS4: {nS4}\tJW: {fJW}")



#### STEMMING OPERATIONS

## No stemming









|

>


|








372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391

            nLocalCS = 0
            i1 = i2 = min(i1, i2)
    nLargestCS += nLocalCS
    return round(max(nLen1, nLen2) - nLargestCS + nTrans)


def showDistance (s1, s2):
    "display distances between <s1> and <s2>"
    nDL = distanceDamerauLevenshtein(s1, s2)
    fDLX = float(distanceDamerauLevenshteinX(s1, s2))
    nS4 = distanceSift4(s1, s2)
    fJW = distanceJaroWinkler(s1, s2)
    echo(f"{s1:22} ≠ {s2:22} \tDL: {nDL:2}\tDLX: {fDLX:2.2}\tS4: {nS4:2}\tJW: {fJW}")



#### STEMMING OPERATIONS

## No stemming
︙︙

Fossil 2.24 [8be0372c10] 2024-04-23 13:25:26
This page was generated in about 0.007s