------------------------------------------------------------------------------- 0. Utilisation ------------------------------------------------------------------------------- > make Créer les executables TextMiningApp et TextMiningCompiler ------------------------------------------------------------------------------- > make check Tester l'implémentation face à la référence Requiert: - Mettre la ref dans ref/TextMining* - Mettre le dictionnaire dans dict/words.txt ------------------------------------------------------------------------------- > make coffee Compiler le code coffeescript vers Javascript. Il est utilisable via js/TextMining* Requiert: - Nodejs: https://github.com/joyent/node/wiki/Installation ------------------------------------------------------------------------------- > make clean Remettre le dossier dans l'état d'origine ------------------------------------------------------------------------------- 1. Decrivez les choix de design de votre programme ------------------------------------------------------------------------------- Dans un premier temps, nous avons codé une version en CoffeeScript (qui cible le Javascript) afin d'avoir rapidement un code fonctionnel. Plusieurs problèmes d'optimisations ont vu le jour : - JSON.stringify n'a pas été pensé pour des données volumineuses. Le système n'arrive pas à construire la chaîne de caractères correspondante à cause d'espace mémoire insuffisant. - Afin d'optimiser l'empreinte mémoire, et ainsi les accès au cache, notre structure de trie est extrêmement compressée. Javascript ne possède pas (encore) de primitives pour accéder efficacement à des parties d'un int32. Ainsi, nous sommes passés sur une implémentation en C++. ------------------------------------------------------------------------------- 2. Listez l’ensemble des tests effectués sur votre programme (en plus des units tests) ------------------------------------------------------------------------------- - 400 erreurs les plus fréquentes en anglais. - 1800 mots français. ------------------------------------------------------------------------------- 3. Avez-vous détecté des cas où la correction par distance ne fonctionnait pas (même avec une distance élevée) ? ------------------------------------------------------------------------------- Non. ------------------------------------------------------------------------------- 4. Quelle est la structure de données que vous avez implémentée dans votre projet, pourquoi ? ------------------------------------------------------------------------------- Notre structure de données est un Trie. On a vu en cours que c'était la structure la plus adaptée pour faire une recherche approximative. Afin de gagner en performance, nous avons décidé de stocker cette structure de la façon la plus concise possible. - Nous ne stockons que les transitions - Chaque transition est stockée sur 64 bits - L'ensemble des transitions d'un noeud est écrit de façon contigue en mémoire avec le champ is_last_child à 1 pour la dernière. - Les noeuds terminaux sont des transitions avec le champ is_final à 1. // Node structure unsigned short is_final : 1; unsigned short is_last_child : 1; ------------ Liens ------------ L'alphabet du dictionnaire d'entrée comporte moins de 64 lettres, ainsi il est possible de stocker la lettre sur 6 bits. Des transformations vont être effectuées pour transformer les numéros ASCII des caractères de [0-255] à [0-63]. Le dictionnaire sous forme de trie comporte plus de 3 millions de transitions. Ainsi nous utilisons 24 bits pour stocker le pointeur vers le noeud suivant. // Specific values for Links unsigned short letter : 6; unsigned int next : 24; -------------- Terminaisons -------------- Lorsqu'un noeud est terminal, nous devons stocker l'information de fréquence du mot. La valeur maximale de ces fréquences est de 2^31 - 1, or nous n'avons que 30 bits de disponibles. Nous allons donc encoder directement toutes les fréquences encodables sur 29 bits. Les fréquences supplémentaires vont être stockées au début du fichier et le champ freq va être l'indice vers la fréquence correspondante. // Specific values for Terminals unsigned short is_overflow : 1; unsigned int freq : 29; ----------------- Taille des fils ----------------- On peut faire un constat simple, si l'on cherche un mot de taille n avec une distance de 1. Tous les mots trouvés vont être de taille n - 1, n ou n + 1. Il est donc inutile de chercher dans tous les sous arbres qui ne contiennent pas de mots de cette taille. La première méthode consiste à créer un trie par taille de mot. Cela n'a pas été concluant. En effet, le dictionnaire est beaucoup plus gros du fait de la réduction de compression. L'autre méthode est d'encoder dans chaque lien les différentes tailles de mots auxquels il mène. Grâce à 32 bits supplémentaires par noeud, nous pouvons marquer 32 tailles de mots différentes. Il suffit ensuite de faire un OU logique avec les tailles de mots recherchées pour prendre, ou non, un lien. // Bitfield for children sizes unsigned int sizes : 32; ------------------------------------------------------------------------------- 5. Proposez un réglage automatique de la distance pour un programme qui prend juste une chaîne de caractères en entrée, donner le processus d’évaluation ainsi que les résultats ------------------------------------------------------------------------------- Un cas d'utilisation est de chercher les n plus proches voisins d'un mot. Pour ce faire, on peut lancer une recherche avec une distance 1, puis 2, puis 3 ... jusqu'à trouver n résultats cummulés. On peut aussi imaginer le faire en une seule passe en réduisant la distance au fur et à mesure que l'on trouve des résultats. ------------------------------------------------------------------------------- 6. Comment comptez vous améliorer les performances de votre programme ------------------------------------------------------------------------------- Il est possible de faire une implémentation qui tire parti d'une architecture multi-processeurs. On pourrait réécrire la boucle de recherche en assembleur afin d'optimiser à la main l'utilisation des registres et le nombre d'instructions. ------------------------------------------------------------------------------- 7. Que manque-t-il à votre correcteur orthographique pour qu’il soit à l’état de l’art ? ------------------------------------------------------------------------------- La fonction de distance actuelle donne la même importance à toutes les insertions, suppressions et échanges. Ce n'est pas le cas en pratique. Il faut rajouter des poids à toutes ces transformations en fonction des lettres. Tous les résultats avec une même distance sont indissociables. Il est possible de rajouter du contexte dans lequel le correcteur orthographique fonctionne pour pouvoir les trier.