README.md

SpellChecker - Projet de IN204, correction orthographique et sémantique

Réalisé par GEFFROY Thomas et TAN Willy

SOMMAIRE

  1. INTRODUCTION

  2. CONSTRUCTION 2.1 Avant de construire 2.2 Constuire SpellChecker

  3. UTILISATION 3.1 Orthographe 3.2 Sémantique

  4. FONCTIONNEMENT 4.1 Correction orthographique 4.2 Correction sémantique

  5. AMÉLIORATIONS

  6. RÉFÉRENCES

======== 1. INTRODUCTION ========

SpellChecker est un logiciel de correction orthographique et sémantique de phrases, utilisant une structure de type BKTree pour l'orthographe et un ensemble de classifieurs basés sur de l'apprentissage automatique de type Winnow. Le logiciel utilise une interface graphique exploitant les possibilités offertes par la bibliothèque Qt.

L'ensemble du projet peut être téléchargé à l'adresse : http://gitlab.ensta.fr/geffroy/SpellChecker.git

Télécharger directement sur le site ou bien appeler git clone http://gitlab.ensta.fr/geffroy/SpellChecker.git

SpellChecker est écrit en C++.

======== 2. CONSTRUCTION ========

==== 2.1 Avant de construire ====

SpellChecker a été écrit pour Linux, et ne marche pas sur Windows ou MACOs.

SpellChecker utilise le compilateur g++ et la version C++14. De ce fait, si la version de g++ sur votre ordinateur est trop ancienne (e.g. les ordinateurs de l'ENSTA), le programme ne compilera pas.

Les bibliothèques utilisées par SpellChecker sont Qt, Boost et Citar. Des versions portables ont été intégrées dans le projet, il n'y a donc normalement pas besoin d'installer Qt, Boost ou Citar.

==== 2.2 Construire SpellChecker ====

Pour construire SpellChecker, lancer 'make' en ligne de commande à la racine du projet.

======== 3. UTILISATION ========

Lors de l'exécution de SpellChecker, une fenêtre comprenant une zone de traitement de texte s'ouvre.

==== 3.1 Orthographe ====

Lorsque vous tapez un mot qui n'existe pas dans le dictionnaire, celui-ci sera souligné en rouge afin de signaler une erreur. Lorsque le curseur de texte reviendra sur le mot en cliquant dessus ou en naviguant à l'aide des flèches), des propositions de correction seront mises en valeur en haut de la fenêtre, incluses dans des boutons. Cliquer sur un des boutons remplacera alors le mot souligné par celui du bouton.

==== 3.2 Sémantique ====

Lorsque vous tapez un mot qui est détecté comme une faute de sémantique (confusion entre their et there, ou encore knew et new par exemple), celui-ci sera souligné en bleu. Lorsque le curseur de texte reviendra sur le mot (en cliquant dessus ou en naviguant à l'aide des flèches), une proposition de correction sera mise en valeur en haut de la fenêtre sous forme d’un bouton. Cliquer sur le bouton remplacera alors le mot souligné par celui du bouton.

======== 4. FONCTIONNEMENT ========

==== 4.1 Correction orthographique ====

La correction orthographique repose sur la structure BKTree exploitant le concept de distance dite de Damerau-Levenshtein.

La distance entre deux mots correspond au nombre d'opérations (substitution, délétion, ajout ou permutation de lettres) pour passer d'un premier mot à un autre. La structure BKTree exploite ces distances pour placer l'ensemble des mots du dictionnaire dans un arbre suivant une logique précise (voir référence). La recherche d'un mot dans l'arbre est faite plus rapidement en moyenne qu'un parcours linéaire du dictionnaire : l'algorithme de recherche ne parcourt qu'environ 5% de l'arbre s'il cherche tous les mots de distance 1 (une erreur de frappe), et entre 10 et 15% de l'arbre pour les mots de distance 2 (deux erreurs de frappe).

L'algorithme de recherche utilisé dans SpellChecker couple la recherche BKTree avec une analyse fréquentielle d'apparition des mots renvoyés. Les mots de plus haute fréquence sont mis en haut de la liste des corrections possibles, et ceux n'apparaissant jamais ou trop rarement (dictionnaire erroné ou trop large) ne sont pas intégrés. Le dictionnaire des fréquences est construit sur la base d'un corpus de textes disponible dans le dossier resources/CORPORA : un algorithme va passer en revue chaque texte et incrémenter la fréquence d'apparition des mots à chaque fois qu'elle les rencontre.

La construction de l'arbre et du dictionnaire des fréquences prenant un certain temps (l'arbre appelle plus de 5 millions de fois le calcul de distance qui construit à chaque appel une matrice de taille 5x5 (taille moyenne des mots), et le dictionnaire passe en revue plus de 1 million de mots), nous avons décidé de les sérialiser (enregistrer dans un fichier annexe) à l'aide des fonctions de la bibliothèque "Serialization" de Boost. On passe ainsi de 10 secondes de construction à moins d'une seconde de chargement de fichier.

