基于条件分布的马尔可夫链霍夫曼编码

debugcn 发表于 Dev

索蒂里斯·迪米特拉斯

在我开始描述我的问题之前，我想指出这个问题是针对我在大学的一门课程的一个项目，所以我不寻求解决方案，而是寻求提示或解释。

所以，让我们假设有 3 个状态 {1,2,3}，我也有转移概率矩阵（3x3）。我编写了一个基于转换矩阵的 matlab 脚本，它为马尔可夫链创建了一个包含 N 个样本的向量。假设第一个状态是状态 1。现在，我需要根据条件分布 p _{X _n |X _n−1}对该链进行霍夫曼编码。

如果我没记错的话，我认为我必须创建 3 个霍夫曼词典并根据之前的状态（？）对上面链中的每个符号进行编码，这意味着每个符号都将使用三个中的一个进行编码我创建的词典，但并非所有词典都使用相同的词典。

如果编码过程正确，我该如何解码编码向量？

我不确定是否应该这样做。

任何想法，将不胜感激。提前致谢！

索蒂里斯·迪米特拉斯

好吧，解决了上述问题后，我决定用八度音程脚本发布答案，以防将来有人需要它。

所以，让我们假设有 5 个状态 {1,2,3,4,5} 并且我也有转移概率矩阵（5x5）。我霍夫曼编码和解码了 1000 次蒙特卡罗实验的马尔可夫链。

Octave 脚本是：

%starting State of the chain
starting_value = 1;
%Chain Length
chain_length = 100;

%# of Monte Carlo experiments
MC=1000;

%Variable to count all correct coding/encoding experiments
count=0;

%Create unique symbols, and assign probabilities of occurrence to them.
symbols = 1:5; 
p1 = [.5 .125 .125 .125 0.125];
p2 = [.25 .125 .0625 .0625 0.5];
p3 = [.25 .125 .125 .25 0.25];
p4 = [.125 0 .5 .25 0.125];
p5 = [0 .5 .25 .25 0];

%Create a Huffman dictionary based on the symbols and their probabilities.
dict1 = huffmandict(symbols,p1);
dict2 = huffmandict(symbols,p2);
dict3 = huffmandict(symbols,p3);
dict4 = huffmandict(symbols,p4);
dict5 = huffmandict(symbols,p5);

% Create the transition matrix for each state
T= [0.5 0.125 0.125 0.125 0.125;
    0.25 0.125 0.0625 0.0625 0.5;
    0.25 0.125 0.125 0.25 0.25;
    0.125 0 0.5 0.25 0.125 ;
    0 0.5 0.25 0.25 0];

%Initialize Marcov Chain
chain = zeros(1,chain_length);
chain(1)=starting_value;

for i=1 :MC
    comp=[];
    dsig=[];
    %Create Markov Chain
    for i=2:chain_length
        this_step_distribution = T(chain(i-1),:);
        cumulative_distribution = cumsum(this_step_distribution);

        r = rand();

        chain(i) = find(cumulative_distribution>r,1);
    end

    comp=huffmanenco(chain(1),dict1);
    %Encode the random symbols.
    for i=2:chain_length
        if chain(i-1)==1
            comp = horzcat(comp,huffmanenco(chain(i),dict1));
        elseif chain(i-1)==2
            comp = horzcat(comp,huffmanenco(chain(i),dict2));
        elseif chain(i-1)==3
            comp = horzcat(comp,huffmanenco(chain(i),dict3));
        elseif chain(i-1)==4
            comp = horzcat(comp,huffmanenco(chain(i),dict4));
        elseif chain(i-1)==5
            comp = horzcat(comp,huffmanenco(chain(i),dict5));
        end
    end

    %Decode the data. Verify that the decoded data matches the original data.
    dsig(1)=starting_value;
    comp=comp(length(dict1{1,1})+1:end);
    for i=2:chain_length
        if dsig(end)==1
            temp=huffmandeco(comp,dict1);
            comp=comp(length(dict1(temp(1)){1,1})+1:end);
        elseif dsig(end)==2
            temp=huffmandeco(comp,dict2);
            comp=comp(length(dict2(temp(1)){1,1})+1:end);
        elseif dsig(end)==3
            temp=huffmandeco(comp,dict3);
            comp=comp(length(dict3(temp(1)){1,1})+1:end);
        elseif dsig(end)==4
            temp=huffmandeco(comp,dict4);
            comp=comp(length(dict4(temp(1)){1,1})+1:end);
        elseif dsig(end)==5
            temp=huffmandeco(comp,dict5);
            comp=comp(length(dict5(temp(1)){1,1})+1:end);
       end
       dsig=horzcat(dsig,temp(1));
    end
    count=count+isequal(chain,dsig);
end

count

“变量”计数是为了确保在所有 MC 实验中，产生的马尔可夫链被正确编码和解码。（显然，如果count等于1000，那么所有的实验都有正确的结果）

本文收集自互联网，转载请注明来源。

如有侵权，请联系[email protected] 删除。