如何编写比特流

Question

我想使用C将一些数据写入位流中。有两种方法可以考虑。一种是将可变长度的符号连接成连续的位序列，但这样做会使我的解码器很难从连续的位流中分离出这些符号。另一种方法是为每个符号分配相同数量的位，这样解码器就可以轻松地恢复原始数据，但由于这些符号具有不同的值，导致位流中许多位为零（我猜是浪费了这些位）。

你有什么提示应该怎么做吗？

我是新手程序员。任何帮助都将不胜感激。

- user1530192

---

这是我对类似问题的回答，链接在这里：https://dev59.com/6mXWa4cB1Zd3GeqPN4hL#11253310 - Viktor Latypov

通常的方法是打包位，但这需要逻辑知道另一侧的位数。你可能最终需要逐位解码以知道何时达到符号的结尾。 - Mark Ransom

您的问题与编码领域有关。如下所述，霍夫曼编码是一种选择。但是，除了霍夫曼编码之外还有其他选项（但它肯定是最受欢迎的）。请参阅Moffat和Turpin的书籍“压缩和编码算法”。大多数压缩书籍都涉及编码；这本书专注于编码。就“难以分离”而言，您需要一个前缀自由的代码--没有任何其他代码的前缀。 - Ray

Answer 1

听起来你正在尝试做类似于哈夫曼压缩方案的事情？我会逐字节（char）进行操作，并跟踪读取上一个符号的字节内偏移量。

假设你的符号都不会比char大。它应该是这个样子的:

struct bitstream {
   char *data;
   int data_size;           // size of 'data' array
   int last_bit_offset;     // last bit in the stream 

   int current_data_offset; // position in 'data', i.e. data[current_data_offset] is current reading/writing byte
   int current_bit_offset;  // which bit we are currently reading/writing
}

char decodeNextSymbol(bitstream *bs) {

}

int encodeNextSymbol(bitstream *bs, char symbol) {

}

对于decodeNextSymbol和encodeNextSymbol的匹配代码，需要使用C位运算符（例如'&'（按位与）和'|'（按位或））。然后，您需要列出所有符号的列表，从最短的开始，并进行一个while循环来匹配最短的符号。例如，如果您的符号之一是'101'，那么如果流是'1011101'，它将匹配第一个'101'，并继续匹配其余的流'1101'。您还必须处理符号值从一个字节溢出到下一个字节的情况。

- Patrick Raphael