Logiciel de traitement de texte Windows
avec outils d'analyse lexicale
Ce projet consiste alors à développer un logiciel de traitement de texte pour la plate-forme Windows. En plus des fonctions de base d’un logiciel de ce type, l’application offre à l’usager des outils efficaces pour vérifier et corriger l’orthographe, comptabiliser le nombre de mots et exécuter certaines vérifications syntaxiques.
Les objectifs d’apprentissage de cet l’exercice sont : l’approfondissement des notions de programmation orientée-objet, la maîtrise de types abstraits de données et le mécanisme des classes, la conception d’algorithmes performants pour les recherches dans le dictionnaire lexical, la manipulation d’arbres binaires et l’initiation à l’utilisation des classes MFCs de Microsoft.
Dans les sections qui suivent, vous retrouverez un survol des fonctionnalités du bien livrable, une description de la problématique et des solutions apportées, une analyse de la performance, une description de la robustesse du code et enfin un mot de clôture. Veuillez vous référer aux annexes du rapport afin de retrouver une analyse des besoins selon l’approche de Parnas , un listing complet du code développé et un échantillon de tests unitaires.
Parmi ces sous-ensembles, on retrouve le menu File, Edit, View et Help. On retrouve ces quatre sous-groupes dans presque tous les logiciels Windows. Le nombre d’éléments dans chaque sous-ensemble peut varier d’une application à l’autre mais certains de ceux-ci sont obligatoires. Parmi ces éléments, on retrouve les fonctions permettant de sauvegarder un document actif sur un support de stockage quelconque ou de rediriger le document actif vers une sortie standard telle que l’imprimante. Dans les deux cas, on doit aussi avoir accès à l’interface du support ou de l’imprimante afin de configurer ou modifier les paramètres correspondants.
Le logiciel TextWriter ne fait alors pas exception à ces standards. Parmi ceux-ci, l’application permet de : créer un nouveau document à base de texte, ouvrir un document existant, sauvegarder, imprimer, avoir un aperçu avant l’impression, faire un zoom avant/arrière ou visualiser une page ou deux à la fois dans l’aperçu, accéder directement à un fichier via une liste de fichiers récemment ouverts, annuler la dernière modification, copier, coller ou supprimer une sélection et afficher des informations à propos de l’application. Les fonctions les plus courantes sont également accessibles via une combinaison de touches de raccourci du clavier.
Les fonctions qui ne sont pas universelles d’une application à une autre contribuent au caractère unique du logiciel. TextWriter incorpore des services d’analyse lexicale aux services accessibles par l’usager. Parmi ceux-ci on retrouve la vérification de l’orthographe, la suggestion de mots du dictionnaire, la correction ou l’ajout d’un nouveau mot, la vérification de la syntaxe et la comptabilisation du nombre de mots du document.
Au niveau de l’interface graphique, on retrouve une barre d’outils qui permet d’accéder directement aux fonctions courantes d’un logiciel de traitement de texte. Les icônes bitmap sur chaque bouton respecte les standards établis par Microsoft et leur sélection est par conséquent plus intuitif. L’application affiche aussi une barre de messages qui présente l’état des touches NumLock, CapsLock, et ScrollLock ainsi qu’une description des fonctions du menu textuel ou de la barre d’outils lorsque la souris les survoles.
III-1. L’environnement de développement
En premier lieu, l’adaptation à un nouvel environnement de développement fait référence au passage de Borland C++ à Visual C++. Ce dernier environnement apporte les classes MFC qui offrent une panoplie de classes pré-fabriquée qui servent à accélérer et simplifier la conception de programmes Windows. Le projet exige par conséquent de rechercher toutes les classes pré-fabriquées qui seraient utiles, d’étudier leur interface, de les instancier et interagir avec leurs fonctions publiques.
Le nouvel environnement apporte également une stratégie d’exécution qui est différente des langages qui utilisent une fonction main explicite. La différence vient du fait que Visual C++ est un environnement de programmation qui est dirigé par les événements (Event Driven) contrairement à un environnement qui est dirigé par la fonction main. Cette nuance exige une approche fondamentalement différente à celle qu’on utiliserait avec un compilateur Borland ou un interpréteur Java. Par exemple, lors de la vérification de l’orthographe, un compilateur Borland permettrait de suspendre le programme lorsqu’une faute potentielle est trouvée et d’attendre la décision de l’utilisateur pour corriger ou non la faute. Cependant, avec Visual C++, si on veut exploiter les avantages que procurent les boîtes de dialogue, on doit se prendre d’une autre façon pour signaler la faute potentielle. Puisque l’approche est dirigée par les événements, on doit parcourir le document, sauvegarder la position d’une faute potentielle le cas échéant, mettre fin à la lecture et afficher la boîte de dialogue avec les informations correspondantes. L’application devient alors idle en attente d’un événement. Si l’usager décide d’ignorer la faute, l’application reprend la lecture à partir de la position laissée et ainsi de suite.
Afin que vous puissiez bien concevoir cette nuance, imaginez que si on adoptait la même approche avec Visual C++ qu’avec Borland C++, seulement la dernière faute potentielle trouvée serait affichée. Puisque chaque faute génère la même boîte de dialogue, chaque nouvelle faute viendra nécessairement écraser les informations de la dernière et ainsi de suite.
III-2. Le recyclage de code existant
En second lieu, le recyclage de code existant provient d’extraits de code écrit en C, en C++ et en JAVA. Le code écrit en C doit être traduit du procédural à l’orienté objet afin de conserver la structure déjà en place avec les classes MFC. Le code C++ peut être intégré au projet avec très peu de modifications. On doit notamment supprimer tous les appels de type cout et cin car l’interaction personne-ordinateur se fera maintenant via l’interface graphique (GUI). Pour ce qui est du code JAVA, on doit traduire tous les identificateurs, types et méthodes qui sont propres à ce langage en recherchant leur équivalent en C++ et en effectuant les modifications requises. On doit ensuite s’assurer que toutes les classes créées, traduites ou importées puissent vivre en harmonie. L’approche du développement basée sur la règle "une seule modification à la fois" est la plus importante pour ce point et doit être respectée rigoureusement. Cette stratégie nous permet de nous assurer de la validité de chaque modification, sans avoir à déboguer pendant des heures.
On doit aussi s’assurer que le nom de nos classes personnelles n’entre pas en conflit avec le nom d’une classe MFC existante. Également, il faut s’assurer que nos classes n’utilisent pas des noms de fonctions qui entrent en conflit avec une les nombreuses macros de l’API de Windows. Dans ce cas, au lieu que notre fonction ou notre classe occulte la classe ou la macro prédéfinie, le compilateur génère une erreur abstraite qui rend le débogage relativement difficile. On pourrait cependant faire appel à la fonction browse du compilateur afin de retracer la source du conflit.
III-3. La mise en oeuvre élégante
En troisième lieu, on doit mettre en oeuvre de façon élégante les outils d’analyse lexicale. Ceci implique de décomposer le module d’analyse lexicale (Speller) en différentes classes. Ceci permet de créer des objets «spécialisés», et de transférer le maximum de responsabilité vers les objets eux-mêmes. Chaque objet peut alors gérer ses propres entrées et sorties et ses propres cas limites. Des classes dérivées peuvent ensuite venir étendre la gamme de fonctions offertes par une classe de base afin d’adapter son fonctionnement au contexte du projet courant.
Par exemple, la classe noeudAVL a été conçue pour définir le conteneur d’un mot en mémoire. La classe AVL a été conçue pour servir d’arbre binaire de recherche. Elle manipule des objets de type noeudAVL. La classe ensemble a été conçue afin de représenter un dictionnaire. Elle fait abstraction à l’arbre binaire de recherche et apporte des fonctions de type ensembliste tels que l’union de deux ensembles (ou dictionnaires), la vérification si un objet est élément d’un ensemble, la vérification si un ensemble est vide, etc.. La classe itAvl a été conçue afin de servir de sélecteur de noeudAVL dans un AVL . Un itérateur est un type d’objet qui permet d’accéder à un élément particulier d’un autre objet de type conteneur.
Une classe pile a été conçue afin de rendre un objet de type itAvl plus performant. On y reviendra dans la section performance de ce rapport. La classe DifferenceDeuxMots est une classe développée par d’anciens étudiants qui a été portée du Java au C++. Elle sert dans ce projet à encapsuler les fonctions nécessaires pour suggérer des mots ayant une forte corrélation avec une faute potentielle trouvée dans un document se faisant analysé. Enfin, la classe CSpeller joue le rôle d’un chef d’orchestre. Elle a été conçue afin de gérer l’interaction de tous les éléments servant à faire la vérification de l’orthographe.
III-4. La suggestion de mots pertinents
La suggestion de mots pertinents qui ont une forte corrélation avec un autre mot est encore, à ce jour, une science inexacte. Même les logiciels de traitement de texte les plus récents sur le marché n’ont pas perfectionné cet aspect. La raison de cette défaillance est reliée au fait que les machines ne peuvent connaître toutes les subtilités d’une langue que si ces subtilités sont définies dans le programme. Le logiciel peut prendre en considération les différences au niveau de la longueur des mots, des caractères qui diffèrent, de l’ordre des lettres, des caractères inversés, de la casse , des accents, etc.. Certains logiciels peuvent également prendre en considération la position des touches sur un clavier, les mots ayant des ressemblances au niveau phonétique, des fautes les plus courantes des humains, des fautes les plus courantes de l’usager, etc..
Il est inutile à dire que le prix à payer pour de tels systèmes est celui de la performance. Le plus un dictionnaire contient de mots, le plus probable il devient de trouver le bon mot mais par conséquent un temps de traitement plus important est requis. Dans ce projet, on tient uniquement compte de la longueur des mots comparés, du nombre de caractères qui diffèrent et du nombre de caractères dont l’ordre a été inversé. Cette décision a été prise à la suite de multiples scénarios de tests qui tiennent compte du nombre de suggestions, leur pertinence ainsi que le temps de traitement. Le produit final a été jugé acceptable par le concepteur.
III-5. Le choix d’une structure de données efficace
En dernier lieu, la question fondamentale de ce projet est celle de la structure de données à choisir pour le dictionnaire. Les options les plus évidentes sont la structure linéaire ou la structure non-linéaire. Des tests de performance ont alors été réalisés afin de comparer la performance d’un tableau dynamique avec un arbre binaire. Bien sûr on pourrait considérer les listes chaînées, les skip lists, les tables creuses, les arbres n-aires ou même l’accès direct au fichier source qui contient le dictionnaire. Cependant, le concepteur a jugé que le tableau dynamique et l’AVL servirait d’échantillon raisonnablement représentatif.
La problématique de ce dilemme vient du fait que le nombre de mots du dictionnaire est arbitraire et par conséquent la structure de données n’est pas fixe. Elle peut être appelée à être modifiée dans le cas de l’ajout subséquente d’un mot. On doit alors considérer la performance de tous les événements potentiels qui agiront sur la structure de données. Parmi ceux-ci on retrouve notamment l’insertion initiale, la recherche, le parcours séquentiel, le tri et l’ajout. Dans la section qui suit, on retrouve une analyse plus détaillée des deux structures du point de vue de la performance. Le choix de la structure à utiliser repose sur les résultats de cette analyse.
Il est clair que si la recherche et le tri des données ne seraient pas nécessaires, le tableau dynamique serait de loin le meilleur choix. Celui-ci a un temps d’insertion qui est constant, c’est-à-dire toujours le même et ultra-rapide : O(1). Même le chargement de 1,000,000 mots serait quasi-transparent sur un système moderne. Cette observation ainsi que la comparaison implicite qu’elle véhicule nous est cependant totalement inutile puisque dans le contexte du dictionnaire, nous aurons à effectuer multiples recherches et possiblement insérer de nouveaux mots.
IV-1. Les tableaux dynamiques ordonnés
Afin de comparer des pommes avec des pommes, considérons le cas d’un tableau ordonné. Une fois le tri effectué, la recherche dans le dictionnaire pourrait se faire de façon assez optimale avec l’algorithme de la recherche dichotomique. Le temps de recherche serait alors de O(lg n). Cependant, le temps d’insertion dans un tableau ordonné se ferait en un temps maximal de O(n). Ceci veut dire que si la valeur à insérer est 10 (n=10), on devra parcourir tous les éléments précédents 10 ainsi que son suivant afin de connaître la position où l’élément devra être inséré. Dans le pire scénario, (puisqu’il s’agit du temps maximal) il y aura 9 éléments avant 10 et 1 après 10. On peut alors concevoir le coût énorme qui résulterait d’une insertion de la valeur 1,000,000 dans un tableau avec 999,999 éléments. Alors, pour fins de comparaison, l’efficacité à surpasser pour le cas du tableau dynamique ordonné est celui de O(lg n) pour la recherche et O(n) pour l’insertion.
IV-2. Les arbre AVL
Si on prend maintenant le cas d’un AVL. Les arbres binaires de recherche sont des arbres spécialement organisés pour les recherches. Ils sont efficaces car ils limitent la complexité de l’insertion et de la recherche à une opération en O(lg n) où n est le nombre de noeuds de l’arbre, pourvu que celui-ci reste équilibré. Cependant, comme un arbre AVL n’est qu’approximativement équilibré (indice d’équilibre entre -1 et 1), on pourrait se demander en quoi cela affecte les performances : il se trouve que le temps d’exécution d’une insertion dans un arbre AVL, dans le pire des cas est T(n) = 1.5k lg n, où k est une constante et n le nombre de noeuds de l’arbre, et que T(n) = k lg n est le temps d’insertion dans un arbre binaire parfaitement équilibré. Tout comme l’insertion dans un arbre parfaitement équilibré, cela donne une complexité d’exécution de O(lg n); cependant, en pratique, la constante de 1.5 influe sur les performances.
Si on reste fidèle à notre objectif de comparaison, on voit alors que, constante de 1.5 présente où non, les arbres AVL sont plus performants que les tableaux dynamiques ordonnés du fait que l’insertion est d’une complexité d’exécution de O(lg n) vs O(n). Cette différence est encore plus significative avec un n assez grand.
IV-3. L’amélioration de la performance des AVL
Certaines mesures ont été prises et d’autres devront l’être pour améliorer davantage la performance de l’AVL servant pour le dictionnaire. En premier lieu, afin d’accélérer le chargement du dictionnaire, le dictionnaire doit être formaté afin de charger l’AVL avec le moins d’équilibrage possible. Le dictionnaire doit donc insérer la racine en premier lieu ainsi qu’insérer une alternance répétée d’éléments de chaque côté de la racine. Ceci a pour effet de diminuer le nombre de rotations nécessaires pour charger le dictionnaire et par conséquent faire diminuer le temps de traitement total. Cette mesure n’a pas été incorporée. Des comparaisons au niveau du chargement en inordre et en préordre ont été effectuées mais aucune option ne s’est avérée assez performante pour traiter un nombre important de valeurs.
En second lieu, on a les itérateurs d’arbres. Les itérateurs ont été utilisés pour accélérer le temps d’accès au noeud suivant de O(lg n) à O(1) en moyenne. Cette action est réalisée en conservant dans une pile le chemin qui va de la racine au noeud courant en ne conservant que les noeuds pour lesquels il faut aller vers la branche de gauche. Pour déterminer le suivant, on passe au noeud de droite s’il existe, ou bien on prend le premier élément de la pile.
La classe itérateur d’arbre est représentée par trois objets principaux : une référence constante à l’arbre concerné, un pointeur sur le noeud courant de cet itérateur et une pile de pointeurs vers des noeuds dans l’arbre. Alors chaque fois que l’on veut traverser k noeuds, on est certain qu’au moins k prochains seront accessibles en O(1). En fait, on aura vraisemblablement accès à plus de k noeuds puisque la plupart de ceux-ci auront un enfant de droite qui sera aussi accessible en O(1). C’est pour cette raison qu’on dit O(1) en moyenne.
On a vu dans la section précédente que les itérateurs peuvent être utilisés afin d’accélérer l’accès au noeud suivant. Cependant, le rôle principal des itérateurs est d’installer une enveloppe de robustesse autour des pointeurs de façon à les rendre aussi sécuritaire que possible. Le passage de paramètres est également toujours fait par référence constante lorsque la situation le permet afin de réduire l’occurrence d’erreurs potentielles.
V-2. L’approche de la coquille
L’approche de la coquille a été utilisée afin de réduire le nombre de fonctions publiques qui manipulent des pointeurs. Cette approche consiste à coder une version publique et une version protégée d’une fonction. Dans la partie publique de la classe, on code une version de la fonction sans pointeurs. Cette fonction appelle à son tour la version protégée qui s’occupe de gérer les pointeurs correspondants. La version publique n’a qu’à savoir si la fonction a réussie ou échouée.
Prenons par exemple la fonction enlever de la classe AVL. La version publique reçoit uniquement le mot à enlever comme argument. La fonction publique appelle à son tour la version protégée avec la référence au noeud correspondant. Celle-ci retourne une valeur booléenne qui informe la version publique du résultat de l’action.
V-3. Les assertions
Des assertions ont aussi été insérées dans le code afin d’assurer la véracité de certaines conditions qui, si violées, pourraient corrompre le système ou causer des accès mémoire illégaux.
Ces applications pratiques ne sont définitivement pas en manque dans le domaine du génie logiciel. De nouveaux besoins en matière de logiciels font surface à chaque jour. On remarque des améliorations significatives dans le domaine du traitement de texte telles que l’entrée de données par l’entremise de la voix ou la reconnaissance de lettres manuscrites. Le domaine de l’intelligence artificielle est également en évolution. On voit apparaître des systèmes experts de plus en plus intelligents pour automatiser des tâches quotidiennes.
Il sera alors très intéressant de suivre la progression de la science qui permettra d’automatiser la traduction de documents, d’effectuer la vérification de la grammaire et bien sûr, la correction exacte de l’orthographe. Ce projet aura donc permis de me sensibiliser aux subtilités du problème et de comprendre un peu plus, pourquoi les solutions en place sont toujours à ce jour imparfaites.
Marc Laframboise.
Le 27 avril, 2001
Un grand merci aussi à M. Danny Thibaudeau pour ses nombreux conseils et pour son intuition infaillible en matière de débogage en Visual C++.
Enfin, j’aimerais remercier l’Université du Québec à Hull pour sa qualité de formation ainsi que pour la priorité inégalée qu’elle accorde aux besoins de ses étudiants.
2. Irvine, Kip R., "C++ And Object-Oriented Programming", Prentice Hall, 1997
3. Sommerville, Ian, "Software Engineering", Fourth Edition, Addison-Wesley, 1994
4. Loudon, Kyle, "Maîtrise des algorithmes en C", Édition française, O’Reilly, 2000
5. "MSDN On-line", Microsoft, 1997