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

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

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

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

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


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

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

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


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

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

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

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

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


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

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

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

Да? Но ведь rank1(2) = 1, а select1(1) = 0.
Значения rank для битового массива — это неубывающая последовательность, в которой могут встречаться равные соседние элементы.
rank1(2) = 1, но также и rank1(0) = 1, rank1(1) = 1. select1(1) = 0 соответствует первому инкременту: rank1(0) = 1.
С этим я не спорю. Но всё же мне кажется, что select нельзя назвать обратной для rank операцией (т.к. описанное условие выполняется не всегда).
Если заранее ввести правила, по которым однозначно определяется, какой именно элемент принять за обратный, то все будет в порядке =)
Причина, по которой вщаимно-обратные rank/select определены не совсем «симметрично», в том, что так навигационные выражения, например, для LOUDS получаются короче. SDS десятилетиями оставались чисто теоретическим упражнением для ума, где оптимизировалась красота ассимптотических оценок в научных статьях.
Хочу поделиться небольшим опытом использования 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. спасибо за статью!
SDS-ки обычно придумываются под «плоскую» модель памяти с равномерным произвольным доступом. Наличие иерархии памяти и асмииетрии в паттернах доступа сильно меняет пространство оптимальных дизайнов (cache-conscious, cache-oblivious и т.п.). Итоговая оптимальная раскладка данных по памяти может сильно отличаться от того, что в пейперах предлагают, а теоретическая O(log N) внезапно стать эффективнее теоретической O(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).
У узла 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) исправила.

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

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

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

Следуя логике «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, без потенциального удвоения или утроения памяти.

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

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

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

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

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

Ты правильно сказал, что количество 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,1,2}) с быстрым доступом? Кроме очевидного использования двух битов на трит или арифметического кодирования 5 тритов (243 варианта) в 8 бит?

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

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


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

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

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

Чем не устраивают описанные вами же 2 бита на трит или 5 тритов на 8 бит? Это же явно лучше одного трита на байт.
Ну так скорость зависит от реализации доступа, а не от способа хранения. Для тех же 5 трит на 8 бит, триты можно доставать делением, а можно через lookup-таблицу. Понятное дело, что делением будет скорее всего в разы медленнее чем через lookup-таблицу. А способ хранения более оптимальный вряд ли можно придумать. Чисто математически понятно, что больше не выжать.
Да, невнимательно прочитала =) Получается 2 бита на 1 трит в битсете.
Only those users with full accounts are able to leave comments. Log in, please.