OK
AJAX error!

Les forumsGrammalecteIdées pour graphspell

Idées pour graphspell

Bonjour,

J'ai regardé vite fait le code pour Graphspell et si j'ai bien compris quand un mot n'est pas valide vous essayez de remplacer des lettres par d'autres et à chaque fois vous vérifiez s'il existe ou pas.

Vu que nous connaissons tous les mots possibles, je me demandais si ça ne serait pas avantageux de faire des pré-filtres avant de vérifier l’existence de la chaîne généré.

Par exemple pour "y" vous essayez avec "yYiIîÎÿŸŷŶýÝỳỲȳȲ" nous savons d'avance qu'il n'y a pas de mot avec "ý", "ỳ", "ŷ" et "ȳ" donc en pré-filtre nous pouvons tester simplement si la chaîne contient "ý", "ỳ", "ŷ", "ȳ" nous vérifions pas l’existence et nous l’excluons directement.
Il est assez simple de créer une liste avec tous les caractères possibles contenu dans les mots dico ;) et donc faire un pré-filtre pour ne vérifier que les contenants que ses caractères est assez simple.

Nous pouvons même peut-être aussi faire un pré-filtre sur 2 lettres...

Sur une base de mot que j'ai, en faisant toutes les combinaisons de 2 lettres avec "bcçdfghjklmnñpqrstvwxzaáàâäāeéèêëēiíìîïīoóòôöōuúùûüūyýỳŷÿȳœæ" il y a 3600 binômes possibles dont 2596 qui ne sont pas comprises dans des mots. Je pense donc que ça pourrait accélérer Graphspell si on ne vérifiait pas dans le dico dès qu'une des combinaisons est comprise dans la chaîne à vérifier.

--

