Structures de données succinctes

• En lisant des articles scientifiques pour optimiser les performances, j’ai découvert pour la première fois le concept de Succinct Data Structures (structures de données succinctes)
• En cherchant des publications sur le sujet, j’ai même échangé directement avec le célèbre chercheur, le professeur Gonzalo Navarro
• Je me suis alors demandé pourquoi, contrairement aux tableaux, hash maps, arbres, etc., ces structures de données étaient si peu utilisées
• Voici donc une brève explication

Aperçu des Succinct Data Structures

• Comme dans la compression de données classique, on stocke les données sous forme compressée, mais elles restent directement exploitables même dans cet état
• Différence avec les méthodes de compression classiques : on peut accéder aux données et les manipuler sans les décompresser
• C’est un domaine de recherche très actif depuis environ 25 ans

Utilisation en Rust

• En programmation système, les performances et l’usage mémoire sont essentiels, ce qui rend ces structures potentiellement très utiles
• Les travaux existants ont surtout été menés en C++, mais on commence aussi à trouver des implémentations en Rust
• Voici quelques bibliothèques susceptibles d’être utiles aux développeurs Rust

Bit Vectors (vecteurs de bits)

• Exemple de tableau de bits : [0, 1, 0, 1, 1, 0, 1, 0]
• Sur un système 64 bits, on peut stocker 64 bits dans un seul entier, ce qui permet de gagner de la place
• Un vecteur de bits en lui-même n’est pas une structure succincte, mais il existe des méthodes pour l’exploiter efficacement

Rank/Select Bit Vector

• Opération Rank : calcule combien de fois 1 apparaît avant un indice donné
  • Exemple : rank(3) → 2
• Opération Select : renvoie la position où apparaît le 1 d’un certain rang
  • Exemple : select(2) → 3
• Peut s’exécuter en complexité temporelle O(1)
• La surcharge mémoire est faible, ce qui est utile pour manipuler de grandes chaînes
• Cas d’usage
  • Utile lorsqu’on stocke une grande chaîne découpée en petites sous-chaînes
  • Permet de déterminer efficacement à quelle sous-chaîne appartient un indice donné
  • Le stockage compressé réduit l’usage mémoire tout en conservant des recherches rapides
• Bibliothèques Rust
  • vers : hautes performances et surcharge minimale
  • sucds : prend en charge des implémentations clairsemées comme SArray
  • vers est particulièrement efficace pour la construction de structures de données efficaces et devrait aussi prendre en charge des implémentations clairsemées à l’avenir

Wavelet Matrix (matrice wavelet)

• Étend le concept de Rank/Select à des données contenant un alphabet plus large
• Exemples : analyse de séquences ADN (A, C, G, T) ou recherche textuelle (caractères UTF-8, 256 symboles)
• Repose sur les vecteurs de bits Rank/Select
• Bibliothèque Rust
  • vers inclut une implémentation de matrice wavelet

FM-Index (index de chaînes compressé)

• Permet de stocker de grands volumes de texte sous forme compressée tout en offrant des fonctions de recherche
• Fonctions principales :
  • count(pattern) : calcule combien de fois un motif (chaîne) apparaît
  • locate(pattern) : renvoie tous les indices où ce motif apparaît
• Utile pour la recherche dans les séquences ADN et la recherche textuelle à grande échelle
• Bibliothèques Rust
  • La bibliothèque fm-index peut être utilisée
  • Auparavant, fid était utilisé, mais une migration vers vers a permis d’améliorer les performances

Balanced Parentheses (représentation par parenthèses équilibrées)

• Compresse le stockage d’une structure arborescente jusqu’à environ 2 bits par nœud
• Arbre d’exemple :

   a  
 /   \  
b     c  

• Peut être représenté sous la forme (()())
• Peut être converti en 1 (parenthèse ouvrante) et 0 (parenthèse fermante) : 110100
• Les opérations Rank/Select permettent d’optimiser les parcours dans l’arbre
• Bibliothèque Rust
  • Implémentation en cours dans la branche dev-bp de vers

Application : stockage et traitement de XML

• Il est possible de stocker du XML en utilisant la représentation par parenthèses équilibrées
• Les vecteurs de bits Rank/Select servent à traiter efficacement les balises XML (p, div, etc.)
• FM-Index permet d’améliorer les performances de recherche textuelle

Conclusion

• Les structures de données succinctes offrent à la fois une faible consommation mémoire et des opérations rapides
• La recherche a été surtout menée en C++, mais les implémentations progressent activement aussi en Rust
• La collaboration avec des chercheurs et des développeurs open source a permis de découvrir de nombreuses possibilités
• Elles ont un fort potentiel d’adoption plus large dans divers domaines de l’informatique à l’avenir

[qwqwhs]

Les structures compressées utilisant les wavelets sont largement employées comme standard dans Djvu. La compression d’image y est vraiment excellente.

[GN⁺]

Commentaires sur Hacker News

• J’ai envoyé un e-mail à Gonzalo Navarro pour lui poser une question, ce qui a finalement conduit à la rédaction d’un article ensemble

  • Un autre de ses articles traite d’une implémentation simple du rank/select sur bitvectors en combinant quelques idées élégantes
  • À cette époque, je me suis vivement intéressé aux structures de données succinctes et j’ai écrit une bibliothèque Rust implémentant plusieurs types de bitvectors ainsi qu’une wavelet matrix
  • Du point de vue de la visualisation de données, je me demandais si des structures de données économes en espace pouvaient fondamentalement améliorer l’exploration interactive de grands jeux de données côté client

• Je suis dans ce domaine depuis plus de 30 ans, mais c’est la première fois que j’entends parler des « structures de données succinctes »

  • Si je n’avais pas vu ce post, je ne l’aurais probablement jamais su
  • Si ces structures de données ont des applications concrètes dans le traitement de graphes, cela pourrait être une découverte importante
  • Le sujet me paraît séduisant

• Les structures de données succinctes ne sont pas forcément plus rapides que les structures classiques quand le jeu de données tient en mémoire

  • Mais sur de grands jeux de données, le temps d’accès au stockage devient prédominant, ce qui donne l’avantage aux structures de données succinctes
  • Les arbres succincts sont comme des œuvres d’art

• J’ai entendu parler du concept de structures de données succinctes pour la première fois grâce à Edward Kmett

  • C’est un célèbre développeur de bibliothèques Haskell, et il a donné il y a longtemps une conférence sur les structures de données succinctes

• Les structures de données succinctes sont vraiment passionnantes

  • Je les ai implémentées en Zig, et l’implémentation principale est une fonction de hachage parfait minimale utilisant des éléments de moins de 4 bits
  • Implémenter ce genre d’algorithmes relève de la magie

• Le livre de Navarro est une excellente étude d’ensemble

  • Le cours d’Erik Demaine sur les structures de données succinctes est également excellent

• J’ai passé la matinée à me documenter sur les structures de données succinctes, et leur efficacité mémoire est étonnante

  • Je travaille sur un projet d’analyse de gros fichiers XML qui consomme beaucoup de RAM
  • Le concept de wavelet matrix semble prometteur pour les travaux centrés sur le texte

• Il existe une manière de rendre efficace en mémoire la représentation en nœuds de grosses structures en mémoire

  • On attribue des offsets aux champs rarement utilisés et on emploie un bitmask pour indiquer la présence des champs
  • Le masquage et popcount permettent un accès rapide

• Le trie Marisa est une structure de données succincte très élégante et utile

  • Il est aussi mentionné dans le livre High Performance Python

• Ma bibliothèque de base pour les structures de données succinctes est SDSL-Lite