Представляя разреженные целочисленные множества?

Question

Что является хорошим способом для представления разреженного набора целых чисел (действительно адресов памяти C) компактным и быстрым способом. Я уже знаю об очевидных вещах, таких как битовые векторы и кодирование длин серий. но я хочу что-то гораздо более компактное, чем одно слово на элемент набора. Мне нужно добавить и удалить элементы и проверить на членство. Мне не нужны другие операции над множествами, например, union.

Я читал об одной такой библиотеке много лет назад, но с тех пор забыл ее название. Я думаю, что он был выпущен как открытый исходный код HP и имел женское имя.

Answer 1

Вы имеете в виду массив Джуди. Это был проект HP. Я думаю, что они используются в ruby ​​и доступны в c. Очень интересная структура данных. Используя тот факт, что выделения (по крайней мере) выровнены по словам, имеют отдельные структуры для плотных и разреженных диапазонов.

http://judy.sourceforge.net/index.html

Answer 2

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

http://en.wikipedia.org/wiki/Bloom_filter

Фильтр Блума, созданный Бертоном Х. Блумом в 1970 году, представляет собой компактную вероятностную структуру данных, которая используется для проверки того, является ли элемент членом набора. Ложные срабатывания возможны, а ложные - нет. Элементы могут быть добавлены в набор, но не удалены (хотя это может быть решено с помощью счетного фильтра)

Answer 3

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

Answer 4

Если вы хотите, чтобы структура была меньше, чем набор данных, вам, вероятно, следует взглянуть на какое-то древовидное расположение. Сделайте каждый уровень четырехсторонним ключом дерева от 2 битов, начиная с верхнего уровня, и он может довольно хорошо сжиматься (если указатели имеют какую-либо степень пространственной локализации). Хитрость была бы в том, чтобы кодировать его достаточно компактно (индексировать в массивы узлов? Дерево, отображаемое на массив?).