WikiDer > Краткая структура данных

Succinct data structure

В Информатика, а лаконичная структура данных это структура данных который занимает пространство, "близкое" к теоретико-информационный нижняя граница, но (в отличие от других сжатых представлений) по-прежнему позволяет выполнять эффективные операции запроса. Первоначально эта концепция была представлена ​​Якобсоном.[1] закодировать битовые векторы, (без ярлыка) деревья, и планарные графы. В отличие от общего сжатие данных без потерь алгоритмы, сжатые структуры данных сохраняют возможность использовать их на месте, не распаковывая их предварительно. Связанное с этим понятие - понятие сжатая структура данных, в котором размер структуры данных зависит от конкретных представляемых данных.

Предположим, что это оптимальное с теоретической точки зрения количество бит, необходимое для хранения некоторых данных. Представление этих данных называется:

  • скрытый если потребуется кусочки космоса,
  • лаконичный если потребуется кусочки пространства, и
  • компактный если потребуется биты пространства.

Например, структура данных, использующая бит памяти компактен, бит лаконичен, биты также лаконичны, и бит неявно.

Таким образом, неявные структуры обычно сводятся к хранению информации с использованием некоторой перестановки входных данных; самый известный пример этого - куча.

Краткие словари

Краткие индексируемые словари, также называемые ранг / выбор словари, составляют основу ряда лаконичных техник представления, в том числе бинарные деревья, -арные деревья и мультимножества,[2] а также суффиксные деревья и массивы.[3] Основная проблема - сохранить подмножество Вселенной , обычно представлен в виде битового массива куда если только Индексируемый словарь поддерживает обычные методы для словарей (запросы и вставки / удаления в динамическом случае), а также следующие операции:

за .

Другими словами, возвращает количество элементов, равное до позиции пока возвращает позицию -е появление .

Есть простое представление[4] который использует бит пространства хранения (исходный битовый массив и вспомогательная конструкция) и опоры классифицировать и Выбрать в постоянное время. Он использует идею, аналогичную идее запросы с минимальным диапазоном; перед тем, как остановиться на подзадаче ограниченного размера, выполняется постоянное количество рекурсий. Битовый массив разделен на большие блоки размера биты и маленькие блоки размера биты. Для каждого большого блока ранг его первого бита хранится в отдельной таблице. ; каждая такая запись занимает бит в общей сложности бит памяти. В большом блоке другой каталог хранит ранг каждого из небольшие блоки, которые он содержит. Разница здесь в том, что ему нужно только битов для каждой записи, так как нужно сохранять только отличия от ранга первого бита в содержащем большом блоке. Таким образом, эта таблица занимает всего биты. Таблица поиска затем можно использовать, который хранит ответ на каждый возможный запрос ранжирования в битовой строке длиной за ; это требует бит места для хранения. Таким образом, поскольку каждая из этих вспомогательных таблиц принимает пространство, эта структура данных поддерживает ранговые запросы в время и биты пространства.

Чтобы ответить на запрос для за постоянное время алгоритм постоянного времени вычисляет:

На практике таблица поиска могут быть заменены поразрядными операциями и меньшими таблицами, которые можно использовать для определения количества битов, установленных в небольших блоках. Это часто бывает выгодно, поскольку сжатые структуры данных находят свое применение в больших наборах данных, и в этом случае пропуски кеша становятся намного более частыми, и шансы вытеснения таблицы поиска из более близких кешей ЦП становятся выше.[5] Запросы выбора можно легко поддерживать, выполняя двоичный поиск в той же вспомогательной структуре, которая используется для классифицировать; однако это требует время в худшем случае. Более сложная структура с использованием биты дополнительного хранилища могут использоваться для поддержки Выбрать в постоянное время.[6] На практике многие из этих решений имеют скрытые константы в обозначения, которые преобладают до того, как станет очевидным какое-либо асимптотическое преимущество; реализации с использованием широких слов и блоков, выровненных по словам, на практике часто работают лучше.[7]

Энтропийно сжатые словари

В космический подход можно улучшить, отметив, что есть отчетливый -подмножества (или двоичные строки длины с точно 1), и, таким образом, теоретико-информационная нижняя граница количества битов, необходимых для хранения . Существует краткий (статический) словарь, который достигает этой границы, а именно, используя Космос.[8] Эта структура может быть расширена для поддержки классифицировать и Выбрать запросы и принимает Космос.[2] Правильный классифицировать однако запросы в этой структуре ограничены элементами, содержащимися в наборе, аналогично тому, как работают минимальные идеальные хеш-функции. Эту границу можно свести к компромиссу между пространством и временем, сократив пространство для хранения словаря до с запросами, принимающими время.[9]

Примеры

