OK
AJAX error!

Les forumsGrammalecteLexiques binaires indexables avec automate à états finis (FSA)

Lexiques binaires indexables avec automate à états finis (FSA)

\o/
Ça marche ! :D

Petit récapitulatif…

Jusqu’à présent, Grammalecte ne pouvait fonctionner en dehors de LibreOffice, car il dépendait grandement de Hunspell, le correcteur orthographique, pour obtenir les données morphologiques dont il a besoin pour connaître la nature des mots qu’il analyse. Par ailleurs, cette dépendance empêchait d’autres langues d’employer ce système, puisque elles ne possédaient pas de dictionnaires Hunspell grammaticalement étiquetés.

Cependant, il existait des lexiques étiquetés pour LanguageTool… Ceux-ci sont conçus comme des automates à états finis (FSA: finite state automaton) qui sont représentés sous la forme d’un gigantesque graphe de tous les mots de la langue. Ces lexiques étaient conçus avec un programme en C (www.eti.pg.gda.pl…) qui les compressait par ailleurs en dictionnaires binaires indexables, afin qu’ils occupent moins de place que les lexiques bruts dont nous disposons (c’est indispensable, car ceux-ci occupent des dizaines voire des centaines de mega-octets et ne sont pas aisément parcourables, ce qui rend nécessaire leur transformation et leur réduction pour réduire l’empreinte mémoire et accélérer les demandes qu’on peut leur faire).

J’avais donc commencé à lire le code de ce programme, mais je trouvais ça abscons (le C n’est plus qu’un vague souvenir pour moi) et ça m’ennuyait de devoir dépendre une fois encore d’un programme tiers pour le correcteur grammatical. Je me suis donc un peu documenté, j’ai pas mal utilisé le travail de Steve Hanov (stevehanov.ca… mais je ne me suis pas servi de sa méthode pour récupérer les données associées, décrite dans son billet suivant : Easy, Minimal Perfect Hashing, car elle n’est pas assez efficace) et j’ai réfléchi pour concevoir mon propre programme en Python capable de faire la même chose, transformer n’importe quel lexique grammaticalement étiqueté, avec le lemme associé à chaque forme fléchie (en somme, les lexiques non compressés de LT).

Voilà donc ce que j’ai fait ces dernières semaines, et ça fonctionne. :)

Tout n’est pas encore parfait, il reste des optimisations à faire, surtout pour certaines langues, mais le français ne pose pas spécifiquement de problèmes.

Voici ce que ça donne pour l’instant :
(Entre crochets, c’est la taille obtenue avec le programme en C qu’utilise LT)

Lexiques de LT :
Français : 18 053 Ko réduits à 814 Ko [575 Ko] (les dicos Hunspell français pèsent ~1 500 Ko)
Asturien : 4 429 Ko réduits à 372 Ko [264 Ko]
Breton : 8 363 Ko réduits à 2 943 Ko [2 897 Ko]
Catalan : 24 894 Ko réduits à 841 Ko [635 Ko]
Tchèque : 573 784 Ko réduits à 64 008 Ko [9 899 Ko]
Danois : 7 341 Ko réduits à 463 Ko [267 Ko]
Hollandais : 9 597 réduits à 2 612 Ko [1 480 Ko]
Anglais : 8 122 Ko réduits à 1 731 Ko [1 146 Ko]
Galicien : 455 282 Ko réduits à 5 031 Ko [4 601 Ko]
Allemand : 202 859 Ko réduits à 1 631 Ko [1 032 Ko]
Italien : 18 622 Ko réduits à 639 Ko [446 Ko]
Khmer : 1 344 Ko réduits à 244 Ko [263 Ko]
Malayalam : 6 Ko réduits à 3 Ko [4 Ko]
Polonais : 188 408 Ko réduits à 10 885 Ko [2 887 Ko]
Roumain : 22 458 Ko réduits à 971 Ko [687 Ko]
Russe : 276 870 Ko réduits à 2 440 Ko [1 724 Ko]
Slovaque : 75 308 Ko réduits à 2 174 Ko [735 Ko]
Espagnol : 18 958 Ko réduits à 828 Ko [603 Ko]
Suédois : 10 301 Ko réduits à 623 Ko [427 Ko]
Tagalog : 202 Ko réduits à 93 Ko [62 Ko]
Ukrainien : illisible, impossible à décompresser avec l’outil fourni par LT.

Ce n’est pas encore aussi bon que le FSA en C, mais je n’ai sciemment pas encore employé toutes les possibilités de compression. Je me moque pas mal que le dico français pèse 240 Ko de plus que l’autre si ça peut me faire gagner en vitesse. Mais il y a certaines langues où il faut revoir certains points et utiliser d’autres techniques pour compresser la taille.

