Bit đóng gói mảng các số nguyên

Question

Tôi có một mảng các số nguyên, giả sử chúng thuộc loại int64_t. Bây giờ, tôi biết rằng chỉ mỗi bit n đầu tiên của mỗi số nguyên đều có ý nghĩa (nghĩa là, tôi biết rằng chúng bị giới hạn bởi một số giới hạn).

Cách hiệu quả nhất để chuyển đổi mảng theo cách mà tất cả không gian không cần thiết bị xóa (tức là tôi có số nguyên đầu tiên tại số a[0], số thứ hai tại a[0] + n bits và vv)?

Tôi muốn nói chung càng nhiều càng tốt, bởi vì n sẽ thay đổi theo thời gian, mặc dù tôi đoán có thể có các tối ưu hóa thông minh cho các quyền cụ thể là n như 2 hoặc sth.

Tất nhiên tôi biết rằng tôi chỉ có thể lặp giá trị trên giá trị, tôi chỉ muốn hỏi bạn StackOverflowers nếu bạn có thể nghĩ ra một số cách thông minh hơn.

Chỉnh sửa:

Câu hỏi này không phải là nén mảng để có ít nhất không gian nhất có thể. Tôi chỉ cần "cắt" n bits từ mọi số nguyên và cho mảng tôi biết chính xác n của các bit mà tôi có thể cắt một cách an toàn.

Answer 1

Tôi biết điều này có vẻ như điều hiển nhiên khi nói rằng tôi chắc chắn có giải pháp, nhưng tại sao không sử dụng loại nhỏ hơn, như uint8_t (tối đa 255)? hoặc uint16_t (tối đa 65535) ?. Tôi chắc rằng bạn có thể thao tác bit trên một số int64_t sử dụng các giá trị và hoạt động được xác định và tương tự, nhưng, ngoài một bài tập học thuật, tại sao?

Và trên ghi chú của bài tập học thuật, Bit Twiddling Hacks là một tài liệu đọc tốt.

Answer 2

Hầu hết mọi thuật toán nén sẽ gần với entropy tối thiểu cần mã hóa các số nguyên, ví dụ, mã Huffman, nhưng truy cập nó như một mảng sẽ không nhỏ.

Answer 3

Tôi đồng ý với keraba rằng bạn cần sử dụng thứ gì đó như mã Huffman hoặc có thể là thuật toán Lempel-Ziv-Welch. Vấn đề với việc đóng gói bit theo cách bạn đang nói đến là bạn có hai lựa chọn:

• Chọn một hằng số n sao cho số nguyên lớn nhất có thể được biểu diễn.
• Cho phép n thay đổi từ giá trị sang giá trị.

Tùy chọn đầu tiên tương đối dễ thực hiện, nhưng thực sự sẽ lãng phí nhiều không gian trừ khi tất cả các số nguyên là khá nhỏ.

Tùy chọn thứ hai có những bất lợi lớn mà bạn phải truyền đạt những thay đổi trong n bằng cách nào đó trong bitstream đầu ra. Ví dụ, mỗi giá trị sẽ phải có độ dài liên kết với nó. Điều này có nghĩa là bạn đang lưu trữ hai số nguyên (mặc dù số nguyên nhỏ hơn) cho mỗi giá trị đầu vào. Có một cơ hội tốt để bạn tăng kích thước tệp bằng phương thức này.

Lợi thế của Huffman hoặc LZW là chúng tạo các danh mục theo cách sao cho độ dài của các mã có thể xuất phát từ bitstream đầu ra mà không thực sự lưu trữ độ dài. Những kỹ thuật này cho phép bạn nhận được rất gần với giới hạn Shannon.

tôi quyết định từ bỏ ý tưởng ban đầu của bạn (không đổi n, loại bỏ bit không sử dụng và đóng gói) thử cho vui và đây là việc thực hiện ngây thơ tôi đến với:

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

này rất hiệu quả vì là bước một chút tại một thời điểm, nhưng đó là cách dễ nhất để thực hiện nó mà không phải đối phó với các vấn đề của endianess. Tôi đã không thử nghiệm điều này hoặc với một loạt các giá trị, chỉ là những người trong thử nghiệm. Ngoài ra, không có kiểm tra giới hạn và giả định rằng bộ đệm đầu ra đủ dài. Vì vậy, những gì tôi nói là mã này có lẽ chỉ tốt cho mục đích giáo dục để giúp bạn bắt đầu.

Answer 4

Tôi không nghĩ bạn có thể tránh lặp lại trên các phần tử. Mã hóa AFAIK Huffman yêu cầu tần số của "ký hiệu", trừ khi bạn biết thống kê của "quy trình" tạo các số nguyên, bạn sẽ phải tính toán (bằng cách lặp qua mọi phần tử).

Answer 5

Nếu bạn có kích thước cố định, ví dụ: bạn biết số của bạn là 38 bit thay vì 64, bạn có thể xây dựng các cấu trúc bằng cách sử dụng các thông số bit. Vui vẻ bạn cũng có các yếu tố nhỏ hơn để vừa với không gian còn lại.

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; 
}; 

Điều này không lớn/ít an toàn cho người dùng khi không có nhảy, vì vậy chỉ có thể được sử dụng trong một chương trình thay vì ở định dạng dữ liệu đã xuất. Nó thường được sử dụng để lưu trữ các giá trị boolean trong các bit đơn mà không cần định nghĩa các thay đổi và mặt nạ.

Answer 6

Hôm nay tôi đã phát hành: PackedArray: Packing Unsigned Integers Tightly (github project).

Công cụ này triển khai vùng chứa truy cập ngẫu nhiên nơi các mục được đóng gói ở cấp bit. Nói cách khác, nó hoạt động như thể bạn có thể thao tác một ví dụ uint9_t hoặc uint17_t mảng:

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

Bắt đầu từ việc thực hiện Jason B, tôi cuối cùng đã viết phiên bản của riêng tôi mà xử lý bit khối thay vì bit duy nhất. Một sự khác biệt là nó là lsb: Nó bắt đầu từ các bit đầu ra thấp nhất sẽ cao nhất. Điều này chỉ làm cho nó khó đọc hơn với một kết xuất nhị phân, như Linux xxd -b. Chi tiết, int* có thể được thay đổi trivially thành int64_t* và thậm chí tốt hơn là unsigned. Tôi đã thử nghiệm phiên bản này với vài triệu mảng và có vẻ như chắc chắn, vì vậy tôi sẽ chia sẻ phần còn lại:

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; 
}