Just nu är det få som tänker påhur filkomprimering fungerar. Jämfört med det förflutna har användning av en persondator blivit mycket enklare. Och nästan alla som arbetar med filsystemet använder arkiv. Men få människor tänker på hur de fungerar och hur filer komprimeras. Den allra första versionen av denna process var Huffman-koderna, och de används den dag i dag i olika populära arkiverare. Många användare tänker inte ens på hur enkelt det är att komprimera en fil och hur den fungerar. I den här artikeln kommer vi att titta på hur komprimering sker, vilka nyanser som hjälper till att påskynda och förenkla kodningsprocessen och också ta reda på vad som är principen för att bygga ett kodande träd.
Den allra första algoritmen för effektiv effektkodning av elektronisk information blev en kod som Huffman föreslog redan i mitten av 1900-talet, nämligen 1952. Det är han som för närvarande är det viktigaste grundelementet i de flesta program som är utformade för att komprimera information. För närvarande är några av de mest populära källorna som använder den här koden ZIP, ARJ, RAR-arkiv och många andra.
Huffman-algoritmen är baserad på schemat,låter dig ersätta de mest troliga, vanligaste tecknen med koder i det binära systemet. 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 har använt alla minimivärden. Denna teknik låter dig minimera kodens längd för varje tecken i originalmeddelandet som helhet.
För att illustrera algoritmen, tagrafisk version av att bygga ett kodträd. För att användningen av denna metod ska vara effektiv är det värt att klargöra definitionen av några av de värden som är nödvändiga för begreppet denna metod. Uppsättningen för en uppsättning bågar och noder som styrs från nod till nod kallas ett diagram. Själva trädet är en graf med en uppsättning specifika egenskaper:
Att bygga en Huffman-kod görs från bokstävermata in alfabetet. En lista över de noder som är fria i det framtida kodträdet bildas. Vikten för varje nod i den här listan bör vara densamma som sannolikheten för att meddelandebokstaven motsvarar den noden. I det här fallet väljs den som väger minst bland flera fria noder i det framtida trädet. Dessutom, om minimiindikatorerna observeras i flera noder, kan du fritt välja något av paren.
För att förbättra komprimeringseffektiviteten måste duNär du bygger ett kodträd, använd all information om sannolikheten för att bokstäver ska visas i en viss fil som är bifogad trädet och låt dem inte spridas över ett stort antal textdokument. Om du först går igenom den här filen kan du omedelbart beräkna statistik över hur ofta bokstäver från objektet som ska komprimeras hittas.
För att påskynda algoritmen, identifiera bokstäverbör utföras inte enligt indikatorerna för sannolikheten för utseendet på en viss bokstav, utan enligt frekvensen för dess förekomst. Detta gör algoritmen enklare och mycket snabbare att arbeta med. Det undviker också flytande punkt och division operationer.
Huffman-koder - enkla och etableradeen algoritm som fortfarande används av många välkända program och företag. Dess enkelhet och tydlighet gör att du kan uppnå effektiva resultat av komprimering av filer i alla storlekar och minska deras lagringsdiskutrymme avsevärt. Med andra ord är Huffman-algoritmen ett långt studerat och välutvecklat schema vars relevans inte minskar fram till i dag.
