霍夫曼解碼子表

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（不能是葉子），以及是否打到流結束標記。