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函数的示例代码：

1. function dict = huffmandict(symbols, p)
   
2. % HUFFMANDICT Generate Huffman dictionary.
   
3. %
   
4. %   dict = HUFFMANDICT(symbols, p) generates a Huffman code dictionary
   
5. %   based on the input symbol probabilities p. symbols is a vector of
   
6. %   distinct data source symbols. The function returns a cell array
   
7. %   containing a two-column lookup table. Column 1 contains the input
   
8. %   symbols and column 2 contains their corresponding Huffman codes.
   
9. 
   
10. nSymbols = length(p);
    
11. dict = cell(nSymbols, 2);
    
12. 
    
13. if nSymbols == 1
    
14.     dict{1, 1} = symbols;
    
15.     dict{1, 2} = '';
    
16. else
    
17.     % Construct initial binary tree nodes
    
18.     counts = zeros(2*nSymbols-1, 1); % Node counts
    
19.     counts(1:nSymbols) = p; % Assign leaf node counts
    
20.    
    
21.     leftChild = zeros(2*nSymbols-1, 1); % Left children
    
22.     rightChild = zeros(2*nSymbols-1, 1); % Right children
    
23.     parent = zeros(2*nSymbols-1, 1); % Parent nodes
    
24.     for i = (nSymbols+1):(2*nSymbols-1)
    
25.         [counts, index] = sort(counts);
    
26.         leftChild(i) = index(1);
    
27.         rightChild(i) = index(2);
    
28.         parent(index(1)) = i;
    
29.         parent(index(2)) = i;
    
30.         counts(i) = counts(1) + counts(2);
    
31.     end
    
32. 
    
33.     % Encode each symbol using its corresponding path in the binary tree
    
34.     codeWord = repmat(' ', nSymbols, nSymbols);
    
35.     for i = 1:nSymbols
    
36.         node = i;
    
37.         while parent(node) ~= 0
    
38.             if leftChild(parent(node)) == node
    
39.                 codeWord(i, nSymbols - ceil(log2(nSymbols) - log2(node+1))) = '0';
    
40.             else
    
41.                 codeWord(i, nSymbols - ceil(log2(nSymbols) - log2(node+1))) = '1';
    
42.             end
    
43.             node = parent(node);
    
44.         end
    
45.         dict{i, 1} = symbols(i);
    
46.         dict{i, 2} = fliplr(codeWord(i, :));
    
47.     end
    
48. end
    
49. 
    
50. 
    
51. function comp = huffmanenco(sig, dict)
    
52. % HUFFMANENCO Perform Huffman encoding.
    
53. %
    
54. %   comp = HUFFMANENCO(sig, dict) encodes the input signal sig using the
    
55. %   provided Huffman dictionary dict. The function returns a binary
    
56. %   string containing the encoded message.
    
57. 
    
58. nBits = 0;
    
59. for i = 1:length(sig)
    
60.     index = find(strcmp(dict(:, 1), sig(i)));
    
61.     nBits = nBits + length(dict{index, 2});
    
62. end
    
63. 
    
64. comp = repmat('0', 1, nBits);
    
65. k = 1;
    
66. for i = 1:length(sig)
    
67.     index = find(strcmp(dict(:, 1), sig(i)));
    
68.     codeWord = dict{index, 2};
    
69.     comp(k:k+length(codeWord)-1) = codeWord;
    
70.     k = k + length(codeWord);
    
71. end

复制代码

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

求最佳答案

G`J

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

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

isdkz

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

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

1. function dict = huffmandict(symbols, p)
   
2.     % Create a cell array of all Huffman nodes, which initially are all
   
3.     % 'leaf' nodes containing symbol-probability pairs.
   
4.     nodes = num2cell([symbols(:) p(:)], 2);
   
5.     while numel(nodes) > 1
   
6.         % Sort all the current nodes by probability.
   
7.         [~, order] = sort([nodes{:, 2}]);
   
8.         nodes = nodes(order);
   
9.         % Combine the two nodes with smallest probability, and build a new
   
10.         % node that points to them.
    
11.         smallestTwo = nodes(1:2);
    
12.         newNode = {[], sum([smallestTwo{:, 2}])};
    
13.         nodes = [{newNode}; nodes(3:end)];
    
14.         % The new node is a 'parent' node and the two selected nodes are its 'children'.
    
15.         newNode{1} = smallestTwo;
    
16.     end
    
17.     % The single remaining node is the root of the Huffman tree.
    
18.     huffTree = nodes{1};
    
19.     % Traverse the Huffman tree to produce the symbol-code dictionary.
    
20.     dict = createDict(huffTree, []);
    
21. end
    
22. 
    
23. function dict = createDict(huffNode, prefix)
    
24.     if iscell(huffNode{1})
    
25.         % huffNode{1} contains two 'children', so we're not at a 'leaf' node.
    
26.         dict = [createDict(huffNode{1}{1}, [prefix 0]);
    
27.                 createDict(huffNode{1}{2}, [prefix 1])];
    
28.     else
    
29.         % We're at a 'leaf' node, so return the symbol and its code.
    
30.         dict = {huffNode{1}, prefix};
    
31.     end
    
32. end
    

复制代码

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

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

复制代码

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

G`J

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

？你是机器人吗