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

Question

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

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

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

如果编码过程是正确的，如何对编码后的向量进行解码？

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

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

Answer 1

没错。三个符号 p11、p12 和 p13 将有一个霍夫曼代码，另一个用于 p21、p22、p23 等。

解码根据当前状态选择使用哪个代码。要么需要假设起始状态，要么需要传输起始状态。

不过这种情况有点奇怪，因为三个符号只有一个霍夫曼码，由1位、2位和2位组成。例如。 0、10、11。因此，您获得的唯一收益是为一位符号选择最高概率。

Answer 2

嗯，解决了上面的问题后，我决定 post 用八度脚本来回答，以防将来有人需要它。

因此，假设有 5 个状态 {1,2,3,4,5}，并且我还有转移概率矩阵 (5x5)。我对 1000 Monte Carlo 次实验的马尔可夫链进行了霍夫曼编码和解码。

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

"variable" 计数是为了确保在所有 MC 实验中，生成的马尔可夫链都得到了正确的编码和解码。（显然，如果 count 等于 1000，那么所有实验的结果都是正确的）

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

Huffman Coding for Markov Chain based on conditional distribution

matlab

huffman-code

markov-chains

information-theory