Implémentation d'un dictionnaire DAWG en C#

Télécharger le projet
Commenter

Description


Origine du projet

Après avoir été relecteur du tutoriel de CarlVB sur le format de compression DAWG, je m'étais promis d'en faire une implémentation en C#.
Il y a quelques semaines que cela m'a repris.

Adaptation à la programmation Objet

Je voulais trouver une adaptation des algorithmes présentés afin d'obtenir une "vraie" structure en graphe au lieu d'un tableau.
Cela est possible en créant deux types personnalisés, les Noeuds et les Arcs qui les relient.
Au final, tout le dictionnaire est contenu dans un seul Noeud, le premier.
Une liste (privée) de l'ensemble des Noeuds est chargée dans la classe dictionnaire, elle est indispensable à la construction et évite de parcourir le graphe lors de l'écriture du fichier de sortie.
 

Utilisation de Linq

 
Grâce à Linq, l'adaptation de la méthode en 2 temps permet une compression aussi efficace que celle en un temps décrite par Carl, à savoir 43099 noeuds.
Mais lors des premières tentatives, la construction était particulièrement longue, jusqu'à plus de 18 minutes.
 

Introduction d'une nouvelle notion

 
La meilleure solution que j'ai trouvée pour réduire cette durée à une minute environ a été d'introduire la notion de Rang.
Il s'agit d'une "quasi-équivalence" permetant un pré-tri de l'ensemble des noueds issus de l'arbre construit pendant la première étape.
Ce pré-tri est réalisé par une réquête GroupBy
 

Et la construcion en 1 temps?

 
Je ne l'ai pas implémentée, en effet, l'algorithme présenté reste assez simple, rapide d'exécution et compresse au mieux le dictionnaire.

Présentation de la solution

Elle comporte deux projets:
  • une librairie qui pourra être utilisée telle quelle ou allégée des tests de vérification de chaque étape.
  • un Winform de test, dont voici une capture d'écran en mode Debug (c'est un petit peu plus rapide en mode Release),

Est-ce utile?

On constate que le fichier ASCII se charge en 1,5 seconde environ.
Le fichier Dawg se charge en 0,6 seconde. Ce petit gain de temps ne justifie pas forcément une construction (unique toutefois) d'une minute.
La taille du fichier est réduite de 4500ko à 630ko, mais là encore, avec les capacités de stockage actuelles, qu'est-ce que 4,5Mo?
La vérification d'un mot dans la liste par Contains ou Any est sensiblement de même durée que la recherche dans le graphe.

Cependant la structure en graphe donne un avantage lors de recherche dans des grilles de lettres pour des jeux type Boogle, Mots Mélés, Lettro etc....

Conclusion

Ce défis m'a permis de trouver une nouvelle méthode de compression, au meilleur taux, en utilisant les outils performant de la framework .Net.

Améliorations possibles

L'utilisation d'un pool de thread pour la réduction de l'arbre pourait permettre de réduire le temps de construction.
Télécharger le projet

Codes Sources

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (Whismeril)