ハフマンツリーを符号化するアルゴリズム

Question

私は、シーケンスを符号化するプログラムを持っています。つまり、ハフマン法を使ってコードワードを作成します。

私はツリー自体をエンコードする必要があります。node = 0、leaf = 1です。最初の要素（0）には2つの子があり、次の2つの要素（たとえば00）にはそれぞれ2つの子があり、次の4つ（10 00）には1つの葉があり、 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 

`

Answer 1

通常、あなただけの各シンボルのコードワードの長さを符号化します。あなたのツリーを構築し、あなたがちょうどもちろん[2,1,3,3]

のような長さの配列を書き出す

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

ザ・を取得した場合、生産の木がたくさんあります同じコードの長さですが、どのコードを使用するかは関係ありません。なぜなら、すべて同じ効率があるからです。長さを書き込んだ後、送信者が全く同じように長さから、新しいツリーを構築するよう

送信者と受信者は、しかし、同じツリーを使用しなければならないの、受信機がすること例えば、

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

送信者と受信者が同じツリーを構築する限り、すべて正常に動作し、1つの同等のツリーを別のツリーと区別するすべての冗長な情報を送信しないようにしました。