用MATLAB写哈夫曼编码

在MATLAB中编写哈夫曼编码的过程主要包括构建哈夫曼树和生成编码两个步骤。首先，你需要计算字符频率，然后用这些频率创建一个优先队列，并通过贪心算法构造哈夫曼树。

以下是简化的步骤：

1. **计算字符频率**：
使用`textscan`读取文本文件，统计每个字符出现的次数，并存储在一个结构体（如`charFreq`）或数组中。

filename = 'your_file.txt';
data = textscan(filename,'%c', 'Delimiter', '');
charFreq = containers.Map(data{1}, ones(size(data{1})));

2. **创建优先队列**：
将字符及其频率放入一个优先队列（这里可以使用`prune`函数），通常我们选择最小频率的元素作为左孩子，将剩余元素分为两半并分别插入到新节点的左右子树。

pq = prune(charFreq);
while ~isempty(pq)
    [leftNode, rightNode] = extractMin(pq); % 提取最小节点
    newNode = struct('freq', leftNode.Value + rightNode.Value, 'left', leftNode, 'right', rightNode);
    delete(pq, leftNode); % 移除已合并的节点
    pq = insertSorted(pq, newNode); % 插入新节点
end

3. **构造哈夫曼树**：
最终的优先队列`pq`的根就是哈夫曼树的根，你可以递归地遍历这个树来获取每个字符的编码。

4. **生成编码**：
可以定义一个辅助函数，记录从根到当前节点的路径，每次遇到右分支就加上0，遇到左分支加1，这样就可以得到从根到每个字符的唯一编码。

function code = getHuffmanCode(node, parentCode, path)
    if isfield(node, 'left') && isfield(node, 'right')
        code = char(parentCode(end)+1) + getHuffmanCode(node.left, parentCode, [path, '0']);
        code = char(parentCode(end)) + getHuffmanCode(node.right, parentCode, [path, '1']);
    else
        code = char(parentCode(end));
    end
end

% 调用函数获取所有字符的哈夫曼编码
[~, huffmanCodes] = cellfun(@(x)getHuffmanCode(x, '', []), pq.values, 'UniformOutput', false);