La structure de données de Trie : un joyau négligé

Dès les premiers jours de notre vie de programmeurs, nous avons tous eu affaire à des structures de données : les tableaux, les listes chaînées, les arbres, les ensembles, les piles et les files d'attente sont nos compagnons de tous les jours, et le programmeur expérimenté sait quand et pourquoi les utiliser. Dans cet article, nous verrons comment une structure de données souvent négligée, le trie , brille vraiment dans des domaines d'application avec des fonctionnalités spécifiques, comme les jeux de mots.

Jeux de mots à titre d'exemple

Pour commencer, considérons un jeu de mots simple : trouvez tous les mots valides dans un tableau de lettres 4x4, en reliant les lettres adjacentes horizontalement, verticalement ou en diagonale. Par exemple, dans le tableau suivant, nous voyons les lettres 'W', 'A', 'I' et 'T' se connecter pour former le mot "WAIT".

La solution naïve pour trouver tous les mots valides serait d'explorer le tableau en commençant par le coin supérieur gauche, puis en déplaçant la profondeur d'abord vers des séquences plus longues, en recommençant à partir de la deuxième lettre de la première rangée, et ainsi de suite. Dans un plateau 4x4, permettant des déplacements verticaux, horizontaux et diagonaux, il y a 12029640 séquences, dont la longueur varie de un à seize caractères.

Maintenant, notre objectif est de trouver la meilleure structure de données pour implémenter ce vérificateur de mots valides, c'est-à-dire notre vocabulaire. Quelques points à garder à l'esprit :

• Nous n'avons besoin que d'un seul exemplaire de chaque mot, c'est-à-dire que notre vocabulaire est un ensemble, d'un point de vue logique.
• Nous devons répondre aux questions suivantes pour un mot donné :
  • La séquence de caractères actuelle comprend-elle un mot valide ?
  • Y a-t-il des mots plus longs qui commencent par cette séquence ? Sinon, nous pouvons abandonner notre première exploration en profondeur, car aller plus loin ne donnera aucun mot valable.

Pour illustrer le second point, considérons le tableau suivant : Il ne sert à rien d'explorer les coups suivants, puisqu'il n'y a pas de mots dans le dictionnaire qui commencent par « ASF ».

Nous aimerions que notre structure de données réponde à ces questions le plus rapidement possible. ~O(1) temps d'accès (pour vérifier une séquence) serait idéal !

Nous pouvons définir l'interface Vocabulary comme ceci (voir ici pour le dépôt GitHub):

 public interface Vocabulary { boolean add(String word); boolean isPrefix(String prefix); boolean contains(String word); }

Trie Data Structure vs Alternatives

L'implémentation de la méthode contains() nécessite une structure de données de sauvegarde qui vous permet de trouver des éléments efficacement, tandis que la méthode isPrefix() nous oblige à trouver «l'élément supérieur suivant», c'est-à-dire que nous devons conserver le vocabulaire trié d'une manière ou d'une autre.

Nous pouvons facilement exclure les ensembles basés sur le hachage de notre liste de candidats : alors qu'une telle structure nous donnerait une vérification en temps constant pour contains() , elle fonctionnerait assez mal sur isPrefix() , dans le pire des cas nécessitant que nous analysions l'ensemble ensemble.

Pour une raison tout à fait opposée, nous pouvons également exclure les listes liées triées, car elles nécessitent de parcourir la liste au moins jusqu'au premier élément supérieur ou égal au mot ou au préfixe recherché.

Deux options valides utilisent une liste triée basée sur un tableau ou un arbre binaire.
Sur la liste triée basée sur un tableau, nous pouvons utiliser la recherche binaire pour trouver la séquence actuelle si elle est présente ou l'élément supérieur suivant à un coût de O(log2(n)) , où n est le nombre de mots dans le dictionnaire.

