허프 먼 트리를 인코딩하는 알고리즘

Question

나는 시퀀스를 인코딩하는 프로그램을 가지고있다. 즉, 허프만 방법을 사용하여 코드 워드를 만든다.

node = 0, leaf = 1 인 트리 자체를 인코딩해야합니다. 첫 번째 요소 (0)에 2 개의 자식이 있고 다음 두 요소 (예 : 00)에도 각각 두 개의 자식이 있고 다음 4 개 (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 

`

Answer 1

일반적으로, 당신은 각각의 심볼에 대한 코드 워드의 길이를 인코딩합니다. 당신이 당신의 나무를 구축하고 예를 들어, 당신은

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

를 사용해서 그냥 물론 [2,1,3,3]

같은 길이의 배열을 쓰는 얻을 생산 나무 많이 있습니다 동일한 코드 길이이지만 모두 똑같이 효율적이기 때문에 어떤 코드를 사용하든 상관 없습니다. 길이를 작성 후 보낸 사람이 정확히 같은 방식으로 길이에서 새 트리를 구축 있도록

보낸 사람과받는 사람은, 그래도 같은 트리를 사용해야합니까, 수신기는 것이다 예를 들어,

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

송신자와 수신자가 동일한 트리를 작성하는 한 모든 것이 올바르게 작동하므로 하나의 등가 트리를 다른 트리와 구별하는 모든 중복 정보를 전송하지 않아도됩니다.