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

Структура данных, эффективная как для хранения в памяти, так и для запросов

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

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

• неявно , если это занимаетнемного места, ${\displaystyle Z+O(1)}$
• лаконичным, если это занимает немного места, и ${\displaystyle Z+o(Z)}$
• компактный, если он занимает немного места. ${\displaystyle O(Z)}$

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

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

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

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

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

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

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

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

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

• ${\displaystyle \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]}$

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

Решения с энтропийным сжатием

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

1. Якобсон, Г. Дж. (1988). Сжатые статические структуры данных (диссертация доктора философии). Питтсбург, Пенсильвания: Университет Карнеги-Меллона.
2. Raman, R.; V. Raman; S. S Rao (2002). «Краткие индексируемые словари с приложениями к кодированию k-арных деревьев и мультимножеств». Труды тринадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 233–242. arXiv : 0705.0552 . CiteSeerX 10.1.1.246.3123 . doi :10.1145/1290672.1290680. ISBN  0-89871-513-X.
3. Садакане, К.; Р. Гросси (2006). «Вдавливание сжатых структур данных в границы энтропии» (PDF) . Труды семнадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . стр. 1230–1239. ISBN 0-89871-605-5. Архивировано из оригинала (PDF) 29-09-2011.
4. Якобсон, Г. (1 ноября 1989 г.). Статические деревья и графы, эффективные с точки зрения пространства (PDF) . 30-й симпозиум IEEE по основам компьютерной науки. doi :10.1109/SFCS.1989.63533. Архивировано из оригинала (PDF) 2016-03-12.
5. Гонсалес, Р.; С. Грабовски; В. Мякинен; Г. Наварро (2005). «Практическая реализация ранжирования и выборочных запросов» (PDF) . Постерные материалы 4-го семинара по эффективным и экспериментальным алгоритмам (WEA) . стр. 27–38.
6. Кларк, Дэвид (1996). Компактные пат-деревья (PDF) (диссертация). Университет Ватерлоо.
7. Vigna, S. (2008). "Broadword Implementation of Rank/Select Queries" (PDF) . Experimental Algorithms . Lecture Notes in Computer Science. Vol. 5038. pp. 154–168. CiteSeerX 10.1.1.649.8950 . doi :10.1007/978-3-540-68552-4_12. ISBN  978-3-540-68548-7. S2CID  13963489.
8. Бродник, А.; Дж. И. Манро (1999). «Членство в постоянном времени и почти минимальное пространство» (PDF) . SIAM J. Comput . 28 (5): 1627–1640. CiteSeerX 10.1.1.530.9223 . doi :10.1137/S0097539795294165. 
9. Пэтрашку, М. (2008). "Succincter" (PDF) . Основы компьютерной науки, 2008. FOCS'08. IEEE 49-й ежегодный симпозиум IEEE по . стр. 305–313.
10. Belazzougui, Djamal; Boldi, Paolo; Pagh, Rasmus; Vigna, Sebastiano (2009-01-04). "Monotone Minimal Perfect Hashing: Searching a Sorted Table with O(1) Accesses". Труды двадцатого ежегодного симпозиума ACM-SIAM по дискретным алгоритмам . Филадельфия, Пенсильвания: Общество промышленной и прикладной математики: 785–794. doi : 10.1137/1.9781611973068.86 . ISBN 978-0-89871-680-1.
11. Assadi, Sepehr; Farach-Colton, Martín; Kuszmaul, William (январь 2023 г.), «Жесткие границы для монотонного минимального совершенного хеширования», Труды ежегодного симпозиума ACM-SIAM по дискретным алгоритмам (SODA) 2023 г. , Филадельфия, Пенсильвания: Общество промышленной и прикладной математики, стр. 456–476, arXiv : 2207.10556 , doi : 10.1137/1.9781611977554.ch20, ISBN 978-1-61197-755-4, получено 2023-04-28
12. Раман, Раджив; Рао, Сатти Шриниваса (2003), «Краткие динамические словари и деревья», Automata, Languages ​​and Programming , Берлин, Гейдельберг: Springer Berlin Heidelberg, стр. 357–368, doi :10.1007/3-540-45061-0_30, ISBN 978-3-540-40493-4, получено 2023-04-28
13. Бендер, Майкл А.; Фарах-Колтон, Мартин; Кусзмаул, Джон; Кусзмаул, Уильям; Лю, Минмоу (09.06.2022). «Об оптимальном соотношении времени и пространства для хэш-таблиц». Труды 54-го ежегодного симпозиума ACM SIGACT по теории вычислений . Нью-Йорк, США: ACM. С. 1284–1297. arXiv : 2111.00602 . doi : 10.1145/3519935.3519969. hdl : 1721.1/146419. ISBN 9781450392648. S2CID  240354692.
14. Ли, Тяньсяо; Лян, Цзинсюнь; Ю, Хуачэн; Чжоу, Жэньфэй (2023). «Точные нижние границы клеточного зонда для динамических кратких словарей». arXiv : 2306.02253 [cs.DS].
15. Надис, Стив (8 февраля 2024 г.). «Ученые нашли оптимальный баланс между хранением данных и временем». Журнал Quanta .
16. Паг, Расмус (1998-01-28). "Низкая избыточность в словарях с O(1) временем поиска в худшем случае". Серия отчетов BRICS . 5 (28). doi : 10.7146/brics.v5i28.19434 . ISSN  1601-5355.
17. Pagh, Rasmus (январь 2001 г.). «Низкая избыточность в статических словарях с постоянным временем запроса». SIAM Journal on Computing . 31 (2): 353–363. doi :10.1137/s0097539700369909. ISSN  0097-5397.
18. Patrascu, Mihai (октябрь 2008 г.). "Succincter". 2008 49-й ежегодный симпозиум IEEE по основам компьютерной науки . IEEE. стр. 305–313. doi :10.1109/focs.2008.83. ISBN 978-0-7695-3436-7. S2CID  257721481.
19. Ю, Хуачэн (2020-06-22). «Почти оптимальный статический краткий словарь Лас-Вегаса». Труды 52-го ежегодного симпозиума ACM SIGACT по теории вычислений . Нью-Йорк, Нью-Йорк, США: ACM. стр. 1389–1401. arXiv : 1911.01348 . doi : 10.1145/3357713.3384274. ISBN 9781450369794. S2CID  207780523.
20. Белаззуги, Джамаль. «Хеширование, смещение и сжатие» (PDF) .