HasLowerProb [{a1_, p1_}, {a2_, p2_}] := (p1 < p2);

ILN [x_] := If [x == 0, 0, - x * Log [x]] / Log [2];

HN[seq_] :=  Simplify[Sum[ILN [seq[[i]]], {i, 1, Length[seq]}]];

Summe [{}] := 0;
Summe [a_] := Module[{i, summe},
                    summe = 0;
                    i = 1;
                    While[ i <= Length[a],
                       summe = summe + a[[i]];
                       i = i + 1];
                       summe];



Huffman [D_, seq_] :=
   Module[{imin, lengthseq, min1, min2, newseq, seq2},
         If [ Length [seq]  <= 1,
                seq, 
                     (* else *)                
            seq2 = seq;
            (* Print[seq2] *); 
            (* find position of the two minimum probs *)
            newseq = Sort [ seq2, HasLowerProb ];
            min1 = Take [newseq, D];
            newseq = Append [ Drop [newseq, D],
                             { Map [Function [x, min1[[x]] [[1]] ],
                                  Range[1,D]],
                               Summe [
                                  Map [Function [x, min1[[x]] [[2]] ],
                                       Range[1,D]]
                                     ] 
                             }
                            ];
           (* Print [newseq] *);
           Huffman [D, newseq]]]


Huff [D_, seq_] := Huffman [D,
                        (* Add symbols so that length is 
                           congruent to
                           1 modulo D-1 *) 
                           Join [seq,
                                 Table[{j + 1000, 0}, 
                                       {j,1, Mod [D-Length[seq], D-1]}]]] [[1]][[1]]
          

Codewort [xi_, huff_] :=
Position [huff, xi];

ProbDistribution [frqlist_] := 
Map[Function[x,x[[2]]], frqlist];

IL [x_] := If [x == 0, 0, - x * Log [x] / Log[2]];
H[seq_] := Simplify[Sum[IL [seq[[i]]], {i, 1, Length[seq]}]];

Entropy [seq_] := H[ProbDistribution[seq]]
AverageCodeWordLength[frqlist_, huff_] := 
Summe [ Map [Function [x, x[[2]] * Length [ Codewort[ x[[1]], huff ] [[1]] ]],
            frqlist]];

frqlist = {{"A", 9/10},
           {"B", 6/100},
           {"C", 15/1000},
           {"D", 15/1000},
           {"E", 1/100}}

Mult [a_, b_] := 
Module [{prod, i, j},
   prod = {};
   i = 1;
   While [i <= Length [a], 
      j = 1;
      While [j <= Length [b],
         prod = Append [prod, a[[i]] * b[[j]]];
         j = j+1;
      ];
      i = i + 1;
   ];
   prod
];

f2 = Mult[frqlist, frqlist];  


huff = Huff [2, f2];
Print [Map [Function[x, {x, Codewort[x[[1]],huff]}], f2]];


(* Berechne die Entropie *)

Print ["Entropy"];
Print [N[ Entropy[f2]]];

(* Berechne die durchschnittliche Codewortlaenge *)
     Print ["Codewortlaenge"];
     Print [N[AverageCodeWordLength [f2, huff]]];


              

















