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

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

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

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

Детали контейнера:

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

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

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

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

Идеи/мнение?

Ответ 1

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

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

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

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

E -> 0b10
W -> 0b11110

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

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

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

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

Ответ 2

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

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

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

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

Ответ 3

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

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

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

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

Я видел несколько решений "кодирования Хаффмана", однако это означает, что для каждой структуры нужно предоставить алгоритм сжатия. Это нелегко обобщить.

Итак, я предпочел бы пойти другим путем и использовать компрессионную библиотеку, такую как "zlib", например, быстрый алгоритм, например, lzo.

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

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

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

Ответ 4

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

const T &operator->(void) const;

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

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

Ответ 5

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