Survei struktur data yang ringkas?

Makalah Fischer bulan ini mengingatkan saya betapa sedikit yang saya tahu tentang seni struktur data yang ringkas, dan algoritma untuk menggunakannya.

Bagi mereka yang tidak tahu tentang struktur data ringkas:

Diberikan struktur kombinatorial, dengan (n) konfigurasi berbeda, dan representasi "berguna" yang dikenal . Apakah ada struktur data "ringkas" yang mengambil penyimpanan sekitar lg ( a ( n ) ) bit namun memungkinkan kami melakukan operasi secepat yang kami bisa dengan representasi normal R ?$R(n)$$\lg(a(n))$$R$

Yang paling menarik saya tertarik jika ada yang ingin mengadakan diskusi

1. Susunan Sufiks. Mereka adalah himpunan bagian dari semua permutasi.

2. Pohon yang Dipesan. Mereka adalah himpunan bagian dari semua string "kurung" biner (varietas yang cocok).

3. Semua nilai terdekat yang lebih kecil, seperti di kertas ( 1 ). Anda tidak hanya dapat memampatkan di kedua dimensi; diijinkan "nilai lebih kecil" array dalam satu arah adalah bagian kecil dari daftar , dan karenanya Anda perlu menyimpan kurang dari n lg ( n ) bit.$\{0,...,n-1\}^n$$n \lg(n)$

Lihat juga tesis Ankur Gupta , dengan penekanan pada data kompresibel.

Jika berbicara tentang struktur data sufiks succit, yang satu ini oleh Navarro dan Mäkinen benar-benar bagus: http://portal.acm.org/citation.cfm?doid=1216370.1216372

Sekarang ada buku tentang masalah ini: Struktur Data Ringkas: Pendekatan Praktis, oleh Gonzalo Navarro. https://dl.acm.org/citation.cfm?id=3092586