Chats dans des boîtes ou structures de données compactes

Que dois-je faire si l'arborescence de recherche a atteint toute la mémoire RAM et est sur le point de rooter les racks voisins dans la salle des serveurs? Que faire d'un index inversé gourmand en ressources? Dois-je me connecter au développement Android si l'utilisateur reçoit «Mémoire du téléphone pleine» et que l'application ne représente que la moitié de la charge d'un conteneur important?

En général, est-il possible de compresser la structure de données afin qu'elle occupe beaucoup moins d'espace, mais ne perd pas ses avantages inhérents? Pour que l'accès à la table de hachage reste rapide et que l'arbre équilibré conserve ses propriétés. Oui tu peux! Pour cela, la direction de l'informatique «Structures de données succinctes» est apparue, explorant la représentation compacte des structures de données. Il se développe depuis la fin des années 80 et est actuellement à son apogée dans la gloire du big data et de la surcharge.

En attendant, y aura-t-il un héros sur Habr qui pourra re-parler trois fois de suite
[səkˈsɪŋkt]?

Porte vers le monde de la compacité

Ainsi, une structure de données est considérée comme compacte (succincte) si elle:

• Il occupe un certain nombre de bits proches de la borne inférieure théorique de l'information.
• Il ne nécessite pas de déballage préliminaire pour une utilisation complète.

Cela signifie que les algorithmes de compression sans perte n'ont rien à voir avec des structures de données compactes. Après tout, ils impliquent la restauration de données à partir d'un état compressé pour le traitement.

Les implémentations familières et «traditionnelles» des graphiques, des tables de hachage et d'autres choses ne sont pas non plus bonnes. Prenez au moins des pointeurs vers des éléments enfants dans l'arborescence de recherche. Ils mangent des endroits décents: $$$O (MN)$ où $$$M$ - la longueur du pointeur, et $$$N$ - le nombre de nœuds dans l'arbre. Mais l'implémentation de l'arbre succinct nous permet d'améliorer le comportement asymptotique $$$2N + o (N)$ qui est proche de la borne inférieure théorique $$$2N - Θ (log N)$ pour le bois de $$$N$ nœuds. Avec la longueur du pointeur $$$M = 8$ octet cela signifie passer de $$$O (8N)$ à un ordre d'asymptotique complètement différent - juste $$$2N$ , considérant que $$$o (N)$ - valeur négligeable par rapport à $$$N$ .

Les structures de données compactes (succinctes) sont des représentations compressées pour des vecteurs de bits, des ensembles multiples, des graphiques planaires et d'autres structures classiques préférées. Souvent, ils sont statiques, construits une seule fois et ne changent pas pendant l'utilisation. Il existe des exceptions - structures succinctes avec des opérations rapides d'ajout et de suppression d'éléments.

La plupart des structures compactes sont basées sur le concept du soi-disant dictionnaire indexable compact. C'est un cas particulier de bitmap (bitmap, bitset). Le bitmap lui-même est idéal pour vérifier si les éléments sont dans un certain ensemble. Si un élément est inclus dans un ensemble, la valeur de bit à un index donné est définie sur 1, sinon, il est réinitialisé à 0. Un exemple essentiel est l'inode-bitmap ext4, UFS et d'autres systèmes de fichiers Unix. Il stocke des données sur les entrées de la table inode qui sont occupées et celles qui sont libres.

Un dictionnaire indexable compact est le même bitmap, mais complété par deux opérations: classer et sélectionner. Ces opérations sont les éléphants sur lesquels repose le monde succinct. En gros, le rang est un décompte du nombre d'éléments, et select est une recherche d'un élément:

• $$$rank_x (i)$ renvoie le nombre de bits égal à $$$x$ dont les indices se situent sur un segment $$$[0; i]$ . Depuis $$$x$ - la valeur du bit, il peut alors être égal exclusivement à 0 ou 1.
• $$$select_x (j)$ indice de retour $$$j$ peu égal à $$$x$ . Le bon sens dit qu'il n'y a pas d'occurrence nulle, il n'y a que la première. Par conséquent$$ $ en ligne $ j> 0 $ en ligne $ : le calcul est effectué à partir d'un. Aussi $$$j$ ne peut pas dépasser le nombre total de bits dans le dictionnaire égal à $$$x$ .

