Введение
Несколько месяцев назад в поисках идей по ускорению кода я изучал множество научных статей по computer science. Не буду притворяться, что хорошо их понимал, но меня не пугает непонятное, и я готов признать своё невежество1. Я обнаружил статью, написанную пятнадцать лет назад2, в которой было множество новых для меня концепций. Мне никак не удавалось в них разобраться.
Что же делать дальше? Можно искать другие статьи, чтобы они заполнили мои пробелы. Это рискованное предприятие, потому что они могут запутать ещё больше, но избежать этого нельзя. Я нашёл статью с нужной структурой данных, в которой упоминался исходный код с веб-сайта. Код был написан на C++, а я работаю на Rust, но решил, что всё равно стоит на него взглянуть. Однако зайдя на сайт, я не обнаружил там ресурс, поэтому я написал владельцу веб-сайта, который оказался преподавателем computer science.
Этот преподаватель (Гонсало Наварро) очень тепло меня принял и сразу же ответил мне3 4. И только в процессе общения с ним я осознал, что видел его фамилию на множестве статей в этой области. Оказалось, я познакомился с одним из специалистов мирового уровня в области компактных структур данных (succinct data structure). Невежество может завести очень далеко.
Что же такое компактные структуры данных? Если вы изучали в последние десятилетия computer science, то могли сталкиваться с ними, но мне не доводилось встречаться с ними в процессе работы программистом, а если и доводилось, то я сразу же о них забыл. Но я считаю, что эти структуры данных обладают потрясающими свойствами.
Все мы пользуемся массивами и хэш-таблицами5, популярны также различные деревья. Нам не нужно полностью понимать их устройство, чтобы эффективно пользоваться их свойствами. А теперь я задаюсь вопросом, почему же люди не используют компактные структуры данных чаще.
Я решил, что стоит немного о них рассказать.
Компактные структуры данных
Чтобы получить представление о компактных структурах данных, полезно сравнить их с компрессией (сжатием). Мы используем сжатие, чтобы уменьшить размер, необходимый для представления данных. Сжатие может быть полезным для экономии места на диске, для передачи меньшего количества данных по сети или для экономии памяти. Но чтобы делать со сжатыми данными что-то полезное, например, получать к ним доступ или запрашивать их, их нужно снова распаковать. А когда потом вам нужно будет сэкономить место, их нужно снова сжимать.
Компактные структуры данных устроены иначе: они хранят своё содержимое в компактном виде, как при сжатии, но этот компактный вид данных обладает полезными свойствами. Его можно использовать!
Похоже, эта область computer science возникла относительно недавно: многие важные структуры данных были изобретены за последние 25 лет.
В этой статье я расскажу о некоторых компактных структурах данных, с которыми мне довелось столкнуться. Не буду утверждать, что обладаю в этой области хоть каким-то опытом, я лишь имеют смутное представление о том, как работают эти структуры данных. Я ведь узнал о них всего несколько месяцев назад! Но, как и говорилось, чтобы их использовать, необязательно знать, как они устроены.
Rust
При системном программировании разработчиков чаще обычного заботят конкретные характеристики структур данных (память, производительность). Меня поразило, что в этой сфере для компактных структур есть достаточно много потенциальных областей применения. Основная часть исследований по компактным структурам данных была проведена на C++. Лично я предпочитаю для системного программирования пользоваться Rust, поэтому я начал искать реализации на Rust. Я поделюсь обнаруженным в надежде, что другим разработчикам на Rust эта информация покажется интересной. Однако общее описание этих структур данных ни в коем случае не ограничивается одним Rust, так что, даже если вы не пишете на Rust, я всё же рекомендую почитать статью.
Битовые векторы
Рассмотрим вектор (массив) битов. Например, [0, 1, 0, 1, 1, 0, 1, 0]
Сказанное ниже будет достаточно очевидным, но я всё равно считаю, что это важно подчеркнуть. Этот битовый вектор состоит из 8 элементов. Это значит, что он помещается в один байт памяти.
В 64-битном компьютере в один нативный integer помещается 64 бита. То есть битовый вектор из 64 элементов поместится в 8 байтов, что довольно прилично, если вспомнить, что в обычном массиве такое количество байтов занимает одно значение integer. Даже bool в Rust занимает байт хранилища.
Сами по себе битовые векторы не являются компактными структурами данных. В конечном итоге, компьютерная память — это огромный массив битов. Но компактные структуры данных стремятся, чтобы важен был каждый бит.
Также важно отметить, что структура данных может представлять себя в виде битового вектора, но на самом деле хранить информацию каким-то особым образом, ускоряющим определённые операции. Об этом мы и поговорим ниже.
Битовый вектор Rank/Select
Битовый вектор rank/select — это базовая компактная структура данных, на основе которой созданы многие другие. Это битовые векторы, поддерживающие особые операции rank и select.
Давайте вернёмся к нашему битовому вектору: [0, 1, 0, 1, 1, 0, 1, 0].
Присвоим каждому элементу индекс (от 0 до 8, не включая 8).
Операция rank для указанного индекса считает количество битов, установленных в массиве до него:
То есть rank(0) равен 0, потому что в этой позиции ещё не установлено ни одного бита, rank(1) равен 1, rank(2) тоже равен 1 (в этой позиции находится 0, то есть другие дополнительные биты не установлены). rank(3) равен 2. rank(7) равен 4.
Операция select обратна операции rank. Можно передать ей ранг и получить индекс, в котором этот бит установлен.
То есть select(1) равен 1, select(2) равен 3, select(3) равен 4, а select(4) равен 6. Это идущие друг за другом индексы, в которых значение равно 1.
Компактная реализация битового вектора rank/select может выполнять эти операции за константное время. Чтобы поддерживать эти операции, достаточно лишь немного данных в дополнение к самому битовому вектору.
▍ Сценарии использования
В каких же ситуациях можно использовать такие структуры? Давайте рассмотрим простой пример.
Допустим, у нас есть большая строка, состоящая из множества маленьких строк. Мы хотим отслеживать, где все эти строки начинаются. Для этого можно использовать множество разных структур, и часто они подойдут лучше, но давайте используем битовый вектор rank/select.
Вот строка с позициями:
Hello$I am a string$I'm amazing$Traditional banana
01234567890123456789012345678901234567890123456789
0 10 20 30 40
Обратите внимание на особые маркеры $. На практике их можно закодировать как .
Итак, эта большая строка состоит из четырёх подстрок, которые можно рассматривать как массив:
["Hello", "I am a string", "I'm amazing", "Traditional banana"]Можно идентифицировать каждую строку числом, являющимся индексом в этом массиве:
Hello$I am a string$I'm amazing$Traditional banana
0 1 2 3
А теперь рассмотрим битовый вектор rank/select. В тех точках строки, где начинается подстрока и находится $, можно задать в векторе бит.
То есть мы получаем следующее:
Hello$I am a string$I'm amazing$Traditional banana
00000100000000000001000000000001000000000000000000
5 19 31
Теперь, когда у нас есть любая позиция, можно, по сути, при помощи rank определять, к какой подстроке она принадлежит — мы получим идентификатор подстроки. Например, позиция 12 находится в «I am a string», поэтому rank(12) возвращает 1.
Если прибавить 1 к идентификатору, то мы получим идентификатор следующей подстроки — полезное свойство.
Можно обратно преобразовать идентификатор подстроки в позицию при помощи select. Например, select(1) вернёт 6, позицию первого $ в строке, то есть начало "I am a string". Если прибавить к этому 1, то мы получим начало следующей подстроки. Значит, если мы хотим найти конец строки, то можем прибавить 1 к идентификатору подстроки и выполнить select для этого значения.
Это позволяет нам компактным образом хранить уникальные идентификаторы для срезов в блоках данных.
При использовании обычного битового вектора rank/select мы дополнительно должны хранить 1 бит, умноженный на длину строки, плюс ещё немного. Для строки длиной в мегабайт это дополнительные 128 килобайт плюс мелочь. Но если установленные биты относительно редки, можно для очень эффективного хранения этой дополнительной информации использовать разреженный битовый вектор rank/select, занимающий гораздо меньше пространства, чем необходимо было бы для исходного битового вектора.
▍ Rust
В Rust мне очень понравилось работать с vers, обладающим и превосходной производительностью, и минимальным оверхедом по сравнению с исходным битовым вектором. Автор крейта активно отвечает на отзывы и работает над множеством потрясающих новых возможностей.
Также стоит внимания библиотека sucds. Особенно любопытна её реализация SArray — реализация разреженного массива. Однако vers, на мой взгляд, имеет более удачную архитектуру для эффективного построения подобных структур данных, нежели sucds. Поэтому с радостью сообщаю, что vers тоже находится в процессе добавления разреженной реализации.
Вейвлет-матрица
Название «вейвлет-матрица» похоже на нечто из научной фантастики. «Док, вейвлет-матрица потеряла синхронизацию! Мы не можем вернуться в 1985 год!». С ней связаны структуры «вейвлет-деревья», в том числе вейвлет-дерево квадрантов — тоже очень крутое название из научной фантастики.
Эти структуры данных обобщают rank/select на «произвольные алфавиты». Алфавит битового вектора состоит из нулей и единиц, но многие данные реального мира имеют более обширный алфавит. Особенно интересна в мире компактных структур данных ДНК, имеющая алфавит из своих нуклеотидов «G», «C», «A» и «T» (размер 4). Ещё один распространённый алфавит — это текст. Если вы используете UTF-8 и храните его байты, то алфавит имеет размер 2566.
В общем случае, чем меньше алфавит, тем лучше: структурам данных требуется меньше места, и они могут быть быстрее.
Давайте рассмотрим строку «banana» в некоем текстовом алфавите наподобие ASCII.
banana
012345
Теперь мы можем выполнять rank и select конкретных символов в алфавите. Давайте возьмём для примера букву (символ) a:
banana
1 2 3
rank(0, 'a') равен 0, так как по индексу 0 пока нет ни одной a. Но rank(5, 'a') вернёт нам ранг 3. Аналогично, select позволяет найти индекс символа в строке: select(2, 'a') вернёт индекс 3, то есть индекс второй a.
Внутри реализации вейвлет-матрицы используются битовые векторы rank/select.
▍ Rust
В Rust крейт vers также содержит реализацию структуры данных «вейвлет-матрица».
FM-индекс
FM-индекс — это структура данных, позволяющая компактным образом хранить текст (любой вектор символов), но при этом допускающая выполнение важных операций запросов. Она использует не больше пространства, чем исходный текст (а в некоторых случаях и меньше).
Важные запросы здесь имеют следующий вид:
count(pattern)— считает количество вхождений паттерна (подстроки) в хранимом тексте,locate(pattern)— возвращает индекс каждого вхождения паттерна в исходном тексте.
Возможность загрузки огромной строки данных ДНК в памяти и быстрого нахождения в ней подстрок крайне важна в биоинформатике. Однако потенциально выиграть от использования FM-индекса может любая сфера применения с большим количеством текста, для которого нужны операции поиска.
▍ Rust
В Rust эту функциональность представляет крейт fm-index.
Изначально крейт fm-index для внутреннего битового вектора rank/select использовал крейт fid (того же автора). Но недавно я портировал fm-index для использования вместо него vers, что существенно повысило производительность fm-index.
Совместно с прекрасным автором fm-index мы работали над совершенствованием его API и функциональности; в этой области готовится ещё много нововведений, в том числе поддержка хранения и поиска больших строк, состоящих из множества подстрок.
Сбалансированные скобки
Рассмотрим дерево данных, в котором каждый узел может иметь произвольное количество дочерних узлов. Такие структуры очень часто встречаются в программировании. В виде таких деревьев представлены и XML, и JSON; также могут выглядеть AST языков программирования.
Если вы хотите обеспечить возможность произвольной навигации по дереву, то вам понадобятся следующие операции с узлами деревьев:
parent(node): возвращает узел, дочерним узлом которого является указанный.first_child(node): возвращает первый дочерний узел узла.next_sibling(node): возвращает следующий родственный узел (в пределах родительского узла).previous_sibling(node): возвращает предыдущий родственный узел (в пределах его родительского узла).
Часто эти деревья представлены в памяти примерно так:
struct Node {
parent_idx: Option<usize>,
first_child: Option<usize>,
next_sibling: Option<usize>,
prev_sibling: Option<usize>
}Достаточно большой объём информации на узел: в 64-битной операционной системе этот узел насчитывает 32 байта, или 256 бита. Сбалансированное дерево скобок позволяет этим же операциям занимать всего по 2 бита на узел! Вообще, есть и небольшой оверхед, используемый внутренним битовым вектором rank/select, и ещё немного в структуре данных управления, но всё равно места требуется на удивление мало.
Как это возможно? Если вкратце, то мы, по сути, кодируем дерево в виде последовательности скобок. Рассмотрим единичное дерево с корневым узлом a и двумя дочерними узлами b и c:
a
/
b cЕго можно представить как «(()())».
(()())
ab c
Внешние скобки кодируют корневой узел a, а две внутренние пары () — его дочерние узлы. Так как у нас есть только открывающая скобка ( и закрывающая скобка ), эту информацию можно хранить в битовом векторе rank/select, где 1 — это открывающая, а 0 — закрывающая скобка.
(()())
110100
А благодаря различным хитрым операциям с использованием rank() и select(), а также небольшой долей вспомогательной информации эта структура может поддерживать всю описанную выше навигацию, а также множество других операций.
▍ Rust
Потрясающий автор vers работает над реализацией на Rust ветви dev-bp крейта vers. Я активно использовал её в своей собственной работе и могу сказать, что она отлично выглядит!
Надстраивание этих структур
Можно использовать эти и другие компактные структуры данных для создания новой функциональности с очень интересными свойствами.
Я работаю над обработкой XML в Rust, а в статье, упомянутой в начале поста, описан способ хранения данных XML с использованием компактных структур данных.
Для хранения дерева XML в ней применяется сбалансированное дерево скобок. Это не позволяет добавлять к узлам информацию, например, информацию тэгов XML (например, p в <p> и </p>). Но можно добавлять информацию к каждому узлу, храня разреженный битовый вектор rank/select для каждого тэга, размечающий соответствующие скобки дополнительной информацией.
В этом случае такой битовый вектор rank/select позволяет выполнять фундаментально новые операции: можно переходить к первому узлу-потомку с определённым тэгом без необходимости обхода промежуточных узлов!
Также в XML содержатся текстовые узлы. Их можно прикрепить к дереву, отслеживая, какая открывающая скобка имеет тэг текстового узла. В статье также применяется FM-индекс для хранения текстовых узлов и обеспечения возможности быстрых запросов к ним.
Возможно, XML — достаточно странная область применения для подобных техник, но представьте язык программирования, хранящий в таком виде своё AST. Огромные AST можно хранить относительно компактно, но при этом они всё равно будут поддерживать интересные операции поиска, что может открыть новые способы реализации компиляторов языков.
Заключение
Теперь, когда я обнаружил эти структуры данных, я задаюсь вопросом, почему они раньше не встречались мне в моей работе программистом. Подозреваю, у них есть большой нераскрытый потенциал. Хотя структуры данных, использующих гораздо больше памяти, в общем случае могут выполнять многие из этих операций эффективнее, способность использовать меньше памяти сама по себе влияет на производительность. А до декабря прошлого года я даже не подозревал, что они существуют! Уверен, что многие разработчики могли бы придумать для них интересные сценарии применения.
Примечания
1. Примите свою растерянность и невежество. Смиритесь с тем, что будете уставать. Именно так вы учитесь чем-то новому.
2. Это статья Fast in-memory XPath search using compressed indexes
3. В последнее время я написал нескольким другим, и результаты были очень положительными! Теперь отправка писем преподавателям computer science — моё новое хобби и суперсила. Обычно это люди, которыми движет любопытство, и они с готовностью делятся своими находками. Они потрясающие!
Тот недавний опыт взаимодействия с преподавателями, а также с опенсорсными разработчиками компактных структур в Rust вернул мне крайне необходимую веру в человечество.
4. Я спросил профессора Наварро, можно ли упоминать его имя. Теперь вы все можете ему писать.
5. На самом деле, я знаю на удивление много программистов, не использующих их. В процессе ревью кода я встречал код, который обходит по всему массиву, чтобы найти одно значение, что запросто приводит к квадратичному времени. Пользуйтесь хэш-таблицами, ребята.
6.В некоторых ситуациях вам может понадобиться алфавит размером с сам Unicode. Постарайтесь избегать этого.
Автор: ru_vds
