Битовая упаковка массива целых чисел
У меня есть массив целых чисел, давайте предположим, что они имеют тип int64_t, Теперь я знаю, что только каждый первый n биты каждого целого числа имеют смысл (то есть я знаю, что они ограничены некоторыми границами).
Какой самый эффективный способ преобразовать массив таким образом, чтобы удалить все ненужное пространство (т.е. у меня есть первое целое число в a[0]второй на a[0] + n bits и так далее)?
Я хотел бы, чтобы это было как можно более общим, потому что n будет меняться время от времени, хотя я думаю, что могут быть разумные оптимизации для конкретных n как полномочия 2 или чч
Конечно, я знаю, что могу просто перебрать значение по значению, я просто хочу спросить вас, Stackruers, можете ли вы придумать какой-нибудь более умный способ.
Редактировать:
Этот вопрос не о сжатии массива, чтобы занять как можно меньше места. Мне просто нужно "срезать" n bits из каждого целого числа и учитывая массив я знаю точное n бит, которые я могу безопасно вырезать.
7 ответов
Сегодня я выпустил: PackedArray: Упаковка целых чисел без знака ( проект на github).
Он реализует контейнер произвольного доступа, где элементы упакованы на уровне битов. Другими словами, он действует так, как если бы вы были в состоянии манипулировать, например, uint9_t или же uint17_t массив:
PackedArray principle:
. compact storage of <= 32 bits items
. items are tightly packed into a buffer of uint32_t integers
PackedArray requirements:
. you must know in advance how many bits are needed to hold a single item
. you must know in advance how many items you want to store
. when packing, behavior is undefined if items have more than bitsPerItem bits
PackedArray general in memory representation:
|-------------------------------------------------- - - -
| b0 | b1 | b2 |
|-------------------------------------------------- - - -
| i0 | i1 | i2 | i3 | i4 | i5 | i6 | i7 | i8 | i9 |
|-------------------------------------------------- - - -
. items are tightly packed together
. several items end up inside the same buffer cell, e.g. i0, i1, i2
. some items span two buffer cells, e.g. i3, i6
Я согласен с Керабой, что вам нужно использовать что-то вроде кодирования Хаффмана или, возможно, алгоритм Лемпеля-Зива-Уэлча. Проблема с упаковкой битов, о которой вы говорите, заключается в том, что у вас есть два варианта:
- Выберите постоянную n такую, чтобы можно было представить наибольшее целое число.
- Позвольте n меняться от значения к значению.
Первый вариант относительно прост в реализации, но он действительно будет тратить много места, если все целые числа не достаточно малы.
Второй вариант имеет главный недостаток, заключающийся в том, что вы должны каким-то образом передавать изменения n в выходной поток битов. Например, каждое значение должно иметь длину, связанную с ним. Это означает, что вы сохраняете два целых числа (хотя и меньшие целые) для каждого входного значения. Есть хороший шанс, что вы увеличите размер файла этим методом.
Преимущество Хаффмана или LZW состоит в том, что они создают кодовые книги таким образом, что длина кодов может быть получена из выходного потока битов без фактического сохранения длин. Эти методы позволяют вам приблизиться к пределу Шеннона.
Я решил попробовать оригинальную идею (константа n, удалить неиспользуемые биты и упаковать), и вот наивная реализация, которую я придумал:
#include <sys/types.h>
#include <stdio.h>
int pack(int64_t* input, int nin, void* output, int n)
{
int64_t inmask = 0;
unsigned char* pout = (unsigned char*)output;
int obit = 0;
int nout = 0;
*pout = 0;
for(int i=0; i<nin; i++)
{
inmask = (int64_t)1 << (n-1);
for(int k=0; k<n; k++)
{
if(obit>7)
{
obit = 0;
pout++;
*pout = 0;
}
*pout |= (((input[i] & inmask) >> (n-k-1)) << (7-obit));
inmask >>= 1;
obit++;
nout++;
}
}
return nout;
}
int unpack(void* input, int nbitsin, int64_t* output, int n)
{
unsigned char* pin = (unsigned char*)input;
int64_t* pout = output;
int nbits = nbitsin;
unsigned char inmask = 0x80;
int inbit = 0;
int nout = 0;
while(nbits > 0)
{
*pout = 0;
for(int i=0; i<n; i++)
{
if(inbit > 7)
{
pin++;
inbit = 0;
}
*pout |= ((int64_t)((*pin & (inmask >> inbit)) >> (7-inbit))) << (n-i-1);
inbit++;
}
pout++;
nbits -= n;
nout++;
}
return nout;
}
int main()
{
int64_t input[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20};
int64_t output[21];
unsigned char compressed[21*8];
int n = 5;
int nbits = pack(input, 21, compressed, n);
int nout = unpack(compressed, nbits, output, n);
for(int i=0; i<=20; i++)
printf("input: %lld output: %lld\n", input[i], output[i]);
}
Это очень неэффективно, потому что это шаг за шагом, но это был самый простой способ реализовать его, не сталкиваясь с проблемами порядка байтов. Я не проверял это ни с широким диапазоном значений, только в тесте. Кроме того, нет проверки границ, и предполагается, что выходные буферы достаточно длинные. Так что я говорю, что этот код, вероятно, хорош только для образовательных целей, чтобы вы начали.
В большинстве случаев любой алгоритм сжатия будет близок к минимальной энтропии, необходимой для кодирования целых чисел, например, для кодирования Хаффмана, но доступ к нему как к массиву будет нетривиальным.
Начиная с реализации Джейсона Б., в конце концов я написал свою собственную версию, которая обрабатывает битовые блоки вместо отдельных битов. Единственное отличие состоит в том, что это lsb: он начинается с младших битов, идущих к старшим Это только затрудняет чтение с бинарным дампом, как в Linux xxd -b, Как деталь, int* можно тривиально изменить на int64_t*и это должно быть еще лучше unsigned, Я уже тестировал эту версию с несколькими миллионами массивов, и она кажется надежной, поэтому я поделюсь с остальными:
int pack2(int *input, int nin, unsigned char* output, int n)
{
int obit = 0;
int ibit = 0;
int ibite = 0;
int nout = 0;
if(nin>0) output[0] = 0;
for(int i=0; i<nin; i++)
{
ibit = 0;
while(ibit < n) {
ibite = std::min(n, ibit + 8 - obit);
output[nout] |= (input[i] & (((1 << ibite)-1) ^ ((1 << ibit)-1))) >> ibit << obit;
obit += ibite - ibit;
nout += obit >> 3;
if(obit & 8) output[nout] = 0;
obit &= 7;
ibit = ibite;
}
}
return nout;
}
int unpack2(int *oinput, int nin, unsigned char* ioutput, int n)
{
int obit = 0;
int ibit = 0;
int ibite = 0;
int nout = 0;
for(int i=0; i<nin; i++)
{
oinput[i] = 0;
ibit = 0;
while(ibit < n) {
ibite = std::min(n, ibit + 8 - obit);
oinput[i] |= (ioutput[nout] & (((1 << (ibite-ibit+obit))-1) ^ ((1 << obit)-1))) >> obit << ibit;
obit += ibite - ibit;
nout += obit >> 3;
obit &= 7;
ibit = ibite;
}
}
return nout;
}
Я знаю, что это может показаться очевидным, так как я уверен, что на самом деле есть решение, но почему бы не использовать меньший тип, например uint8_t (максимум 255)? или же uint16_t (максимум 65535)?. Я уверен, что вы могли бы немного манипулировать на int64_t используя определенные значения и / или операции и тому подобное, но, кроме академических упражнений, почему?
И на ноте академических упражнений, Bit Twiddling Hacks - хорошее чтение.
Если у вас фиксированные размеры, например, вы знаете, что ваш номер 38 бит, а не 64, вы можете строить структуры, используя битовые спецификации. Забавно, у вас также есть меньшие элементы, чтобы поместиться в оставшееся пространство.
struct example {
/* 64bit number cut into 3 different sized sections */
uint64_t big_num:38;
uint64_t small_num:16;
uint64_t itty_num:10;
/* 8 bit number cut in two */
uint8_t nibble_A:4;
uint8_t nibble_B:4;
};
Это не безопасно с прямым порядком байтов без каких-либо скачков, поэтому может использоваться только в программе, а не в экспортированном формате данных. Это довольно часто используется для хранения логических значений в отдельных битах без определения сдвигов и масок.
Я не думаю, что вы можете избежать перебора элементов. AFAIK Кодирование Хаффмана требует частот "символов", которые, если вы не знаете статистику "процесса", генерирующего целые числа, вам придется вычислять (путем итерации по каждому элементу).