Supposons que nous ayons un dictionnaire indexable dans lequel 4 des 7 bits sont définis. Alors $$$rank_1$ et $$$select_1$ prendra les valeurs suivantes:

Un exemple de dictionnaire indexable et son calcul $$$rank_1$ , $$$select_1$ .

Un lecteur attentif remarquera que sélectionner est l'inverse du rang. Si $$$rang_1 (5) = 4$ alors $$$select_1 (4) = 5$ .

Quelqu'un avait déjà vu à la vue de $$$rank_1 (i)$ ? Et tout cela parce que cette opération généralise le poids de Hamming - le nombre de caractères non nuls dans la séquence. Pour les séquences binaires, le poids de Hamming est également appelé popcount (population count).

Le rang / sélection s'applique également aux bits rejetés. Voici un exemple de calcul $$$rank_0$ et $$$select_0$ pour des bits égaux à 0:

Un exemple de dictionnaire indexable compact et son calcul $$$rank_0$ , $$$select_0$ .

Vu un arbre en bitiks

Nous utilisons ces connaissances pour construire un arbre de préfixes compact! Les arbres de préfixe sont bons pour trouver des chaînes par préfixe. Avec leur aide, une liste déroulante d'indices de recherche (sjest) est souvent implémentée. L'approche de la succinctisation de l'arbre des préfixes est extrêmement généralisée et démontre au maximum tous les raisins secs des structures compactes. Contrairement à un arbre binaire, pour lequel des formules particulières sont dérivées qui interfèrent avec l'image globale.

Trois méthodes de représentation compacte des arbres sont les plus populaires:

• BP (parenthèses équilibrées) - séquences de parenthèses équilibrées.
• DFUDS (séquence de degrés unaires en profondeur d'abord) - une séquence de nœuds codés en unités triés par recherche en profondeur.
• LOUDS (séquences de degrés unaires ordonnées par niveau) - séquences de nœuds codés en unités triées par niveau.

Quelle est la chaîne logique suspecte de la traduction de «degré unaire» en «nœud codé unique»? Eh bien. Un degré unaire dans ces noms signifie un moyen de coder les nœuds d'arbre avec une séquence d'unités en fonction du nombre de nœuds enfants, toujours avec un zéro dans la bande-annonce.

Ces trois méthodes de représentation des arbres sont unies par la présence d'opérations rapides: trouver un parent; trouver le premier descendant; trouver le dernier descendant; Trouvez les nœuds adjacents gauche et droit. La possibilité fondamentale et l'efficacité d'autres opérations diffèrent d'une méthode à l'autre.

Arrêtons-nous sur la méthode LOUDS. Après l'avoir compris, il ne sera pas difficile de traiter avec les deux autres. De plus, l'année dernière, les arbres LOUDS ont célébré leur 30e anniversaire! Des opérations supplémentaires utiles pour les arbres LOUDS sont implémentées dans $$$O (1)$ : trouver le nombre de descendants du nœud; calculer le nombre de descendants du nœud parmi tous ses descendants (premier descendant, deuxième, $$$i$ th, etc.); trouver $$$i$ progéniture. L'inconvénient de LOUDS est l'absence d'un algorithme efficace pour compter le nombre de nœuds de sous-arbre.

L'essence de la méthode est simple: stocker les clés des nœuds d'arbre et toutes les informations précieuses dans un tableau régulier, et représenter la structure arborescente comme une séquence de bits. Au total, nous avons deux structures statiques. Mais il n'est pas nécessaire d'allouer de la mémoire pour les pointeurs aux nœuds d'arbre: les transitions entre eux sont implémentées à l'aide de formules avec l'utilisation active de rank / select.

Avertissement, arborescence des préfixes:

Arbre de préfixe prêt pour la compression à l'aide de la méthode LOUDS.

Préparez l'arbre pour la présentation sous forme binaire:

1. Attachez l'arbre à la fausse racine. Il jouera son rôle très prochainement.
2. Nous numérotons tous les nœuds de l'arbre, niveau par niveau, de gauche à droite, comme dans BFS (recherche en largeur d'abord). La fausse racine est ignorée et la vraie est indexée par zéro.
3. Encodez les nœuds. Le nœud d'arbre est codé par une séquence d'unités correspondant aux descendants directs, plus zéro. Si le nœud a quatre enfants, alors il est codé comme 11110, et si aucun - comme 0. La fausse racine est codée en premier. Il a un seul descendant, donc son code est 10.

