# Rešitev: 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
```