霍夫曼解码子表

Question

我一直在试图实现一个huffman解码器，并且my initial attempt由于解码算法的次优选择而遭受低性能。

我想我尝试使用表查找来实现huffman解码。但是，我在生成子表时遇到了一些困难，并希望有人能指出我正确的方向。

struct node 
{ 
    node*    children; // 0 right, 1 left 
    uint8_t    value; 
    uint8_t    is_leaf; 
}; 

struct entry 
{ 
    uint8_t    next_table_index; 
    std::vector<uint8_t> values; 

    entry() : next_table_index(0){} 
}; 

void build_tables(node* nodes, std::vector<std::array<entry, 256>>& tables, int table_index); 
void unpack_tree(void* data, node* nodes); 

std::vector<uint8_t, tbb::cache_aligned_allocator<uint8_t>> decode_huff(void* input) 
{ 
    // Initial setup 
    CACHE_ALIGN node     nodes[512] = {}; 

    auto data = reinterpret_cast<unsigned long*>(input); 
    size_t table_size = *(data++); // Size is first 32 bits. 
    size_t result_size  = *(data++); // Data size is second 32 bits. 

    unpack_tree(data, nodes); 

    auto huffman_data = reinterpret_cast<long*>(input) + (table_size+32)/32; 
    size_t data_size = *(huffman_data++); // Size is first 32 bits.  
    auto huffman_data2 = reinterpret_cast<char*>(huffman_data); 

    // Build tables 

    std::vector<std::array<entry, 256>> tables(1); 
    build_tables(nodes, tables, 0); 

    // Decode 

    uint8_t current_table_index = 0; 

    std::vector<uint8_t, tbb::cache_aligned_allocator<uint8_t>> result; 
    while(result.size() < result_size) 
    { 
     auto& table = tables[current_table_index]; 

     uint8_t key = *(huffman_data2++); 
     auto& values = table[key].values; 
     result.insert(result.end(), values.begin(), values.end()); 

     current_table_index = table[key].next_table_index; 
    } 

    result.resize(result_size); 

    return result; 
} 

void build_tables(node* nodes, std::vector<std::array<entry, 256>>& tables, int table_index) 
{ 
    for(int n = 0; n < 256; ++n) 
    { 
     auto current = nodes; 

     for(int i = 0; i < 8; ++i) 
     { 
      current = current->children + ((n >> i) & 1);  
      if(current->is_leaf) 
       tables[table_index][n].values.push_back(current->value); 
     } 

     if(!current->is_leaf) 
     { 
      if(current->value == 0) 
      { 
       current->value = tables.size(); 
       tables.push_back(std::array<entry, 256>()); 
       build_tables(current, tables, current->value); 
      } 

      tables[table_index][n].next_table_index = current->value; 
     } 
    } 
} 

void unpack_tree(void* data, node* nodes) 
{ 
    node* nodes_end = nodes+1;  
    bit_reader table_reader(data); 
    unsigned char n_bits = ((table_reader.next_bit() << 2) | (table_reader.next_bit() << 1) | (table_reader.next_bit() << 0)) & 0x7; // First 3 bits are n_bits-1. 

    // Unpack huffman-tree 
    std::stack<node*> stack; 
    stack.push(&nodes[0]);  // "nodes" is root 
    while(!stack.empty()) 
    { 
     node* ptr = stack.top(); 
     stack.pop(); 
     if(table_reader.next_bit()) 
     { 
      ptr->is_leaf = 1; 
      ptr->children = nodes[0].children; 
      for(int n = n_bits; n >= 0; --n) 
       ptr->value |= table_reader.next_bit() << n; 
     } 
     else 
     { 
      ptr->children = nodes_end; 
      nodes_end += 2; 

      stack.push(ptr->children+0); 
      stack.push(ptr->children+1); 
     } 
    } 
} 

Answer 1

首先，避免所有这些载体。您可以将指针指向单个预分配的缓冲区，但您不希望在整个内存中分配这些极小的缓冲区的场景，并且您的缓存占用空间会遍布整个屋顶。

还要注意，非叶状态的数量可能远远少于256.事实上，它可能低至128.通过为它们分配低状态ID，我们可以避免为整个状态集生成表条目节点（总共可能高达511个节点）。毕竟，消费输入后，我们永远不会结束在一个叶节点上;如果我们这样做，我们产生输出，然后回到根。

然后，我们应该做的第一件事就是将那些与内部节点相对应的状态（即指向非叶子的指针）重新分配给低状态数字。您可以使用它来减少状态转换表的内存消耗。一旦我们分配了这些低状态数字，我们就可以遍历每个可能的非叶状态以及每个可能的输入字节（即一个双重嵌套的循环）。按照基于位的解码算法遍历树，并记录输出字节集合，最终的节点ID（不能是叶子），以及是否打到流结束标记。