Implémentation d'un dictionnaire DAWG en C#

Soyez le premier à donner votre avis sur cette source.

Vue 3 629 fois - Téléchargée 811 fois

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.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
199
Date d'inscription
mercredi 23 avril 2003
Statut
Contributeur
Dernière intervention
25 mai 2017
7
Salut Whis,

Bravo pour ce projet et merci à toi et à vb95 de faire vivre le DAWG, là où j'ai complètement décroché.

Bonne continuation,

Amicalement,

Carl
Messages postés
14466
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
6 juillet 2020
420 >
Messages postés
199
Date d'inscription
mercredi 23 avril 2003
Statut
Contributeur
Dernière intervention
25 mai 2017

Merci Carl
Messages postés
2166
Date d'inscription
samedi 11 janvier 2014
Statut
Contributeur
Dernière intervention
1 juillet 2020
109 >
Messages postés
14466
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
6 juillet 2020

De rien carlvb !
ton Scrabble a de beaux jours devant lui ! Et tout cela grâce à toi
Amitiés
Messages postés
2166
Date d'inscription
samedi 11 janvier 2014
Statut
Contributeur
Dernière intervention
1 juillet 2020
109
Salut Whismeril
j'ai testé
un seul mot ! BRAVO
mais je ne m'y ferais jamais avec les classes que ce soir en VB et encore moins en c# . Et j'ai du mal aussi à comprendre le code ( pourquoi j'ai appris VB à la base et non le C )
bon weekend à toi
Messages postés
14466
Date d'inscription
mardi 11 mars 2003
Statut
Contributeur
Dernière intervention
6 juillet 2020
420 >
Messages postés
2166
Date d'inscription
samedi 11 janvier 2014
Statut
Contributeur
Dernière intervention
1 juillet 2020

Bonjour, merci.
Je pourrais passer tout ça dans un traducteur VB.Net, mais j'ai appelé de nombreuses variables pareil, avec juste la casse différente.
Vb n'aime pas , et le traducteur renomme bizarrement.

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.