信息论压缩算法--香农码

香农编码（通常指香农-范诺编码）是一种基于符号概率构建前缀码的变长无失真信源编码方法，其基本原理是：将信源符号按概率降序排列，递归二分划分为概率和近似相等的两组，逐层分配二进制码元（0/1），使高频符号对应短码、低频符号对应长码，码长近似取为 li=⌈−log⁡2pi⌉li​=⌈−log2​pi​⌉，确保前缀性与可译性。‌‌

• ‌步骤1‌：将信源符号按概率从大到小排序；
• ‌步骤2‌：递归将符号集划分为两个概率和尽可能接近的子集，分别赋予码元 0 和 1；
• ‌步骤3‌：对每个子集重复划分，直至每个子集仅含一个符号；
• ‌步骤4‌：从根到叶的路径即为该符号的二进制码字（自上而下构建码树）。‌‌

需注意：‌香农编码 ≠ 香农第一定理（信源编码定理）‌；前者是具体编码方法（非最优，效率常低于哈夫曼编码），后者是证明“平均码长 ≥ 熵，且可达逼近”的存在性定理。香农编码虽理论意义重要，但因划分方式不唯一、常未能充分利用短码，实际已较少单独使用。‌‌

%定义信源 px=[0.2,0.19,0.18,0.17,0.15,0.10,0.01]; hx=0; %码长 l=[]; decode=[]; g=0; G=[]; ca=[]; HX=0; strArray={'0.'}; for i=1:length(px)-1 strArray=[strArray,{'0.'}]; end % 对码源进行递减排列 px=sort(px,'descend'); %码长 decode=ceil(-log2(px)); G=[0,cumsum(px)]; G=G(1:end-1); %码字求取 temp=G; for i=1:length(px) for j=1:decode(i) strArray{i}=strcat(strArray{i},int2str(floor(temp(i)*2))); temp(i)=temp(i)*2-floor(temp(i)*2); end end for i=1:length(px) temp1=strArray{i}; ca=[ca,{temp1(3:3+decode(i)-1)}]; end %UI建设 fprintf('=============编码结果===========\n'); fprintf('概率\t\t累加概率\t\t码长\t\t码字\n'); for i=1:length(px) fprintf('%.2f\t%.2f\t\t%d\t\t%s\n',px(i),G(i),decode(i),ca{i}); end %把元胞数组转换成字符串数组 substr_lengths = cellfun(@length, ca); avg_length = mean(substr_lengths); fprintf('平均子串长度: %.2f\n', avg_length); fprintf('平均熵:%g\n', sum(px.*(-log2(px))));