Umfrage zu prägnanten Datenstrukturen?

Fischers Artikel in diesem Monat erinnerte mich daran, wie wenig ich über die Kunst prägnanter Datenstrukturen und Algorithmen zu ihrer Verwendung weiß.

Für diejenigen, die sich mit prägnanten Datenstrukturen nicht auskennen:

Vorausgesetzt, eine kombinatorische Struktur mit einer (n) unterschiedlichen Konfiguration und einer bekannten "nützlichen" Darstellung . Gibt es eine "prägnante" Datenstruktur, in der ungefähr lg ( a ( n ) ) Bits gespeichert werden, die es uns jedoch ermöglicht, Operationen so schnell wie möglich mit der normalen Darstellung R durchzuführen ?$R(n)$$\lg(a(n))$$R$

Die Besten, die mich interessieren, wenn jemand eine Diskussion führen möchte

1. Suffix-Arrays. Sie sind eine Teilmenge aller Permutationen.

2. Bestellte Bäume. Sie sind eine Teilmenge aller binären "Klammern" (die übereinstimmende Sorte).

3. Alle nächstkleineren Werte wie im Artikel ( 1 ). Sie können nicht nur in beiden Dimensionen komprimieren. die zulässige „kleinerer Wert“ Arrays in eine Richtung ist eine kleine Untergruppe von Listen , und daher müssen Sie weniger als n lg ( n ) Bits speichern .$\{0,...,n-1\}^n$$n \lg(n)$

Schauen Sie sich auch die These von Ankur Gupta mit Schwerpunkt auf komprimierbaren Daten an.

Wenn man von Succix-Datenstrukturen spricht, ist diese von Navarro und Mäkinen wirklich gut: http://portal.acm.org/citation.cfm?doid=1216370.1216372

Es gibt jetzt ein Buch zum Thema: Kompakte Datenstrukturen: Ein praktischer Ansatz von Gonzalo Navarro. https://dl.acm.org/citation.cfm?id=3092586