Коты в коробочках, или Компактные структуры данных

image


Как быть, если дерево поиска разрослось на всю оперативку и вот-вот подопрет корнями соседние стойки в серверной? Что делать с инвертированным индексом, жадным до ресурсов? Завязывать ли с разработкой под Android, если пользователю прилетает «Память телефона заполнена», а приложение едва на половине загрузки важного контейнера?


В целом, можно ли сжать структуру данных, чтобы она занимала заметно меньше места, но не теряла присущих ей достоинств? Чтобы доступ к хэш-таблице оставался быстрым, а сбалансированное дерево сохраняло свои свойства. Да, можно! Для этого и появилось направление информатики «Succinct data structures», исследующее компактное представление структур данных. Оно развивается с конца 80-х годов и прямо сейчас переживает расцвет в лучах славы big data и highload.


А тем временем на Хабре найдется ли герой, способный пересковоговорить три раза подряд
[səkˈsɪŋkt]?


Дверь в мир компактности


Итак, структура данных считается компактной (succinct), если она:


  • Занимает количество бит, близкое к информационно-теоретической нижней границе.
  • Не требует предварительной распаковки для полноценного использования.

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


Привычные, «мейнстримовые» реализации графов, хэш-таблиц и прочего тоже не годятся. Взять хотя бы указатели на дочерние элементы в дереве поиска. Они отъедают порядочно места: $O(MN)$, где $M$ — длина указателя, а $N$ — количество узлов в дереве. Зато succinct реализация дерева позволяет улучшить асимптотику до $2N + o(N)$, что близко к теоретической нижней границе $2N − Θ(log N)$ для дерева из $N$ узлов. При длине указателя $M=8$ байт это означает переход от $O(8N)$ к совершенно другому порядку асимптотики — всего лишь $2N$, если учитывать, что $o(N)$ — пренебрежимо малая величина относительно $N$.


Компактные (succinct) структуры данных — это сжатые представления для битовых векторов, мультимножеств, планарных графов и других всеми любимых классических структур. Зачастую они статические, построенные единожды и не меняющиеся в процессе использования. Есть и исключения — succinct-структуры с быстрыми операциями добавления и удаления элементов.


В основе большинства компактных структур лежит концепция так называемого компактного индексируемого словаря. Это — частный случай битовой карты (bitmap, bitset). Сама по себе битовая карта идеальна для проверки вхождения элементов в некое множество. Если элемент включен в множество, то значение бита по заданному индексу устанавливается в 1, если нет — сбрасывается в 0. Жизненный пример — inode-битмапа ext4, UFS и других юниксовых файловых систем. Она хранит данные о том, какие записи в таблице индексных дескрипторов заняты, а какие — свободны.


Компактный индексируемый словарь — это та же битовая карта, но дополненная двумя операциями: rank и select. Эти операции — слоны, на которых зиждется мир succinct. Грубо говоря, rank — это подсчет количества элементов, а select — поиск элемента:


  • $rank_x(i)$ возвращает количество бит, равных $x$, чьи индексы лежат на отрезке $[0; i]$. Так как $x$ — значение бита, то он может быть равен исключительно 0 или 1.
  • $select_x(j)$ возвращает индекс $j$-го бита, равного $x$. Здравый смысл говорит, что нулевого вхождения не бывает, есть только первое. Поэтому $inline$j > 0$inline$: подсчет ведется от единицы. Кроме того, $j$ не может превышать суммарное количество битов в словаре, равных $x$.

Допустим, у нас есть индексируемый словарь, в котором 4 из 7 бит установлены. Тогда $rank_1$ и $select_1$ примут следующие значения:



Пример индексируемого словаря и расчета для него $rank_1$, $select_1$.


Внимательный читатель заметит, что select — обратная операция для rank. Если $rank_1(5) = 4$, то $select_1(4)=5$.


У кого-нибудь возникло дежавю при виде $rank_1(i)$? А все потому, что эта операция обобщает Вес Хэмминга — количество ненулевых символов в последовательности. Применительно к бинарным последовательностям Вес Хэмминга также называется popcount (population count).


Rank/select применимы и для сброшенных битов. Вот пример расчета $rank_0$ и $select_0$ для битов, равных 0:



Пример компактного индексируемого словаря и расчета для него $rank_0$, $select_0$.


Распилить дерево на битики


Используем же это знание, чтобы построить компактное префиксное дерево! Префиксные деревья хороши для поиска строк по префиксу. С их помощью зачастую реализуется выпадающий список поисковых подсказок (саджест). Подход к succinct'изации префиксного дерева предельно обобщенный и по максимуму демонстрирует весь изюм компактных структур. В отличие от бинарного дерева, для которого выведены частные формулы, мешающие увидеть общую картину.


