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

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

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

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

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

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

const T &operator->(void) const;

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

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

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

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

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

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

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

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

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

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

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