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

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

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

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

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

Edit:

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

Ответ 1

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

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

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

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

Преимущество Huffman или 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]);
}

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

Ответ 2

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

Ответ 3

Сегодня я выпустил: PackedArray: Packing Unsigned Integer Tightly (проект 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

Ответ 4

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

И на заметке академических упражнений Бит Tweedling Hacks является хорошим показателем.

Ответ 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;
};

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

Ответ 6

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

Ответ 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;
}