1

我已经建立了霍夫曼树。但我不知道将代码存储为位，因为我不知道如何

处理可变长度。

我想创建一个表，以位存储霍夫曼代码以打印编码结果。

我不能使用像 bitset 这样的 STL 容器。

我有这样的尝试

   void traverse( string code = "")const
   {
        if( frequency == 0 ) return;
        if ( left ) {
             left->traverse( code + '0' );
             right->traverse( code + '1' );
        }
        else {//leaf node
             huffmanTable[ch] = code;
        }
   }

你能给我一些算法来处理它吗？

我想存储“0”使用 1 位，“1”使用 1 位。

提前谢谢。

4

3 回答 3

2

您将需要一个缓冲区、一个用于跟踪缓冲区大小（以字节为单位）的变量，以及一个用于跟踪缓冲区中有效位数的变量。

存储一点：

  1. 检查添加位是否会增加存储的字节数。如果不是，请跳至步骤 4。

  2. 缓冲区中是否有空间存储额外的字节？如果是，请跳至步骤 4。

  3. 重新分配一个大几个字节的存储缓冲区。复制现有数据。增加保存缓冲区大小的变量。

  4. 计算将存储下一位的字节位置和位位置。根据需要设置或清除该位。

  5. 增加保存存储位数的变量。

于 2012-12-11T00:02:41.500 回答
1

您可以使用固定大小的结构来存储表，而只使用位来存储编码输入：

struct TableEntry {
  uint8_t size;
  uint8_t code;
};

TableEntry huffmanTable[256];

void traverse(uint8_t size; uint8_t code) const {
        if( frequency == 0 ) return;
        if ( left ) {
             left->traverse(size+1, code << 1 );
             right->traverse(size+1, (code << 1) | 1 );
        }
        else {//leaf node
             huffmanTable[ch].code = code;
             huffmanTable[ch].size = size;
        }
}

对于编码，您可以使用David发布的算法。

于 2012-12-11T00:03:20.160 回答
1

基本上我会根据树的最大密钥长度/深度在这里使用两种不同方法之一：

  • 如果您有一个固定长度并且它比您可用的整数数据类型（如long int）短，您可以使用 perreal 显示的方法。

  • If you don't know the maximum depth and think you might be running out of space, I'd use std::vector<bool> as the code value. This is a special implementation of the vector using a single bit per value (essentially David's approach).

于 2012-12-11T00:12:02.147 回答