Rešitev: Huffmanovo kodiranje

Iz MaFiRaWiki

Naloga: Huffmanovo kodiranje

 Clear[frekvence]

frekvence::usage = "frekvence[pod] vrne par {f,z}, pri čemer so f relativne frekvence znakov z, ki nastopajo v nizu pod.";

 frekvence[pod_] := Module[{p = ToUpperCase[Characters[pod]], znaki, tmp},
 znaki = Union[p];
 frek = Map[Count[p, #] &, znaki];
 tmp = Map[{#[1], #} &, Transpose[{frek, znaki}]];
 Return[Sort[tmp]]];


 Clear[zdruzi, drevo]
 zdruzi[{f_, z_}, {f1_, z1_}] := {f + f1, {z, z1}}
 zdruzi[frek_] := Module[{prvi = frek[1], drugi = frek[2], novi},
 novi = zdruzi[prvi, drugi]; 
 Sort[Append[Drop[frek, 2], novi]]
 ]
 drevo[frek_] := Module[{n = Length[frek]}, First[Nest[zdruzi, frek, 
 n - 1]][2]];


 Clear[podatek, podatek1];
 podatek = "AAAABBCCCD";                                                 
 podatek1 = "Ne vem kaj ti naj napišem.";
 Clear[koda, pravakoda, kodiraj]
 koda[drevo_] := koda[drevo, ""]
 koda[{levi_List, desni_List}, tk_] := {koda[levi, tk <> "1"], koda  [desni, tk <> "0"]}
 koda[znak_, tk_] := tk
 pravakoda[drevo_] := Module[{k = koda[drevo]}, Transpose[{Transpose  [Partition[
 Flatten[drevo], 2]][2], Flatten[k]}]]
 kodiraj[besedilo_, koda_] := 
 Apply[StringJoin, Characters[besedilo] /. Map[(#[1] -> #[2] &), koda]]

Poglejmo si delovanje programa:

 In[118]:= frekvence[podatek1]
 Out[118]= {{1,{1,.}},{1,{1,K}},{1,{1,P}},{1,{1,Š}},{1,{1,T}},{1,{1,V}},
           {2,{2,I}},{2,{2,J}},{2,{2,M}},{3,{3,A}},{3,{3,E}},{3,{3,N}},{5,{5, }}}
 In[119]:= drevo[%]
 Out[119]= {{{5, },{{3,A},{3,E}}},{{{3,N},{{2,I},{2,J}}},{{{2,M},{{1,.},{1,K}}},
           {{{1,P},{1,Š}},{{1,T},{1,V}}}}}}
 In[120]:= kodiraj["ABCDAB",{{"A","010"},{"B","1111"},{"C","00"},{"D","110011"}}]
 Out[120]= 0101111001100110101111
 In[121]:= Apply[StringJoin,%]
 Out[121]=0101111001100110101111
 In[122]:= frekvence[podatek1]
 Out[122]= {{1,{1,.}},{1,{1,K}},{1,{1,P}},{1,{1,Š}},{1,{1,T}},{1,{1,V}},
           (2,{2,I}},{2,{2,J}},{2,{2,M}},{3,{3,A}},{3,{3,E}},{3,{3,N}},{5,{5, }}}
 In[123]:= drevo[%]
 Out[123]= {{{5, },{{3,A},{3,E}}},{{{3,N},{{2,I},{2,J}}},{{{2,M},{{1,.},
           {1,K}}},{{{1,P},{1,Š}},{{1,T},{1,V}}}}}}
 In[124]:= pravakoda[%]
 Out[124]= {{ ,11},{A,101},{E,100},{N,011},{I,0101},{J,0100},{M,0011},{.,00101},
           {K,00100},{P,00011},{Š,00010},{T,00001},{V,00000}}
 In[125]:= kodiraj["MATEMATIKA",%]
 Out[125]= 001110100001100001110100001010100100101
 In[126]:= Partition[Flatten[%%%],2]
 Out[126]= {{5, },{3,A},{3,E},{3,N},{2,I},{2,J},{2,M},{1,.},{1,K},
           {1,P},{1,Š},{1,T},(1,V}}
 In[127]:= Transpose[%%%][2]
 Out[127]= {11,101,100,011,0101,0100,0011,00101,00100,00011,00010,00001,00000}
 In[128]:= Transpose[{%%,%}]
 Out[128]= {{{5, },11},{{3,A},101},{{3,E},100},{{3,N},011},{{2,I},0101},
           {{2,J},0100},{{2,M},0011},{{1,.},00101},{{1,K},00100},
           {{1,P},00011},{{1,Š},00010},{{1,T},00001},{{1,V},00000}}
 In[129]:= Clear[s,f,d,p]
 s="HUFFMANOVO KODIRANJE"
 f = frekvence[s]
 d =drevo[f]
 p=pravakoda[d]
 kodiraj[s,pravakoda[d]]
 Out[130]= HUFFMANOVO KODIRANJE
 Out[131]= {{1,{1, }},{1,{1,D}},{1,{1,E}},{1,{1,H}},{1,{1,I}},{1,{1,J}},{
           1,{1,K}},{1,{1,M}},{1,{1,R}},{1,{1,U}},{1,{1,V}},{2,{2,A}},{
           2,{2,F}},{2,{2,N}},{3,{3,O}}}
 Out[132]= {{{{{1, },{1,D}},{{1,E},{1,H}}},{{{1,I},{1,J}},{{1,K},{1,M}}}},{{{{1,R},{1,U}},{
           3,O}},{{{1,V},{2,A}},{{2,F},{2,N}}}}}
 Out[133]= {{ ,1111},{D,1110},{E,1101},{H,1100},{I,1011},{J,1010},{K,1001},{M,1000},{
           R,0111},{U,0110},{O,010},{V,0011},{A,0010},{F,0001},{N,0000}}
 Out[134]= 11000110000100011000001000000100011010111110010101110101101110010000010101101
Osebna orodja