Un arbre de préfixe avec des nœuds numérotés. Les nœuds sont codés.

Dans le processus de traversée d'arbre niveau par niveau, un dictionnaire indexable compact est formé - une séquence de bits provenant de nœuds codés collés de haut en bas et de gauche à droite. Nous avons une séquence de 21 bits. Soit dit en passant, il est appelé LBS (chaîne de bits LOUDS).

Dictionnaire indexable compact pour l'arborescence des préfixes.

L'arbre de préfixe LOUDS compact est construit. LBS pour bois avec $$$N$ nœuds (le faux ne compte pas) prend $$ peu. La chose la plus intéressante reste - des formules pour parcourir un arbre transformé en bitmap.

Recherchez le premier enfant . Transition à partir d'un nœud $$$i$ à son premier nœud enfant s'effectue selon la formule:

$$

$$firstChild (i) = select_0 (i + 1) - i$$

$$$i$ - il s'agit du numéro de nœud dans la plaque précédente apposée en violet.

Trouvez le premier descendant du nœud avec l'index 3 (la lettre "a"):

$$

$$firsthild (3) = select_0 (3 + 1) - 3 = select_0 (4) - 3 = 9 - 3 = 6$$

Le premier nœud enfant est à l'index 6, et c'est la lettre «k». Nous appliquons la formule pour la racine de l'arbre:

$$

$$firstChild (0) = select_0 (0 + 1) - 0 = select_0 (1) = 1$$

Nous avons trouvé une feuille avec l'index 1, la lettre «et». Converge! Il est devenu clair pourquoi une fausse racine était nécessaire: pour la magie de l'indexation des nœuds. Pour éviter d'étranges erreurs avant de passer aux descendants du nœud $$$i$ Ce serait bien de connaître le nombre de ces descendants. En effet, pour les feuilles de l'arbre, ce qui n'est pas surprenant, la formule donne un résultat insuffisant. Pour trouver le descendant suivant après le premier, vous devez ajouter 1. À son index, c'est logique, car les descendants d'un nœud sont toujours à proximité, sans lacunes. Mais lorsque vous les parcourez, vous devez vous arrêter à temps - déterminer quel descendant est considéré comme le dernier.

Rechercher le dernier descendant d'un nœud $$$i$ passe en deux temps: déterminer l'indice de la dernière unité dans le code du nœud - c'est lui qui désigne cet enfant puis déterminer l'indice de l'enfant lui-même:

$$

$$lastChildPos (i) = select_0 (i + 2) -1$$

Après avoir reçu l'index de la dernière unité dans le code de noeud, il faut vérifier que le bit à cet index est bien positionné. Sinon, la conclusion se suggère: c'est un nœud sans descendance, une feuille. Si le bit est activé, continuez ensuite:

$$

$$lastChild (i) = rank_1 (lastChildPos (i) -1)$$

Trouvez le dernier descendant du nœud 2 (la lettre "k").

$$

$$lastChildPos (2) = select_0 (2 + 2) -1 = select_0 (4) -1 = 9-1 = 8$$

Le bit à l'index 8 est 1, donc le nœud 2 n'est pas une feuille, et nous pouvons trouver l'index de son dernier enfant:

