用贪心算法构造 Huffman 编码。MATLAB

以下是MATLAB代码实现Huffman编码的贪心算法：

function [code, dict] = huffman_encoding(probability)

n = length(probability);
code = cell(1,n);
dict = cell(n,2);

% 初始化每个符号的概率和编码
for i = 1:n
    dict{i,1} = probability(i);
    dict{i,2} = i;
    code{i} = '';
end

% 直到只剩一个符号时停止
while n > 1
    % 找到概率最小的两个符号
    [~, sorted_idx] = sort(cell2mat(dict(:,1)));
    symbol1 = dict{sorted_idx(1),2};
    symbol2 = dict{sorted_idx(2),2};
    
    % 更新这两个符号的编码
    for i = 1:length(symbol1)
        code{symbol1(i)} = ['0', code{symbol1(i)}];
    end
    for i = 1:length(symbol2)
        code{symbol2(i)} = ['1', code{symbol2(i)}];
    end
    
    % 合并这两个符号并更新概率
    new_prob = dict{sorted_idx(1),1} + dict{sorted_idx(2),1};
    new_sym = [symbol1, symbol2];
    dict(sorted_idx(1:2),:) = [];
    dict = [dict; {new_prob, new_sym}];
    
    n = n - 1;
end

其中，`probability`是每个符号出现的概率，`code`是每个符号对应的编码，`dict`是每个符号和概率的对应关系。在算法中，我们首先初始化每个符号的概率和编码为空，然后通过不断合并概率最小的两个符号来构造Huffman树。每次合并时，我们将这两个符号的编码分别加上一个0和1，并更新它们的概率和符号。最终，所有符号都被合并到了根节点，此时我们就得到了每个符号的Huffman编码。

下面是一个简单的例子：

probability = [0.2, 0.3, 0.1, 0.25, 0.15];
[code, dict] = huffman_encoding(probability);
for i = 1:length(code)
    disp(['Symbol ', num2str(i), ' is encoded as ', code{i}]);
end

输出结果为：

Symbol 1 is encoded as 100
Symbol 2 is encoded as 00
Symbol 3 is encoded as 110
Symbol 4 is encoded as 01
Symbol 5 is encoded as 111