Voyage au pays des structures de données exotiques

Aujourd'hui, le développeur Java moyen est familier avec le framework Collections de java, et notamment les 3 grandes familles de structures de données principales (la respectable trinité) que sont les List, les Set et les Map.

Si vous êtes un peu plus curieux, vous avez commencé à vous intéresser aux différentes implémentations de ces interfaces, et à connaître les cas d'utilisation et les tradeoff de classes telles que la LinkedList, le LinkedHashSet ou autre WeakHashMap...

Mais il existe des structures de données plus "exotiques", que l'on rencontre plus rarement car elles ont des cas d'utilisation moins génériques que la trinité. Dans cet article, je vais essayer de faire l'introduction de ces 5 structures de manière compréhensible, ainsi qu'indiquer les problèmes qu'elles peuvent servir à adresser.

Stocker et rechercher efficacement des chaînes dans les Tries

Une Trie (un mot issu de l'anglais retrieval, et se prononçant donc "tri"), est une structure de données arborescente ordonnée, pouvant être utilisée pour représenter une collection de chaînes de caractères ou encore parfois un dictionnaire de paires clés-valeurs dans lequel les clés sont des chaînes.

Contrairement à un arbre binaire, les noeuds ne stockent pas leur clé intégralement, mais celle-ci est plutôt déterminée par la position du noeud dans l'arborescence, où chaque niveau stocke un caractère de la clé. La clé de chaque noeud d'une branche a ainsi un préfixe commun avec ses parents. Typiquement, seules les feuilles de l'arbre et certains noeuds intermédiaires sont des "noeuds d'intérêt" représentant une clé complète (et portant une valeur associée dans le cas d'un dictionnaire clés-valeurs).

Les 3 schémas ci-dessous présentent une trie simple. Les "noeuds d'intérêt" sont plus épais (ce sont ceux qui correspondent à des mots complets):

trie stockant les mots le, lin, la, lui, sel, sec, sa, salle, sale et sac.

les clés sont explicitées sous chaque noeud d'intérêt.

trie en mode dictionnaire. La valeur associée (sous le noeud) est le genre du mot.

Cette organisation rend la trie efficace en recherche (au pire O(m) avec m la taille de la clé), mais aussi en insertion et en suppression (performances quasi égales dans les trois cas car les algorithmes sont similaires). La structure est particulièrement adaptée:

• au stockage de mots du dictionnaire (bien que si l'on ne souhaite pas associer une information à ces mots il existe une structure encore plus efficace, les graphe orientés acycliques)

• à la recherche du mot le plus proche (préfixe commun le plus long), particulièrement adapté à de l'autocomplétion

• à la recherche approximative, comme on peut la trouver dans nos smartphones lors de la suggestion/correction de mots.

• au tri lexicographique

Par rapport à un arbre binaire de recherche, la trie est plus performante (l'ABR a des performances dans le pire cas en O(m log n) avec n le nombre d'éléments dans l'arbre), plus efficace en mémoire dans le cas de petites clés (qui ont donc plus de chance d'avoir des préfixes communs).

Par rapport à une hashtable, la trie permet un parcours ordonné, a une performance plus constante en écriture (pas d'opération coûteuse de reconstruction de l'index lorsque la table est pleine), des performances similaires en recherche à une table au hash parfait (qui fonctionne en O(m) pour l'évaluation du hash puis O(1) pour la récupération de la valeur) mais ne présente pas de risque de collision (donc potentiellement plus performante qu'une hashtable imparfaite dans le pire scénario).

Il existe une variante compactée de la trie pour les cas où les opérations de recherche sont prévalentes (en effet une trie avec des mots très distincts peut rapidement occuper un trop-plein d'espace, avec des branches très verticales représentant des mots sans préfixes communs, et le compactage réduit ces branches).

De même, une trie n'est pas forcément limitée aux chaînes de caractère, la variante dite "*bitwise trie*" stockant des bits à la place des caractères permet de représenter des clés constituées de courtes séquences de bits (par exemple des entiers).

La Trie a été inventée en 1960 par Edward Fredkin.

Prendre des raccourcis avec les Skip Lists

La Skip List est à la base une liste chaînée triée, mais avec un twist. Certaines valeurs espacées dans la chaîne de base sont chaînées de manière additionnelle entre elles. Pour être plus explicite, faisons un parallèle avec la vie réelle et imaginons un réseau de transports en commun. Dans le schéma ci-dessous, on voit deux lignes de métro: la standard M1, et une ligne express A.

On remarque que les deux lignes ont toute une portion A-H qui suit le même parcours, mais que seul un sous-ensemble des arrêts (B, E, G) est commun. Cette portion, c'est notre skiplist!

La ligne M1 représente la liste chaînée de base, où tous les éléments (les arrêts) sont présents. La Express A représente le chaînage additionnel, qui permet de raccourcir le parcours entre 2 points.

Ainsi, pour aller de A à H dans une liste chaînée classique il nous faudrait marquer l'arrêt aux 7 stations. Mais en prenant en compte la ligne express, on passe à 4 arrêts (aller de A à B, prendre l'express de B à E puis à G, reprendre la ligne de base de G à H).

La Skip List ne se limite pas à une voie express, mais est organisée en couches, chacune permettant de prendre des raccourcis dans la couche inférieure. Chaque élément d'une couche a une probabilité p fixée à l'avance de faire partie de la couche supérieure.

Pour effectuer une recherche, on part de la couche supérieure que l'on parcourt horizontalement jusqu'à trouver un élément supérieur ou égal à celui que l'on recherche (la liste est déjà ordonnée). Si l'élément courant est égal, nous avons notre résultat. Sinon, on revient d'une étape en arrière, on descend dans la couche inférieure et on répète le processus, et ce jusqu'à tomber sur l'élément recherché ou la fin de la liste.

Une telle structure est potentiellement moins performante qu'un arbre équilibré dans les pires cas (où l'agencement aléatoire des couches aurait produit une structure très déséquilibrée), mais est en contrepartie plus facile à mettre en oeuvre, et se comporte efficacement en pratique (recherche en O(log n) une fois que l'on a fixé la probablité p). On peut jouer avec p pour faire varier l'espace mémoire vs la performance.

La skip list a été inventée par William Pugh comme remplaçante potentielle (plus simple) des arbres équilibrés en 1990. Faisant l'usage de la probabilité d'appartenance à la couche supérieure, c'est donc une structure probabiliste...

Des probas? Dans MES structures de données? Les filtres de Bloom

La skip list n'est pas la seule à introduire la notion de probabilité dans les structures de données (que l'on a plus l'habitude de voir déterministes). La structure suivante utilise par exemple une approche probabiliste pour travailler pragmatiquement avec des ensembles de données particulièrement grands.

Un filtre de Bloom est une structure qui permet de déterminer l'appartenance à un ensemble en faisant un compromis entre la taille mémoire occupée et la précision de la réponse. Il est donc particulièrement utile quand l'ensemble est gigantesque et la mémoire limitée. La nature probabiliste du filtre de Bloom se trouve dans le fait que des faux positifs (i.e. l'élément X n'appartient pas à notre Set mais est identifié comme y appartenant par le filtre) soient possibles avec une probabilité p, mais pas les faux négatifs.

En fait, la taille d'un Bloom Filter est fixe : le filtre est un tableau de m bits associé à k fonctions de hachage permettant de mapper tout élément de l'ensemble à une des m cases du tableau. Ces fonctions de hachage ont une répartition uniforme des éléments de l'ensemble sur le tableau, et doivent évidemment avoir une répartition différente. Au départ, le filtre représente un ensemble vide, et toutes les cases sont à 0.

Pour ajouter un élément à l'ensemble, on le passe aux k fonctions de hachage, et chaque position retournée par les fonctions est mise à 1 dans le tableau de bits. Pour vérifier l'appartenance d'un élément z à l'ensemble, on le passe de même aux k fonctions de hachage. Si l'une des positions retournées contient 0, alors on sait avec certitude que z ne fait pas partie de l'ensemble. Sinon il est probable qu'il en fasse partie.

illustration d'un bloom filter très simple

Ci dessus le bloom filter représente l'ensemble (a, b, c), avec trois fonctions de hachage (flèches solides, tirets et pointillées). Le test d'appartenance de z échoue puisque le troisième hash pointe sur une case portant 0.

Un filtre de Bloom est bien plus compact qu'une structure représentant classiquement les ensembles (comme un HashSet) car il ne nécessite pas de stocker les éléments eux même. Il est particulièrement utile lorsqu'il s'agit de déterminer si un élément ne fait pas partie d'un ensemble, afin par exemple de sortir rapidement d'un traitement lourd ne devant se produire que sur un ensemble identifié (par exemple, vérifier qu'une URL entrée dans le navigateur ne fasse pas partie d'une liste noire : d'abord une vérification rapide avec le bloom filter, puis en cas de potentiel positif une vérification plus certaine avec comparaison à chaque URL de la liste).

Le bloom filter a pour limitation qu'il n'est pas possible de retirer un élément de l'ensemble sans reconstruire le filtre, et on ne peut pas connaître avec certitude le nombre d'éléments exact ayant été ajoutés. De plus, la probabilité de collision dans les fonctions de hachage (et donc de faux positifs) augmente avec le nombre d'éléments présents dans le set.

Pour palier cette limitation de la suppression, on peut soit utiliser un second bloom filter des éléments supprimés (mais on a alors des faux-positifs de suppression, ce qui n'est pas forcément désirable), soit utiliser la variante dite "compteur" dans laquelle chaque bit du tableau est remplacé par un compteur (typiquement de 3 ou 4 bits). L'ajout d'un élément dans cette variante incrémente le compteur (plutôt que de simplement passer le bit à 1), la suppression passe par une décrémentation du compteur et la vérification d'appartenance se contente de vérifier que tout les compteurs pointés par les fonctions de hachage sont supérieurs à 1. On doit par contre faire attention aux dépassements arithmétiques (qui doivent laisser le compteur à sa valeur maximum, afin de garder les propriétés du bloom filter) et la taille du filtre est multipliée par la taille du compteur.

Les filtres de Bloom ont été conceptualisés en 1970 par Burton Howard Bloom.

Les Hash-Trees, un élagage du contrôle de cohérence

Un Hash Tree, ou Arbre de Merkle, est une structure arborescente utilisée pour pouvoir effectuer du contrôle de cohérence sur des portions de gros fichiers ou des ensembles de fichiers, sans avoir à posséder l'ensemble du (des) fichier(s).

En fait chaque noeud du Hash Tree va porter le hachage cryptographique de ses fils, jusqu'à ce qu'on atteigne les feuilles de l'arbre qui portent les hachages de chaque bloc du fichier. Le noeud racine porte donc un hash "maître" pouvant représenter le fichier dans son ensemble. Ce hash maître devra être obtenu via une source plus sûre que les données à vérifier (typiquement via une autorité de confiance, un site répertoire dans le cas du Peer-To-Peer par exemple).

Une fois le hash maître obtenu, on peut vérifier l'Arbre de Merkle transmis depuis une source non sécurisée (en cas d'échec de la vérification on le récupérera par exemple depuis une autre source). Il devient dès lors possible de vérifier l'intégrité d'un bloc reçu d'une source non sécurisée, en ne se reposant que sur une partie du Hash Tree (il devrait donc même être possible de recevoir et valider le Hash Tree de manière incrémentale).

Par exemple, dans le schéma précédent pour valider le bloc 2 il suffit de posséder Hash0-0 et Hash1. On peut combiner le hash du bloc 2 avec Hash0-0 puis combiner le résultat avec Hash1 pour vérifier qu'on obtient bien le hash maître. Comme il est aussi peut faisable en pratique de falsifier Hash0-0 et Hash1 que de falsifier une bonne fonction de hachage cryptographique pour lui faire donner un résultat déterminé, on pourra récupérer Hash0-0 et Hash1 eux aussi d'une source non sécurisée...

De même, si on obtient les fragments 3 et 4 d'une autre source, leur intégrité peut être vérifiée simplement en possédant le Hash0. Même si l'on est en train de recevoir des fragments 1 et 2 corrompus, cela n'impacte pas notre vérification de 3 et 4 avec un HashTree validé : calcul du hash du bloc 3 et du bloc 4, calcul du hash de la concaténation de ceux-ci puis combinaison avec Hash0 pour vérifier par rapport au hash maître.

Les Hash Trees, ou Arbres de Merkle, sont notamment utilisés dans les protocoles P2P (Direct Connect, Gnutella) pour vérifier que les portions de fichiers sont reçues sans dommages. L'usage de fonctions de hachage cryptographiques telles que Tiger permet de s'assurer que les données n'ont pas été malintentionnellement altérées (on pourrait se contenter de fonctions plus simples comme CRC pour juste se prémunir d'altérations accidentelles). On les retrouve aussi dans le système de contrôle de version Git, la base NOSQL Apache Cassandra ou encore dans la monnaie virtuelle BitCoin... Ils ont été inventés par Ralph Merkle en 1979