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

香农编码通常指香农-范诺编码是一种基于符号概率构建前缀码的变长无失真信源编码方法其基本原理是将信源符号按概率降序排列递归二分划分为概率和近似相等的两组逐层分配二进制码元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]; hx0; %码长 l[]; decode[]; g0; G[]; ca[]; HX0; strArray{0.}; for i1:length(px)-1 strArray[strArray,{0.}]; end % 对码源进行递减排列 pxsort(px,descend); %码长 decodeceil(-log2(px)); G[0,cumsum(px)]; GG(1:end-1); %码字求取 tempG; for i1:length(px) for j1:decode(i) strArray{i}strcat(strArray{i},int2str(floor(temp(i)*2))); temp(i)temp(i)*2-floor(temp(i)*2); end end for i1:length(px) temp1strArray{i}; ca[ca,{temp1(3:3decode(i)-1)}]; end %UI建设 fprintf(编码结果\n); fprintf(概率\t\t累加概率\t\t码长\t\t码字\n); for i1: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))));