編碼霍夫曼樹的算法

我有一個編碼序列的程序，即用霍夫曼方法創建碼字。編碼霍夫曼樹的算法

我需要對樹本身進行編碼，其中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

這是合理的，我看到了，我仍然想按照我描述的方式對樹進行編碼 –

編碼霍夫曼樹的算法

回答

相關問題