Conséquences pour l’avenir :
— plus grand-chose à faire pour rendre autonome Grammalecte et le faire fonctionner comme serveur (les résultats seront fournis au format JSON),
— il sera enfin possible de concevoir des tests automatiques pour éviter les régressions provoquées par les nouvelles règles (moins de faux positifs imprévus),
— il sera possible pour Lightproof/Grammalecte d’utiliser les lexiques de LT,
— rien ne s’oppose plus à l’adaptation de Grammalecte pour Firefox (mais ce n’est pas demain la veille, hein, car je ne suis pas un expert en JavaScript et je ne connais pas la programmation pour Mozilla, il faudra donc du temps et surtout de la motivation).

Tout ça est conçu avec Python 3.3 en quelques centaines de lignes de code.

Il y a encore du boulot, mais ça avance.
le 27 novembre 2012 à 20:09
Bravo !

Tout ça est conçu avec Python 3.3 en quelques centaines de lignes de code.


est-ce à dire que la venue de Python 3.3 sur Libreoffice 4.0 est importante pour Grammalecte ?
le 27 novembre 2012 à 23:03
Bravo ! Ça semble très intéressant.

Est-ce que la prochaine version de Grammalecte pourra donc être utilisée sans Libreoffice ?
Je suis aussi assez curieux du format de fichier employé encoder le FSA. Y a-t-il des informations à ce sujet ?

PS: pas de stats pour le lexique espéranto ?
le 28 novembre 2012 à 01:11

est-ce à dire que la venue de Python 3.3 sur Libreoffice 4.0 est importante pour Grammalecte ?


Oui, d’une certaine manière. Mais c’est surtout du confort de programmation. Grammalecte serveur exigera Python 3.3, mais c’est indépendant de Grammalecte comme extension. En fait, la rétrocompatibilité de Python 3.3 devrait permettre de gérer les deux versions sans trop de peine.

Est-ce que la prochaine version de Grammalecte pourra donc être utilisée sans Libreoffice ?


La prochaine version mineure, non, mais la version 0.3, oui. D’ici quelques semaines, je pense. En fait, je veux d’abord finaliser la travail pour les autres langues afin de pouvoir passer le bébé à LibreOffice/Lightproof.

pas de stats pour le lexique espéranto ?


Je n’ai pas vu de lexique pour l’espéranto.
languagetool.svn.sourceforge.net…
C’est où ?

Je suis aussi assez curieux du format de fichier employé encoder le FSA. Y a-t-il des informations à ce sujet ?


Eh bien, c’est un format binaire personnel assez simple.

1. On liste tous les caractères du lexique et on les place dans une liste VAL.

2. On calcule un code d’affixation pour toutes les entrées du lexique afin de pouvoir retrouver le lemme de chaque mot.
Par exemple, avec «mangèrent», lemme «manger», le code est «5er» qui signifie «ôter les 5 dernières lettres au mot, puis ajouter “er”». Ce code est identique pour de nombreuses entrées en «-èrent» comme vous vous en doutez, et ça permet un gain de place énorme.
Pour le français, quelque 800 codes d’affixation permettent de retrouver les lemmes des quelque 550 000 mots du dictionnaire.
On ajoute la liste des codes d’affixation à la liste VAL.

3. On ajoute la liste des étiquettes grammaticales à la liste VAL.

4. Conception du graphe des mots (en.wikipedia.org…) :
Chaque mot est représenté par une liste d’indices pointant sur la liste VAL.
Par exemple, pour «mangèrent» :
m, a, n, g, è, r, e, n, t, 5er, v1it_ipsi_3pl == 13, 1, 14, 7, 28, 18, 5, 14, 20, 435, 1372

Chaque valeur pointe sur la liste VAL un caractère, un code d’affixation ou une étiquette grammaticale.

La particularité de ce graphe, c’est que le dernier “node” n de chaque mot et le “node” n-2 sont étiquetés comme nodes finaux.

5. Fichier binaire du dictionnaire :

a. Entête
/pyfsa/version

b. Infos
nombre de caractères /
nombre d’octets pour représenter un arc /
nombre d’octets pour représenter une adresse du node /
etc.
C’est une liste de valeurs utiles pour gérer le dico.

c. VAL
Liste des valeurs de VAL, séparées par un code tabulation

d. Le graphe de mots
Liste des nodes du graphe, chacun étant eux-mêmes une liste d’(arcs+adresse du node suivant), chaque valeur étant codée sur un nombre d’octets définis dans Infos. (Un arc est une valeur d’un mot pointant sur la liste VAL).
Par exemple, pour le français, chaque arc utilise deux octets, chaque adresse de node 3 octets.
|_|_|_|_|_|_|_|_| |_|_|_|_|_|_|_|_| |_|_|_|_|_|_|_|_| |_|_|_|_|_|_|_|_| |_|_|_|_|_|_|_|_|

