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

В информатике краткая структура данных — это структура данных , которая использует объем пространства, «близкий» к нижней границе теории информации , но (в отличие от других сжатых представлений) по-прежнему позволяет выполнять эффективные операции запроса. Первоначально эта концепция была предложена Джейкобсоном. для кодирования битовых векторов , (немаркированных) деревьев и плоских графов . В отличие от обычных алгоритмов сжатия данных без потерь , краткие структуры данных сохраняют возможность использовать их на месте, без предварительного их распаковки. С этим связано понятие сжатой структуры данных , поскольку размер хранимых или закодированных данных аналогичным образом зависит от конкретного содержания самих данных.

Предположим, что $Z$ — это теоретико-информационное оптимальное количество бит, необходимое для хранения некоторых данных. Представление этих данных называется:

• неявно, если это требует $Z+O(1)$ кусочки пространства,
• кратко, если это займет $Z+o(Z)$ кусочки пространства и
• компактный, если потребуется $O(Z)$ кусочки пространства.

Например, структура данных, использующая $2Z$ биты хранения компактны, $Z+{\sqrt {Z}}$ биты краткие, $Z+\lg Z$ бит также является кратким, и $Z+3$ бит является неявным.

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

Краткие индексируемые словари

Краткие индексируемые словари, также называемые словарями ранга/выбора , составляют основу ряда методов краткого представления, включая двоичные деревья . $k$-арные деревья и мультимножества , а также суффиксные деревья и массивы . Основная проблема заключается в хранении подмножества $S$ вселенной $U=[0\dots n)=\{0,1,\dots ,n-1\}$, обычно представленный в виде битового массива $B[0\dots n)$ где $B[i]=1$ если только $i\in S.$ Индексируемый словарь поддерживает обычные методы работы со словарями (запросы и вставки/удаления в динамическом случае), а также следующие операции:

• $\mathbf {rank} _{q}(x)=|\{k\in [0\dots x]:B[k]=q\}|$
• $\mathbf {select} _{q}(x)=\min\{k\in [0\dots n):\mathbf {rank} _{q}(k)=x\}$

для $q\in \{0,1\}$.

Другими словами, $\mathbf {rank} _{q}(x)$ возвращает количество элементов, равное $q$ до позиции $x$ пока $\mathbf {select} _{q}(x)$ возвращает позицию $x$-е появление $q$.

Существует простое представление который использует $n+o(n)$ биты памяти (исходный битовый массив и $o(n)$ вспомогательная структура) и поддерживает ранжирование и выбор в постоянное время. Он использует идею, аналогичную той, что используется для запросов с минимальным диапазоном ; существует постоянное количество рекурсий, прежде чем остановиться на подзадаче ограниченного размера. Битовый массив $B$ разбит на большие блоки размером $l=\lg ^{2}n$ биты и небольшие блоки размером $s=\lg n/2$ биты. Для каждого большого блока ранг его первого бита хранится в отдельной таблице. $R_{l}[0\dots n/l)$; каждая такая запись занимает $\lg n$ бит в общей сложности $(n/l)\lg n=n/\lg n$ биты памяти. Внутри большого блока еще один каталог $R_{s}[0\dots l/s)$ хранит ранг каждого из $l/s=2\lg n$ небольшие блоки, которые он содержит. Разница здесь в том, что нужно только $\lg l=\lg \lg ^{2}n=2\lg \lg n$ бит для каждой записи, поскольку необходимо сохранять только различия от ранга первого бита в содержащем большом блоке. Таким образом, эта таблица занимает в общей сложности $(n/s)\lg l=4n\lg \lg n/\lg n$ биты. Таблица поиска $R_{p}$ затем можно использовать, чтобы сохранить ответ на каждый возможный запрос ранга в битовой строке длины $s$ для $i\in [0,s)$; это требует $2^{s}s\lg s=O({\sqrt {n}}\lg n\lg \lg n)$ немного места для хранения. Таким образом, поскольку каждая из этих вспомогательных таблиц занимает $o(n)$ пространстве эта структура данных поддерживает ранжированные запросы в $O(1)$ время и $n+o(n)$ кусочки пространства.

Чтобы ответить на запрос о $\mathbf {rank} _{1}(x)$ в постоянное время алгоритм постоянного времени вычисляет:

• $\mathbf {rank} _{1}(x)=R_{l}[\lfloor x/l\rfloor ]+R_{s}[\lfloor x/s\rfloor ]+R_{p}[x\lfloor x/s\rfloor ,x{\text{ mod }}s]$

На практике таблица поиска $R_{p}$ могут быть заменены побитовыми операциями и таблицами меньшего размера, которые можно использовать для определения количества битов, установленных в маленьких блоках. Это часто бывает полезно, поскольку краткие структуры данных находят свое применение в больших наборах данных, и в этом случае промахи в кэше становятся гораздо более частыми, и вероятность исключения таблицы поиска из ближайших кэшей ЦП становится выше. Запросы выбора можно легко поддерживать, выполняя двоичный поиск по той же вспомогательной структуре, что и для Rank ; однако это требует $O(\lg n)$ время в худшем случае. Более сложная структура с использованием $3n/\lg \lg n+O({\sqrt {n}}\lg n\lg \lg n)=o(n)$ биты дополнительной памяти могут использоваться для поддержки выбора в постоянное время. На практике многие из этих решений имеют скрытые константы в $O(\cdot )$ обозначения, которые доминируют до того, как станет очевидным какое-либо асимптотическое преимущество; реализации, использующие операции с расширенными словами и блоки с выравниванием по словам, на практике часто работают лучше.

Энтропийно-сжатые решения

