сжатый вектор / класс массива со случайным доступом к данным

Question

Я хотел бы создать класс «сжатый массив» / «сжатый вектор» (подробности ниже), который обеспечивает произвольный доступ к данным с более или менее постоянным временем.

«более или менее постоянное время» означает, чтохотя время доступа к элементу не является постоянным, оно не должно увеличиваться, когда я подхожу к определенной точке массива.Т.е. контейнер не должен делать значительно больше вычислений (например, «распаковать все заново, чтобы получить последний элемент» и «почти ничего не делать, чтобы получить первый»), чтобы получить один элемент.Вероятно, это может быть достигнуто путем разбиения массива на куски сжатых данных.Т.е. доступ к одному элементу должен занять «среднее время» + - некоторое отклонение.Я мог бы сказать, что я хочу, чтобы время доступа в лучшем случае и время доступа в худшем случае были относительно близки к среднему времени доступа.

Какие у меня варианты (подходящие алгоритмы / уже доступные контейнеры - если они есть)?

Сведения о контейнере:

1. Контейнер действует как линейный массив идентичных элементов (например, std :: vector)
2. После инициализации контейнера данные становятся постоянными иникогда не меняетсяКонтейнер должен обеспечивать доступ только для чтения.
3. Контейнер должен вести себя как массив / std :: vector - то есть значения, доступные через оператор [], есть .size () и т. Д.
4. Этобыло бы хорошо, если бы я мог сделать это как шаблон класса.
5. Доступ к данным должен быть более или менее постоянным.Мне не нужно одинаковое время доступа для каждого элемента, но мне не нужно распаковывать все, чтобы получить последний элемент.

Пример использования:
Бинарный поиск по данным.

Детали данных:
1. Данные представляют собой структуры, состоящие в основном из чисел с плавающей запятой и нескольких целых чисел.Здесь больше поплавков, чем целых.Нет строк.
2. Маловероятно, что в массиве много идентичных элементов, поэтому простое индексирование данных будет невозможно.
3. Размер одного элемента меньше 100 байт.
4.Общий размер данных на контейнер составляет от нескольких килобайт до нескольких мегабайт.
5. Данные не редки - это непрерывный блок элементов, все они назначены, «пустых слотов» нет.

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

Идеи / Мнения?

Answer 1

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

Что касается сжатия, у вас нетИсключительное понимание структуры ваших данных, так что вы в порядке с некоторой стандартной энтропийной кодировкой .В идеале, хотелось бы запустить GZIP для всего массива и покончить с ним, но это потеряло бы доступ O (1), что крайне важно для вас.

A решение заключается виспользуйте кодирование Хаффмана вместе с индексной таблицей .

Кодирование Хаффмана работает путем замены каждого входного символа (например, байта ASCII) другим символом переменная длина бита, в зависимости от частоты появления во всем потоке.Например, символ E появляется очень часто, поэтому он получает короткую битовую последовательность, в то время как 'W' редко и получает длинную битовую последовательность.

E -> 0b10
W -> 0b11110

Теперь сожмите весь массив с помощью этогометод.К сожалению, поскольку выходные символы имеют переменную длину, вы больше не можете индексировать свои данные, как раньше: номер элемента 15 больше не равен stream[15*sizeof(item)].

К счастью, эту проблему можно решить с помощью дополнительного индексная таблица index, в которой хранится начало каждого элемента в сжатом потоке.Другими словами, сжатые данные для элемента 15 можно найти на stream[index[15]];В индексной таблице накапливаются переменные выходные значения.

Итак, чтобы получить элемент 15, вы просто начинаете распаковывать байты с stream[index[15]].Это работает, потому что кодирование Хаффмана не делает ничего необычного для вывода, оно просто объединяет новые кодовые слова, и вы можете начать декодирование внутри потока без необходимости декодировать все предыдущие элементы.

Конечно,индексная таблица добавляет некоторые накладные расходы ;Вы можете настроить гранулярность так, чтобы compressed data + index table все еще был меньше, чем original data.

Answer 2

Вы пишете код для встроенной системы и / или у вас есть сотни или тысячи этих контейнеров?Если нет, хотя я думаю, что это интересный теоретический вопрос (+1), я подозреваю, что замедление в результате выполнения декомпрессии будет нетривиальным и что было бы лучше использовать std::vector.

