基于马尔可夫链转移概率的Huffman编码实现问题咨询

你提到的两种编码方案均为合法实现，区别如下：

• 仅为A、B、C、D四个单字符生成编码：属于一阶马尔可夫信源条件哈夫曼编码，也是你当前Matlab代码对应的逻辑：每编码完一个字符，就根据该字符对应的转移概率切换哈夫曼字典。比如前一个输出字符是A，下一个字符就用dict1编码；前一个输出字符是B，下一个就用dict2编码。你当前代码的问题有两个：一是转移矩阵T的第三行多写了一个0，维度不匹配会直接报错；二是缺少了信源稳态分布计算步骤，你需要先求解A、B、C、D的稳态概率，用来生成首个字符的编码字典。
• 为AA、AB、AD等所有双字符组合生成编码：属于扩展信源哈夫曼编码，相当于把两个相邻字符打包为一个新的符号，你需要先计算每个双字符组合的联合概率=前序字符稳态概率×对应转移概率，再将所有16种双字符组合作为符号集生成统一哈夫曼字典即可。该方案不需要编码过程中切换字典，但编码延迟更高，压缩效率和第一种方案基本一致。

代码错误修正 #

先修正转移矩阵的维度错误，正确的代码基础框架如下：

% 修正第三行多余的0，每行4个值对应转移到A、B、C、D的概率
T=[0.7 0.2 0 0.1; 
   0 0.8 0 0.2; 
   0.7 0.1 0.2 0; 
   0 0 0.6 0.4]; 
symbols = ['A','B','C','D'];
p1 = T(1,:);
p2 = T(2,:);
p3 = T(3,:);
p4 = T(4,:);

条件哈夫曼实现（低延迟，推荐） #

1. 求解信源稳态分布π，满足π*T = π且sum(π) = 1，用稳态概率生成首个字符的哈夫曼字典
2. 编码逻辑：首个字符用稳态概率字典编码，后续每个字符根据上一个输出的字符切换对应转移概率字典编码
3. 解码逻辑：先解码出首个字符，后续每个字符根据上一个解码出的字符切换对应转移概率字典解码即可

双字符扩展哈夫曼实现 #

1. 先计算所有16种双字符组合的联合概率p(xy) = π(x) * T(x,y)
2. 将所有双字符组合作为新的符号集，直接调用huffmandict生成统一编码字典即可

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