Популярнее всего три метода компактного представления деревьев:


  • BP (balanced parentheses) — сбалансированные скобочные последовательности.
  • DFUDS (depth-first unary degree sequence) — последовательности единично-закодированных узлов, сортированных поиском в глубину.
  • LOUDS (level-ordered unary degree sequences) — последовательности единично-закодированных узлов, сортированных по уровням.

Что за подозрительная логическая цепочка перевода «unary degree» в «единично-закодированный узел»? Что ж. Unary degree в этих названиях означает способ кодирования узлов дерева последовательностью единиц по количеству дочерних узлов, обязательно с нулем в прицепе.


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


Остановимся на методе LOUDS. Поняв его, не составит труда разобраться с двумя другими. К тому же, в прошлом году LOUDS-деревья отметили свой 30-й день рождения! Дополнительные полезные операции для LOUDS-деревьев реализуются за $O(1)$: найти количество потомков узла; вычислить номер потомка узла среди всех его потомков (первый потомок, второй, $i$-ый и т.д.); найти $i$-ого потомка. Недостаток LOUDS — отсутствие эффективного алгоритма подсчета количества узлов поддерева.


Суть метода проста: хранить ключи узлов дерева и всю ценную информацию в обычном массиве, а структуру дерева представить как последовательность бит. Итого имеем две статические структуры. Зато не нужно выделять память под указатели на узлы дерева: переходы между ними реализованы по формулам с активным применением rank/select.


Внимание, префиксное дерево:



Префиксное дерево, готовое к сжатию методом LOUDS.


Подготовим дерево к представлению в бинарном виде:


  1. Прикрепим дерево к фейковому корню. Он сыграет свою роль совсем скоро.
  2. Пронумеруем все узлы дерева уровень за уровнем слева направо, как при BFS (поиске в ширину). Фейковый корень игнорируется, а настоящий индексируется нулем.
  3. Закодируем узлы. Узел дерева кодируется последовательностью единиц, соответствующим прямым потомкам, плюс ноль. Если у узла четыре дочерних элемента, то он кодируется как 11110, а если ни одного — как 0. Фейковый корень кодируется в первую очередь. У него единственный потомок, поэтому его код 10.


Префиксное дерево с пронумерованными по уровням узлами. Узлы закодированы.


В процессе поуровневого обхода дерева формируется компактный индексируемый словарь — последовательность бит из склеенных сверху вниз и слева направо закодированных узлов. У нас это 21-битная последовательность. Кстати, она называется LBS (LOUDS Bit String).



Компактный индексируемый словарь для префиксного дерева.


Компактное префиксное дерево LOUDS построено. LBS для дерева с $N$ узлами (фейковый не в счет) занимает $2N+1$ бит. Осталось самое интересное — формулы для обхода дерева, превращенного в битовую карту.


Поиск первого потомка. Переход от узла $i$ к его первому дочернему узлу осуществляется по формуле:


$firstChild(i)= select_0(i + 1) - i$


$i$ — это номер узла, в предыдущей табличке проставленный фиолетовым.


Найдем первого потомка узла с индексом 3 (буква «а»):


$firstСhild(3) = select_0(3+1) - 3 = select_0(4) - 3 = 9 - 3 = 6$


Первый дочерний узел находится по индексу 6, и это буква «к». Применим формулу для корня дерева:


$firstChild(0) = select_0(0+1) - 0 = select_0(1) = 1$


Мы нашли лист с индексом 1, букву «и». Сходится! Стало ясно, зачем потребовался фейковый корень: для магии индексации узлов. Во избежание странных ошибок перед переходом к потомкам узла $i$ неплохо бы выяснить количество этих потомков. Ведь для листьев дерева, что не удивительно, формула дает неадекватный результат. Чтобы найти следующего за первым потомка, нужно к его индексу прибавить 1. Это логично, потому что потомки одного узла всегда находятся рядом, без промежутков. Но при итерации по ним нужно вовремя остановиться — определить, какой потомок считается последним.


Поиск последнего потомка узла $i$ проходит в два этапа: определение индекса последней единицы в коде узла — именно она обозначает данного потомка; а затем определение индекса самого потомка:


$lastChildPos(i) = select_0(i+2)-1$


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


$lastChild(i) = rank_1(lastChildPos(i)-1)$


Найдем последнего потомка узла 2 (буква «к»).


$lastChildPos(2) = select_0(2+2)-1=select_0(4)-1=9-1=8$


Бит по индексу 8 равен 1, следовательно, узел 2 — не лист, и мы можем найти индекс его последнего потомка:


$lastChild(i) = rank_1(8-1)=5$


Количество потомков. Простейший способ определить количество потомков — вычесть из индекса последнего потомка узла индекс его первого потомка и прибавить 1:


$childrenCount(i) = lastСhild(i) - firstСhild(i)+1$