Les 3 bits de poids fort de la valeur d’un arc servent à coder des informations spécifiques :
— ce node est-il un node final ?
— cet arc est-il le dernier arc du node ?
— le node suivant est-il placé en mémoire juste après ce node ? (ceci n’est pas encore implémenté)

Tout sera documenté plus en détail avec le code.
le 28 novembre 2012 à 10:11

Tout sera documenté plus en détail avec le code.


Super :-)

[...] pour le français, chaque arc utilise deux octets, chaque adresse de node 3 octets.


Je regarderai un peu par curiosité quand c’est disponible. Peut-être que ça vaut la peine d’utiliser un bitstream (plutôt que d'aligner les code sur 1/2/3/4… octets) avec des codes de tailles variables (moins de bits pour les codes fréquents que pour les codes rares, i.e. codes Huffman. Ça peut être plus compact si les codes ont une distribution de fréquence non-uniforme. Mais décoder un bitsteam est aussi un peu plus lent et un peu plus compliqué.
le 28 novembre 2012 à 10:30

Je n’ai pas vu de lexique pour l’espéranto.
languagetool.svn.sourceforge.net…
C’est où ?


Ah oui bien sûr. Un dictionnaire est utilisé uniquement pour la vérification orthographique de l'espéranto, mais pas pour la morphologie. Le tagger de LT pour l’espéranto n’utilise pas de dictionnaire. Il assigne la morphologie en analysant la terminaison des mots : *o = nom, *oj = nom pluriel, *a = adjectif, *as = verbe présent, *i = verbe infinitif, etc. C'est possible puisque l’espéranto est régulier. L'avantage de cette approche est que la morphologie est correcte même pour les mots absents dans le dictionnaire. Pas mal de mots manquent dans les dictionnaires Hunspell espéranto. C'est aussi beaucoup plus compact que d’utiliser un dictionnaire.

Voici le tagger espéranto de LT :

languagetool.svn.sourceforge.net…

le 28 novembre 2012 à 11:10
Dans ce cas, il faudra créer un graphe sans les étiquettes grammaticales et le lemme, et faire la même chose que le code Java en Python. Ça ne devrait pas être compliqué.
le 28 novembre 2012 à 11:39
En modifiant la méthode de création des affixes, on obtient de bien meilleurs résultats pour certaines langues. En effet, dans le test précédent, je me contentais de générer les affixes permettant de créer lemme uniquement à partir de la fin (suffixation). Ce qui ne convient pas du tout à certaines langues.

Avec le breton, en me basant plutôt sur la plus grande sous-chaîne commune entre le lemme et la forme fléchie, on obtient de bien meilleurs résultats. Le nombre de code d’affixation est divisé par dix, et, comme ça simplifie grandement le graphe des mots, le dictionnaire binaire ne pèse plus que 823 Ko au lieu des 2 943 Ko de la méthode précédente.
Pareillement, avec le polonais, je passe d’un dico binaire 10 885 Ko à 2 979 Ko.
Enfin, avec le tchèque, je passe de 64 008 Ko à 4 796 Ko.

Ce qui est mieux (pour le breton et le tchèque) ou très proche (pour le polonais) de ce que fait la version C de LT.

Et il me reste une méthode pour compresser encore plus tout ça, mais je ne pense pas que ce soit nécessaire ou utile. Je vais le faire uniquement au cas où on décide de me casser les pieds avec ça. :)
le 28 novembre 2012 à 18:47
De nouveaux résultats plus détaillés :
www.dicollecte.org…
le 29 novembre 2012 à 14:24
Bon, après divers essais pour compresser encore les dictionnaires, je suis convaincu que c’est largement faisable, mais pas si simple ; il y a pas mal de méthodes possibles, dont la mise en œuvre est plus ou moins compliquée, et je ne sais pas trop laquelle est la meilleure, il faudrait que je fasse pas mal de tests et que je réfléchisse plus longuement. J’ai décidé de laisser courir l’affaire quelque temps, car là mon esprit sature un peu sur cette question. J’espère y voir plus clair plus tard, en pensant à autre chose et en me reposant. Car mon cerveau fume un peu en ce moment. J’ai besoin de repos. ;)

Du coup, j’ai décidé de poster et publier ce qui marche déjà bien :
nabble.documentfoundation.org…
le 04 décembre 2012 à 20:18
Voilà de nouveaux résultats en compressant le dictionnaire binaire :
www.dicollecte.org…

Mon programme donne les chiffres de l’avant-dernière colonne, ceux de la dernière sont ceux des dicos de LT. C’est étonnamment inégal, mais comme je ne sais pas trop comment fonctionne le script qu’utilise LT, difficile de savoir pourquoi.

On peut sûrement encore faire mieux. J’ai une autre idée à tester, et je crois que j’en resterai là. :)
le 06 décembre 2012 à 17:05

Notification par e-mail    0