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.

I dagarna har jag knackat lite C-kod igen. Det var inte så länge sen i och för sig och det börjar kännas bekvämt att arbeta i. Jag har äntligen, eller ska vi säga slutligen, insätt att för att programmera smidigt i Linux-miljö räcker det inte med att behärska programspråket. Man måste även kunna en hel del om miljön och olika verktyg som finns till hands för att underlätta arbetet. Linux innehåller ju en rad mängd verktyg som från början antagligen utformades för att fylla något behov i samband med programutveckling.

För att slippa en massa fönster men också för att kunna arbeta smidigt via terminal bestämde jag mig för att fördjupa mig, eller rättare skrapa lite hårdare på ytan av Vim. Vim är en akronym för Vi improved, som för övrigt innehåller akronymen Vi som fått sitt namn efter kommandot visual i radeditorn ex. Ex i sin tur är en akronym för EXtended som också är en radeditor för Unix-system. Allihop härstammar de från editorn ed som var standardeditor i den första distributionen av BSD. Men tillbaka till Vim som alltså är en texteditor skriven redan 1991 med öppen källkod och finns för ett flertal operativsystem.

Precis som många andra verktyg i Unix-miljö är Vim inget undantag när det gäller användarvänligheten. Inlärningströskeln är mycket hög och många användare, jag inkluderad, har stora svårigheter i början när det gäller de mest basala funktioner som redigering av text eller att helt enkel avsluta editorn. Anledningen till detta är att många är vana vid de grafiska användargrännsnitten som inte alls var vanliga när VIm och dess föregångare skapades. Två kriterier för Vim var att kunna använda det via terminal och utan mus. Man införde därför ett antal modes, eller lägen, ett för kommandoinmatning, ett för textredigering med mera. När Vim startas hamnar man i kommandoläge, vilket många nya användare inte är vana vid. Man måste alltså läsa en hel del dokumentation för att överhuvud taget komma igång att mata in text i Vim. När den tröskeln är passerad öppnar sig en ocean av inställningar, funktionallitet och verktyg som är oumbärliga för programmerare.