Сжатие массива разреженных битов

Question

У меня есть массивы 1024 байта (8192 бит), которые в основном равны нулю.

Будет установлено от 0,01% до 10% битов (произвольно, без паттерна).

Как их можно сжать, учитывая отсутствие структуры и относительно небольшой размер?

(Моей первой мыслью было сохранение расстояний между установленными битами. Мне нужно 13 бит на каждое расстояние, но в худшем случае требуется 10% занятости. 13 * 816 / 8 знак равно 1326 байт, что не является улучшением.)

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

Answer 1

I've dealt deeply with a similar problem, but my sets are much bigger (30 million possible values with between 1 and 30 million elements in each set), so they both gain much more from compression and the compression metadata is insignificant compared to the size of the data. I have never gone down to squeezing things into units smaller than uint16_tпоэтому то, что я напишу ниже, может не сработать, если вы начнете разбивать 13-битные значения на куски. Такое ощущение, что должно работать, но будьте бдительны.

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

Стратегии:

1. Если в наборе очень мало элементов, вы не можете сделать лучше, чем массив с надписью "1, 4711, 8140", поэтому в этом случае данные кодируются как: [3, 1, 4711, 8140]

2. Если почти все элементы находятся в наборе, вы можете просто отслеживать элементы, которых нет. Например, [8190, 17, 42].

3. Если примерно половина элементов находится в наборе, то вы почти ничего не можете сделать лучше, чем растровое изображение, поэтому вы получаете [4000, {bitmap}], это единственный случай, когда ваши данные оказываются длиннее, чем строго несжатые.

4. Если задано больше, чем "несколько", но гораздо меньше, чем "около половины", я нашел другую стратегию. Разделите биты возможных значений в наборе пополам. Допустим, у нас есть 2^16 (это проще описать, вероятно, оно должно работать для 2^13) возможных значений. Значения разделены на 256 диапазонов с каждым диапазоном с 256 возможными значениями. Затем у нас есть массив с 256 байтами, каждый из этих байтов описывает, сколько значений находится в каждом диапазоне (поэтому байт 0 сообщает нам, сколько элементов [0,255], байт 1 дает нам [256,511] и т. Д.) Сразу после следующих массивов. со значениями в каждом диапазоне мод 256. Хитрость заключается в том, что, хотя каждый элемент в наборе, закодированный как массив (стратегия 1), будет иметь 2 байта, в этой схеме каждый элемент имеет только 1 байт + 256 статических байтов для подсчета элементы. Это означает, что, как только у нас будет более 256 элементов в наборе, это экономит нам пространство, переключаясь со стратегии 1 на 4.

5. Стратегия 4 может быть доработана (возможно, бессмысленно, если ваши данные случайные, как вы упомянули, но у моих данных иногда было больше шаблонов, поэтому у меня это работало) Так как нам все еще нужно 8 бит для каждого элемента в предыдущей кодировке, как только массив элементов переходит в 32 элемента (256 байтов), мы можем вместо этого сохранить его как растровое изображение. Это также хорошая точка останова для переключения стратегий между 4/5 и 3. Если все массивы в этой стратегии - просто битовые карты, то мы должны просто использовать стратегию 3 (она более сложна, но точка останова между стратегиями может быть предварительно вычислена достаточно). точно, что вы в конечном итоге выберете наиболее эффективную стратегию каждый раз).

Я только смутно пытался сохранить дельты между числами в наборе. Быстрые эксперименты показали, что они не были намного эффективнее, чем стратегии, о которых я говорил выше, имели непредсказуемые вырожденные случаи, но самое главное, приложению, с которым я работаю, действительно нравится не десериализовывать свои данные, а просто использовать их напрямую с диска (ММАП).