信息论哈夫曼编码实验

信息论中的哈夫曼编码是一种变字长编码，可以使得编码的平均码长很接近信息熵的编码。其基本思想是，出现概率大的符号编码短一点（码长小），出现概率小的符号则用更多的码来表示。下面是哈夫曼编码的实验步骤和代码实现：

1. 实验步骤：
- 统计待编码的字符出现的频率。
- 将字符按照频率从小到大排序。
- 将频率最小的两个字符合并成一个节点，其权值为两个字符的频率之和。
- 将新节点插入到已排序的字符列表中。
- 重复步骤3和4，直到只剩下一个节点。
- 从根节点开始，对每个节点进行编码，左子节点编码为0，右子节点编码为1。
- 对每个字符进行编码，将其对应的编码串连接起来即为哈夫曼编码。

2. 代码实现：

% 定义字符集和对应的频率
symbols = {'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H'};
freq = [0.05, 0.1, 0.15, 0.2, 0.25, 0.1, 0.1, 0.05];

% 构建哈夫曼树
nodes = cell(length(symbols), 1);
for i = 1:length(symbols)
    nodes{i} = struct('Symbol', symbols{i}, 'Freq', freq(i));
end
while length(nodes) > 1
    [freqs, idx] = sort(cellfun(@(x) x.Freq, nodes));
    left = nodes{idx(1)};
    right = nodes{idx(2)};
    newNode = struct('Symbol', {left.Symbol, right.Symbol}, 'Freq', left.Freq + right.Freq);
    nodes = {nodes{idx(3:end)}, newNode};
    nodes = sort(nodes, @(x) x.Freq);
end

% 生成编码表
root = nodes{1};
codeTable = cell(length(symbols), 1);
for i = 1:length(symbols)
    code = '';
    node = root;
    while ~isempty(node.Symbol)
        if ismember(symbols{i}, node.Symbol{1})
            code = [code, '0'];
            node = node(1);
        else
            code = [code, '1'];
            node = node(2);
        end
    end
    codeTable{i} = code;
end

% 输出编码表
for i = 1:length(symbols)
    fprintf('%s: %s\n', symbols{i}, codeTable{i});
end