Бит-упаковка массива целых чисел

Question

У меня есть массив целых чисел, допустим, они имеют тип int64_t. Теперь я знаю, что только каждый первый n бит каждого целого числа имеет смысл (то есть, я знаю, что они ограничены некоторыми ограничениями).

Каков наиболее эффективный способ преобразования массива таким образом, что все ненужное пространство удаляется (т. Е. У меня есть первое целое число в a[0], второе - a[0] + n bits и т. Д.)?

Я бы хотел, чтобы он был как можно более общим, потому что время от времени будет меняться время от времени: n, хотя я предполагаю, что могут быть умные оптимизации для конкретных n, таких как полномочия 2 или sth.

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

Edit:

Этот вопрос не о сжатии массива принимать как минимум пространства, как это возможно. Мне просто нужно «вырезать» n bits из каждого целого числа и получить массив, который я знаю, точный n бит, который можно безопасно разрезать.

Answer 1

Я знаю, что это может показаться очевидным, поскольку я уверен, что на самом деле есть решение, но почему бы не использовать меньший тип, например uint8_t (max 255)? или uint16_t (макс. 65535) ?. Я уверен, что вы могли бы манипулировать на int64_t с использованием определенных значений или операций и т. П., Но, помимо академических упражнений, почему?

И на заметке академических упражнений, Bit Twiddling Hacks хорошо читается.

Answer 2

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

Answer 3

Я согласен с керабой, что вам нужно использовать что-то вроде кодирования Хаффмана или, возможно, алгоритма Лемпеля-Зива-Уэлша. Проблема с битовой упаковкой, о которой вы говорите, состоит в том, что у вас есть два варианта:

• Выберите константу n, чтобы было представлено наибольшее целое число.
• Разрешить n варьироваться от значения к значению.

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

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

Преимущество Huffman или LZW заключается в том, что они создают кодовые книги таким образом, что длина кодов может быть получена из выходного битового потока без фактического хранения длин. Эти методы позволяют вам приблизиться к пределу Шеннона.

я решил дать вашу оригинальную идею (константа п, удалить неиспользуемые биты и пакет) попробовать для развлечения и вот наивная реализация я придумал:

#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]); 
} 

Это очень неэффективно, потому что это шаги по одному бит за раз, но это был самый простой способ реализовать его, не затрагивая проблемы endianess. Я не тестировал это либо с широким диапазоном значений, а только с тестами. Кроме того, проверка границ не выполняется, и предполагается, что выходные буферы достаточно длинные. Так что я говорю, что этот код, вероятно, хорош только для образовательных целей, чтобы вы начали.

Answer 4

Я не думаю, что вы можете избежать итерации по всем элементам. Для кодирования AFAIK Huffman требуются частоты «символов», которые, если вы не знаете статистику «процесса», генерирующего целые числа, вам придется вычислять (путем итерации по каждому элементу).

Answer 5

Если у вас есть фиксированные размеры, например. вы знаете, что ваш номер 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; 
}; 

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

Answer 6

Сегодня я выпустил: PackedArray: Packing Unsigned Integers Tightly (github project).

Он реализует контейнер произвольного доступа, где элементы упакованы на уровне бит. Другими словами, он действует так, как будто вы можете манипулировать, например, 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 

Answer 7

Начиная от реализации Jason B, я в конце концов написал свою собственную версию, которая обрабатывает битовые блоки вместо отдельных битов. Одно из отличий заключается в том, что это 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; 
}