Sinon pour l'ordre des suggestions ne serait-il pas possible d'ajouter l'indice d'utilisation (ou le nombre total d'utilisation qui est dans le lexique) du mot dans le dico et d'utilisé cette info pour classer les suggestions ?

--

PS: je dis peut-être des bêtises vu que j'ai pas vérifié mes théories ;)
le 04 octobre 2018 à 14:59
Bonjour,

Toute idée pour accélérer le moteur de suggestion de Graphspell est bonne à prendre, attendu que c’est l’algorithme le plus coûteux de Grammalecte.

Cela dit, Graphspell ne fonctionne pas comme vous le supposez.

L’algorithme de suggestion essaie de parcourir le graphe de mots avec la chaîne entrée par l’utilisateur. On ne fait pas la substitution de toutes les lettres possibles, on ne fait la substitution que si l’on rencontre dans le graphe de mots une substitution possible (autrement dit, on filtre déjà, mais sans avoir eu à créer de filtre). Mettons que l’utilisateur a tapé la lettre “e”. On ne va pas faire toutes les substitutions de “e” possibles, mais seulement celles avec les lettres qu’on trouve au node du graphe où on se trouve. Si le node indique que les prochains arcs sont “é”, “e”, “a”, “i”, “n”, “x”, seuls les arcs “é” et “e” seront parcourus selon les équivalences décrites dans le fichier “char_player”.

Sur une base de mot que j'ai, en faisant toutes les combinaisons de 2 lettres avec "bcçdfghjklmnñpqrstvwxzaáàâäāeéèêëēiíìîïīoóòôöōuúùûüūyýỳŷÿȳœæ" il y a 3600 binômes possibles dont 2596 qui ne sont pas comprises dans des mots. Je pense donc que ça pourrait accélérer Graphspell si on ne vérifiait pas dans le dico dès qu'une des combinaisons est comprise dans la chaîne à vérifier.


Oui, c’est une très bonne idée pour éviter les permutations inutiles et peut-être d’autres recherches absurdes. Bien vu.

Sinon pour l'ordre des suggestions ne serait-il pas possible d'ajouter l'indice d'utilisation (ou le nombre total d'utilisation qui est dans le lexique) du mot dans le dico et d'utiliser cette info pour classer les suggestions ?


L’indice de fréquence n’est pas encore intégré dans le dictionnaire de Grammalecte, attendu que celui-ci manque souvent de fiabilité, et que ça va alourdir le dictionnaire pour pas grand-chose. Par ailleurs, utiliser l’indice de fréquence, c’est peut-être plus traitre qu’on ne l’imagine, c’est souvent les mots les plus rares qu’on ne sait pas écrire correctement. Faudrait voir.
le 05 octobre 2018 à 09:33
Merci de votre réponse.

J'ai un "site de poésie" ouvert à tous, dans celui-ci :
* Les fautes les plus fréquentes sont genre "coeur" d'une manière générale tous les mots avec des "œ" ou "æ"
* Après il y a souvent des erreurs d’accents (et majoritairement sur les majuscules)
=> Pour ces deux cas, il est facilement possible de tester en priorité et surement ne pas chercher d'autres possibilités si des suggestions sont trouvé (ou avec une version de permutation avec moins de cas). A mon avis c'est pratiquement sure que la bonne suggestion serais faite ;)

Sinon comme autre idée (mais avec le gros inconvénient de grossir énormément les data et vraiment pas sure que ça serait "rentable") serait de "phonétisé" tous les mots puis pour chaque phonème d'avoir la liste de tous les mots possible. Et donc convertir l'entré utilisateur en phonème et vérifier s'il est existant et si c'est le cas retourner la liste des mots du phonème.

Pour l'ordre des suggestions c'est le genre de chose où ça ne satisfera jamais tout le monde.
le 05 octobre 2018 à 13:41

IllusionPerdu :
* Les fautes les plus fréquentes sont genre "coeur" d'une manière générale tous les mots avec des "œ" ou "æ"
* Après il y a souvent des erreurs d’accents (et majoritairement sur les majuscules)


Le moteur de suggestion gère déjà très bien ces cas-là. Le problème, c’est que le moteur ne peut pas savoir à l’avance quand le problème ne concerne que l’accentuation. Ce que le cerveau voit immédiatement, le correcteur l’ignore. Il faudrait donc faire deux passes de recherche (une simple pour l’accentuation, une autre pour le reste), mais, dans ce cas, rien ne garantit que ça ira plus vite, puisqu’il faudra parcourir le graphe deux fois.
En fait, le problème concerne surtout le tri des suggestions qui est une affaire plus délicate qu’il n’y paraît.

Sinon comme autre idée (mais avec le gros inconvénient de grossir énormément les data et vraiment pas sure que ça serait "rentable") serait de "phonétisé" tous les mots puis pour chaque phonème d'avoir la liste de tous les mots possible. Et donc convertir l'entré utilisateur en phonème et vérifier s'il est existant et si c'est le cas retourner la liste des mots du phonème.


En fait, le moteur de suggestion procède déjà par substitution phonétique, mais il n’a pas besoin de phonétiser à l’avance tous les mots, il le fait au fur et à mesure en parcourant les lettres.
le 05 octobre 2018 à 20:08
Finalement, vérifier l’existence des digrammes ne changent pas grand-chose pour accélérer la recherche des graphies correctes, car même s’il existe de nombreux digrammes inutiles, dans les faits, on ne les rencontre pas si souvent. Ça accélère quand même un peu la recherche en éliminant les cas extrêmes.
Par contre, j’ai modifié un micro-réglage dans la sélection des graphies retenues, et ça a accéléré grandement (×2+ dans certains cas) le moteur de suggestion.
le 06 octobre 2018 à 15:55
C'est une bonne nouvelle (surtout pour le micro réglage) !

Les cas qui peuvent nous paraître extrême peuvent se produire plus souvent qu'on ne le pense vu que nous avons pas de contrôle sur la saisie du texte.

Sinon dans le tokenizer pour trouver les mots il y a [/^[a-zA-Zà-öÀ-Ö0-9ø-ÿØ-ßĀ-ʯfi-stᴀ-ᶿ_]+(?:[’'`-][a-zA-Zà-öÀ-Ö0-9ø-ÿØ-ßĀ-ʯfi-stᴀ-ᶿ_]+)*/, 'WORD'] je pense que dans les intervalles "à-ö", "À-Ö", "ø-ÿ", "Ø-ß", "Ā-ʯ", "fi-stᴀ" il y a pas mal de caractères qui en fait ne sont pas possibles dans tous les mots du dico donc comme autre micro-optimisation : faire le recensement des caractères du dico et donc vérifier que la saisie comporte que ses caractères peut aussi apporter un autre petit gain.

En tout cas bravo pour votre réactivité.
le 06 octobre 2018 à 16:58
Les caractères du dictionnaire sont déjà recensés, ils servent d’arcs aux nœuds du graphe de mots. Pour les caractères exotiques (non existants dans le dictionnaire), le moteur de suggestion tente de faire des substitutions ou les ignore.
le 06 octobre 2018 à 19:22
Après une analyse rapide je pense que dans la partie


# Phonetic replacements
for sRepl in cp.get1toXReplacement(sNewWord[-1:], cCurrent, sRemain[1:2]):
self._suggest(oSuggResult, sRepl + sRemain[1:], nMaxSwitch, nMaxDel, nMaxHardRepl, nMaxJump, nDist, nDeep+1, iAddr, sNewWord, True)
for sRepl in cp.d2toX.get(sRemain[0:2], ()):
self._suggest(oSuggResult, sRepl + sRemain[2:], nMaxSwitch, nMaxDel, nMaxHardRepl, nMaxJump, nDist, nDeep+1, iAddr, sNewWord, True)


il faudrait aussi vérifié les bigrâmes et donc faire


# Phonetic replacements
for sRepl in cp.get1toXReplacement(sNewWord[-1:], cCurrent, sRemain[1:2]):
if self.isNgramsOK(sRepl[-1] + sRemain[1:2]):
self._suggest(oSuggResult, sRepl + sRemain[1:], nMaxSwitch, nMaxDel, nMaxHardRepl, nMaxJump, nDist, nDeep+1, iAddr, sNewWord, True)
for sRepl in cp.d2toX.get(sRemain[0:2], ()):
if self.isNgramsOK(sRepl[-1] + sRemain[2:3]):
self._suggest(oSuggResult, sRepl + sRemain[2:], nMaxSwitch, nMaxDel, nMaxHardRepl, nMaxJump, nDist, nDeep+1, iAddr, sNewWord, True)


le 08 octobre 2018 à 14:38
Par curiosité je viens de regarder tous les bigrâmes généré et je me demande l'utilité de garder :

"d ", "e ","n ","o ","w ","l ","s ","a ","t ","y ","x "


et

" M", " A", " F", " D", " I", " b", " C", " L", " d", " P", " V", " R", " Y", " B", " S", " T"


vu que graphspell ne vérifie pas les mots avec un espace (si je me trompe pas).
le 08 octobre 2018 à 16:34
Pour la version javascript de ibdawg il est préférable de laisser le l2grams en array et de modifier la function isNgramsOK en :


isNgramsOK (sChars) {
if (sChars.length != 2) {
return true;
}
return this.a2grams.indexOf(sChars) !== false;
}


la vérification est environs 2 fois plus rapide ;)
le 08 octobre 2018 à 23:48

IllusionPerdu :
if self.isNgramsOK(sRepl[-1] + sRemain[1:2]):

if self.isNgramsOK(sRepl[-1] + sRemain[2:3]):


Non, ça n’a pas d’utilité de tester les digrammes de lettres qui ne se touchent pas.


graphspell ne vérifie pas les mots avec un espace (si je me trompe pas)


En fait, si, depuis peu. Il y a des mots avec espace dans le dictionnaire. Tous les digrammes sont créés à partir des mots du dictionnaire, et c’est bien parce qu’il y a des espaces dans ceux-ci qu’on les retrouve dans les digrammes.
Mais, oui, il n’est pas certain que les digrammes avec espaces soient utiles. Je vais les enlever, je pense.


il est préférable de laisser le l2grams en array.
la vérification est environs 2 fois plus rapide ;)


Tu es sûr ? Voilà qui est surprenant.
Avec quelle longueur de liste tu as testé ? Avec quel moteur JS ? Il est un peu étonnant que ça soit plus rapide de tester tous les éléments d’une liste plutôt que la présence d’un élément dans un ensemble.
le 09 octobre 2018 à 09:57
Bon, j’ai voulu vérifier, mais je n’y suis pas parvenu. Pour une raison quelconque, dans isNgramsOK, JS me déclare que this.l2grams est undefined et je n’arrive pas à comprendre pourquoi. (Qu’est-ce que JS me gonfle…)
le 09 octobre 2018 à 10:56
Pour le test de rapidité j'ai essayer sous chrome (vu que c'est le navigateur que j'utilise le plus). J'ai fait un copier coller de la liste des l2grams depuis le fichier fr-allvars.json :


l2grams = new Set([la liste copier direct du fichier])
l2grams2 = [la liste copier direct du fichier]
l2grams3={};l2grams.forEach(v => l2grams3[v]=v);

console.time('#Objet');
for (let i = 0; i < 10000000; i++) {
l2grams3['èè'] !== false;
}
console.timeEnd('#Objet');
console.time('#Set');
for (let i = 0; i < 10000000; i++) {
l2grams.has('èè');
}
console.timeEnd('#Set');
console.time('#Index');
for (let i = 0; i < 10000000; i++) {
l2grams2.indexOf('èè') !== false;
}
console.timeEnd('#Index');
console.time('#Include');
for (let i = 0; i < 10000000; i++) {
l2grams2.includes('èè') == true;
}
console.timeEnd('#Include');


ce qui donne =>


(Quand le bigram n'existe pas)
#Objet: 157.31787109375ms
#Set: 230.652099609375ms
#Index: 75.159912109375ms
#Include: 60244.133056640625ms
--
(Sur une valeur qui existe)
#Objet: 98.22509765625ms
#Set: 132.152099609375ms
#Index: 73.361083984375m
#Include: 62361.846923828125ms



Je pense avoir relativement bien compris le code en python (même s'il a pratiquement qu'avec dicollecte ou j'ai fait un truc avec) mais tu envoie dans les sugestion a chercher
=> ligne 347 : self._suggest(oSuggResult, sRepl + sRemain[1:] ...) donc en mettant if self.isNgramsOK(sRepl[-1] + sRemain[1:2]): avant cette ligne fait qu'on vérifie
bien les bigrame pour se qui est envoyer
=> ligne 349 self._suggest(oSuggResult, sRepl + sRemain[2:] ...) donc j'ai ajouté if self.isNgramsOK(sRepl[-1] + sRemain[2:3]):

--

Bizarre le this.l2grams est undefined et en remplacant le (Ligne 272) this.a2grams = new Set(this.l2grams); en this.a2grams = this.l2grams; et donc dans isNgramsOK avec le this.a2grams...
le 09 octobre 2018 à 12:23
Oups tester le même code sous firefox pour le benchmark... Le indexOf met beaucoup plus de temps.
jsfiddle.net…
J'ai baisser le nombre dans la boucle ;)

Mais se qui est bizarre c'est que le indexOf deviens moins performant... les résultat ne sont pas cohérents avec le bench dans la console :S
le 09 octobre 2018 à 12:54
OK, je viens enfin de piger pourquoi j’avais ce foutu undefined : c’est à cause de mon dictionnaire personnel que je n’avais pas resauvegardé et qui donc ne possédait pas l’attribut «l2grams».

Bref, une fois mon manque de discernement élucidé, j’ai pu faire des tests. Je préfère tester en condition normale d’utilisation. Les valeurs sont donc celles du mécanisme de suggestion (avec Firefox). La première ligne, c’est avec le dictionnaire commun, la seconde, c’est avec mon dictionnaire personnel.

Array
Suggestions for jamaiss in 0.88 s
Suggestions for jamaiss in 0.035 s
Suggestions for jugemnt in 0.708 s
Suggestions for jugemnt in 0.013 s
Suggestions for quy in 0.518 s
Suggestions for quy in 0.047 s
Suggestions for épouvantablle in 0.835 s
Suggestions for épouvantablle in 0.028 s
Suggestions for canonniser in 2.549 s
Suggestions for canonniser in 0.08 s
Suggestions for publis in 0.25 s
Suggestions for publis in 0.009 s

Set
Suggestions for jamaiss in 0.394 s
Suggestions for jamaiss in 0.029 s
Suggestions for jugemnt in 0.24 s
Suggestions for jugemnt in 0.008 s
Suggestions for quy in 0.283 s
Suggestions for quy in 0.029 s
Suggestions for épouvantablle in 0.182 s
Suggestions for épouvantablle in 0.012 s
Suggestions for canonniser in 0.593 s
Suggestions for canonniser in 0.053 s
Suggestions for publis in 0.094 s
Suggestions for publis in 0.006 s

Conclusion : c’est bien plus rapide avec Set qu’avec Array, surtout quand le dictionnaire est volumineux.

Tu t’es probablement laissé abuser à cause de l’implémentation de indexOf de Array. Si ça se trouve, Array sauvegarde le résultat de la demande. Et comme tu demandes toujours la même chose, tu as des résultats biaisés.

Ajout : Nos messages se sont croisés. Effectivement, ça vient peut-être aussi de la différence Firefox-Chrome. (Mais il faudrait tester en ne demandant pas toujours la même chose, car c’est peut-être juste une optimisation interne…)
le 09 octobre 2018 à 12:55
Il doit y avoir une optimisation quelque part qui font que les benchmarks ne donne pas la même chose. Et sinon as-tu essayé en transformant en Objet ?

Malgré les incohérences entre les deux moteurs (pour indexOf et le Set) il semblerait qu'avec un Objet se soit toujours plus rapide (se qui est logique vu que le set est basé sur un objet) et vu que pour l'utilisation qu'on en as on a pas besoin des avantages du Set a cet endroit.

Ajout: Oui surement une optimisation dans chrome pour blazer les benchmark et pouvoir dire que c'est le navigateur le plus rapide ;)
le 09 octobre 2018 à 13:21
Je réfléchis à voix haute ;)
Se qui cause la lenteur des suggestions c'est qu'on est obligé de parcourir le graphe plusieurs fois avec des tests de remplacement de caractère.

L'ajout des 2grams permettent de limiter certain parcours => Nouveau problème : La liste est 2grams est assez conséquente

Il y a certain 2grams qui sont dut aux unités de mesure par exemple les dérivé Ω (19 variants) ℓ : kΩ MΩ ... dans la majorité des cas ses 2grams sont inutile. Ne faut-il pas les exclure et utilisé l’élimination des parcours avec les 2grams que si le "mot" a chercher est plus grand de X caractères ? (donc deux méthode de suggestion en fonction de la taille du "mot" a rechercher)

Serait-il intéressant de connaitre la taille du mot le plus long de chaque 2grams afin d'ajouté une condition du type si le "mot" a chercher est plus grand de X caractères que le 2grams max ne pas continuer de parcourir avec les nouvelle condition ? idem pour le plus court.

Seraait-il intéressant de connaitre le mot le plus long commençant par chaque lettre afin de ne même pas commencer le parcourt du graphe si le "mot" a chercher est plus grand ou plus petit de X caractères que le mot le plus long ? (peut être même avec les deux premières lettres)

L'idée de 2 méthodes de suggestion en fonction de la taille du mot est puisque si nous ajoutons pas mal de "if" ou de condition pour les petit mots ça alourdira surement plus (et donc plus lent) que de parcourir tous les cas possible.

J’espère que cette petite réflexion vous donnera des idées ;)
le 09 octobre 2018 à 14:54

Notification par e-mail    1