Tout d'abord, regardons les contraintes du problème. Vous souhaitez stocker une liste de mots pour un jeu dans une structure de données qui prend efficacement en charge le problème "anagramme". Autrement dit, étant donné un "rack" de n lettres, quels sont tous les mots de n lettres ou moins dans la liste de mots qui peuvent être créés à partir de ce rack. la liste de mots sera d'environ 400 000 mots, et donc probablement d'environ un à dix Mo de données de chaîne lorsqu'elles ne sont pas compressées.
Un trie est la structure de données classique utilisée pour résoudre ce problème car il combine à la fois l'efficacité de la mémoire et l'efficacité de la recherche. Avec une liste de mots d'environ 400 000 mots de longueur raisonnable, vous devriez pouvoir conserver le trie en mémoire. (Par opposition à une solution de type b-tree où vous conservez la majeure partie de l'arborescence sur le disque car elle est trop grande pour tenir en mémoire en une seule fois.)
Un trie n'est fondamentalement rien de plus qu'un arbre à 26 aires (en supposant que vous utilisez l'alphabet romain) où chaque nœud a une lettre et un bit supplémentaire sur chaque nœud qui indique s'il s'agit de la fin du mot.
Alors esquissons la structure des données :
class TrieNode
{
char Letter;
bool IsEndOfWord;
List<TrieNode> children;
}
Ce n'est bien sûr qu'un croquis; vous voudriez probablement que ceux-ci aient des accesseurs et des constructeurs de propriété appropriés et ainsi de suite. De plus, une liste plate n'est peut-être pas la meilleure structure de données ; peut-être qu'une sorte de dictionnaire est préférable. Mon conseil est de le faire fonctionner d'abord, puis de mesurer ses performances, et s'il est inacceptable, alors expérimentez en apportant des modifications pour améliorer ses performances.
Vous pouvez commencer avec un trie vide :
TrieNode root = new TrieNode('^', false, new List<TrieNode>());
C'est-à-dire qu'il s'agit du nœud "racine" du trie qui représente le début d'un mot.
Comment ajouter le mot "AA", le premier mot du dictionnaire Scrabble ? Eh bien, faites d'abord un nœud pour la première lettre :
root.Children.Add('A', false, new List<TrieNode>());
OK, notre essai est maintenant
^
|
A
Ajoutez maintenant un nœud pour la deuxième lettre :
root.Children[0].Children.Add(new trieNode('A', true, new List<TrieNode>()));
Notre essai est maintenant
^
|
A
|
A$ -- we notate the end of word flag with $
Génial. Supposons maintenant que nous voulions ajouter AB. Nous avons déjà un nœud pour "A", alors ajoutez-y le nœud "B$":
root.Children[0].Children.Add(new trieNode('B', true, new List<TrieNode>());
et maintenant nous avons
^
|
A
/ \
A$ B$
Continuez comme ça. Bien sûr, plutôt que d'écrire "root.Children[0]...", vous allez écrire une boucle qui recherche dans le trie pour voir si le nœud que vous voulez existe, et sinon, créez-le.
Pour stocker votre trie sur le disque - franchement, je stockerais simplement la liste de mots sous forme de fichier texte brut et je reconstruirais le trie lorsque vous en aurez besoin. Cela ne devrait pas prendre plus de 30 secondes environ, puis vous pourrez réutiliser le trie en mémoire. Si vous souhaitez stocker le trie dans un format qui ressemble plus à un trie, il ne devrait pas être difficile de trouver un format de sérialisation.
Pour rechercher le trie correspondant à un rack, l'idée est d'explorer chaque partie du trie, mais d'élaguer les zones où le rack ne peut pas correspondre. Si vous n'avez pas de "A" sur le rack, il n'est pas nécessaire de descendre dans un nœud "A". J'ai esquissé l'algorithme de recherche dans votre question précédente.
J'ai une implémentation d'un essai persistant de style fonctionnel sur lequel je voulais bloguer depuis un moment, mais je n'y suis jamais parvenu. Si je publie finalement cela, je mettrai à jour cette question.