$$

$$lastChild (i) = rang_1 (8-1) = 5$$

Le nombre de descendants. La façon la plus simple de déterminer le nombre de descendants est de soustraire l'index de son premier descendant de l'index du dernier descendant du nœud et d'ajouter 1:

$$

$$childrenCount (i) = lasthild (i) - firsthild (i) + 1$$

Mais supposons que le nœud $$$i$ il y a un nœud voisin $$$i + 1$ situé au même niveau d'arbre que $$$i$ . Ensuite, le nombre de descendants $$$i$ peut être défini comme la différence entre les indices des premiers descendants des nœuds $$$i + 1$ et $$$i$ :

$$

$$childrenCount (i) = firsthild (i + 1) - firsthild (i)$$

Les descendants du nœud sont également numérotés séquentiellement. Si le premier descendant $$$i$ Est-ce $$$j$ puis le second - $$$j + 1$ et ainsi de suite jusqu'au descendant d'un nœud voisin à ce niveau $$$i + 1$ (le cas échéant).

Le nombre de descendants de la feuille «et» d'index 1 devrait être nul:

$$

$$childrenCount (1) = (select_0 (2 + 1) - 2) - (select_0 (1 + 1) - 1) = 3 - 3 = 0$$

Recherche parent d'un nœud $$$i$ organisé par la formule:

$$

$$parent (i) = rank_0 (select_1 (i + 1) - 1) -1$$

Nous allons l'utiliser pour rechercher le parent du nœud 6 (la lettre «k»):

$$

$$parent (6) = rank_0 (select_1 (7) - 1) -1 = rank_0 (9) -1 = 3$$

Il s'agit du nœud 3, la lettre "a".

Avec la connaissance des formules des indices enfant et parent, il n'est pas difficile de faire le tour de l'arbre entier. L'essentiel est de ne pas oublier le traitement des conditions aux limites pour la racine et les feuilles.

Quelques kopecks sur les méthodes BP et DFUDS. Les deux méthodes ont des asymptotiques spatiales - $$$2N + o (N)$ peu pour le bois de $$$N$ nœuds, et les deux sont similaires dans la représentation d'un nœud d'arbre sous la forme de crochets ouvrants et fermants.

BP (parenthèses équilibrées) convertit un arbre en une séquence de crochets, une paire pour chaque nœud. Pour ce faire, l'arbre va en profondeur; chaque nœud est visité deux fois. Lors de la première visite, le crochet d'ouverture est enregistré, lors de la deuxième visite - le crochet de fermeture. Entre eux se trouvent des parenthèses d'enfants.

Il est pratique de représenter la séquence de crochets sous la forme d'un bitmap, où 1 est le crochet d'ouverture et 0 est le crochet de fermeture. Toutes les formules pour travailler avec BP sont affinées pour une recherche rapide. Contrairement à LOUDS, BP vous permet de calculer rapidement la taille d'un sous-arbre et de déterminer l'ancêtre commun le plus proche de deux nœuds. Mais trouvez $$$i$ -le descendant est beaucoup plus compliqué que dans LOUDS.

