Huffman koder: exempel, applikationer

Just nu tänker få människor om det faktum,hur komprimering fungerar Jämfört med det förflutna har det blivit mycket lättare att använda en persondator. Och praktiskt taget alla personer som arbetar med filsystemet använder arkiv. Men få människor tänker på hur de fungerar och vilken princip är komprimeringen av filer. Den allra första versionen av denna process var Huffman-koderna, och de används fortfarande i olika populära arkiver. Många användare tycker inte ens om hur lätt det är att komprimera filen och enligt vilket system det fungerar. I den här artikeln ser vi på hur komprimering fungerar, vilka nyanser bidrar till att påskynda och förenkla kodningsprocessen, och vi förstår också hur principen att bygga ett kodande träd är.

Algoritmens historia

Den allra första algoritmen för effektivkodning av elektronisk information var den kod som Huffman föreslog i mitten av det tjugonde århundradet, nämligen 1952. Det är för närvarande det viktigaste elementet i de flesta program som skapats för att komprimera information. För närvarande är en av de mest populära källorna som använder denna kod ZIP, ARJ, RAR arkiv och många andra.

Denna Huffman-algoritm används också förkomprimering av JPEG-bilder och andra grafiska objekt. Tja, alla moderna faxmaskiner använder också kodning, uppfunnit 1952. Trots det faktum att sedan koden skapades så mycket tid har gått, används den idag i de nyaste skalen och på utrustning av gamla och moderna typer.

Principen om effektiv kodning

Grunden för Huffman-algoritmen är ett schema,Det tillåter att ersätta de mest sannolika, oftast stötte symbolerna med koder för ett binärt system. Och de som är mindre vanliga ersätts med längre koder. Övergången till långa Huffman-koder sker först efter att systemet använder alla minimivärden. Med den här tekniken kan du minimera kodens längd för varje tecken i det ursprungliga meddelandet som helhet.

En viktig punkt är att i börjankodning av sannolikheten för förekomsten av bokstäver bör redan vara känd. Det är från dessa att det slutliga meddelandet kommer att sammanställas. Baserat på dessa data är Huffman-kodträdet konstruerat, baserat på vilket processen för kodning av bokstäver i arkivet kommer att utföras.

Huffmans kod, exempel

För att illustrera algoritmen, låt oss taen grafisk version av byggandet av ett kodträd. För att använda denna metod var effektiv är det värt att klargöra definitionen av några värden som är nödvändiga för begreppet denna metod. Satsen med bågar och noder som är riktade från nod till nod kallas vanligen en graf. Själva trädet är ett diagram med en uppsättning vissa egenskaper:

• i varje nod kan man inte ange mer än en av bågarna;
• En av noderna måste vara trädets rot, det vill säga ingen båge borde gå in i den alls;
• om från roten för att börja röra sig längs bågar, bör denna process tillåta att komma helt in i någon av noderna.

Det finns också ett sådant koncept som ingår i kodernaHuffman, som ett träd av ett träd. Det är en nod från vilken ingen båge ska fly. Om två noder är anslutna med en båge, är en av dem föräldern, det andra barnet, beroende på vilken nod bågen kommer ifrån och vilken den är i. Om två noder har samma moderkod, kallas de vanligen broderliga noder. Om, förutom löven, finns flera bågar i noderna, kallas detta träd binärt. Detta är precis Huffmans träd. Egenheten hos noderna i denna konstruktion är att vikten av varje förälder är lika med summan av vikten hos alla sina nodala barn.

Algoritm för att bygga ett träd enligt Huffman

Konstruktionen av Huffman-koden är gjord i bokstäverav ingångs alfabetet. En lista över de noder som är lediga i det framtida kodträdet skapas. Vikten av varje nod i denna lista bör vara densamma som sannolikheten för att bokstaven i meddelandet som motsvarar denna nod uppträder. I det här fallet, bland de få fria noderna i det framtida trädet, väljs den som väger minst. Samtidigt, om miniminivåerna observeras i flera noder, är det möjligt att välja fritt paret.

Då skapandet av föräldernnod, som bör väga så mycket som summan av detta par noder väger. Efter detta skickas föräldern till listan med fria noder, och barnen raderas. Samtidigt får bågarna motsvarande index, en och nollor. Denna process upprepas exakt så länge som nödvändigt för att lämna endast en nod. Därefter skrivs binära tal ner från topp till botten.

Förbättrad komprimeringseffektivitet

För att öka komprimeringseffektiviteten är det nödvändigt atttiden för att bygga ett kodträ för att använda all data om sannolikheten för bokstäver som förekommer i en viss fil som bifogas ett träd och inte låta dem sprida sig över ett stort antal textdokument. Om du först går igenom den här filen kan du omedelbart beräkna statistiken om hur ofta bokstäver från ett objekt som ska komprimeras uppstår.

Acceleration av kompressionsprocessen

För att påskynda algoritmen, definitionen av bokstäverDet är nödvändigt att inte utföra indikatorer på sannolikheten för att denna eller den där bokstaven uppträder och om frekvensen av dess förekomst. Tack vare detta blir algoritmen enklare, och arbetet med det accelereras kraftigt. Detta undviker också operationerna i samband med flytande kommatecken och uppdelning.

Dessutom arbetar i detta läge dynamisktHuffman-koden, eller snarare algoritmen själv, är inte föremål för några ändringar. Detta beror främst på det faktum att sannolikheterna är direkt proportionella mot frekvenserna. Det är värt att ägna särskild uppmärksamhet åt att filens slutvikt eller den så kallade rotknutpunkten kommer att motsvara summan av antalet bokstäver i objektet som ska behandlas.

slutsats

Huffmans koder - enkla och långa etableradealgoritmen, som fortfarande används av många kända program och företag. Dess enkelhet och tydlighet gör det möjligt att uppnå effektiva komprimeringsresultat för filer av alla storlekar och avsevärt minska det utrymme de upptar på lagringsskivan. Med andra ord är Huffman-algoritmen ett långt studerat och väldesignat schema, vars relevans inte minskar till denna dag.

Och tack vare möjligheten att minska storleken på filer,deras överföring via nätverket eller på andra sätt blir enklare, snabbt och bekvämt. Med algoritmen kan du komprimera absolut all information utan att skada strukturen och kvaliteten, men med den maximala effekten av att minska filens vikt. Med andra ord, Huffman kod kodning var och är den mest populära och faktiska metoden för filstorlek komprimering.

</ p>