rickard.n

Nu är det äntligen dags att skriva om det som jag hade som tydligaste syfte med den här bloggen när jag startade den, nämligen programmering. Det har tyvärr inte blivit så mycket med det men nu är det alltså dags. Som inledning hade jag tänkte ta upp lite av det som jag läser om i skolan just nu och det är kodningsteori.

När man ska komprimera data på något sätt utan att förlora någon information, det vill säga förlustfri komprimering, används ofta Huffmankod som är en sorts prefixkod. Prefixkod bygger på att man kodar symboler med olika antal bitar beroende på hur ofta symbolen förekommer. Ju större sannolikhet ju färre bitar och tvärt om. Huffman utvecklade 1952 en algoritm för att beräkna den mest effektiva prefixkoden och algoritmen ersatte därmed Huffmans handledare, Robert Fanos algoritm för att beräkna prefixkoder men som inte alltid ger den mest effektiva. Fanos algoritm kallas också för Shannon-Fano eftersom Fano arbetade med Claude Shannon för att komma fram till algoritmen som helt och hållet baseras på Shannons arbete med informationsteori.

I många kända komprimeringstillämpningar används huffmankod, till exempel i zip, jpeg, och mpeg, naturligtvis i kombination med andra komprimeringsalgoritmer men huffmankod är fortfarande viktig för att generera prefixkod. Jag har gjort en implementation av Fano-kod som jag kommer att publicera här. Syftet är att även implementera Huffmankod och jämföra dessa två och se vilken som är bäst när det gäller effektivitet, komplexitet och resursutnyttjande.

Principen för Fanokod är följande:

Algorithm:

We have a sorted list of elements a₁ to a_n with an associated probability p₁ to p_n. The list is sorted by probability in descending order.

1. Divide the list in two parts so that the total probabilities are as close to being equal as possible.
2. Assign the left sub list 1 and the right 0.
3. Apply step 1 and 2 on each sub list until all lists have a length of one.
4. Enter the accumulated sequence of ones and zeros into the element code attribute.