matlab三元最优霍夫曼编码

### Matlab 中实现三元最优霍夫曼编码

#### 构建频率表
为了创建三元霍夫曼编码，首先需要统计输入数据中各个符号出现的频次。这一步骤对于任何类型的霍夫曼编码都是必要的。

function freqTable = buildFrequencyTable(data)
    uniqueSymbols = unique(data);
    n = length(uniqueSymbols);
    freqTable = zeros(n, 2);
    
    for i = 1:n
        symbol = uniqueSymbols(i);
        count = sum(data == symbol);
        freqTable(i,:) = [symbol, count];
    end
    
    % 将表格按照频率降序排列
    [~, idx] = sort(freqTable(:,2), 'descend');
    freqTable = freqTable(idx,:);
end

#### 创建三叉霍夫曼树
不同于二叉霍夫曼树，在三元情况下，每次迭代会选择三个最小概率节点组合成一个新的父节点[^1]。

classdef TernaryHuffmanNode
    properties
        value;
        frequency;
        children {0};
    end
    
    methods
        function obj = TernaryHuffmanNode(value,frequency)
            if nargin > 0
                obj.value = value;
                obj.frequency = frequency;
            end
        end
        
        function addChild(obj,node)
            obj.children{end+1} = node;
        end
    end
end


function root = createTernaryTree(frequencies)
    nodes = arrayfun(@(i)TernaryHuffmanNode(frequencies{i,1},frequencies{i,2}), ...
                     num2cell(frequencies,2));
                     
    while numel(nodes)>1
        % 对节点按频率升序排序
        sortedNodes = sortrows(cell2table([nodes(:).frequency]),':','ascend').Var1';
        
        newParent = TernaryHuffmanNode([],sum(sortedNodes(1:min(end,3))));
        
        for k=1:min(numel(sortedNodes),3)
            newParent.addChild(nodes{sortedNodes(k)});
            nodes(sortedNodes(k))=[];
        end
        
        nodes{end+1}=newParent; %#ok<AGROW>
    end
    
    root = nodes{1};
end

#### 编码映射生成
一旦建立了三叉霍夫曼树，则可以通过遍历该树来获取每个字符对应的编码字符串。

function codes = generateCodes(node,prefix='')
    if isempty(node.children)
        codes{node.value+1} = prefix;
        return;
    else
        codes = {};
        for i=1:length(node.children)
            childPrefix = strcat(prefix,num2str(i-1)); 
            subcodes = generateCodes(node.children{i},childPrefix);
            codes = [codes;subcodes];
        end
    end
end

#### 数据压缩过程
最后利用上述函数完成实际的数据压缩操作：

data = randi([0 9],1e4,1); % 假设随机整数作为测试样本
freqs = cell2table(buildFrequencyTable(data),'VariableNames',{'Symbol' 'Count'});
treeRoot = createTernaryTree(freqs{:,:});
huffCodes = table(generateCodes(treeRoot)','VariableNames',{'CodeWord'});
compressedData = huffEncode(data,huffCodes);

% 显示前几个原始值及其对应编码
disp(head(horzcat(table(data(1:5)'),huffCodes)))