Zwięzłe badanie struktur danych?

Artykuł Fischera w tym miesiącu przypomniał mi, jak mało wiem o sztuce zwięzłych struktur danych i algorytmów ich używania.

Dla tych, którzy nie wiedzą o zwięzłych strukturach danych:

Biorąc pod uwagę kombinatoryczną strukturę, z (n) odrębnymi konfiguracjami i znaną „użyteczną” reprezentacją . Czy istnieje „zwięzła” struktura danych, która wymaga przechowywania około lg ( a ( n ) ) bitów, ale pozwala nam wykonywać operacje tak szybko, jak to możliwe przy normalnej reprezentacji R ?$R(n)$$\lg(a(n))$$R$

Najważniejsze, którymi jestem zainteresowany, jeśli ktoś chciałby podjąć dyskusję

1. Tablice sufiksów. Są podzbiorem wszystkich permutacji.

2. Zamówione drzewa. Są podzbiorem wszystkich ciągów binarnych „nawiasów” (dopasowana odmiana).

3. Wszystkie najbliższe mniejsze wartości, jak w pracy ( 1 ). Nie tylko możesz kompresować w obu wymiarach; Dopuszczalne wartości „mniej” tablice w jednym kierunku, to tylko mała część list , a zatem musisz przechowywać mniej niż n lg ( n ) bitów.$\{0,...,n-1\}^n$$n \lg(n)$

Zobacz także tezę Ankura Gupty , ze szczególnym uwzględnieniem danych podlegających kompresji.

Jeśli chodzi o struktury danych sufiksu sufiksu, to ta autorstwa Navarro i Mäkinena jest naprawdę dobra: http://portal.acm.org/citation.cfm?doid=1216370.1216372

Jest teraz książka na ten temat: Kompaktowe struktury danych: praktyczne podejście autorstwa Gonzalo Navarro. https://dl.acm.org/citation.cfm?id=3092586