Но допустим, у узла $i$ существует соседний узел $i+1$, который располагается на том же уровне дерева, что и $i$. Тогда количество потомков $i$ можно определить как разность индексов первых потомков узлов $i+1$ и $i$:


$childrenCount(i) = firstСhild(i+1) - firstСhild(i)$


Потомки узла также пронумерованы последовательно. Если первый потомок $i$ — это $j$, то второй — $j+1$ и так далее вплоть до потомка соседнего на этом уровне узла $i+1$ (если таковой есть).


Количество потомков листа «и» с индексом 1 ожидаемо нулевое:


$childrenCount(1) =(select_0(2+1) - 2) - (select_0(1+1) - 1) = 3 - 3 = 0$


Поиск родителя для узла $i$ организуется по формуле:


$parent(i) = rank_0(select_1(i+1) - 1) -1$


Воспользуемся ей для поиска родителя узла 6 (буква «к»):


$parent(6) = rank_0(select_1(7) - 1) -1 = rank_0(9) -1 = 3$


Это узел 3, буква «а».


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


Пара копеек про методы BP и DFUDS. У обоих методов пространственная асимптотика — $2N + o(N)$ бит для дерева из $N$ узлов, и оба они схожи представлением узла дерева в виде открывающих и закрывающих скобок.


BP (balanced parentheses) конвертирует дерево в последовательность скобок, по паре на каждый узел. Для этого дерево обходится в глубину; каждый узел посещается дважды. При первом посещении записывается открывающая скобка, при повторном — закрывающая. Между ними оказываются скобки дочерних элементов.


Последовательность скобок удобно представить в виде битовой карты, где 1 — открывающая скобка, а 0 — закрывающая. На быстрый поиск в ней заточены все формулы для работы с BP. В отличие от LOUDS, BP позволяет быстро подсчитать размер поддерева и определить ближайшего общего предка у двух узлов. А вот найти $i$-ого потомка гораздо сложнее, чем в LOUDS.


DFUDS (depth-first unary degree sequence) схож одновременно и с BP, и с LOUDS. С BP его объединяет обход дерева в глубину и его скобочное представление. А принцип расстановки скобок такой же, как принцип кодирования узлов в LOUDS. Перед обходом дерева заранее добавляем в скобочную последовательность одну открывающую скобку. Потом при обходе узлов записываем открывающие скобки по количеству потомков, плюс одну закрывающую. Получается, что локальность хранения потомков у DFUDS выше, чем у BP. Вычисление размера поддерева и поиск ближайшего общего предка осуществляются за $O(1)$. Зато определение высоты поддерева и поиск родителя на $j$-ом уровне — тяжелые для DFUDS операции.


Для наглядности сравним методы LOUDS, BP и DFUDS на примере мини-дерева.



Оранжевым цветом пронумерованы узлы дерева как при обходе в ширину (для LOUDS), синим — как при обходе в глубину (для BP и DFUDS).



LOUDS, BP и DFUDS представления дерева.


Не удивляйтесь, если в англоязычных работах увидите отличия в формулах. Среди математиков встречаются любители индексировать начиная с единицы. А некоторые разработчики считают слова rank и range созвучными, поэтому делают rank на полуинтервале $[0; i)$. Из-за необходимости сохранения симметричности rank/select они вычисляют $select(i)$ как $select(i+1)$. Зато некоторые формулы в таком виде выглядят короче.


Разреженный массив: взболтать, но не смешивать


Разреженный массив (sparse array) — еще одна структура, буквально созданная для сжатия. Размер такого массива порой на порядки превышает количество заполненных элементов. А пустые элементы либо принимают значение по умолчанию, либо помечаются чем-то вроде null. Разреженный массив маячит на горизонте всякий раз при необходимости хранить множество объектов и связей между ними. На ум сразу приходят графы друзей в социальных сетях, алгоритмы ранжирования поисковой выдачи, Excel-подобные таблицы, симуляторы электрических схем с миллиардами транзисторов в чипе.


Зачастую такие массивы по-лавкрафтовски циклопические, при наивной реализации не умещаются в оперативку, оставаясь фактически не заполненными. В зависимости от требований к памяти и скорости разреженные массивы превращают в куда более компактные хэш-таблицы, списки смежности, бинарные деревья… или подвергают succinct'изации.


Допустим, у нас есть разреженный массив строк. Прицепим к нему компактный индексируемый словарь. Что это даст?



Разреженный массив с битовой картой.


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



Массив без пустых элементов.


Вычисление индекса в сжатом массиве. После проверки присутствия элемента неплохо бы получить доступ к его значению в исходном массиве, то есть сопоставить индекс $i$ в индексируемом словаре индексу $j$ в сжатом массиве. Не сюрприз, что для этого используется rank:


$j = rank_1(i) -1$