==== 4.2 Correction sémantique ====

La correction sémantique repose sur un algorithme d'apprentissage automatique utilisant des classifieurs de type Winnow. L'algorithme utilisé prend en entrée une phrase, cherche dans la phrase des mots pouvant être confondus (à partir d'un ensemble de confusion défini au préalable). Si l'un de ces mots est présent, l'algorithme extrait le contexte dans lequel le mot apparaît (les mots présents autour mais aussi le rôle des mots adjacents, par exemple si le mot est suivi d'un verbe ou non), évalue la cohérence du mot dans le contexte à l'aide du classifieur de ce mot, compare avec la cohérence des mots pouvant être confondus, et retourne le mot le plus cohérent.

La fonction calculant la cohérence de chaque mot est entraînée sur un corpus préalablement préparé pour être lu par l'algorithme. Chaque phrase du corpus est analysée par un étiqueteur de rôle (POSTagger) retournant alors la structure de chaque phrase (sujet verbe complément...). L'algorithme récupère alors les structures et les contextes (features) récurrents lors de l'entraînement, et les ajoute à l'ensemble des features possibles autour de chaque mot.

L'étiqueteur utilisé est celui de la bibliothèque citar (voir lien en référence). Celui-ci reposant sur de la prédiction à l'aide d'apprentissage automatique, l'étiquetage est donc parfois imparfait (des mots peuvent ne pas être étiquetés). Toutefois, celui-ci donne des résultats assez précis pour que la correction finale soit possible.

L'entraînement et la préparation des corpus prenant du temps (le corpus utilisé prenant plus d'une heure à être préparé), une fois ceux-ci faits, les classifieurs et les corpus sont sérialisés à l'aide de la bibliothèque Serialization de Boost.

======== 5. AMÉLIORATIONS ========

Une des améliorations principales pouvant être apportées serait d'entraîner beaucoup plus l'algorithme : le corpus donné est trop petit, mais malheureusement les performances limités de nos ordinateurs ne permettaient pas de charger des corpus plus grands. De ce fait, plein de mots ne sont pas pris en compte lors de l'apprentissage automatique. Avec un apprentissage plus poussé, l'algorithme pourrait alors prédire plus précisément. L'ensemble de confusion pourrait être plus large afin d'agrandir la correction.

La correction orthographique pourraît être améliorée en prenant en compte les erreurs liées à la proximité des touches sur le clavier. En effet, la distance de damerau-levenshtein est une distance théorique qui ne prend pas en compte la nature même des mots. En définissant une distance plus "humaine", la correction pourrait être plus précise.

======== 6. RÉFÉRENCES ========

Aides à la compréhension des BKTree : https://nullwords.wordpress.com/2013/03/13/the-bk-tree-a-data-structure-for-spell-checking/ http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees https://signal-to-noise.xyz/post/bk-tree/ https://fr.wikipedia.org/wiki/Distance_de_Damerau-Levenshtein

Aides à la compréhension de l'algorithme de Winnow : https://en.wikipedia.org/wiki/Winnow_(algorithm) http://www.cs.yale.edu/homes/aspnes/pinewiki/WinnowAlgorithm.html https://pdfs.semanticscholar.org/58db/a823fc1d5f5d45c6fb7414aba7fed7011fb8.pdf https://www.codeproject.com/Articles/826449/Context-Sensitive-Spelling-Correction-using-Winnow

Bibliothèque Boost et aide à la sérialisation : http://www.boost.org/doc/libs/1_62_0/index.html https://openclassrooms.com/courses/serialisation-avec-boost

Bibliothèque Citar : https://github.com/danieldk/citar-cxx

Corpus de texte : http://www.anc.org/data/oanc/download/ http://www.sls.hawaii.edu/bley-vroman/brown_corpus.html