Enquête succincte sur les structures de données?

L'article de Fischer ce mois-ci m'a rappelé à quel point je connaissais mal l'art des structures de données succinctes et les algorithmes pour les utiliser.

Pour ceux qui ne connaissent pas les structures de données succinctes:

Étant donné une structure combinatoire, avec une (n) configurations distinctes et une représentation "utile" connue . Existe-t-il une structure de données "succincte" qui prend en charge environ bits tout en nous permettant d'effectuer des opérations aussi rapidement que possible avec la représentation normale ?$R(n)$$\lg(a(n))$$R$

Les meilleurs qui m'intéressent si quelqu'un souhaite entretenir une discussion

1. Tableaux de suffixes. Ils sont un sous-ensemble de toutes les permutations.

2. Arbres ordonnés. Ils sont un sous-ensemble de toutes les chaînes "parenthèses" binaires (la variété correspondante).

3. Toutes les plus petites valeurs les plus proches, comme dans le document ( 1 ). Non seulement vous pouvez compresser dans les deux dimensions; les tableaux "de plus petite valeur" autorisés dans une direction sont un petit sous-ensemble de listes , et donc vous devez stocker moins de bits.$\{0,...,n-1\}^n$$n \lg(n)$

Consultez également la thèse d'Ankur Gupta , en mettant l'accent sur les données compressibles.

Si pour parler des structures de données de suffixe succit, celle de Navarro et Mäkinen est vraiment bonne: http://portal.acm.org/citation.cfm?doid=1216370.1216372

Il existe maintenant un livre sur le sujet: Compact Data Structures: A Practical Approach, par Gonzalo Navarro. https://dl.acm.org/citation.cfm?id=3092586