Краткий обзор структур данных?

Статья Фишера за этот месяц напомнила мне, как мало я знаю об искусстве кратких структур данных и алгоритмах их использования.

Для тех, кто не знает о сжатых структурах данных:

Учитывая комбинаторную структуру, с (n) различными конфигурациями и известным «полезным» представлением . Существует ли «краткая» структура данных, которая занимает около битов, но позволяет нам выполнять операции так быстро, как мы можем с нормальным представлением ?$R(n)$$\lg(a(n))$$R$

Лучшие из них меня интересуют, если кто-то хотел бы развлечь дискуссию

1. Суффиксные массивы. Они являются подмножеством всех перестановок.

2. Упорядоченные деревья. Они являются подмножеством всех двоичных строк в скобках (совпадающее разнообразие).

3. Все ближайшие меньшие значения, как в статье ( 1 ). Вы можете не только сжать в обоих измерениях; допустимые массивы «меньшего значения» в одном направлении представляют собой небольшое подмножество списков , и, следовательно, вам необходимо хранить менее битов.$\{0,...,n-1\}^n$$n \lg(n)$

Также ознакомьтесь с тезисом Анкура Гупты с акцентом на сжимаемые данные.

Если говорить о структурах данных succit Суффикс, то это Наварро и Мякинен действительно хороши: http://portal.acm.org/citation.cfm?doid=1216370.1216372

В настоящее время книга Гонсало Наварро на тему: Компактные структуры данных: практический подход. https://dl.acm.org/citation.cfm?id=3092586