The $n+o(n)$ космический подход можно улучшить, отметив, что существуют $\textstyle {\binom {n}{m}}$ отчетливый $m$-подмножества $[n)$ (или двоичные строки длины $n$ точно с $m$ 1) и, таким образом, $\textstyle {\mathcal {B}}(m,n)=\lceil \lg {\binom {n}{m}}\rceil$ — это нижняя граница теории информации для количества бит, необходимых для хранения $B$. Существует краткий (статический) словарь, который достигает этой границы, а именно, используя ${\mathcal {B}}(m,n)+o({\mathcal {B}}(m,n))$ космос. Эту структуру можно расширить для поддержки ранжирования и выбора , а также дублей. запросов ${\mathcal {B}}(m,n)+O(m+n\lg \lg n/\lg n)$ космос. Однако запросы правильного ранга в этой структуре ограничены элементами, содержащимися в наборе, аналогично тому, как работают минимальные совершенные функции хеширования. Эту границу можно свести к компромиссу между пространством и временем, уменьшив объем памяти словаря до ${\mathcal {B}}(m,n)+O(nt^{t}/\lg ^{t}n+n^{3/4})$ с запросами, принимающими $O(t)$ время.

Также возможно создать индексируемый словарь, поддерживающий ранг (но не выбор), который использует менее $\textstyle {\mathcal {B}}(m,n)$ биты. Такой словарь называется монотонной минимальной совершенной хеш-функцией и может быть реализован с использованием всего лишь $O(m\log \log \log n)$ биты.

Краткие хеш-таблицы

Краткая хеш-таблица, также известная как краткий неупорядоченный словарь, представляет собой структуру данных, в которой хранятся $m$ ключи от вселенной $\{0,1,\dots ,n-1\}$ используя пространство $(1+o(1)){\mathcal {B}}(m,n)$ бит и при этом поддерживают запросы членства в постоянное ожидаемое время. Если краткая хэш-таблица также поддерживает вставки и удаления с постоянным ожидаемым временем, то она называется динамической , в противном случае она называется статической.

Первая динамическая краткая хэш-таблица была создана Раманом и Рао в 2003 году. В случае, когда $n={\text{poly}}(m)$, их решение использует пространство ${\mathcal {B}}(m,n)+O(m\log \log m)$ биты. Впоследствии было показано, что эту пространственную границу можно улучшить до ${\mathcal {B}}(m,n)+O(m\log \log \log \cdots \log m)$ бит для любого постоянного числа логарифмов и немного позже эта граница также оказалась оптимальной. Последнее решение поддерживает все операции в худшем случае с постоянным временем с высокой вероятностью.

Первая статическая краткая хэш-таблица была создана Пагом в 1999 году. В случае, когда $n={\text{poly}}(m)$, их решение использует пространство ${\mathcal {B}}(m,n)+O(m(\log \log m)^{2}/\log m)$ бит и поддерживает для наихудшего случая запросы с постоянным временем . Эта граница впоследствии была улучшена до ${\mathcal {B}}(m,n)+m/{\text{poly}}\log m$ биты, а затем ${\mathcal {B}}(m,n)+{\text{poly}}\log m$ биты. Тогда как первые два решения поддерживает запросы с постоянным временем наихудшего случая, последний поддерживает запросы с постоянным ожидаемым временем. Окончательное решение также требует доступа к справочной таблице размера $n^{\epsilon }$, но эта таблица поиска не зависит от набора сохраняемых элементов.

Другие примеры

Строка произвольной длины ( строка Паскаля ) занимает пространство Z + log( Z ) и поэтому является краткой. Если существует максимальная длина – что и имеет место на практике, поскольку 2 ³² = 4 ГиБ данных — это очень длинная строка, а 2 ⁶⁴ = 16 EiB данных на практике больше, чем любая строка – тогда строка с длиной также подразумевается, занимая Z + k пространство , где k — количество данных, представляющее максимальную длину (например, 64 бита).

Когда необходимо закодировать последовательность элементов переменной длины (например, строк), существуют различные возможности. Прямой подход заключается в сохранении длины и элемента в каждой записи, а затем их можно размещать друг за другом. Это позволяет эффективно использовать следующий, но не находить k -й элемент. Альтернативой является размещение элементов по порядку с помощью разделителя (например, строки с нулевым завершением ). При этом вместо длины используется разделитель, и это существенно медленнее, поскольку необходимо сканировать всю последовательность на наличие разделителей. Оба они экономят пространство. Альтернативный подход — внеполосное разделение: элементы можно просто размещать один за другим, без разделителей. Границы элементов затем могут быть сохранены как последовательность длин или, лучше, смещений в этой последовательности. Альтернативно, вместе с ней кодируется отдельная двоичная строка, состоящая из 1 в позициях, где начинается элемент, и 0 во всех остальных местах. Учитывая эту строку, $select$ Функция может быстро определить, где начинается каждый элемент, учитывая его индекс. Это компактно , но не лаконично, так как занимает 2 Z пространства, что равно O( Z ).

Другой пример — представление двоичного дерева : произвольное двоичное дерево на $n$ узлы могут быть представлены в $2n+o(n)$ бит, поддерживая при этом множество операций над любым узлом, включая поиск его родителя, его левого и правого дочернего элемента и возврат размера его поддерева, каждый из которых за постоянное время. Количество различных бинарных деревьев на $n$ узлы это ${\tbinom {2n}{n}}$$/(n+1)$. Для больших $n$, это о $4^{n}$; таким образом, нам нужно как минимум около $\log _{2}(4^{n})=2n$ бит для его кодирования. Таким образом, краткое двоичное дерево будет занимать всего $2$ бит на узел.

См. также

• Минимальная идеальная хэш-функция
• Краткие неинтерактивные аргументы знаний