DFUDS (séquence de degré unaire en profondeur d'abord) est similaire à la fois BP et LOUDS. Avec BP, il associe une marche d'arbre en profondeur et sa représentation en bracket. Et le principe des parenthèses est le même que le principe de codage des nœuds dans LOUDS. Avant de parcourir l'arbre, nous ajoutons une parenthèse ouvrante à la séquence de parenthèses à l'avance. Ensuite, lors de la traversée des nœuds, nous écrivons des crochets ouverts en fonction du nombre de descendants, plus un fermant. Il s'avère que la localité de stockage des descendants dans DFUDS est plus élevée que celle de BP. Le calcul de la taille du sous-arbre et la recherche de l'ancêtre commun le plus proche sont effectués pour $$$O (1)$ . Mais déterminer la hauteur du sous-arbre et trouver le parent sur $$$j$ niveau - opérations lourdes pour DFUDS.

Pour plus de clarté, nous comparons les méthodes LOUDS, BP et DFUDS en utilisant le mini-arbre comme exemple.

Les nœuds de l'arbre sont numérotés en orange comme s'ils marchaient en largeur (pour LOUDS), en bleu - comme en marchant en profondeur (pour BP et DFUDS).

Vues d'arbres LOUDS, BP et DFUDS.

Ne soyez pas surpris si vous voyez des différences dans les formules dans les œuvres en anglais. Parmi les mathématiciens, il y a des amateurs d'indexation à partir de l'un. Et certains développeurs considèrent les mots rang et gamme consonant, donc ils font le rang la moitié du temps. $$$[0; i)$ . En raison de la nécessité de maintenir la symétrie de rang / sélection, ils calculent $$$sélectionner (i)$ comment $$$sélectionner (i + 1)$ . Mais certaines formules sous cette forme semblent plus courtes.

Tableau clairsemé: secouez mais ne mélangez pas

Un tableau clairsemé est une autre structure littéralement créée pour la compression. La taille d'un tel tableau est parfois supérieure de plusieurs ordres de grandeur au nombre d'éléments remplis. Et les éléments vides prennent une valeur par défaut ou sont marqués avec quelque chose comme null. Un réseau clairsemé se profile à l'horizon chaque fois que nécessaire pour stocker de nombreux objets et les relations entre eux. Les graphiques d'amis sur les réseaux sociaux, les algorithmes de classement des moteurs de recherche, les tableaux de type Excel, les simulateurs de circuits électriques avec des milliards de transistors dans une puce viennent immédiatement à l'esprit.

Souvent, ces tableaux sont cyclopéens dans le style Lovecraftian, avec une implémentation naïve, ils ne rentrent pas dans la RAM, restant pratiquement vide. Selon les besoins en mémoire et en vitesse, les tableaux clairsemés se transforment en tables de hachage beaucoup plus compactes, listes de contiguïté, arbres binaires ... ou succinctes.

Disons que nous avons un tableau clairsemé de chaînes. Attachez-y un dictionnaire indexable compact. Que va-t-il donner?

Tableau clairsemé avec un bitmap.

Maintenant, sans accéder directement au tableau d'origine, il est facile de vérifier si un élément y est présent à l'index d'intérêt. Rien n'empêche de réduire le tableau d'origine en jetant tous les éléments non remplis:

Un tableau sans éléments vides.

Calcul d'un index dans un tableau compressé. Après avoir vérifié la présence d'un élément, il serait intéressant d'accéder à sa valeur dans le tableau d'origine, c'est-à-dire de mapper l'index $$$i$ dans l'index du dictionnaire indexé $$$j$ dans un tableau compressé. Pas étonnant que le rang soit utilisé pour cela:

$$

$$j = rang_1 (i) -1$$

Vérifions comment les choses se passent avec le 8ème élément: $$$bitmap [8] = 0$ . Donc, dans le tableau d'origine, il n'y a pas un tel élément. Et l'élément 7? $$$bitmap [7] = 1$ . Obtenez sa valeur: $$$rang_1 (7) - 1 = 3-1 = 2$ . À l'index 2 est "go".

Calcul de l'index dans le tableau source. Certes, dans le tableau, vous devrez rechercher des éléments par valeur! Si les données ne sont pas triées, la recherche est réduite à la recherche de $$$O (N)$ où $$$N$ - le nombre d'éléments non vides. Pour l'élément trouvé $$$j$ peut avoir besoin d'obtenir son index $$$i$ comme si le tableau n'était pas réduit. Pour ce faire, utilisez select, l'inverse de rank:

$$

$$i = select_1 (j + 1)$$

Par exemple, recherchez la ligne «C ++». Dans un tableau compact, il est situé à l'index 0. Et son index dans le tableau d'origine est $$$select_1 (0 + 1) = 3$ .

Déjà sur un exemple avec des lignes d'économies de mémoire notables. Si le tableau est conçu pour stocker des classes avec de nombreux champs, les économies deviennent beaucoup plus importantes. De plus, la recherche dans une baie compacte est plus rapide que dans une baie large et clairsemée: elle est mieux mise en cache par le processeur. Un dictionnaire indexé sur les bits est plus susceptible de tenir dans une ligne de cache qu'un tableau régulier de nombres, de chaînes ou de types personnalisés fantaisistes.

Bien sûr pour le stockage $$$2 ^ {30}$ les éléments décrits ne conviennent pas. Son applicabilité se termine là où les problèmes de croissance de l'indice commencent. Mais bien sûr, cette méthode de compression des tableaux et ses variations a sa propre niche. Un exemple courant est la mise en œuvre du protocole BitTorrent. Le bitmap contient des informations sur les segments de fichiers téléchargés et les pairs échangent les index de leurs segments. Un exemple d'espace est les options de transmission de données segmentées qui sont utilisées par les rovers, Voyagers et la station New Horizons, labourant les espaces ouverts trans-Neptune.

Les exemples décrits de succinctisation d'un arbre de préfixes et d'un tableau clairsemé sont construits sur une base commune. Il est basé sur une croyance inébranlable en l'efficacité des opérations de rang / sélection. Sans elle, toute la théorie des structures compactes mais assez rapides éclate aux coutures. La pertinence d'utiliser des structures compactes en dehors des thèses dépend du rang et de la vitesse de sélection.

En fait, ces opérations peuvent être mises en œuvre de manière extrêmement efficace: rang - pour $$$O (1)$ ; sélectionner - pour $$$O (log (log N))$ , ce qui est également presque constant. Et bien sûr, ce n'est pas sans quelques astuces. Et comme il doit y avoir une légère sous-estimation dans tout travail avec un complot compliqué, je m'arrêterai ici.

Faits intéressants

Quelle est la limite inférieure théorique des ressources occupées en termes de théorie de l'information? Disons qu'une structure de données stocke beaucoup de $$$N$ éléments. Pour les identifier sans collision, vous avez besoin d'un certain nombre de bits, pas moins de $$$X = log_2N$ . $$$X$ et il y a cette borne très inférieure déterminée par la formule de Hartley. Dans certains cas particuliers, ayant des informations sur la nature des données stockées, la structure peut être compressée encore plus efficacement.

La chaîne succincte est-elle une structure de données? Il contient $$$N$ et se termine par un caractère ASCII nul. Il faut donc $$$N + 1$ lieux, et donc ... elle est succincte, et plus précisément implicite! Ce qui nous amène à la question suivante.

Toutes les structures succinctes sont-elles également compactes? Le domaine de recherche succinct définit jusqu'à trois types de structures compactes dont la complexité spatiale diffère:

• compact - $$$O (N)$ . Complexité linéaire de $$$N$ - le nombre d'articles stockés. «» . . , : . , . , 0 , . $$$O(2N)$ ( 2 , ) select .
• succinct — $$$N + o(N)$ . — , succinct data structures . : (Pascal string), . $$$N + log(N)$ .
• implicit — $$$N + O(1)$ . , . : (heap) . $$$N + 1$ .

? , , . succinct- . , -, FM-, RMQ (range minimum queries), LCP (longest common prefix), , succinct'. -.

, , . Et pas seulement ça. , , X, .

succinct — , «- ». Succinct — . , , succinct. , . (IME) Google, . MAPS.ME succinct- .

, . ., 97 % -: . 3 %.

Et ensuite?

, succinct:

• rank/select Bitmagic Library.
• , succinct. .
• MIT, succinct.
• , 18 .
• , succinct.
• RRR — .

, :

• Projet de bibliothèque de structures de données succinctes en C ++.
• Projet BitMagic en C ++.
• Package avec une implémentation succincte d'Elias-Fano en Python.
• Implémentation de quelques structures succinctes à Rust.