matlab算法实现改进的香农编码

Question

matlab实现下面编码：
香农编码存在的的不足主要是香农编码方法由于在编码过程中以码字的码长作为先决条件而没有考虑各个码字之间的相关性，这就导致了编码结果会出现很大的冗余，往往编码效率很低。比如某个码字编码为111，但由于香农编码规则事先规定了该码字的先定码长为6，因此该码字的码长就必须为6。显而易见，由于对码长的限制，会导致码字的平均码长变大，从而降低了编码效率。
针对上面的缺点，本文通过如下的优化算法对香农编码效率进行提高和改善。
优化算法原理是首先忽略码字的码长限定，只根据最小概率来计算其对应的码长l，接着以此为参考，计算出所有累加概率对应的二进制串，并对二进制串的长度作出规定，即规定所有的二进制串的长度均为l，然后从每个长度为l的二进制串中选择符合原则的码字，码字选取的原则是任意一个码字一定不是前后备用码的前缀，同时码字的选择必须要从二进制串的最左端开始。从左往右依次选取。具体步骤如下：
（1）将信源符号按照递减顺序降序排列；
（2）计算概率最小符号的对数值，；
（3）计算出第j个符号的累加概率；
（4）将每个符号对应的累加概率进行二进制转换，取小数点后面的j位作为备用码；
（5）选取符号所对应的码字原则为：
码字的选取从概率最大的符号对应的备用码的第一个二进制位开始，从前往后依次选取；
码字的选取不能是前后备用码的前缀，而且每个码字的选取应尽可能短。
结果显示编码效率以及编码结果，最好能对比传统的香农编码和改进的香农编码的运行时间

Answer 1

该回答引用ChatGPT

如有疑问，可以回复我！

运行结果

代码如下：

% 定义信源符号及其对应的概率
source = ['A', 'B', 'C', 'D', 'E'];
prob = [0.5, 0.2, 0.15, 0.1, 0.05];

% 首先按照递减顺序对信源符号进行排序
[sorted_prob, index] = sort(prob, 'descend');
sorted_source = source(index);

% 计算最小概率对应的码长
L_min = ceil(log2(1/sorted_prob(end)));

% 计算每个符号对应的累加概率
cum_prob = cumsum(sorted_prob);

% 将每个符号的累加概率转换成二进制串，取小数点后 L_min 位作为备用码
binary_cum_prob = dec2bin(round(cum_prob * 2^L_min), L_min+1);

% 为每个符号选取码字
codewords = cell(size(source));
used_codewords = cell(size(source));
for i = 1:length(source)
    % 选取符号对应的备用码
    binary_code = binary_cum_prob(i, 2:end);
    
    % 从备用码中选取不是前后备用码前缀的码字
    used_codewords_cell = cell(1, length(used_codewords));
    for j = 1:length(used_codewords)
        used_codewords_cell{j} = char(used_codewords{j});
    end
    used_codewords_str = join(used_codewords_cell, '');
    for j = 1:L_min
        codeword = binary_code(1:j);
        if ~startsWith(used_codewords_str, codeword)
            codewords{i} = codeword;
            used_codewords{i} = [used_codewords{i}, {codeword}];
            break;
        end
    end
end

% 打印编码结果
fprintf('信源符号\t概率\t码字\n');
for i = 1:length(source)
    fprintf('%c\t\t%.2f\t%s\n', sorted_source(i), sorted_prob(i), codewords{i});
end