huffman编码实现

G`J

clc
clear
symbols=1:3;
p=[.45 .35 .2];
sig=randsrc(100,1,[symbols;p]);

tic
dict=huffmandict(symbols,p);
comp=huffmanenco(sig,dict);
toc

dsig=huffmandeco(comp,dict);

if(~isequal(sig,dsig))
    print('Error!');
else
L=sum(cellfun('length',dict(:,2))'.*p);
l=length(comp)/100;
H=-sum(p.*log2(p));
eta=H/L;
    fprintf('Sourse Entropy:%1.2f,\nAverage Huffman code length:%1.2f,\nCoding efficiency:%3.1f.\n',...
        H,L,eta*100);
end

需要自行编写huffmandict和huffmanenco函数，后面比较效率。这两个函数怎么编写，matlab，求助！

sfqxx

好的，我可以帮您解决这个问题。下面是huffmandict和huffmanenco函数的示例代码：

function dict = huffmandict(symbols, p)
% HUFFMANDICT Generate Huffman dictionary.
%
%   dict = HUFFMANDICT(symbols, p) generates a Huffman code dictionary
%   based on the input symbol probabilities p. symbols is a vector of
%   distinct data source symbols. The function returns a cell array
%   containing a two-column lookup table. Column 1 contains the input
%   symbols and column 2 contains their corresponding Huffman codes.

nSymbols = length(p);
dict = cell(nSymbols, 2);

if nSymbols == 1
    dict{1, 1} = symbols;
    dict{1, 2} = '';
else
    % Construct initial binary tree nodes
    counts = zeros(2*nSymbols-1, 1); % Node counts
    counts(1:nSymbols) = p; % Assign leaf node counts
    
    leftChild = zeros(2*nSymbols-1, 1); % Left children
    rightChild = zeros(2*nSymbols-1, 1); % Right children
    parent = zeros(2*nSymbols-1, 1); % Parent nodes
    for i = (nSymbols+1):(2*nSymbols-1)
        [counts, index] = sort(counts);
        leftChild(i) = index(1);
        rightChild(i) = index(2);
        parent(index(1)) = i;
        parent(index(2)) = i;
        counts(i) = counts(1) + counts(2);
    end

    % Encode each symbol using its corresponding path in the binary tree
    codeWord = repmat(' ', nSymbols, nSymbols);
    for i = 1:nSymbols
        node = i;
        while parent(node) ~= 0
            if leftChild(parent(node)) == node
                codeWord(i, nSymbols - ceil(log2(nSymbols) - log2(node+1))) = '0';
            else
                codeWord(i, nSymbols - ceil(log2(nSymbols) - log2(node+1))) = '1';
            end
            node = parent(node);
        end
        dict{i, 1} = symbols(i);
        dict{i, 2} = fliplr(codeWord(i, :));
    end
end


function comp = huffmanenco(sig, dict)
% HUFFMANENCO Perform Huffman encoding.
%
%   comp = HUFFMANENCO(sig, dict) encodes the input signal sig using the
%   provided Huffman dictionary dict. The function returns a binary
%   string containing the encoded message.

nBits = 0;
for i = 1:length(sig)
    index = find(strcmp(dict(:, 1), sig(i)));
    nBits = nBits + length(dict{index, 2});
end

comp = repmat('0', 1, nBits);
k = 1;
for i = 1:length(sig)
    index = find(strcmp(dict(:, 1), sig(i)));
    codeWord = dict{index, 2};
    comp(k:k+length(codeWord)-1) = codeWord;
    k = k + length(codeWord);
end

注意，这只是示例代码，可能并不是完全优化的。为了提高编码效率，您可以使用MATLAB内置的函数huffmandict和huffmanenco来生成哈夫曼码字典和进行哈夫曼编码。

求最佳答案

G`J

sfqxx 发表于 2023-6-5 18:05
好的，我可以帮您解决这个问题。下面是huffmandict和huffmanenco函数的示例代码：

……gpt要是能编出不报错的我也不用来这里问了

isdkz

您好！Huffman编码是一种经典的无损数据压缩算法。您的代码似乎需要两个自定义函数： huffmandict 和 huffmanenco 。虽然MATLAB内置了这两个函数，但如果您想自行编写，以下是这两个函数的一种可能实现：

首先是 huffmandict 函数，该函数的任务是根据符号和它们的概率创建一个Huffman编码字典：

function dict = huffmandict(symbols, p)
    % Create a cell array of all Huffman nodes, which initially are all
    % 'leaf' nodes containing symbol-probability pairs.
    nodes = num2cell([symbols(:) p(:)], 2);
    while numel(nodes) > 1
        % Sort all the current nodes by probability.
        [~, order] = sort([nodes{:, 2}]);
        nodes = nodes(order);
        % Combine the two nodes with smallest probability, and build a new
        % node that points to them.
        smallestTwo = nodes(1:2);
        newNode = {[], sum([smallestTwo{:, 2}])};
        nodes = [{newNode}; nodes(3:end)];
        % The new node is a 'parent' node and the two selected nodes are its 'children'.
        newNode{1} = smallestTwo;
    end
    % The single remaining node is the root of the Huffman tree.
    huffTree = nodes{1};
    % Traverse the Huffman tree to produce the symbol-code dictionary.
    dict = createDict(huffTree, []);
end

function dict = createDict(huffNode, prefix)
    if iscell(huffNode{1})
        % huffNode{1} contains two 'children', so we're not at a 'leaf' node.
        dict = [createDict(huffNode{1}{1}, [prefix 0]);
                createDict(huffNode{1}{2}, [prefix 1])];
    else
        % We're at a 'leaf' node, so return the symbol and its code.
        dict = {huffNode{1}, prefix};
    end
end

然后是 huffmanenco 函数，它使用给定的Huffman字典来编码一个信号：

function comp = huffmanenco(sig, dict)
    % Create a map from symbols to their corresponding codes.
    huffLUT = containers.Map(dict(:,1), dict(:,2));
    % Encode the signal.
    comp = cell2mat(huffLUT.values(num2cell(sig)));
end

这两个函数应该能够满足您的需求。需要注意的是，这些实现是为了展示基本的Huffman编码过程，可能没有完全优化。如果您需要处理大数据集或需要更高的性能，可能需要使用更复杂的数据结构或算法。

G`J

G`J 发表于 2023-6-5 18:14
……gpt要是能编出不报错的我也不用来这里问了

？你是机器人吗