А строка с завершающим нулем (C строка) берет Z +1 пробел и, следовательно, неявно. Строка произвольной длины (Строка Паскаля) берет Z + журнал (Z) пространство и, таким образом, является лаконичным. Если есть максимальная длина - что имеет место на практике, поскольку 232 = 4 ГиБ данных - очень длинная строка, а 264 = 16 EiB данных больше, чем любая строка на практике - тогда строка с длиной также неявна, принимая Z + k пространство, где k - количество данных, представляющих максимальную длину (например, 64 бита).

Когда необходимо закодировать последовательность элементов переменной длины (например, строк), существуют различные возможности. Прямой подход состоит в том, чтобы сохранить длину и элемент в каждой записи - затем их можно разместить один за другим. Это позволяет эффективный следующий, но не находит kй пункт. Альтернативой является размещение элементов по порядку с разделителем (например, строка с завершающим нулем). При этом вместо длины используется разделитель, что значительно медленнее, так как всю последовательность необходимо сканировать на наличие разделителей. Оба они занимают мало места. Альтернативный подход - внеполосное разделение: элементы можно просто разместить один за другим без разделителей. Затем границы элементов могут быть сохранены как последовательность длины или, лучше сказать, смещений в этой последовательности. В качестве альтернативы, вместе с ним кодируется отдельная двоичная строка, состоящая из единиц в позициях, где начинается элемент, и нулей во всех остальных местах. Учитывая эту строку, функция может быстро определить, где начинается каждый элемент, по его индексу.[10] Это компактный но нет лаконично, как нужно 2Z пространство, которое есть O (Z).

Другой пример - представление двоичное дерево: произвольное двоичное дерево на узлы могут быть представлены в битов, поддерживая при этом различные операции на любом узле, включая поиск его родителя, его левого и правого дочерних элементов и возврат размера его поддерева, каждое в постоянное время. Количество различных бинарных деревьев на узлы . Для больших , речь идет о ; таким образом нам нужно как минимум около биты для его кодирования. Таким образом, сжатое двоичное дерево заняло бы только бит на узел.

Смотрите также

Рекомендации

  1. ^ Джейкобсон, Дж. Дж (1988). Краткие статические структуры данных (Кандидатская диссертация). Питтсбург, Пенсильвания: Университет Карнеги-Меллона.
  2. ^ а б Raman, R .; В. Раман; С. С. Рао (2002). «Краткие индексируемые словари с приложениями для кодирования k-арных деревьев и мультимножеств». Материалы тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам. стр.233–242. arXiv:0705.0552. CiteSeerX 10.1.1.246.3123. Дои:10.1145/1290672.1290680. ISBN 0-89871-513-X.
  3. ^ Sadakane, K .; Р. Гросси (2006). "Сжатие сжатых структур данных до границ энтропии" (PDF). Материалы семнадцатого ежегодного симпозиума ACM-SIAM по дискретному алгоритму. С. 1230–1239. ISBN 0-89871-605-5. Архивировано из оригинал (PDF) 29 сентября 2011 г.
  4. ^ Якобсон, Г. (1 ноября 1989 г.). Компактные статические деревья и графы (PDF). 30-й симпозиум IEEE по основам компьютерных наук. Дои:10.1109 / SFCS.1989.63533. Архивировано из оригинал (PDF) на 2016-03-12.
  5. ^ González, R .; С. Грабовски; В. Мякинен; Г. Наварро (2005). «Практическая реализация запросов на ранжирование и выборку» (PDF). Объем постерных материалов 4-го семинара по эффективным и экспериментальным алгоритмам (WEA). С. 27–38.
  6. ^ Кларк, Дэвид (1996). Компактные деревья для похлопывания (PDF) (Кандидатская диссертация). Университет Ватерлоо.
  7. ^ Винья, С. (2008). Широкая реализация запросов ранжирования / выбора (PDF). Экспериментальные алгоритмы. Конспект лекций по информатике. 5038. С. 154–168. CiteSeerX 10.1.1.649.8950. Дои:10.1007/978-3-540-68552-4_12. ISBN 978-3-540-68548-7.
  8. ^ Бродник, А .; Дж. И. Манро (1999). «Принадлежность к постоянному времени и почти минимальному пространству» (PDF). SIAM J. Comput. 28 (5): 1627–1640. CiteSeerX 10.1.1.530.9223. Дои:10.1137 / S0097539795294165.
  9. ^ Пэтрашку, М. (2008). "Succincter" (PDF). Основы информатики, 2008. FOCS'08. 49-й ежегодный симпозиум IEEE по. С. 305–313.
  10. ^ Belazzougui, Джамал. "Хешировать, перемещать и сжимать" (PDF).