Далее, вы уверены, что данные, которые вы храните, достаточно избыточны, чтобы меньшие блоки их фактически сжимались?Вы пробовали сберегать блоки разных размеров (возможно, степени 2) и пробовали запустить их через gzip в качестве упражнения?Может случиться так, что любые дополнительные данные, необходимые для помощи алгоритму декомпрессии (в зависимости от подхода), уменьшат преимущества пространства при выполнении такого типа сжатого контейнера.

Если вы решите, что все еще целесообразно выполнить сжатие, тогдаЕсть, по крайней мере, пара возможностей, но ни одна из них не написана заранее.Вы можете сжимать каждый отдельный элемент, сохраняя указатель на блок сжатых данных.Тогда доступ к индексу остается постоянным, просто нужно распаковать фактические данные.Возможно, использование прокси-объекта сделает процесс распаковки данных более простым и прозрачным (и, возможно, даже позволит использовать std::vector в качестве базового контейнера).

С другой стороны, std::deque уже хранит свои данные в блокахтак что вы можете использовать аналогичный подход здесь.Например, std::vector<compressed_data_chunk>, где каждый кусок содержит, скажем, 10 элементов, сжатых вместе как ваш основной контейнер.Затем вы все равно можете напрямую проиндексировать нужный вам блок, распаковать его и вернуть элемент из распакованных данных.Если вы хотите, ваш содержащий объект (который содержит vector) может даже кэшировать последний распакованный кусок или два для дополнительной производительности при последовательном доступе (хотя это совсем не поможет бинарному поиску).

Answer 3

Я уже давно об этом думаю.С теоретической точки зрения я выделил 2 возможности:

• Flyweight, поскольку повторение может быть уменьшено с помощью этого шаблона.
• Сериализация (сжатие - это некоторая форма сериализации)

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

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

У меня естьвидел несколько решений «кодирования по Хаффману», однако это означает, что для каждой структуры необходимо обеспечить алгоритм сжатия.Обобщать нелегко.

Поэтому я бы предпочел пойти другим путем и использовать библиотеку сжатия, например, 'zlib', выбрав быстрый алгоритм, например, lzo.

• B * дерево (или вариант) с большим количеством элементов на узел (так как он не перемещается), как, скажем, 1001. Каждый узел содержит сжатое представление массива элементов.Индексы не сжаты.
• Возможно: cache_view для доступа к контейнеру при сохранении последних 5 (или около того) декомпрессированных узлов или чего-либо еще.Другой вариант - реализовать подсчет ссылок и сохранять данные несжатыми, пока кто-то получает дескриптор одного из элементов в узле.

Некоторые замечания:

• ifВы должны иметь большое количество элементов / ключей на каждом узле, которое у вас близко к постоянному времени доступа, например, с 1001 это означает, что существует только 2 уровня косвенности, если вы храните менее миллиона элементов, 3 уровня косвенности на миллиарди т.д. ...
• вы можете создать читаемый / записываемый контейнер с такой структурой.Я бы сделал так, чтобы я перекомпрессировал только когда я закончу писать узел.

Answer 4

Могут ли некоторые ответы на вопрос "Какой лучший алгоритм сжатия позволяет случайное чтение / запись в файл?" быть адаптированы к вашим данным в памяти?

Answer 5

Хорошо, насколько я понимаю, вам нужен какой-то шаблон доступа. По сути, создайте адаптер шаблона, который имеет в качестве аргумента один из ваших типов элементов, к которому он получает внутренний доступ через что-либо, указатель, индекс в вашем BLOB-объекте и т. Д. Сделайте адаптер похожим на указатель:

const T &operator->(void) const;

и т.д.. поскольку проще создать адаптер указателя, чем эталонный адаптер (хотя см. вектор, если вы хотите знать, как написать один из них). Обратите внимание, я сделал этот метод доступа постоянным в соответствии с вашими рекомендациями. Затем предварительно вычислите смещения при загрузке / сжатии большого двоичного объекта и заполните вектор классом шаблонного адаптера. Имеет ли это смысл? Если вам нужно больше деталей, я буду рад предоставить.

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