Проверим, как обстоят дела с 8-м элементом: $bitmap[8] = 0$. Значит, в исходном массиве такого элемента нет. А что с элементом 7? $bitmap[7] = 1$. Получим его значение: $rank_1(7) - 1 = 3-1 = 2$. По индексу 2 находится «go».


Вычисление индекса в исходном массиве. Наверняка в массиве потребуется искать элементы по значению! Если данные не сортированы, поиск сводится к перебору за $O(N)$, где $N$ — количество не пустых элементов. Для найденного элемента $j$ может потребоваться получить его индекс $i$, как если бы массив не был ужат. Для этого воспользуемся select — обратной операцией к rank:


$i = select_1(j+1)$


Для примера отыщем строку «C++». В компактном массиве она находится по индексу 0. А ее индекс в исходном массиве равен $select_1(0+1) = 3$.


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


Конечно, для хранения $2^{30}$ элементов описанный способ не годится. Его применимость заканчивается там, где начинаются проблемы с разрастанием индекса. Но своя ниша у этого способа сжатия массивов и его вариаций, конечно, есть. Будничный пример — это реализация протокола BitTorrent. Битовая карта содержит информацию о скачанных сегментах файлов, и пиры обмениваются индексами имеющихся у них сегментов. Космический пример — варианты сегментированной передачи данных, которые используют марсоходы, Вояджеры и станция «Новые Горизонты», бороздящая транснептуновые просторы.


Описанные примеры succinct'изации префиксного дерева и разреженного массива построены на общем фундаменте. Он основан на несокрушимой вере в эффективность операций rank/select. Без нее вся теория компактных, но достаточно быстрых структур трещит по швам. От скорости rank и select зависит адекватность использования компактных структур за пределами диссертаций.


Эти операции в самом деле можно реализовать крайне эффективно: rank — за $O(1)$; select — за $O(lg (lg N))$, что тоже почти константа. И конечно без некоторых уловок не обойдется. А так как в любом произведении с запутанным сюжетом должна витать легкая недосказанность, на этом я и остановлюсь.


Интересные факты


Что такое теоретическая нижняя граница занимаемых ресурсов с точки зрения теории информации? Допустим, структура данных хранит множество из $N$ элементов. Чтобы идентифицировать их без коллизий, потребуется количество бит, не меньшее $X=log_2N$. $X$ и есть та самая нижняя граница, определенная по формуле Хартли. В некоторых частных случаях, обладая информацией о природе хранимых данных, структуру удается ужать еще эффективнее.


Считается ли сишная строка succinct структурой данных? Она содержит $N$ символов и завершается нулевым символом ASCII. Значит, занимает $N+1$ места, и поэтому… она succinct, а конкретнее, implicit! Что приводит нас к следующему вопросу.


Все ли succinct структуры одинаково компактны? Область исследования succinct определяет аж три вида компактных структур, различающихся пространственной сложностью:


  • compact — $O(N)$. Линейная сложность от $N$ — количества хранимых элементов. Самые «халявные» в плане требований к сжатию структуры. Так сказать разминка перед настоящим хардкором. Если уж мы заговорили про строки, то подходит следующий пример: последовательность строк переменной длины. Строки хранятся одна за другой, безо всяких разделителей. Для поиска отдельных строк формируется битовая карта, в которой все биты сброшены в 0 кроме битов с индексами, соответствующими началам строк. Эта структура занимает $O(2N)$ (множитель 2 при использовании символов Ландау правильнее всего опустить, но так нагляднее) и позволяет реализовать быстрый select для определения начала каждой строки в последовательности.
  • succinct — $N + o(N)$. Структуры с этой пространственной сложностью — то, что имеется ввиду под succinct data structures по умолчанию. Пример из мира строк: строки наподобие паскалевских (Pascal string), в которых последовательность символов предваряется их количеством. Они занимают $N + log(N)$.
  • implicit — $N + O(1)$. Структуры, дополнительно использующие фиксированное количество памяти. Примеры: куча (heap) и сишная строка. Обе структуры занимают $N + 1$.

Какие еще компактные структуры используются на практике? В смысле, не для научных публикаций по плану кафедры, а в качестве обкатанных боевых решений. В статье речь шла про succinct-префиксные деревья и разреженные массивы. Но это вершина айсберга, в глубине которого кроются компактные вейвлет-деревья, FM-индексы, RMQ (range minimum queries), LCP (longest common prefix), суффиксные массивы и огромное количество других структур, пригодных к succinct'изации. У каждой из них своя сфера использования и свои соотношения эффективности-компактности.


Эпилог


Компактные структуры данных здорово облегчают жизнь разработчикам поисковых движков, мобильных приложений, высоконагруженных сервисов. И не только. В принципе для любого проекта, работающего с растущими объемами данных, может наступить час X, когда бутылочным горлышком внезапно станут структуры данных в их текущей реализации.


