2024年5月5日-matlab

正在编写matlab程序，以实现哈夫曼编码

思路

• 第一步，降序排列符号
• 第二步，将0和1分别分配给概率最小的两个码元
• 第三步，将概率最小的这两个码元进行概率相加
  • 然后重复第一步到第三步，直到数组长度变为1
  • 以上过程中，0和1记录在code矩阵中，code是一个N-1×N的矩阵，
• 第四步，从上往下读取编码后的结果，将离散的0和1串联成为01序列

其中，一到四步在循环内完成。

同时对两个数组进行排序

[p_SD,reflect(i,1:M)] = sort(p_SD,'descend');

这一句的意思是对 p_SD、reflect的第i行的1～M位进行排序，顺序是按照p_SD的大小降序。matlab的代码在直观性上很抽象。虽然确实很强大。

要求长度一样即可。

注意对于矩阵的一行排序的时候，其他行不会被改变。

参考代码思路梳理

参考代码来自https://blog.csdn.net/weixin_46258766/article/details/117607050

原本的全部代码：

%% 实验四：哈夫曼编码仿真实现
clear all
clc
% 用户输入符号概率
p = input('请输入离散信源概率分布，例如[0.5,0.5]：\n');
N = length(p);

% 将概率排序并获得单步码字排序
code = strings(N-1,N);% 初始化单步过程的码字
reflect = zeros(N-1,N);% 初始化位置对应向量
p_SD = p;% p_SD为每次得到的概率排序数组
for i=1:N-1           % i表示排序后第几个符号
    M = length(p_SD);
    [p_SD,reflect(i,1:M)] = sort(p_SD,'descend');% 将概率从大到小进行排序
    code(i,M) = '1';% 概率最小的是1
    code(i,M-1) = '0';% 概率第二小的暂且定义为0
    p_SD(M-1) = p_SD(M-1)+p_SD(M);% 将最后两个概率相加
    p_SD(M)=[];
end

% 根据位置对应向量和单步过程的码字计算对应码字
CODE = strings(1,N); % 初始化对应码字
for i=1:N
    column = i;
    for m=1:N-1
        [row,column] = find(reflect(m,:)==column);
        CODE(1,i) = strcat(CODE(1,i),code(m,column));
        % 将最小的两个概率映射成一个
        if column==N+1-m
            column = column-1;
        end
    end
end
CODE = reverse(CODE);

% 计算平均码长
for i=1:N
    L(i) = size(char(CODE(1,i)),2);
end
L_ave = sum(L.*p);      
H = sum(-p.*log2(p));   % 计算信源信息熵
yita = H/L_ave;         % 计算编码效率

% 展示输出码字、平均码长和编码效率
disp(['信号符号  ',num2str(1:N)]);
disp(['对应概率  ',num2str(p)]);
disp(['对应码字  ',CODE]);
disp(['平均码长',num2str(L_ave)]);
disp(['编码效率',num2str(yita)]);

第一段，准备：

初始化用到的向量，矩阵，还有概率数组。

clear all
clc
% 用户输入符号概率
p = input('请输入离散信源概率分布，例如[0.5,0.5]：\n');
N = length(p);

% 将概率排序并获得单步码字排序
code = strings(N-1,N);% 初始化单步过程的码字
reflect = zeros(N-1,N);% 初始化位置对应向量
p_SD = p;% p_SD为每次得到的概率排序数组

第一个循环：

1. 排序：同时排序p_SD和reflect的第i行
2. 对code进行赋值
3. 概率相加，最后一位消除

总之p_SD始终是从大到小的概率降序，在排序过程中，reflect会记录每一次循环中的排序结果。reflect和code都是N-1×N大小的矩阵，每一行对应循环中的一轮。

for i=1:N-1           % i表示排序后第几个符号
    M = length(p_SD);
    [p_SD,reflect(i,1:M)] = sort(p_SD,'descend');% 将概率从大到小进行排序
    code(i,M) = '1';% 概率最小的是1
    code(i,M-1) = '0';% 概率第二小的暂且定义为0
    p_SD(M-1) = p_SD(M-1)+p_SD(M);% 将最后两个概率相加
    p_SD(M)=[];
end

第二个循环：

将之前得到的code、reflect合并成为CODE。

m 对应行，i 对应列（的末尾）。i 也可以说是对应 CODE 的每一个元素，或者说是每一个码字。

中间的一层循环是对于每一行进行扫描，首先找到 reflect 的这一行中数值与 column 相同的那一列，然后根据找到的这个数据的位置，找到 code 里面对应的数据（0 或者 1），连接在 CODE 对应位置数据的尾端。

如果 column == N+1-m，也就是找到的数据位置在右边的那个对角线上，那么往左挪一格。

用文字说明起来可能很抽象。

总之就是 (m,column) 这个坐标的移动是二者的先后移动。呈现在图形上就是锯齿状的移动。每一行上，只有右对角线和左对角线上面的数据是有意义的，记录着 0 和 1。

% 根据位置对应向量和单步过程的码字计算对应码字
CODE = strings(1,N); % 初始化对应码字
for i=1:N
    column = i;
    for m=1:N-1
        [row,column] = find(reflect(m,:)==column);
        CODE(1,i) = strcat(CODE(1,i),code(m,column));
        % 将最小的两个概率映射成一个
        if column==N+1-m
            column = column-1;
        end
    end
end
CODE = reverse(CODE);

数据处理：

% 计算平均码长
for i=1:N
    L(i) = size(char(CODE(1,i)),2);
end
L_ave = sum(L.*p);      
H = sum(-p.*log2(p));   % 计算信源信息熵
yita = H/L_ave;         % 计算编码效率

展示：

% 展示输出码字、平均码长和编码效率
disp(['信号符号  ',num2str(1:N)]);
disp(['对应概率  ',num2str(p)]);
disp(['对应码字  ',CODE]);
disp(['平均码长',num2str(L_ave)]);
disp(['编码效率',num2str(yita)]);

思路

在第一轮循环中，直接记录 CODE。

即，CODE 和 table_data 等宽，table_data 第一行为码字，第二行为概率，第三行为12345的顺序。每一轮循环中，顺序的最后两个被分别赋予 0 和 1。注意不是数组的最后两个，而是table_data第三行的最小的两个。也就是 N-i（对应1） 和 N-i-1（对应0）。