DawgSharp
1.0.0
[Package NuGet] [Obtenir une licence commerciale]
DAWG (Directed Acyclic Word Graph) est une structure de données permettant de stocker et de rechercher de grandes listes de mots et des dictionnaires. Elle peut être 40 fois plus efficace que la classe .NET Dictionary pour certains types de données.
À titre d'exemple, mon site Web héberge un dictionnaire de 2 millions de mots qui occupait 56 Mo sur le disque et prenait 7 secondes à charger (lors de l'utilisation de Dictionary et BinarySerializer). Après le passage à DAWG, il faut désormais 1,4 Mo sur le disque et 0,3 seconde pour le chargement.
Comment est-ce possible ? Pourquoi le dictionnaire standard n'est-il pas aussi intelligent que DAWG ? Le fait est que DAWG fonctionne bien avec les chaînes en langage naturel et peut ne pas fonctionner aussi bien avec les chaînes générées telles que les clés de licence (OIN1r4Be2su+UXSeOj0TaQ). Les mots du langage humain ont tendance à avoir de nombreuses séquences de lettres communes, par exemple -ilité en capacité , possibilité , agilité , etc. et l'algorithme en profite en trouvant ces séquences et en les stockant une seule fois pour plusieurs mots. DAWG s'est également révélé utile pour représenter les données ADN (séquences de gènes). L'histoire du DAWG remonte à 1985. Pour plus d'informations, recherchez sur Google DAWG ou DAFSA (Deterministic Acyclic Finite State Automaton).
DawgSharp est une implémentation de DAWG, une parmi tant d'autres. Qu’est-ce qui le rend spécial ?
Load/Save pour écrire les données sur le disque et les relire.Dans cet exemple, nous allons simuler un scénario d'utilisation impliquant deux programmes, l'un pour générer le dictionnaire et l'écrire sur le disque et l'autre pour charger ce fichier et utiliser le dictionnaire en lecture seule pour les recherches.
Obtenez d’abord le code en clonant ce référentiel ou en installant le package NuGet.
Créez et remplissez un objet DawgBuilder :
var words = new [ ] { " Aaron " , " abacus " , " abashed " } ;
var dawgBuilder = new DawgBuilder < bool > ( ) ; // <bool> is the value type.
// Key type is always string.
foreach ( string key in words )
{
dawgBuilder . Insert ( key , true ) ;
} (Vous pouvez également faire var dawgBuilder = words.ToDawgBuilder(key => key, _ => true); )
Appelez BuildDawg dessus pour obtenir la version compressée et enregistrez-la sur le disque :
Dawg < bool > dawg = dawgBuilder . BuildDawg ( ) ;
// Computer is working. Please wait ...
using ( var file = File . Create ( " DAWG.bin " ) )
dawg . SaveTo ( file ) ;Relisez maintenant le fichier et vérifiez si un mot particulier se trouve dans le dictionnaire :
var dawg = Dawg < bool > . Load ( File . Open ( " DAWG.bin " ) ) ;
if ( dawg [ " chihuahua " ] )
{
Console . WriteLine ( " Word is found. " ) ;
} Les classes Dawg et DawgBuilder prennent un paramètre de modèle appelé <TPayload> . Cela peut être n’importe quel type que vous voulez. Juste pour pouvoir tester si un mot est dans le dictionnaire, un bool suffit. Vous pouvez également en faire un int , une string ou une classe personnalisée. Mais méfiez-vous d’une limitation importante. DAWG ne fonctionne bien que lorsque l'ensemble de valeurs que TPayload peut prendre est relativement petit. Plus c’est petit, mieux c’est. Par exemple, si vous ajoutez une définition pour chaque mot, cela rendra chaque entrée unique et votre graphique deviendra un arbre (ce qui n'est peut-être pas trop mal !).
Un autre aspect intéressant de DAWG est sa capacité à récupérer efficacement tous les mots commençant par une sous-chaîne particulière :
dawg . MatchPrefix ( " awe " ) La requête ci-dessus renverra un IEnumerable<KeyValuePair> qui peut contenir des clés telles que awe, aweful et Awesome . L'appel dawg.MatchPrefix("") renverra tous les éléments du dictionnaire.
Si vous devez plutôt rechercher par suffixe, il n’existe pas de méthode MatchSuffix. Mais l’effet souhaité peut être obtenu en ajoutant les clés inversées puis en utilisant MatchPrefix() sur les clés inversées :
dawgBuilder . Insert ( " ability " . Reverse ( ) , true ) ;
.. .
dawg . MatchPrefix ( " ility " . Reverse ( ) ) GetPrefixes() renvoie tous les éléments du dictionnaire dont les clés sont des sous-chaînes d'une chaîne donnée. Par exemple:
dawg . GetPrefixes ( " awesomenesses " )Pourrait renvoyer des clés telles que crainte, génial, génialité et enfin génialités .
Une autre fonctionnalité intéressante est la méthode int GetLongestCommonPrefixLength(IEnumerable<char> word) . Si word est trouvé dans le dictionnaire, il renverra sa longueur ; sinon, il renverra la longueur du mot le plus long trouvé dans le dictionnaire et qui est également le début du mot donné. Par exemple, si prepare est dans le dictionnaire mais que preempt ne l'est pas, alors dawg.GetLongestCommonPrefixLength("preempt") renverra 3 qui est la longueur de "pre".
La classe DawgBuilder n'est pas thread-safe et ne doit être accessible que par un seul thread à un moment donné.
La classe Dawg est immuable et donc thread-safe.
La classe MultiDawg peut stocker plusieurs valeurs sur une seule clé de chaîne de manière très efficace en termes de mémoire.
L'API a été conçue pour s'adapter à un scénario d'utilisation particulier (voir ci-dessus) et peut être étendue pour prendre en charge d'autres scénarios, par exemple en pouvant ajouter de nouveaux mots au dictionnaire une fois celui-ci compacté. Je n’en avais tout simplement pas besoin, donc ce n’est pas implémenté. Vous n'aurez aucune exception. Il n'y a tout simplement pas de méthode Insert sur la classe Dawg .
Implémentez l'interface IDictionary sur DawgBuilder et Dawg (#5).
DawgSharp est sous licence GPLv3, ce qui signifie qu'il peut être utilisé gratuitement dans des projets open source. Lire la licence complète
Si vous souhaitez utiliser DawgSharp dans un projet propriétaire, veuillez acheter une licence commerciale sur http://morpher.co.uk.