Но succinct — не безвредный подорожник на коленку, от которого «хуже-то уж точно не будет». Succinct — это демон со множеством имен. Призвать и управлять им подвластно лишь искушенному демонологу, имеющему кристальное представление о хитростях, опасностях и могуществе succinct. Достоверно известно, что такие храбрецы живут среди нас. Они приложили руку к редактору метода ввода (IME) в Google, компактному представлению ДНК в Гонконгском университете. В MAPS.ME мы используем succinct-реализацию для обработки географических высот.


Как бы то ни было, знание о компактных представлениях для знакомых структур данных однажды может стать судьбоносным при принятии решений об оптимизации проекта. Ибо как сказал Дональд К., в 97 % случаев лучше забыть о микро-оптимизациях: преждевременная оптимизация корень всех зол. Однако мы не должны упускать наши возможности в оставшихся 3 %.


Что дальше?


Для тех, кто жаждет теоретических подробностей из мира succinct:



Для тех, кто желает поскорее перейти от теории к практике:


Mail.ru Group
Building the Internet

Comments 42

    +3
    Однозначно в закладки, спасибо
      0
      Материал топовый, однозначно к прочтению и не на один раз.
        +2
        SDS сложны в инжиниринге и требуют сложной операционной «обвязки». Обычно они статические. Хочешь что-то обновить — пересоздавай всё заново, что для больших структур неудобно. Динамические SDS возможны, некоторые, но они имеют гораздо худшее время произвольного чтения: O(log N) против O(1), что на практике может означать «на порядок и хуже». Ну и они на порядок-три сложнее в инжиниринге, чем их статические аналоги. Всё это пока что делает SDS непрактичными за пределами нескольких узких ниш, где без них ну просто никуда (например, биоинформатика). Затраты на разработку будут огромными, а выигрыш с экономической точки зрения — сомнительным. Проще старыми добрыми b-/lsm-tree всё делать.

        SDS хороши как индексы и self-индексы. Они могут ускорять выполнение некоторых операций. Хрестоматийный уже пример — суффиксные деревья для полнотекстового поиска по геному, сжатые графы социальных сетей, web-графы. Из более экзотических (пока) применений — кодирование распределений вероятностей. А то вероятностные алгоритмы есть, а вот вероятностными структурами данных, образно говоря, не намазано. Из еще более экзотических применений — «выжимки» структрированной информации из нейронных сетей. Да сколько угодно применений, когда в голове есть тервер и теория алгоритмов (а не только тервер и линейка). Потому что «струтктура данных» — это просто кодирование некоторого многомерного распределения в машинных кодах.

        Более жизненный пример. С помощью searchable sequence можно накладывать некую структуру (например, иерархическую) на неструктурированные массивы. Например, с помощью сжатой битовой карты с поддержкой rank/select можно допольно просто отобразить табилицу-построчник на сырой байтовый массив, с возможностью произвольной навигации по с строкам (привет, удобная постраничная прокрутка). SDS можно использовать как строительные кубики для создания практических решений с необходимимы свойствами.

        Высокая инженерная сложность не является фундаментальным препятствием. Со временем, компактные (compact), безизбыточные (succinct) и сжатые (compressed) структуры данных займут свое достойное место в инструментарии практикующих программистов.
          0
          Например, с помощью сжатой битовой карты с поддержкой rank/select можно допольно просто отобразить табилицу-построчник на сырой байтовый массив, с возможностью произвольной навигации по с строкам

          Есть JSON-парсеры, основанные на этой идее, например, hw-json.


          Статья с детальным описанием идеи semi-indices: https://www.researchgate.net/publication/221613393_Semi-indexing_semi-structured_data_in_tiny_space

            0
            Спасибо за ссылку. Да, сам так делаю.
          +3
          "[səkˈsɪŋkt]" три раза смог произнести, «пересковоговорить» не смог.
            0
            Эти операции в самом деле можно реализовать крайне эффективно: rank — за O(1); select — за O(lg(lg(N)), что тоже почти константа. И конечно без некоторых уловок не обойдется.

            Самое интересное-то и не написали!


            Интересно, насколько возрастет потребление памяти, ведь для выполнения rank за константу — точно какой-то предподсчет нужен. Мне очень интересно, остается ли какое-либо преимущество по сравнению с не succint деревом, например. Особенно, если вместо 64-битных указателей хранить номера детей, которые больше lg(N) бит не требуют.

              0
              С предподсчетом все не так страшно, как может показаться.

              Во-первых, спасают оптимизации на аппаратном уровне: в большинстве процессоров реализован popcnt, который быстро считает количество установленных битов в слове. Интел довольно давно разработал набор команд SSE4 с POPCNT для регистров 16, 32, 64 бита. AMD — аналогично. А также есть вариации с ускорением посредством SIMD.

              Если забыть про аппаратное ускорение, то конечно есть техники для предподсчета rank таким образом, чтобы не раздувать занимаемое пространство. Многие из них основываются на списках с пропусками для блоков битовой строки. Но это очень большая тема, тянет на отдельную статью с красивыми графиками сравнения производительности и занимаемых ресурсов.
                0
                rank за константу — точно какой-то предподсчет нужен.

                Я использовал у себя в проекте подобный подход. Мне нужно было хранить сбалансированное бинарное дерево. Для него даже никакого предрасчёта не потребовалось.


                Особенно, если вместо 64-битных указателей хранить номера детей,

                Для бинарного дерева даже номера не нужно хранить. Только сами данные.
                У меня ускорение действительно было по сравнению с обработкой дерева, "запакованного" классическим способом.

                  0
                  Если почитать про реализацию, по приведенным ссылкам (конкретно — в BitMagic), то можно увидеть, что за O(1) находится блок из 65536 бит, в котором потом осуществляется дальнейший поиск. Накладные расходы по памяти у них на один такой блок кроме самих бит блока: 4 байта (это для 32-битных индексов, для 64-битных должно быть соответственно 8) + 2 * 2 байта для ускорения поиска в самих блоках.
                  +1
                  Внимательный читатель заметит, что select — обратная операция для rank. Если rank1(5) = 4, то select1(4) = 5.

                  Да? Но ведь rank1(2) = 1, а select1(1) = 0.
                    0
                    Значения rank для битового массива — это неубывающая последовательность, в которой могут встречаться равные соседние элементы.
                    rank1(2) = 1, но также и rank1(0) = 1, rank1(1) = 1. select1(1) = 0 соответствует первому инкременту: rank1(0) = 1.
                      0
                      С этим я не спорю. Но всё же мне кажется, что select нельзя назвать обратной для rank операцией (т.к. описанное условие выполняется не всегда).
                        0
                        Если заранее ввести правила, по которым однозначно определяется, какой именно элемент принять за обратный, то все будет в порядке =)
                          0
                          Ок :)
                            0
                            Причина, по которой вщаимно-обратные rank/select определены не совсем «симметрично», в том, что так навигационные выражения, например, для LOUDS получаются короче. SDS десятилетиями оставались чисто теоретическим упражнением для ума, где оптимизировалась красота ассимптотических оценок в научных статьях.
                    +1
                    Хочу поделиться небольшим опытом использования LOUDS в задаче нахождения всех строк из заранее заданного набора как подстрок входной строки. Т.е. к примеру, есть 100 000 небольших (3-50 символов) строк-фильтров, их надо компактно хранить и уметь быстро найти все такие строки, которые являются подстрокой тестируемой.

                    LOUDS действительно сильно помогает даже с накладными расходами, о которых через предложение. К примеру, реализация double array trie потребляла бы раз в 5 больше памяти. На самом деле я использовал Aho–Corasick. Для этого в trie параллельно с массивом битов использовал массивы для хранения данных. К примеру, по тем же смещениям, что и rank1 (c небольшой корректировкой), в еще одном массиве лежат символы (8 bits, типа ASCII (К сожалению, я дальше не исследовал, но мне кажется, что тут можно сделать поддержку UTF-8 с довольно приличными характеристиками, когда в других реализация размер алфавита довольно ограничен.)), а так же в еще одном массиве битов информация о том, является ли данный символ концом какой-либо строки.
                    Такой же трюк для структуры Aho–Corasick, суффиксные и конечные ссылки (терминология из вики) так же хранятся в массивах, плюс битовые массивы для индикации есть ли у этого узла соответствующая ссылка.
                    Как можно заметить коэффициент у О-большое уже не такой уж и маленький, как в статье.
                    Может легко оказаться, что если найти разумный подход с N-граммами, то выгоднее хранить извлеченные подстроки из строк словаря в хеш-таблице, а сами строки отдельно.

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

                    Скорость работы при этом может оказаться сравнима, ну или, к примеру, достаточной для текущей бизнес задачи. Кстати, все упирается в select, где в моем случае скорее О(log(N)) (rank9 + бинарный поиск блока), чем O(log(log(N)), SIMD пока не использовали. Кстати, в случае с N-граммами можно относительно легко и дешево модифицировать сам словарь со строками.
                    К сожалению у меня не было возможности копать дальше, если у кого-то есть опыт, то было бы интересно услышать.

                    PS. спасибо за статью!
                      0
                      SDS-ки обычно придумываются под «плоскую» модель памяти с равномерным произвольным доступом. Наличие иерархии памяти и асмииетрии в паттернах доступа сильно меняет пространство оптимальных дизайнов (cache-conscious, cache-oblivious и т.п.). Итоговая оптимальная раскладка данных по памяти может сильно отличаться от того, что в пейперах предлагают, а теоретическая O(log N) внезапно стать эффективнее теоретической O(1).
                      +1
                      Спасибо за интересную статью :) Коты в коробочках великолепны!
                      Есть вопрос. В разделе «Количество потомков» приведено две формулы:

                      [1] childrenCount(i) = lastChild(i) — firstChild(i) + 1
                      [2] childrenCount(i) = firstChild(i + 1) — firstChild(i)

                      Формула [2] требует меньше вычислений, т.к. расчет двух первых потомков это два select'а, а вычисление первого и последнего потомков это два select'а + rank. При этом формула [1] — универсальна, а у формулы [2] есть ограничение, узел должен быть не последним на своем уровне дерева:

                      Но допустим, у узла i существует соседний узел i+1, который располагается на том же уровне дерева, что и i.

                      Как понять, что выбранный узел не является последним на уровне дерева?

                      P.S. В статье в формуле [1] опечатка childrenCount(i) = lastChild(i + 1) — firstChild(i) + 1, полагаю должно быть lastChild(i).
                        0
                        У узла i есть сосед i + 1 на том же уровне дерева (иными словами, узел не является крайним справа в ряду), если выполняется условие:
                        x = select1(i + 1) + 1
                        LBS[x] == 1


                        Есть ли у узла с i=4 (буква «е») сосед i+1?
                        x = select1(4 + 1) + 1 = 8
                        LBS[8] = 1
                        Да, i + 1 — сосед.

                        Есть ли сосед у узла с i=5 (буква «о»)?
                        x = select1(5 + 1) + 1 = 9
                        LBS[9] = 0
                        Нет, i + 1 не является соседом, он находится уже на следующем уровне иерархии.

                        P.S. Спасибо, опечатку в childrenCount(i) исправила.
                        +1

                        М… Я может чего-то не догнал, но почему O(8N) и O(2N) во введении преподносятся как "разный порядок асимптотики"? Асимптотика-то одна, O(N), она один шут с точностью до константы.

                          0
                          Во введении сравниваются не O(8N) и O(2N), а O(8N) и 2N + o(N). 2N, без O.
                            0

                            Ну так 2N — это тоже O(8N).

                              0
                              2N возрастает строго как 2N. На константу не домножается.
                              O(N) возрастает линейно от N, то есть N может быть домножено на любую константу (да, в том числе на 2, но может и на 10).
                                +1

                                А может и на 0.5, если изначальное O(MN) было на самом деле MN/16.

                              0

                              Асимптотика-то один шут одинаковая, так что поправка принимается, но вопрос остаётся. Каким образом O(8N) = O(N) имеет "совершенно другой порядок асимптотики" чем 2N = O(N)? И там, и там асимптотика — линейная.

                                0
                                Следуя логике «2N — это O(N)», у зависимостей
                                f(N) = 10N,
                                g(N) = N + lg(N),
                                h(N) = N + 8
                                одинаковая асимптотика. Если не вылезать за рамки теоретической математики, то почему бы не огрубить до верхней границы O(N). Это верно.

                                Но речь идет про девайсы с ограниченной памятью, на них не удастся рассматривать эти функции как предельные с N -> inf. И f(N) = O(N), g(N) = N + o(N) и h(N) = N + O(1) уже нельзя назвать ростом одного порядка. f = O(N) — это оценка сверху, в которой N может быть помножено на любую константу, а f = N — это четкая гарантия N, без потенциального удвоения или утроения памяти.
                                  0

                                  Так тогда вообще с самого начала не стоило говорить про O(MN), раз предельный случай для нас неактуален, разве нет?

                                    0

                                    Это конечно уже некропост, но. Вопрос не в том, что у Вас структуры данных плохие. Может и хорошие. Но термин "порядок асимптотики" вы, по-видимому, не вполне понимаете. На всякий случай поясню. Порядок — в узком смысле это цифра в показатели степени переменной. Поэтому хоть у Вас 10⁻⁹ N, хоть 10⁶ N, порядок не меняется. Порядок меняется если у Вас c₁ N и c₂ N², скажем. В более широком смысле, под "порядком" понимают характер роста вообще, и тогда exp(N) тоже попадает в "порядок", хотя там, конечно, цифры в показателе нет — но растёт она быстрее любой степенной функции, поэтому "порядок асимптотики" у неё больше, чем у любой степенной. Ну и так далее. Но все эти порядки призваны только в общих чертах описать тенденцию роста функции при больших значениях аргумента, не более того.
                                    И, конечно, может быть более эффективный алгоритм с той же (или даже худшей!) асимптотикой. Взять те же mergesort vs quicksort. Но при одинаковой асимптотике, "более эффективный" он строго линейно. Т.е. если алгоритм в 10 раз более эффективный, то он для любых N в 10 раз более эффективный, и ожидать чуда при попытке обработать в 100 раз больше данных — не стоит. А при разных порядках асимптотики — да запросто.

                              +1
                              Я экспериментировал с Python обёрткой для sdsl-lite:
                              github.com/QratorLabs/pysdsl

                              Просто чтобы можно было быстро что-то с этими алгоритмами наделать (или сделать самостоятельно на базе низкоуровневых функций и структур).
                                +1

                                А можно поподробнее объяснить, как выводится формула firstChild(i) = select0(i + 1) — i?
                                То есть индекс начала битовой кодировки i-того элемента мы можем получить с помощью select0(i + 1) + 1, поскольку каждый элемент имеет ровно один ноль в битовой кодировке, плюс у нас есть фейковый элемент. select0(i + 1) — это индекс окончания битовой кодировки предыдущего элемента. Но почему мы, вычитая из этого индекса i, будем всегда получать номер первого потомка i-того элемента?

                                  0
                                  Ты правильно сказал, что количество 0 в LBS совпадает с количеством узлов дерева + 1. А фейковый корень добавляется для того, чтобы количество 1 точно совпадало с количеством узлов.

                                  Поэтому select0(i + 1) — это не только индекс 0 в фрагменте LBS, относящемся узлу i — 1. Это индекс 0 перед той самой 1, которая по номеру совпадает с номером искомого первого потомка. Иными словами, select0(i + 1) + 1 — индекс единицы в LBS, номер которой — и есть номер первого потомка i.
                                  Этот индекс нужно превратить в номер узла, и для этого используется rank1:

                                  firstChild(i) = rank1( select0(i + 1) )

                                  Получили еще одну формула для firstChild(i). Также известно соотношение между rank и select:
                                  select0(x) = y
                                  rank0(y) = x
                                  rank1(y) = y — x

                                  select0(i + 1) — i выводится из этого соотношения и второй формулы firstChild(i). Заранее извиняюсь, если где напутала с +-1.

                                  P.S. Еще есть формула, определяющая зависимость rank0 и rank1 (для select чего-то похожего нет):
                                  i = rank0(i — 1) + rank1( i — 1)
                                    0

                                    Да, с rank1 стало понятнее. Круто, спасибо!

                                  0

                                  А есть какая-нибудь структура для компактного хранения больших массивов "тритов" (принимающих значения из множества {0,1,2}) с быстрым доступом? Кроме очевидного использования двух битов на трит или арифметического кодирования 5 тритов (243 варианта) в 8 бит?

                                    0
                                    А какие требования к структуре? Планируется только доставать триты по индексу, или еще искать по значению, добавлять, удалять? Известна ли верхняя граница количества тритов? Какой желателен компромисс между скоростью и объемом (т.е. есть ли ограничения на объем)?
                                      0

                                      Массивы тритов неизменяемого после создания размера, размером до нескольких миллиардов тритов.
                                      Операции: быстрые запись и чтение по индексу (впрочем, запись выполняется однократно, но эти несколько млрд операций записи не должны выполняться дольше ~нескольких секунд). Между скоростью и объёмом предпочтение отдаётся скорости, но вместе с тем есть желание уменьшить объём с текущего 1 байта на трит.


                                      Впрочем, эти массивы тритов таки образуют деревья… Значение "2" у i-того трита означает, что ячейка по этому индексу i имеет листья, находящиеся в другом массиве по индексам [i*k; (i+1)*k). k — число листьев — фиксировано для конкретного массива.

                                        0
                                        Под описание подходит контейнер типа std::bitset из c++. Триты записываются в битсет один за другим. Первый лежит начиная с индекса 0, второй — начиная с 3 и тд. Аллоцировать заранее по количеству тритов, обращение по индексу — за O(1).
                                          0

                                          Ээ… Кажется, вы не так поняли. Трит — это не тройка битов, а "троичный бит", ~1.58 бита двоичного. Один трит принимает значение из множества {0,1,2} (в отличие от бита, у которого значения из {0,1}).

                                            0
                                            Чем не устраивают описанные вами же 2 бита на трит или 5 тритов на 8 бит? Это же явно лучше одного трита на байт.
                                              0

                                              Интересуюсь, вдруг есть что-то более быстрое.

                                                0
                                                Ну так скорость зависит от реализации доступа, а не от способа хранения. Для тех же 5 трит на 8 бит, триты можно доставать делением, а можно через lookup-таблицу. Понятное дело, что делением будет скорее всего в разы медленнее чем через lookup-таблицу. А способ хранения более оптимальный вряд ли можно придумать. Чисто математически понятно, что больше не выжать.
                                              0
                                              Да, невнимательно прочитала =) Получается 2 бита на 1 трит в битсете.

                                    Only users with full accounts can post comments. Log in, please.