MATLAB中霍夫曼编码的字典/树传输问题问询

1. Serializing the Huffman Dictionary for Transmission #

Great point about needing to send the dictionary alongside encoded data—Bob can’t decode without it! MATLAB doesn’t have a built-in function for this exact workflow, but it’s totally doable to implement the serialization logic you outlined: an 8-bit length marker, followed by the dictionary’s bitstream, then the encoded payload.

Here’s a practical, step-by-step approach with code:

• First, generate your base dictionary using huffmandict:

  symbols = [1, 2, 3, 4, 5]; % Example input symbols
  prob = [0.3, 0.2, 0.2, 0.15, 0.15]; % Corresponding probabilities
  [dict, avglen] = huffmandict(symbols, prob);
  

• Next, serialize the dictionary into a bitstream. We’ll encode symbols, their code lengths, and the codes themselves. Let’s assume your symbols fit into 8 bits (adjust the bit width if you’re using larger values):

  function dict_bits = serialize_dict(dict, symbol_bit_width)
      dict_bits = [];
      num_symbols = size(dict, 1);
      % First, encode the number of symbols (using 8 bits here—expand if needed)
      dict_bits = [dict_bits, de2bi(num_symbols, 8, 'left-msb')];
      
      for i = 1:num_symbols
          % Encode the symbol itself
          symbol_bits = de2bi(dict{i,1}, symbol_bit_width, 'left-msb');
          dict_bits = [dict_bits, symbol_bits];
          
          % Encode the length of the Huffman code (4 bits covers lengths up to 15, which is typical)
          code_len = length(dict{i,2});
          dict_bits = [dict_bits, de2bi(code_len, 4, 'left-msb')];
          
          % Encode the Huffman code bits
          dict_bits = [dict_bits, dict{i,2}];
      end
  end
  

• Generate your encoded data with huffmanenco:

  input_vector = [1,2,3,4,5,1,1,2]; % Example input sequence
  encoded_data = huffmanenco(input_vector, dict);
  

• Combine everything into the final transmission stream:

  symbol_bit_width = 8; % Match your symbol range
  dict_bitstream = serialize_dict(dict, symbol_bit_width);
  N = length(dict_bitstream);
  % Encode N as 8 bits (ensure N <= 255; use more bits if your dictionary is larger)
  N_bits = de2bi(N, 8, 'left-msb');
  % Final transmission bitstream
  transmission_stream = [N_bits, dict_bitstream, encoded_data];
  

• On Bob’s end, a deserialization function will rebuild the dictionary:

  function [dict, remaining_bits] = deserialize_dict(bitstream, symbol_bit_width)
      % Extract the number of symbols first
      num_symbols = bi2de(bitstream(9:16), 'left-msb');
      current_bit = 17;
      dict = cell(num_symbols, 2);
      
      for i = 1:num_symbols
          % Extract the symbol
          symbol = bi2de(bitstream(current_bit:current_bit+symbol_bit_width-1), 'left-msb');
          current_bit = current_bit + symbol_bit_width;
          
          % Extract code length
          code_len = bi2de(bitstream(current_bit:current_bit+3), 'left-msb');
          current_bit = current_bit + 4;
          
          % Extract Huffman code
          code = bitstream(current_bit:current_bit+code_len-1);
          current_bit = current_bit + code_len;
          
          dict{i,1} = symbol;
          dict{i,2} = code;
      end
      remaining_bits = bitstream(current_bit:end);
  end
  

  Bob can then use huffmandeco with the reconstructed dictionary to recover the original data.

2. Generating a Huffman Tree and Converting It Back to a Dictionary #

MATLAB doesn’t expose the Huffman tree directly from huffmandict, but you can build the tree manually using symbol probabilities, then traverse it to generate codes (or serialize the tree for even more efficient transmission).

Here’s how to build a Huffman tree:

function huff_tree = build_huffman_tree(symbols, prob)
    % Initialize leaf nodes
    nodes = struct();
    for i = 1:length(symbols)
        nodes(i).symbol = symbols(i);
        nodes(i).prob = prob(i);
        nodes(i).left = [];
        nodes(i).right = [];
    end
    
    % Merge nodes until only one tree remains
    while length(nodes) > 1
        % Sort nodes by probability
        [sorted_probs, idx] = sort([nodes.prob]);
        nodes = nodes(idx);
        
        % Merge the two lowest-probability nodes
        new_node = struct();
        new_node.prob = sorted_probs(1) + sorted_probs(2);
        new_node.left = nodes(1);
        new_node.right = nodes(2);
        new_node.symbol = []; % Internal node has no symbol
        
        % Replace the two nodes with the merged one
        nodes = [new_node; nodes(3:end)];
    end
    
    huff_tree = nodes(1);
end

Then, traverse the tree to generate the dictionary:

function dict = tree_to_dict(huff_tree)
    dict = cell(0,2);
    traverse_tree(huff_tree, [], dict);
end

function traverse_tree(node, current_code, dict)
    if ~isempty(node.symbol)
        % Leaf node: add symbol and code to dictionary
        dict{end+1,1} = node.symbol;
        dict{end,2} = current_code;
        return;
    end
    % Traverse left branch (assign 0)
    traverse_tree(node.left, [current_code, 0], dict);
    % Traverse right branch (assign 1)
    traverse_tree(node.right, [current_code, 1], dict);
end

To serialize the tree for transmission, use a pre-order traversal: mark internal nodes with a 0 bit, and leaf nodes with a 1 bit followed by the symbol. Bob can reconstruct the tree from this bitstream and generate the dictionary himself.

内容的提问来源于stack exchange，提问作者Jay