Комментарии 43
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
Эти операции в самом деле можно реализовать крайне эффективно: rank — за O(1); select — за O(lg(lg(N)), что тоже почти константа. И конечно без некоторых уловок не обойдется.
Самое интересное-то и не написали!
Интересно, насколько возрастет потребление памяти, ведь для выполнения rank за константу — точно какой-то предподсчет нужен. Мне очень интересно, остается ли какое-либо преимущество по сравнению с не succint деревом, например. Особенно, если вместо 64-битных указателей хранить номера детей, которые больше lg(N) бит не требуют.
Во-первых, спасают оптимизации на аппаратном уровне: в большинстве процессоров реализован popcnt, который быстро считает количество установленных битов в слове. Интел довольно давно разработал набор команд SSE4 с POPCNT для регистров 16, 32, 64 бита. AMD — аналогично. А также есть вариации с ускорением посредством SIMD.
Если забыть про аппаратное ускорение, то конечно есть техники для предподсчета rank таким образом, чтобы не раздувать занимаемое пространство. Многие из них основываются на списках с пропусками для блоков битовой строки. Но это очень большая тема, тянет на отдельную статью с красивыми графиками сравнения производительности и занимаемых ресурсов.
rank за константу — точно какой-то предподсчет нужен.
Я использовал у себя в проекте подобный подход. Мне нужно было хранить сбалансированное бинарное дерево. Для него даже никакого предрасчёта не потребовалось.
Особенно, если вместо 64-битных указателей хранить номера детей,
Для бинарного дерева даже номера не нужно хранить. Только сами данные.
У меня ускорение действительно было по сравнению с обработкой дерева, "запакованного" классическим способом.
Внимательный читатель заметит, что select — обратная операция для rank. Если rank1(5) = 4, то select1(4) = 5.
Да? Но ведь rank1(2) = 1, а select1(1) = 0.
rank1(2) = 1, но также и rank1(0) = 1, rank1(1) = 1. select1(1) = 0 соответствует первому инкременту: rank1(0) = 1.
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. спасибо за статью!
Есть вопрос. В разделе «Количество потомков» приведено две формулы:
[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).
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 — это тоже O(8N).
Асимптотика-то один шут одинаковая, так что поправка принимается, но вопрос остаётся. Каким образом O(8N) = 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 раз больше данных — не стоит. А при разных порядках асимптотики — да запросто.
github.com/QratorLabs/pysdsl
Просто чтобы можно было быстро что-то с этими алгоритмами наделать (или сделать самостоятельно на базе низкоуровневых функций и структур).
А можно поподробнее объяснить, как выводится формула firstChild(i) = select0(i + 1) — i?
То есть индекс начала битовой кодировки i-того элемента мы можем получить с помощью select0(i + 1) + 1, поскольку каждый элемент имеет ровно один ноль в битовой кодировке, плюс у нас есть фейковый элемент. select0(i + 1) — это индекс окончания битовой кодировки предыдущего элемента. Но почему мы, вычитая из этого индекса i, будем всегда получать номер первого потомка i-того элемента?
Поэтому 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 — число листьев — фиксировано для конкретного массива.
Ээ… Кажется, вы не так поняли. Трит — это не тройка битов, а "троичный бит", ~1.58 бита двоичного. Один трит принимает значение из множества {0,1,2} (в отличие от бита, у которого значения из {0,1}).
Интересуюсь, вдруг есть что-то более быстрое.
Спасибо за отличную статью!
Коты в коробочках, или Компактные структуры данных