编码霍夫曼树的算法

我有一个编码序列的程序，即用霍夫曼方法创建码字。编码霍夫曼树的算法

我需要对树本身进行编码，其中node = 0，leaf = 1。它应该像一个二进制堆，我猜，其中第一个元素（0）表示它有2个孩子，接下来的两个元素（例如00）每个都有两个孩子，接下来的四个（10 00） - 有一个叶子和3个非叶孩子等

我有一个给定序列的结果，但我不知道如何得到它。

function [ ] = encodeTwoPassHuff() 
global CODE 
global codeTree 
codeTree=[]; 
clc; 

inputStr='IF_WE_CANNOT_DO_AS_WE_WOULD_WE_SHOULD_DO_AS_WE_CAN'; 
a=unique(inputStr); 
N=size(inputStr,2); 
Nx = zeros(1, size(a, 2)); 
for i = 1:size(a,2) 
    for j = 1:N   
     if (a(i) == inputStr(j)) 
      Nx(i) = Nx(i)+1; 
     end 
    end 
end 
for i = 1 : size(a, 2) 
    prob(i) = Nx(i)/N; 
end 


CODE = cell(length(prob), 1); 


p=prob; 
s = cell(length(p), 1); 
for i = 1:length(p) 
    s{i} = i; 
end 

while size(s, 1) > 2 
    [p,i] = sort(p, 'ascend'); 
    p(2) = p(1) + p(2); 
    p(1) = []; 
    s = s(i);   
    s{2} = {s{1},s{2}}; 
    s(1) = [];   
end 


CODE = makecode(s, []);  


fprintf('00010000010100110111101101111\n'); % encoded tree (true) 
fprintf('%d', codeTree); % my result 
fprintf('\n'); 

for i = 1:length(CODE) 
    len(i) = length(CODE{i}); 
end 

% print 
disp('symbol | probabil | len | codeword'); 
for i=1:length(prob) 
     fprintf('%5s\t %.4f\t %3d\t %s\n', a(i), prob(i), len(i), num2str(CODE{i})); 
end 

end 


function [CODE]=makecode(ss, codeword) 
global CODE 
global codeTree 

if isa(ss,'cell') % node 
    codeTree = [codeTree 0]; 
    makecode(ss{1}, [codeword 1]); 
    makecode(ss{2}, [codeword 0]); 

else    % leaf 
    CODE{ss} = char('0' + codeword); 
    codeTree = [codeTree 1]; 
end 
end

来源

2017-04-30 Ans-lte

不幸的是，那不是霍夫曼树。 – beaker

@beaker，哦，好吧，也许你可以改进它？我认为没关系，只要它能够提供与经过验证的霍夫曼代码相同的平均码字长度。 –

我不明白你怎么可以做出这种说法，当你不仅不能生成树，但你的代码不起作用。你甚至没有足够描述你想要做什么。 – beaker

通常情况下，你只是编码每个符号的码字的长度。例如，如果你建立你的树，你会得到

A -> 10 
B -> 0 
C -> 111 
D -> 110

的你刚写出来的长度阵列状[2,1,3,3]

当然，也有大量的树木产生代码长度相同，但使用哪一个并不重要，因为它们的效率都是相同的。

的发送者和接收者都必须使用相同树，不过，这样写出来的长度后，发送者建立从上长新树以完全相同的方式，接收器将，例如，

A -> 00 
B -> 1 
C -> 010 
D -> 011

只要发送者和接收者构建了同一棵树，一切正常，并且避免了传输所有可以区分一个等价树的冗余信息。

来源

2017-04-30 18:21:14

这是合理的，我看到了，我仍然想按照我描述的方式对树进行编码 –

编码霍夫曼树的算法

回答

相关问题