Nous pouvons implémenter un vocabulaire basé sur un tableau qui maintient toujours l'ordre de comme celui-ci, en utilisant les standards java.util.ArrayList et java.util.Collections.binarySeach :

 public class ListVocabulary implements Vocabulary { private List<String> words = new ArrayList<String>(); /** * Constructor that adds all the words and then sorts the underlying list */ public ListVocabulary(Collection<String> words) { this.words.addAll(words); Collections.sort(this.words); } public boolean add(String word) { int pos = Collections.binarySearch(words, word); // pos > 0 means the word is already in the list. Insert only // if it's not there yet if (pos < 0) { words.add(-(pos+1), word); return true; } return false; } public boolean isPrefix(String prefix) { int pos = Collections.binarySearch(words, prefix) ; if (pos >= 0) { // The prefix is a word. Check the following word, because we are looking // for words that are longer than the prefix if (pos +1 < words.size()) { String nextWord = words.get(pos+1); return nextWord.startsWith(prefix); } return false; } pos = -(pos+1); // The prefix is not a word. Check where it would be inserted and get the next word. // If it starts with prefix, return true. if (pos == words.size()) { return false; } String nextWord = words.get(pos); return nextWord.startsWith(prefix); } public boolean contains(String word) { int pos = Collections.binarySearch(words, word); return pos >= 0; } }

Si nous décidions d'utiliser un arbre binaire, l'implémentation pourrait être encore plus courte et plus élégante (encore une fois, voici un lien vers le code) :

 public class TreeVocabulary extends TreeSet<String> implements Vocabulary { public TreeVocabulary(Collection<String> c) { super(c); } public boolean isPrefix(String prefix) { String nextWord = ceiling(prefix); if (nextWord == null) { return false; } if (nextWord.equals(prefix)) { Set<String> tail = tailSet(nextWord, false); if (tail.isEmpty()) { return false; } nextWord = tail.iterator().next(); } return nextWord.startsWith(prefix); } /** * There is a mismatch between the parameter types of vocabulary and TreeSet, so * force call to the upper-class method */ public boolean contains(String word) { return super.contains(word); } }

Dans les deux cas, nous pouvons nous attendre à des performances O(log n) pour chaque méthode d'accès ( contains() et isPrefix() ). En ce qui concerne les besoins en espace, l'implémentation basée sur un tableau et l'implémentation basée sur un arbre nécessitent O(n+M) où n est le nombre de mots dans le dictionnaire et M est la taille en octets du dictionnaire, c'est-à-dire la somme de la longueur de les chaînes du dictionnaire.

Applications Trie : Quand et pourquoi utiliser Tryes

Les performances logarithmiques et la mémoire linéaire ne sont pas mauvaises. Mais il y a quelques autres caractéristiques de notre domaine d'application qui peuvent nous conduire à de meilleures performances :

• Nous pouvons sans risque supposer que tous les mots sont en minuscules.
• Nous n'acceptons que les lettres az - pas de ponctuation, pas de trait d'union, pas d'accent, etc.
• Le dictionnaire contient de nombreuses formes fléchies : pluriels, verbes conjugués, mots composés (par exemple, maison -> femme de ménage). Par conséquent, de nombreux mots partagent le même radical .
• Les mots ont une longueur limitée. Par exemple, si nous travaillons sur un tableau 4x4, tous les mots de plus de 16 caractères peuvent être ignorés.

C'est là qu'intervient le trie (prononcé « essayer »). Mais qu'est -ce qu'un trie exactement ? Les essais sont des structures de données négligées, trouvées dans les livres mais rarement dans les bibliothèques standard.

Pour nous motiver, considérons d'abord l'enfant phare de l'informatique : l'arbre binaire. Maintenant, lorsque nous analysons les performances d'un arbre binaire et disons que l'opération x est O(log(n)) , nous parlons constamment de log base 2. Mais que se passerait-il si, au lieu d'un arbre binaire, nous utilisions un arbre ternaire, où chaque nœud a trois enfants (ou une distribution de trois). Ensuite, nous parlerions de base de journal 3. (C'est une amélioration des performances, mais seulement d'un facteur constant.) Essentiellement, nos arbres deviendraient plus larges mais plus courts, et nous pourrions effectuer moins de recherches car nous n'avons pas besoin de descendre tout à fait si profond.

Pour aller plus loin, et si nous avions un arbre avec une diffusion égale au nombre de valeurs possibles de notre type de données ?

C'est la motivation derrière le trie. Et comme vous l'avez peut-être deviné, un trie est bien un arbre, un arbre à trie pour ainsi dire !

Mais, contrairement à la plupart des arbres binaires que vous utiliseriez pour trier des chaînes, ceux qui stockeraient des mots entiers dans leurs nœuds, chaque nœud d'un trie contient un seul caractère (et même pas cela, comme nous le verrons bientôt) et a une diffusion maximale égale à la longueur de l'alphabet. Dans notre cas, la longueur de l'alphabet est de 26 ; donc les nœuds du trie ont une sortance maximale de 26. Et, alors qu'un arbre binaire équilibré a une profondeur log2(n) , la profondeur maximale du trie est égale à la longueur maximale d'un mot ! (Encore une fois, plus large mais plus court.)

Au sein d'un trie, les mots ayant le même radical (préfixe) partagent la zone mémoire qui correspond au radical.

Pour visualiser la différence, considérons un petit dictionnaire composé de cinq mots. Supposons que les lettres grecques indiquent des pointeurs et notez que dans le trie, les caractères rouges indiquent des nœuds contenant des mots valides .

Implémentation Java Trie

Comme nous le savons, dans l'arborescence, les pointeurs vers les éléments enfants sont généralement implémentés avec une variable gauche et droite, car la diffusion maximale est fixée à deux.

Dans un trie indexant un alphabet de 26 lettres, chaque nœud a 26 enfants possibles et donc 26 pointeurs possibles. Chaque nœud comporte ainsi un tableau de 26 (pointeurs vers) sous-arbres, où chaque valeur peut être nulle (s'il n'y a pas un tel enfant) ou un autre nœud.

Comment, alors, cherchons-nous un mot dans un essai ? Voici la méthode qui, étant donné un String s , identifiera le nœud qui correspond à la dernière lettre du mot, s'il existe dans l'arbre :

 public LowercaseTrieVocabulary getNode(String s) { LowercaseTrieVocabulary node = this; for (int i = 0; i < s.length(); i++) { int index = LOWERCASE.getIndex(s.charAt(i)); LowercaseTrieVocabulary child = node.children[index]; if (child == null) { // There is no such word return null; } node = child; } return node; }

La LOWERCASE.getIndex(s.charAt(i)) renvoie simplement la position du ième caractère dans l'alphabet. Sur le nœud renvoyé, un node de propriété booléenne indique que le nœud correspond à la dernière lettre d'un mot, c'est-à-dire une lettre marquée en rouge dans l'exemple précédent. Étant donné que chaque nœud conserve un compteur du nombre d'enfants, si ce compteur est positif, il y a des mots plus longs dans le dictionnaire qui ont la chaîne actuelle comme préfixe. Remarque : le nœud n'a pas vraiment besoin de conserver une référence au caractère auquel il correspond, car il est implicite dans sa position dans le trie.

Analyse des performances

Ce qui fait que la structure en trie fonctionne vraiment bien dans ces situations, c'est que le coût de la recherche d'un mot ou d'un préfixe est fixe et dépend uniquement du nombre de caractères du mot et non de la taille du vocabulaire.

Dans notre domaine spécifique, puisque nous avons des chaînes de 16 caractères au maximum, 16 étapes exactement sont nécessaires pour trouver un mot qui est dans le vocabulaire, alors que toute réponse négative, c'est-à-dire que le mot ou le préfixe n'est pas dans le trie, peut être obtenue en 16 étapes maximum également ! Considérant que nous avons précédemment ignoré la longueur de la chaîne lors du calcul de la complexité du temps d'exécution pour la liste triée basée sur le tableau et l'arbre, qui est caché dans les comparaisons de chaînes, nous pouvons également l'ignorer ici et déclarer en toute sécurité que la recherche est effectuée en temps O(1) .

Compte tenu des besoins en espace (et en se rappelant que nous avons indiqué par M la taille en octets du dictionnaire), le trie pourrait avoir M nœuds dans le pire des cas, si aucune chaîne ne partageait un préfixe. Mais puisque nous avons observé qu'il y a un haut degré de redondance dans le dictionnaire, il y a beaucoup de compression à faire. Le dictionnaire anglais utilisé dans l'exemple de code est de 935 017 octets et nécessite 250 264 nœuds, avec un taux de compression d'environ 73 %.

Cependant, malgré cela, même un trie compressé nécessitera généralement plus de mémoire qu'un arbre ou un tableau. En effet, pour chaque nœud, au moins 26 x sizeof(pointer) octets sont nécessaires, plus une surcharge pour l'objet et des attributs supplémentaires. Sur une machine 64 bits, chaque nœud nécessite plus de 200 octets, alors qu'un caractère de chaîne nécessite un seul octet, ou deux si l'on considère les chaînes UTF.

Essais et tests de performance

Alors, qu'en est-il des performances ? Les implémentations de vocabulaire ont été testées dans deux situations différentes : vérification de 20 000 000 chaînes aléatoires et recherche de tous les mots dans 15 000 tableaux générés aléatoirement à partir de la même liste de mots.

Quatre structures de données ont été analysées : une liste triée basée sur un tableau, un arbre binaire, le trie décrit ci-dessus et un trie utilisant des tableaux d'octets correspondant à l'index alphabétique des caractères eux-mêmes (une optimisation des performances mineure et facile à mettre en œuvre). Voici les résultats, en ms :

Le nombre moyen de coups effectués pour résoudre le tableau est de 2 188. Pour chaque mouvement, une recherche de mots et une recherche de préfixes sont effectuées, c'est-à-dire que pour vérifier tous les tableaux, plus de 32 millions de recherches de mots et 32 ​​millions de recherches de préfixes ont été effectuées. Remarque : ceux-ci pourraient être réalisés en une seule étape, je les ai gardés séparés pour plus de clarté dans l'exposition. Les compacter en une seule étape réduirait presque de moitié le temps de résolution des planches, et favoriserait probablement encore plus le trie.

Comme on peut le voir ci-dessus, la recherche de mots fonctionne mieux avec le trie même lors de l'utilisation de chaînes, et est encore plus rapide lors de l'utilisation d'index alphabétiques, ces derniers étant plus de deux fois plus rapides qu'un arbre binaire standard. La différence dans la résolution des tableaux est encore plus évidente, la solution rapide trie-alphabet-index étant plus de quatre fois plus rapide que la liste et l'arbre.

Emballer

Le trie est une structure de données très spécialisée qui nécessite beaucoup plus de mémoire que les arbres et les listes. Cependant, lorsque des caractéristiques de domaine spécifiques s'appliquent, comme un alphabet limité et une redondance élevée dans la première partie des chaînes, cela peut être très efficace pour optimiser les performances.

Les références

Une explication détaillée des essais et des alphabets peut être trouvée dans le chapitre 5 du livre de Robert Sedgewick "Algorithms, 4th edition". Le site Web compagnon de Princeton contient le code d'une implémentation d'Alphabet et de TrieST plus complète que mon exemple.

La description du trie et des implémentations pour différentes langues peut également être trouvée sur Wikipedia et vous pouvez également consulter cette ressource trie de l'Université de Boston.