Huffman-koding. Del 1.
Introduksjon
Hei kjære leser! Denne artikkelen vil diskutere en av måtene å komprimere data på. Denne metoden er ganske utbredt og fortjener litt oppmerksomhet. Dette materialet beregnes i volum for tre artikler, hvorav den første vil være viet til kompresjonsalgoritmen, den andre - til programvareimplementeringen av algoritmen, og den tredje - til dekompresjon. Komprimeringsalgoritmen vil bli skrevet i C++, dekompresjonsalgoritmen i Assembler.
Men før du fortsetter med selve algoritmen, bør en liten teori inkluderes i artikkelen.
Litt teori
Komprimering (kompresjon) - en måte å redusere mengden data for videre overføring og lagring.
Dekompresjon Er en måte å gjenopprette komprimerte data tilbake til originale data.
Komprimering og dekompresjon kan være enten uten tap av kvalitet (når den overførte/lagrede informasjonen i komprimert form etter dekompresjon er helt identisk med den originale), eller med tap av kvalitet (når dataene etter dekompresjon avviker fra originalen). For eksempel kan tekstdokumenter, databaser, programmer bare komprimeres på en måte uten tap av kvalitet, mens bilder, videoer og lydfiler komprimeres nettopp på grunn av tap av kvaliteten på originaldataene (et typisk eksempel på algoritmer er JPEG , MPEG, ADPCM), noen ganger umerkelig tap av kvalitet selv ved 1:4 eller 1:10 komprimering.
Hovedtypene av emballasje skilles ut:I tillegg er kodene valgt på en slik måte at det under dekodingen var mulig å entydig bestemme elementet i de originale dataene. Med denne tilnærmingen er bare bitorientert koding mulig, der tillatte og forbudte koder skilles. Hvis koden ved dekoding av en bitsekvens viste seg å være forbudt, må en bit til av den opprinnelige sekvensen legges til den og dekodingsoperasjonen må gjentas. Eksempler på slik koding er Shannon- og Huffman-algoritmene, sistnevnte vil vi vurdere.
- Desimal pakking er beregnet på å pakke tegndata som kun består av tall. I stedet for å bruke 8 bits for et tegn, er det ganske rasjonelt å bruke bare 4 bits for desimale og heksadesimale sifre, 3 bits for oktale, og så videre. Med denne tilnærmingen merkes allerede en kompresjon på minst 1:2.
- Relativ koding er en tapsgivende koding. Det er basert på det faktum at det påfølgende dataelementet skiller seg fra det forrige med en mengde som tar mindre plass i minnet enn selve elementet. Et typisk eksempel er ADPCM (Adaptive Differencial Pulse Code Modulation) lydkomprimering, som er mye brukt i digital telefoni og tillater komprimering av lyddata i forholdet 1:2 med nesten umerkelig kvalitetstap.
- Symbolsk undertrykkelse- en metode for informasjonskomprimering, der lange sekvenser med identiske data erstattes med kortere.
- Statistisk koding basert på det faktum at ikke alle dataelementer forekommer med samme frekvens (eller sannsynlighet). Med denne tilnærmingen velges koder slik at det hyppigste elementet tilsvarer koden med kortest lengde, og minst hyppige - med størst.
Mer spesifikt om algoritmen
Som allerede kjent fra forrige underseksjon, er Huffmans algoritme basert på entropikoding. La oss se nærmere på implementeringen.
La det være en datakilde som overfører tegn (a_1, a_2, ..., a_n) med varierende grad av sannsynlighet, det vil si at hver a_i har sin egen sannsynlighet (eller frekvens) P_i (a_i), og det er minst ett par a_i og a_j, i \ ne j, slik at P_i (a_i) og P_j (a_j) ) er ikke er like. Dermed dannes et sett med frekvenser (P_1 (a_1), P_2 (a_2), ..., P_n (a_n)), hva har det med å gjøre \ displaystyle \ sum_ (i = 1) ^ (n) P_i (a_i) = 1, siden senderen ikke overfører flere tegn enn (a_1, a_2, ..., a_n).
Vår oppgave er å finne slike kodesymboler (b_1, b_2, ..., b_n) med lengder (L_1 (b_1), L_2 (b_2), ..., L_n (b_n)) slik at gjennomsnittslengden på kodesymbolet ikke overstiger gjennomsnittslengden til det originale symbolet. I dette tilfellet er det nødvendig å ta hensyn til betingelsen om at hvis P_i (a_i)> P_j (a_j) og i \ ne j, da L_i (b_i) \ le L_j (b_j).
Huffman foreslo å bygge et tre der nodene mest sannsynlig er minst fjernt fra roten. Derfor er selve metoden for å konstruere et tre:
1. Velg to symboler a_i og a_j, i \ ne j, slik at P_i (a_i) og P_j (a_j) fra hele listen (P_1 (a_1), P_2, ..., P_n (a_n)) er minimale.
2. Reduser tregrener fra disse to elementene til ett punkt med sannsynlighet P = P_i (a_i) + P_j (a_j) ved å merke en gren med null og den andre med en (etter eget skjønn).
3. Gjenta trinn 1 og ta hensyn til det nye punktet i stedet for a_i og a_j, hvis antallet resulterende poeng er mer enn ett. Ellers har vi nådd roten til treet.
La oss nå prøve å bruke den oppnådde teorien og kode informasjonen som overføres av kilden, ved å bruke eksemplet med syv tegn.
La oss se nærmere på den første syklusen. Figuren viser en tabell der hvert symbol a_i har sin egen sannsynlighet (frekvens) P_i (a_i). I henhold til punkt 1 velger vi to symboler fra tabellen med lavest sannsynlighet. I vårt tilfelle er disse a_1 og a_4. I henhold til punkt 2 reduserer vi tregrenene fra a_1 og a_4 til ett punkt og merker grenen som leder til a_1 med en, og grenen som leder til a_4 med null. Over det nye punktet tildeler vi dets sannsynlighet (i dette tilfellet - 0,03) I fremtiden gjentas handlingene under hensyntagen til det nye punktet og uten å ta hensyn til a_1 og a_4.Etter gjentatt repetisjon av handlingene ovenfor, bygges følgende tre:
Ved det konstruerte treet kan du bestemme verdien av kodene (b_1, b_2, ..., b_n), synkende fra roten til det korresponderende elementet a_i, mens du tildeler null eller én til den resulterende sekvensen når du passerer hver gren (avhengig av hvordan den bestemte grenen er navngitt). Dermed ser kodetabellen slik ut:
Jegb iL i (b i) 1 011111 62 1 13 0110 44 011110 65 010 36 00 27 01110 5
La oss nå prøve å kode en sekvens av tegn.
La symbolet a_i svare (som et eksempel) til tallet i. La det være en sekvens 12672262. Du må få den resulterende binære koden.
For koding kan du bruke den allerede eksisterende kodesymboltabellen b_i, ta i betraktning at b_i tilsvarer symbolet a_i. I dette tilfellet vil koden for siffer 1 være sekvensen 011111, for siffer 2 - 1, og for siffer 6 - 00. Dermed får vi følgende resultat:Data12672262 Kodelengde Innfødt 001010110111010010110 01024 bit Kodet 011111100011101100119 bit
Som et resultat av kodingen vant vi 5 biter og skrev sekvensen i 19 biter i stedet for 24.
Dette gir imidlertid ikke et fullstendig estimat for datakomprimering. La oss gå tilbake til regnestykket og estimere komprimeringsforholdet til koden. Dette krever et entropi-estimat.
Entropi- et mål på usikkerheten til en situasjon (random variabel) med et endelig eller partall av utfall. Matematisk er entropi formulert som summen av produktene av sannsynlighetene for forskjellige tilstander i systemet ved logaritmene til disse sannsynlighetene, tatt med motsatt fortegn:H (X) = - \ displaystyle \ sum_ (i = 1) ^ (n) P_i \ cdot log_d (P_i).
Hvor X er en diskret tilfeldig variabel (i vårt tilfelle et kodesymbol), og d er en vilkårlig base større enn én. Valget av basen er ensbetydende med valget av en viss måleenhet for entropi. Siden vi har å gjøre med binære sifre, er det rasjonelt å velge d = 2 som grunnlag.
Dermed kan entropien for vårt tilfelle representeres som:H (b) = - \ displaystyle \ sum_ (i = 1) ^ (n) P_i (a_i) \ cdot log_2 (P_i (a_i)).
Entropi har en bemerkelsesverdig egenskap: den er lik den minste tillatte gjennomsnittslengden til et kodesymbol \ overline (L_ (min)) i biter. Den samme gjennomsnittlige lengden på kodesymbolet beregnes av formelen
\ overlinje (L (b)) = \ visningsstil \ sum_ (i = 1) ^ (n) P_i (a_i) \ cdot L_i (b_i).
Ved å erstatte verdiene i formlene H (b) og \ overline (L (b)), får vi følgende resultat: H (b) = 2.048, \ overlinje (L (b)) = 2100.
Verdiene til H (b) og \ overline (L (b)) er veldig nærme, noe som indikerer en reell gevinst i valget av algoritmen. La oss nå sammenligne den gjennomsnittlige lengden på det originale symbolet og den gjennomsnittlige lengden på kodesymbolet gjennom forholdet:\ frac (\ overline (L_ (src))) (L (b)) = \ frac (3) (2,1) = 1,429.
Dermed fikk vi et kompresjonsforhold på 1:1,429, noe som er veldig bra.
Og til slutt, la oss løse det siste problemet: dekryptering av bitsekvensen.
La det være en sekvens av biter for vår situasjon:001101100001110001000111111
Det er nødvendig å bestemme kildekoden, det vil si å dekode denne sekvensen.
Selvfølgelig, i en slik situasjon, kan du bruke kodetabellen, men dette er ganske upraktisk, siden lengden på kodesymbolene ikke er konstant. Det er mye mer praktisk å stige ned treet (starter fra roten) i henhold til følgende regel:
1. Utgangspunktet er roten til treet.
2. Les en ny bit. Hvis det er null, gå langs grenen merket med null, ellers - med en.
3. Hvis punktet vi treffer er det siste, så har vi bestemt kodetegnet, som skal skrives ned og gå tilbake til punkt 1. Ellers skal punkt 2 gjentas.
La oss vurdere et eksempel på dekoding av det første symbolet. Vi er i et punkt med en sannsynlighet på 1,00 (roten av treet), les den første biten av sekvensen og går langs grenen merket med null til et punkt med en sannsynlighet på 0,60. Siden dette punktet ikke er det siste punktet i treet, leser vi neste bit, som også er null, og går langs grenen merket med null til punktet a_6, som er den siste. Vi dechiffrerte symbolet - dette er tallet 6. Vi skriver det ned og går tilbake til sin opprinnelige tilstand (flytt til roten).
Dermed tar den dekodede sekvensen formen.Data
001101100001110001000111111 Kodelengde Kodet 00110110000111000100011111127 biter Original 6223676261233 biterI dette tilfellet var forsterkningen 6 bits med en ganske kort sekvenslengde.
Konklusjonen tyder på seg selv: Algoritmen er enkel. En merknad bør imidlertid gjøres: denne algoritmen er god for å komprimere tekstinformasjon (vi bruker faktisk omtrent 60 tegn av de tilgjengelige 256 når du skriver tekst, det vil si at sannsynligheten for å møte andre tegn er nær null), men dårlig nok til å komprimere programmer (siden programmet er alle symboler nesten like sannsynlige). Så effektiviteten til algoritmen avhenger veldig av typen data som komprimeres.
P.S
I denne artikkelen undersøkte vi Huffman-kodealgoritmen, som er basert på ikke-uniform koding. Den lar deg redusere størrelsen på overførte eller lagrede data. Algoritmen er lett å forstå og kan gi reelle gevinster. I tillegg har den en mer bemerkelsesverdig egenskap: evnen til å kode og dekode informasjon i farten, forutsatt at sannsynlighetene til kodeordene er riktig bestemt. Selv om det er en modifikasjon av algoritmen som lar deg endre trestrukturen i sanntid.
I neste del av artikkelen vil vi se på byte-orientert filkomprimering ved hjelp av Huffman-algoritmen, implementert i C ++.
Huffman-koding. Del 2
Introduksjon
I den siste delen undersøkte vi kodingsalgoritmen, beskrev dens matematiske modell, utførte koding og dekoding ved å bruke et spesifikt eksempel, beregnet gjennomsnittslengden på kodeordet, og bestemte også komprimeringsforholdet. I tillegg ble det trukket konklusjoner om fordeler og ulemper med denne algoritmen.
Men i tillegg til dette er det fortsatt to spørsmål som ikke er løst: implementeringen av programmet som komprimerer datafilen, og programmet som pakker ut den komprimerte filen. Denne artikkelen er viet til det første spørsmålet. Derfor bør du begynne å designe.
Design
Det første trinnet er å beregne hyppigheten av forekomst av tegn i filen. For å gjøre dette beskriver vi følgende struktur:
// Struktur for å beregne frekvensen til tegnet
typedef struct TFreq
int ch;
TTable * tabell;
DWORD frekv;
) TFreq;
Denne strukturen vil beskrive hver karakter av 256. kap- selve ASCII-karakteren, frekv- antall forekomster av symbolet i filen. Felt bord- peker til struktur:
// nodebeskrivelse
typedef struct TTable
int ch;
TTtabell * venstre;
TTtabell * høyre;
) TT-tabell;
Som sett, Ttabell Er en nodebeskrivelse som deler inn null og én. Ved hjelp av disse strukturene vil konstruksjonen av kompresjonstreet i fremtiden bli utført. La oss nå erklære vår frekvens og vår node for hvert symbol:
TFreq Freq [256];
La oss prøve å finne ut hvordan treet skal bygges. I det innledende stadiet må programmet gå gjennom hele filen og telle antall forekomster av tegn i den. I tillegg må programmet lage en nodebeskrivelse for hvert symbol det finner. Etter det, fra de opprettede nodene, under hensyntagen til frekvensen av symboler, bygger programmet et tre, plasserer nodene i en viss rekkefølge og etablerer koblinger mellom dem.
Det konstruerte treet er bra for å dekode filen. Men for koding av en fil er det upraktisk, fordi det ikke er kjent i hvilken retning man skal gå fra roten for å komme til det nødvendige tegnet. For dette er det mer praktisk å bygge en tegn-til-kode konverteringstabell. Derfor vil vi definere en struktur til:
// Kodetegnbeskrivelse
typedef struct TOPcode
DWORD opcode;
DWORD len;
) TOPcode;
Her opcode Er kodekombinasjonen av tegnet, og len- lengden (i biter). Og la oss erklære en tabell med 256 slike strukturer:
TOPcode Opcodes [256];
Når du kjenner tegnet som skal kodes, kan du bestemme kodeordet fra tabellen. La oss nå gå direkte videre til å beregne frekvensen av symboler (og ikke bare).
Telle symbolfrekvenser
I prinsippet er ikke denne handlingen vanskelig. Det er nok å åpne filen og telle antall tegn i den, fylle ut de riktige strukturene. La oss se gjennomføringen av denne handlingen.
For å gjøre dette, vil vi erklære globale filbeskrivelser:i- filen som de ukomprimerte dataene leses fra.
FIL * inn, * ut, * montere;
ute- filen som de komprimerte dataene er skrevet inn i.
montere- en fil der treet vil bli lagret i en form som er praktisk for utpakking. Siden utpakkeren skal skrives i assembler, er det ganske rasjonelt å gjøre treet til en del av utpakkeren, det vil si å representere det i form av instruksjoner i Assembler.
Det første trinnet er å initialisere alle strukturer med nullverdier:
// Å telle frekvensen av symboler
int CountFrequency (ugyldig)
int i; // loop variabel
int count = 0; // andre variabel i loopen
DWORD TotalCount = 0; // filstørrelse.
// Initialiser strukturer
for (i = 0; i< 256 ; i++ )
Frekv [i] .frekv = 0;
Frekv [i] .tabell = 0;
Frekv [i] .ch = i;
Etter det teller vi antall forekomster av symbolet i filen og filstørrelsen (selvfølgelig ikke på den mest ideelle måten, men eksemplet trenger klarhet):
// Telle frekvensen av symboler (symbolsk)
mens (! feof (in)) // til slutten av filen er nådd
i = fgetc (in);
hvis (i! = EOF) // hvis ikke slutten av filen
Frekv [i] .frekv ++; // frekvens ++
TotalCount ++; // størrelse ++
Siden koden er ujevn, vil det være vanskelig for utpakkeren å finne ut hvor mange tegn som skal leses. Derfor er det nødvendig å fikse størrelsen i utpakkingsbordet:
// "Fortell" utpakkeren filstørrelsen
fprintf (assembly, "coded_file_size: \ n dd% 8lxh \ n \ n ", TotalCount);
Etter det blir alle brukte tegn flyttet til begynnelsen av arrayet, og ubrukte blir overskrevet (ved permutasjoner).
// flytt alle ubrukte tegn til slutten
i = 0;
telle = 256;
mens jeg< count) // har ikke nådd slutten ennå
if (Freq [i] .freq == 0) // hvis frekvensen er 0
Frekv [i] = Frekv [- telling]; // kopier deretter oppføringen fra slutten
ellers
i ++; // alt er OK - fortsett.
Og først etter en slik "sortering" blir minne tildelt for noder (for en viss økonomi).
// Tildel minne for noder
for (i = 0; i< count; i++ )
Frekv [i] .tabell = ny TTtabell; // lag en node
Frekv [i] .tabell -> venstre = 0; // ingen tilkoblinger
Frekv [i] .tabell -> høyre = 0; // ingen tilkoblinger
Frekv [i] .tabell -> ch = Frekv.ch; // kopier symbolet
Freq [i] .freq = Freq.freq; // og frekvens
retur teller;
Dermed skrev vi en funksjon for den første initialiseringen av systemet, eller, hvis du ser på algoritmen i den første delen av artikkelen, "skrev ned symbolene som ble brukt i en kolonne og tildelte sannsynligheter til dem", og også for hver symbol opprettet et "startpunkt" - en node - og initialiserte den ... Inn i feltene venstre og Ikke sant skrev ned nuller. Dermed, hvis noden er den siste i treet, vil den være lett å se etter venstre og Ikke sant lik null.
Treoppretting
Så, i forrige seksjon, "skrev vi ned symbolene som ble brukt i en kolonne og tildelte sannsynligheter til dem." Faktisk tildelte vi ikke sannsynligheter til dem, men tellerne til brøken (det vil si antall forekomster av tegn i filen). Nå må vi bygge et tre. Men for å gjøre dette, må du finne det minste elementet i listen. For å gjøre dette introduserer vi en funksjon der vi sender to parametere - antall elementer i listen og elementet som skal ekskluderes (fordi vi vil søke i par, og det vil være veldig ubehagelig om vi mottar det samme elementet to ganger fra funksjonen):
// finn noden med lavest sannsynlighet.
int FindLeast (int count, int indeks)
int i;
DWORD min = (indeks == 0)? ti; // elementet som skal telles
// minimalt
for (i = 1; i< count; i++ ) // sløyfe gjennom matrisen
hvis (i! = indeks) // hvis elementet ikke er ekskludert
if (Freq [i] .frekv< Freq[ min] .freq ) // сравниваем
min = i; // mindre enn minimum - husk
retur min; // returner minimumsindeksen
Søket er ikke vanskelig: Først velger vi "minimum"-elementet i matrisen. Hvis det ekskluderte elementet er 0, tar vi det første elementet som minimum, ellers anser vi null som minimum. Når vi går gjennom matrisen, sammenligner vi det nåværende elementet med "minimum", og hvis det viser seg å være mindre, markerer vi det som minimum.
Nå er faktisk selve trebyggingsfunksjonen:Kodesymboltabell
// Funksjon for å bygge et tre
void PreInit (int count)
int ind1, ind2; // elementindekser
TTable * tabell; // peker til "ny node"
mens (tell> 1) // løkke til vi når roten
ind1 = Finnminst (antall, - 1); // første node
ind2 = Finnminst (tell, ind1); // andre node
tabell = ny TT-tabell; // opprette en ny node
tabell-> lm = - 1; // ikke endelig
table-> left = Freq [ind1] .tabell; // 0 - node 1
table-> right = Frekv [ind2] .tabell; // 1 - node 2
Frekv [ind1] .ch = - 1; // endre posten om
Freq [ind1] .freq + = Freq [ind2] .freq; // frekvens for symbol
Frekv [ind1] .tabell = tabell; // og skriv en ny node
if (ind2! = (- telling)) // hvis ind2 ikke er den siste
Frekv [ind2] = Frekv [antall]; // deretter på sin plass
// legg den siste i matrisen
Så vi bygde et tre i minnet: vi tok to noder i par, opprettet en ny node, der vi skrev pekere til dem, hvoretter den andre noden ble fjernet fra listen, og i stedet for den første noden skrev vi en ny en med en gaffel.
Nå oppstår et annet problem: det er upraktisk å kode i et tre, fordi du trenger å vite nøyaktig hvilken bane et bestemt symbol er på. Problemet løses imidlertid ganske enkelt: en annen tabell opprettes - en tabell med kodesymboler - og bitkombinasjonene til alle brukte symboler skrives inn i den. For å gjøre dette er det nok å krysse treet rekursivt en gang. Samtidig, for ikke å omgå den igjen, kan du legge til genereringen av en assembler-fil til bypass-funksjonen for videre dekoding av komprimerte data (se avsnittet " Design").
Egentlig er ikke selve funksjonen komplisert. Den bør tildele 0 eller 1 til kodeordet hvis noden ikke er endelig, ellers legg til kodetegnet i tabellen. I tillegg til alt dette, generer en monteringsfil. Tenk på denne funksjonen:
void RecurseMake (TTable * tbl, DWORD opcode, int len)
fprintf (assembly, "opcode% 08lx_% 04x: \ n ", opcode, len); // etikett til fil
if (tbl-> ch! = - 1) // siste node
BYTE mod = 32 - len;
Opcodes [tbl-> ch] .opcode = (opcode >> mod); // lagre koden
Opkoder [tbl-> ch] .len = len; // og dens lengde (i biter)
// og lag den tilsvarende etiketten
fprintf (samle, "db% 03xh, 0ffh, 0ffh, 0ffh \ n \ n", tbl-> ch);
ellers // noden er ikke endelig
opcode >> = 1; // frigjør plass til en ny bit
len ++; // øke lengden på kodeordet
\ n ", opcode, len);
fprintf (assembly, "dw opcode% 08lx_% 04x \ n \ n ", opcode | 0x80000000, len);
RecurseMake (tbl-> venstre, opcode, len);
RecurseMake (tbl-> høyre, opcode | 0x80000000, len);
// fjern noden (den er ikke lenger nødvendig)
slette tbl;
Blant annet, etter å ha krysset en node, sletter funksjonen den (frigjør pekeren). La oss nå finne ut hvilke parametere som sendes til funksjonen.
I prinsippet er ikke funksjonen mer komplisert enn den "klassiske faktoren" og bør ikke forårsake noen vanskeligheter.
- tbl- noden som skal omgås.
- opcode- gjeldende kodeord. Den viktigste biten må alltid være gratis.
- len- lengden på kodeordet.
Bitutgang
Så vi kom til den ikke veldig hyggelige delen av arkiveringsverktøyet vårt, nemlig utdataene av kodesymboler til en fil. Problemet er at kodesymbolene er ujevne i lengde og utgangen må gjøres bit for bit. Dette vil hjelpe funksjonen PutCode... Men først, la oss erklære to variabler - telleren for bitene i byten og utdatabyten:
// Bitteller
int OutBits;
// Vist tegn
BYTE OutChar;
OutBits økes med én hver gang en bit sendes ut, OutBits == 8 signaliserer at OutChar skal lagres i en fil.
void PutCode (int ch)
int len;
int utkode;
// få lengden på kodeordet og selve kodeordet
outcode = Opcodes [ch] .opcode; // kodeord
len = Opcodes [ch] .len; // lengde (i biter)
mens (len> 0) // utgang bit for bit
// Loop mens OutBits-variabelen ikke brukes fullt ut
mens ((OutBits< 8 ) && (len> 0 ) )
OutChar >> = 1; // frigjør plass
OutChar | = ((utkode & 1)<< 7 ) ; // og legg litt i det
utkode >> = 1; // neste kodebit
len -- ; // redusere lengden
OutBits ++ ; // antall biter økte
}
// hvis alle 8 biter brukes, lagre dem i en fil
hvis ( OutBits == 8 )
{
fputc( OutChar, ut ) ; // lagre til fil
OutBits = 0 ; // satt til null
OutChar = 0 ; // alternativer
}
}
}
I tillegg må du organisere noe som "fflush", det vil si etter utdata fra det siste kodeordet OutChar vil ikke passe inn i utdatafilen fordi OutBits! = 8. Herfra kommer en annen liten funksjon:
// "Tøm" bitbufferen
tomrom EndPut (tomrom)
{
// Hvis det er biter i bufferen
hvis ( OutBits ! = 0 )
I dag er det få av brukerne som er interessert i spørsmålet knyttet til filkomprimeringsmekanismen. Sammenlignet med tidligere har prosessen med å jobbe med en personlig datamaskin blitt mye enklere.
I dag bruker nesten alle brukere som jobber med filsystemet arkiver. Det er imidlertid få brukere som har tenkt på hvordan filer komprimeres.
Huffman-koder var det første alternativet. De brukes fortsatt i forskjellige arkiver. De fleste brukere tenker ikke engang på hvor enkelt det er å komprimere en fil ved å bruke dette opplegget. I denne anmeldelsen skal vi se på hvordan komprimering utføres, hvilke funksjoner som hjelper til med å fremskynde og forenkle kodingsprosessen. Vi vil også prøve å forstå de grunnleggende prinsippene for å bygge et kodetre.
Algoritme: historie
Den første algoritmen designet for å effektivt kode elektronisk informasjon var en kode foreslått av Huffman i 1952. Det er denne koden som i dag kan betraktes som det grunnleggende elementet i de fleste programmer designet for å komprimere informasjon. En av de mest populære kildene som bruker denne koden i dag er RAR, ARJ, ZIP-arkiver. Denne algoritmen brukes også til å komprimere JPEG-bilder og grafikk. Alle moderne fakser bruker også en kodingsalgoritme som ble oppfunnet i 1952. Til tross for at det har gått mye tid siden opprettelsen av denne koden, brukes den effektivt i utstyr av den gamle typen, så vel som i nytt utstyr og skjell.
Prinsippet om effektiv koding
I hjertet av Huffman-algoritmen er et opplegg som lar deg erstatte de mest sannsynlige og vanligste tegnene med binære koder. De tegnene som er mindre vanlige, erstattes med lange koder. Overgangen til lange Huffman-koder utføres først etter at systemet har brukt alle minimumsverdiene. Denne teknikken gjør det mulig å minimere lengden på koden per tegn i den opprinnelige meldingen. I dette tilfellet ligger det særegne i det faktum at sannsynlighetene for utseendet til bokstaver i begynnelsen av kodingen allerede må være kjent. Den endelige meldingen vil være sammensatt av dem. Basert på denne informasjonen konstrueres et Huffman-kodetre. På grunnlag av det vil prosessen med å kode bokstaver i arkivet bli utført.
Huffman-kode: eksempel
For å illustrere Huffman-algoritmen, vurder en grafisk versjon av å bygge et kodetre. For å bruke denne metoden var mer effektiv, det er nødvendig å klargjøre definisjonen av noen av verdiene som er nødvendige for konseptet med denne metoden. Hele samlingen av et sett med noder og buer som er rettet fra node til node kalles en graf. Selve treet er en graf med et sett med spesifikke egenskaper. Hver node skal ikke inneholde mer enn én av alle buer. En av nodene må være roten til treet. Dette betyr at buer ikke skal komme inn i det i det hele tatt. Hvis du starter fra roten av å bevege deg langs buene, bør denne prosessen tillate deg å komme til hvilken som helst node.
Huffman-koder inkluderer også et slikt konsept som et blad av et tre. Den representerer en node som ingen bue skal gå ut fra. Hvis to noder er forbundet med en bue, er en av dem en forelder, og den andre er et barn. Hvis to noder har en felles foreldrenode, kalles de søskennoder. Hvis nodene i tillegg til bladene har flere buer, kalles et slikt tre binært. Dette er akkurat hva Huffman-treet er. Et trekk ved nodene til denne strukturen er at vekten til hver forelder er lik summen av vekten til nodalbarna.
Huffman tree: konstruksjonsalgoritme
Konstruksjonen av Huffman-koden utføres fra bokstavene i inndataalfabetet. En liste over noder som er ledige i det fremtidige kodetreet dannes. I denne listen må vekten til hver node være den samme som sannsynligheten for forekomst av meldingsbokstaven som tilsvarer den gitte noden. Blant flere ledige noder velges den som veier minst. Hvis det samtidig observeres minimumsindikatorer i flere noder, kan du fritt velge hvilket som helst par. Etter det opprettes den overordnede noden. Den skal veie like mye som summen av det gitte nodeparet veier. Forelderen sendes deretter til listen med ledige noder. Barn fjernes. I dette tilfellet mottar buene de tilsvarende indikatorene, nuller og enere. Denne prosessen gjentas så mange ganger som det tar å forlate bare én node. Etter det skrives binære sifre fra topp til bunn.
Hvordan forbedre kompresjonseffektiviteten
For å øke effektiviteten av komprimering, under konstruksjonen av kodetreet, er det nødvendig å bruke alle dataene om sannsynligheten for utseendet til bokstaver i en bestemt fil som er festet til treet. De skal ikke være spredt over et stort antall tekstdokumenter. Går du gjennom denne filen på forhånd, kan du få statistikk over hvor ofte bokstaver som finnes fra objektet som skal komprimeres.
Hvordan få fart på komprimeringsprosessen
For å fremskynde driften av algoritmen, bør identifiseringen av bokstaver utføres ikke av indikatorene for utseendet til visse bokstaver, men etter hyppigheten av deres forekomst. Takket være dette blir algoritmen enklere, og arbeidet med den akselereres betydelig. Det gjør det også mulig å unngå divisjons- og flyttalloperasjoner. Når du arbeider i denne modusen, kan ikke algoritmen endres. Dette skyldes hovedsakelig at sannsynlighetene er direkte proporsjonale med frekvensene. Det er også verdt å ta hensyn til det faktum at den endelige vekten til rotnoden vil være lik summen av antall bokstaver i objektet som skal behandles.
Produksjon
Huffman-koder er en enkel og veletablert algoritme som fortsatt brukes i mange populære programmer i dag. Enkelheten og klarheten til denne koden lar deg oppnå effektiv komprimering av filer i alle størrelser.
Boken "Fundamental Algorithms and Data Structures in Delphi" er en unik opplærings- og referansemanual for de vanligste datamanipulasjonsalgoritmene som har vist seg å være pålitelige og bevist av mange generasjoner av programmerere. I følge Delphi Informant magazine fra 2002 har denne boken blitt anerkjent av Delphi-applikasjonsfellesskapet som "den beste boken om praktisk bruk av alle Delphi-versjoner."
Boken dekker i detalj de grunnleggende konseptene for algoritmer og grunnleggende datastrukturer, algoritmer for sortering, søking, hashing, parsing, datakomprimering og mange andre emner som er nært knyttet til applikasjonsprogrammering. En overflod av godt testede kodeeksempler øker dramatisk raskere ikke bare mestring av grunnleggende algoritmer, men bidrar også til en mer dyktig tilnærming til daglig programmering.
Til tross for at boken først og fremst er ment for profesjonelle utviklere av Delphi-applikasjoner, vil den absolutt være nyttig for nybegynnere programmerere, og vise dem teknikkene og triksene som er så populære blant ekte "proffer". Alle eksempelkoder nevnt i boken er tilgjengelige for nedlasting fra forlagets nettsted.
Bok:
Huffman-kodealgoritmen er veldig lik Shannon-Fano-komprimeringsalgoritmen. Denne algoritmen ble oppfunnet av David Huffman i 1952 ("A method for the Construction of Minimum-Redundancy Codes") og er enda mer vellykket enn Shannon-Fano-algoritmen. Dette er fordi Huffman-algoritmen er matematisk garantert å generere den minste koden for hvert av tegnene i de originale dataene.
I likhet med bruken av Shannon-Fano-algoritmen, må du bygge et binært tre, som også vil være et prefiksetre, der alle data lagres i blader. Men i motsetning til Shannon-Fano-algoritmen, som er ovenfra og ned, vil konstruksjonen denne gangen gjøres fra bunnen og opp. Først skanner vi inndataene, og teller antall forekomster av verdiene til hver byte, som vi gjorde med Shannon-Fano-algoritmen. Når denne symbolfrekvenstabellen er opprettet, kan du begynne å bygge treet.
Vi vil betrakte disse symbol-tall-parene som en "pool" av noder i det fremtidige Huffman-treet. La oss fjerne de to nodene med de minste verdiene av antall forekomster fra dette bassenget. La oss knytte dem til den nye overordnede noden og sette tellerverdien til overordnet node lik summen av tellerne til de to undernodene. La oss sette den overordnede noden tilbake i bassenget. Fortsett denne prosessen med å fjerne to noder og legge til en overordnet node i deres plass til det bare er én node igjen i bassenget. På dette tidspunktet kan du fjerne én node fra bassenget. Det er rotnoden til Huffman-treet.
Den beskrevne prosessen er ikke veldig intuitiv, så la oss lage et Huffman-tre for setningen "Hvor mye ved kan en tremesse chuck?" Vi har allerede beregnet antall forekomster av symbolene i denne setningen og presentert dem i form av tabell 11.1, så nå vil det være nødvendig å bruke den beskrevne algoritmen på den for å bygge et komplett Huffman-tre. La oss velge to noder med de minste verdiene. Det er flere noder å velge mellom, men vi vil velge noder "m" og For begge disse nodene er antall forekomster av symboler 1. Lag en overordnet node med tellingen 2 og fest de to valgte nodene til den som barn. La oss sette den overordnede noden tilbake i bassenget. La oss gjenta syklusen helt fra begynnelsen. Denne gangen velger vi nodene a og D., slår dem sammen til et minitre og setter overordnet node (hvis telleren igjen er 2) tilbake i bassenget. La oss gjenta syklusen igjen. Denne gangen har vi en enkelt node med en tellerverdi på 1 (node "H") og tre noder med tellerverdier lik 2 (node "k" og de to overordnede nodene som ble lagt til før). Velg noden "til", fest den til noden "H" og legg igjen foreldrenoden til bassenget med en tellerverdi på 3. Velg deretter to overordnede noder med tellerverdier på 2, fest dem til en ny forelder node med en tellerverdi på 3 4, og legg denne overordnede noden til bassenget. De første trinnene for å konstruere et Huffman-tre og det resulterende treet er vist i fig. 11.2.
Figur 11.2. Bygge et Hoffman-tre
Ved å bruke dette treet, akkurat som treet laget for Shannon-Fano-koding, kan du beregne koden for hvert av tegnene i den opprinnelige setningen og bygge Tabell 11.5.
Tabell 11.5. Huffman koder for eksempelsetningstegn
Symbol - Antall opptredener
Plass - 00
Vær oppmerksom på at denne kodetabellen ikke er den eneste mulige. Når det er tre eller flere noder, hvorav to må velges, er det alternativer for resultattreet og dermed resultatkodene. Men i praksis vil alle disse mulige variantene av trær og koder gi maksimal komprimering. De er alle likeverdige.
Nå kan du beregne koden for hele forslaget. Det starter med biter:
1111110111100001110010100...
og inneholder bare 131 biter. Hvis den opprinnelige setningen var kodet i ASCII-koder, en byte per tegn, ville den inneholde 286 biter. I dette tilfellet er således kompresjonsforholdet omtrent 54%.
La oss gjenta igjen at, som med Shannon-Fano-algoritmen, er det nødvendig å på en eller annen måte komprimere treet og inkludere det i de komprimerte dataene.
Gjenoppretting utføres på nøyaktig samme måte som når du bruker Shannon-Fano-koding: du må rekonstruere treet fra dataene som er lagret i den komprimerte strømmen, og deretter bruke den til å lese den komprimerte bitstrømmen.
La oss se på Huffman-koding fra et synspunkt på høyt nivå. Når vi implementerer hver av komprimeringsteknikkene som vil bli beskrevet i dette kapittelet, vil vi lage en enkel subrutine som tar både en inngangs- og en utgangsstrøm og komprimerer alle dataene i inngangsstrømmen og legger den på utgangsstrømmen.
Denne TDHuffroanCompress-underrutinen på høyt nivå som gjør Huffman-koding er vist i oppføring 11.5.
Oppføring 11.5. Huffman-kodingsrutine på høyt nivå
prosedyre TDHuffmanCompress (aInStream, aOutStream: TSream);
HTree: THuffmanTree;
HCodes: PHuffmanCodes;
BitStrm: TtdOutputBitStream;
Signatur: longint;
(utskriftshodeinformasjon (signatur og størrelse på ukomprimerte data))
Signatur: = TDHuffHeader;
aOutStream.WriteBuffer (Signatur, sizeof (longint));
Størrelse: = aInStream.Size;
aOutStream.WriteBuffer (Størrelse, størrelse på (lengde));
(i fravær av data for komprimering, må du avslutte subrutinen)
hvis (Størrelse = 0) da
(forberedelse)
(lag en komprimert bitstrøm)
BitStrm: = TtdOutputBitStream.Create (aOutStream);
(tildel minne under et Huffman-tre)
HTree: = THuffmanTree.Create;
(bestem fordelingen av symboler i inngangsstrømmen og utfør en Huffman-trekonstruksjon nedenfra og opp)
HTree.CalcCharDistribution (aInStream);
(skriv ut treet til en bitstrøm for å lette oppgaven med datagjenopprettingsprogrammet)
HTree.SaveToBitStream (BitStrm);
(hvis rotnoden til Huffman-treet er et blad, består inngangsstrømmen av kun et enkelt repeterende tegn, og derfor er oppgaven fullført. Ellers må inngangsstrømmen komprimeres)
hvis ikke HTree.RootIsLeaf så begynn
(tildel minne for en rekke koder)
(beregn alle koder)
HTree.CalcCodes (HCoder ^);
(komprimer tegnene i inngangsstrømmen til en bitstrøm)
DoHuffmanCompression (aInStream, BitStrm, HCodes ^);
hvis (HCoder<>null) da
Kast (HCoder);
Koden inneholder mange elementer som vi ikke har dekket ennå. Men vi kan godt først vurdere driften av programmet som helhet, og deretter fortsette med å vurdere hvert enkelt trinn. Først av alt skriver vi en liten overskrift til utgangsstrømmen, etterfulgt av lengden på inngangsstrømmen. Deretter vil denne informasjonen forenkle oppgaven med datagjenoppretting, og sikre at den komprimerte strømmen samsvarer med den vi opprettet. Vi lager deretter et bitstrømsobjekt som inneholder utdatastrømmen. Det neste trinnet er å lage en forekomst av THuffmanTree-klassen. Denne klassen, som du snart vil se, vil bli brukt til å lage et Huffman-tre og inneholder ulike metoder for å hjelpe til med denne oppgaven. En av metodene til dette nye objektet, kalt først, CalcCharDistribution-metoden, bestemmer statistikken for tegnfordelingen i inndatastrømmen, og bygger deretter et prefiks Huffman-tre.
Etter at Huffman-treet er bygget, kan du kalle SaveToBitStream-metoden for å skrive trestrukturen til utdatastrømmen.
Deretter gjør vi spesialsaksbehandling og noen optimaliseringer. Hvis inngangsstrømmen består av bare noen få repetisjoner av samme karakter, vil rotnoden til Huffman-treet være et blad. Hele prefiksetreet består av bare én node. I dette tilfellet vil utdatabitstrømmen allerede inneholde nok informasjon til at gjenopprettingsprogrammet kan gjenopprette den opprinnelige filen (vi har allerede skrevet størrelsen på inngangsstrømmen og en enkelt bit inn i bitstrømmen).
Ellers må inndatastrømmen inneholde minst to forskjellige symboler, og Huffman-treet ser ut som et vanlig tre, ikke en enkelt node. I dette tilfellet utfører vi optimalisering: vi beregner kodetabellen for hvert tegn som forekommer i inngangsstrømmen. Dette vil spare tid i neste trinn, når selve komprimeringen er ferdig, siden vi ikke trenger å hele tiden navigere i treet for å kode hvert tegn. HCodes-matrisen er en enkel 256-elements matrise som inneholder kodene til alle tegn og konstruert ved å kalle CalcCodes-metoden til Huffman-treobjektet.
Til slutt, når alle disse datastrukturene er definert, kaller vi DoHuffmanCompression-rutinen for å utføre selve datakomprimeringen. Koden for denne rutinen er vist i oppføring 11.6.
Notering 11.6. Huffman kompresjonssløyfe
prosedyre DoHuffmanCompression (aInStream: TSream;
aBitStream: TtdOutputBitStream;
var aCodes: THuffmanCodes);
Buffer: PByteArray;
BytesRead: longint;
(tilbakestill inngangsstrømmen til utgangstilstand)
mens (BytesRead<>0) gjør
(skriv en bitstreng for hvert blokktegn)
for i: = 0 til pred (BytesRead) gjør aBitStream.WriteBits (aCodes]);
BytesRead: = aInStream.Read (Buffer ^, HuffmanBufferSize);
DoHuffmanCompression-subrutinen tildeler en stor buffer for å lagre blokker med data som leses fra inngangsstrømmen, og vil kontinuerlig lese blokker fra inngangsstrømmen, og komprimere dem til strømmen er oppbrukt. Denne bufringen av data fungerer som en enkel optimaliseringsteknikk for å forbedre effektiviteten til hele prosessen. For hvert tegn i blokken skriver subrutinen den tilsvarende koden fra aCodes-matrisen til utdatabitstrømmen.
Nå som vi har sett hvordan Huffman-komprimering på høyt nivå utføres, er det på tide å se på klassen som gjør mesteparten av beregningen. Dette er en indre klasse THuffmanTree. De tilknyttede typene er deklarert i oppføring 11.7.
Først erklærer vi en Huffman-treenode THaffxnanNode og en rekke av disse nodene THaffmanNodeArray med en fast størrelse. Denne matrisen vil bli brukt til å lage den faktiske trestrukturen og vil inneholde nøyaktig 511 elementer. Hvorfor akkurat dette beløpet?
Dette tallet bestemmes av et lite teorem (eller lemma) om egenskapene til et binært tre, som ennå ikke er nevnt.
Notering 11.7. Huffman tre klasse
PHuffmanNode = ^ THuffmanNode;
THuffmanNode = pakket post
hnCount: longint;
hnLeftInx: longint;
hnRightInx: longint;
hnIndex: longint;
PHuffmanNodeArray = ^ THuffmanNodeArray;
THuffmanNodeAr ray = array av THuffmanNode;
THuffmanCodeStr = streng;
PHuffmanCodes = ^ THuffmanCodes;
THuffmanCodes = array av TtdBitString;
THuffmanTree = klasse privat
FTree: THuffmanNodeArray;
prosedyre htBuild;
prosedyre htCalcCodesPrim (aNodeInx: heltall;
var aCodeStr: THuffmanCodeStr;
var aCodes: THuffmanCodes);
funksjon htLoadNode (aBitStream: TtdInputBitStream): heltall;
prosedyre htSaveNode (aBitStream: TtdOutputBitStream;
aNode: heltall);
konstruktør Lag;
prosedyre CalcCharDistribution (aStream: TSream);
prosedyre CalcCodes (var aCodes: THuffmanCodes);
funksjon DecodeNextByte (aBit St ream: TtdInputBitStream): byte;
prosedyre LoadFromBitStream (aBitStream: TtdInputBitStream);
funksjon RootIsLeaf: boolsk;
prosedyre SaveToBitStream (aBitStream: TtdOutputBitStream);
egenskap Root: heltall lest FRoot;
Anta at treet bare inneholder to typer noder: interne, som har nøyaktig to underordnede noder, og blader, som ikke har noder (med andre ord, det er ingen noder med bare én underordnet node - dette er akkurat den typen en prefiksetre). Hvor mange interne noder har dette treet hvis det inneholder n blader? Lemmaet sier at et slikt tre inneholder nøyaktig n - 1 interne noder. Denne påstanden kan bevises ved induksjon. Når n = 1, er lemmaet klart sant, siden treet bare inneholder rotnoden.
Anta nå at lemmaet er sant for alle jeg< n, где n < 1, и рассмотрим случай, когда i = n. В этом случае дерево должно содержать, по меньшей мере, один внутренний узел - корневой. Этот корневой узел имеет два дочерних дерева: левое и правое. Если левое дочернее дерево имеет x листьев, то, согласно сделанному нами допущению, оно должно содержать x - 1 внутренних узлов, поскольку x < n. Аналогично, согласно сделанному допущению, если правое дочернее дерево имеет y листьев, оно должно содержать y - 1 внутренних узлов. Все дерево содержит n листьев, причем это число должно быть равно X + Y (вспомните, что корневой узел является внутренним). Следовательно, количество внутренних узлов равно (x-1) + (y-1) + 1, что составляет в точности n-1.
Hvordan kan dette lemmaet hjelpe oss? I et prefiksetre må alle tegn lagres i blader. Ellers ville det være umulig å få entydige koder. Derfor, uavhengig av utseendet, vil et prefiksetre som et Huffman-tre inneholde maksimalt 511 noder: maksimalt 256 blader og maksimalt 255 interne noder. Derfor bør vi være i stand til å implementere et Huffman-tre (i det minste gi koding av byteverdier) som en 511-elementarray.
Strukturen til en node inkluderer et tellerfelt (som inneholder det totale antallet forekomster av tegn for selve noden og alle dens undernoder), indeksene til venstre og høyre barnenoder, og til slutt et felt som inneholder indeksen til denne. selve noden (denne informasjonen vil lette konstruksjonen av Huffman-treet).
Årsaken til valget av Huffman-kodetyper (THuffmanCodeStr og THuffmanCodes) vil bli tydelig etter å ha vurdert genereringen av koder for hvert av tegnene.
Create-konstruktøren til Huffman-treklassen initialiserer ganske enkelt den interne matrisen til treet.
Notering 11.8. Konstruere et Huffman Tree-objekt
konstruktør THuffmanTree.Create;
arvet Opprett;
FillChar (FTree, sizeof (FTree), 0);
for i: = 0 til 510 do
FTree [i] .hnIndex: = i;
Siden konstruktøren ikke tildeler noe minne, og ingen minneallokering gjøres i noe annet objekt i klassen, er det ingenting for en eksplisitt destruktor å gjøre. Derfor bruker klassen som standard TObject.Destroy-metoden.
Den første metoden som ble kalt på Huffman-treet i kompresjonsrutinen var CalcCharDistribution. Denne metoden leser inndatastrømmen, beregner antall forekomster av hvert tegn og bygger deretter treet.
Notering 11.9. Beregning av antall forekomster av symboler
prosedyre THuffmanTree.CalcCharDistribution (aStream: TSream);
Buffer: PByteArray;
BytesRead: heltall;
(les alle byte, hold tellere for hver byte-verdi, start på begynnelsen av strømmen)
aStream.Position: = 0;
GetMem (Buffer, HuffmanBufferSize);
mens (BytesRead<>0) gjør
for i: = pred (BytesRead) ned til 0 do
inc (FTree] .hnCount);
BytesRead: = aStream.Read (Buffer ^, HuffmanBufferSize);
FreeMem (Buffer, HuffmanBufferSize);
(bygg et tre)
Som du kan se i oppføring 11.9, beregner det meste av metodekoden antall forekomster av tegn og lagrer disse verdiene i de første 256 nodene i matrisen. For å forbedre effektiviteten gir metoden blokk-for-blokk-lesninger av inngangsstrømmen (før utregningssyklusen utføres, allokerer den en stor blokk med minne på haugen og frigjør den etter beregning). Til slutt, på slutten av subrutinen, kalles den interne htBuild-metoden for å bygge treet.
Før vi utforsker implementeringen av denne viktige interne metoden, la oss se på en mulig implementering av trebyggingsalgoritmen. Husk at vi starter med å lage en "pool" av noder, en for hver karakter. Vi velger de to minste nodene (dvs. de to nodene med de laveste tellingene) og fester dem til den nye overordnede noden (sett dens telling til summen av tellingene til dens underordnede noder), og skyver deretter overordnet tilbake i bassenget . Vi fortsetter denne prosessen til det bare er én node igjen i bassenget. Hvis du husker diskusjonen i kapittel 9, blir det åpenbart hvilken struktur du kan bruke for å implementere denne amorfe "poolen": prioritetskøen. Strengt tatt bør vi bruke et sorteringstre med det minste elementplukket (vanligvis implementeres en prioritetskø for å returnere det største elementet).
Notering 11.10. Bygge et Huffman-tre
funksjon CompareHuffmanNodes (aData1, aData2: peker): heltall; langt;
Node1: PHuffmanNode absolutt aData1;
Node2: PHuffmanNode absolutt aData2;
(MERK: denne sammenligningsrutinen er designet for å implementere en Huffman-prioritetskø, som er et * minste utvalgssorteringstre *. Derfor bør den returnere elementer i motsatt rekkefølge av det som forventes)
if (Node1 ^ .hnCount)> (Node2 ^ .hnCount) da
if (Node1 ^ .hnCount) = (Node2 ^ .hnCount)
annet Resultat: = 1;
prosedyre THuffmanTree.htBuild;
PQ: TtdPriorityQueue;
Node1: PHuffmanNode;
Node2: PHuffmanNode;
RootNode: PHuffmanNode;
(opprett prioritert kø)
PQ: = TtdPriorityQueue.Create (CompareHuffmanNodes, null);
PQ.Name:= "Huffman tree minheap";
(legg til alle noder som ikke er null i køen)
for i: = 0 til 255 do
if (FTree [i] .hnCount<>0) da
PQ.Enqueue (@FTree [i]);
(SPESIELL TILFELDELSE: det er bare én node som ikke er null, dvs. inngangsstrømmen består av kun ett tegn, gjentatt en eller flere ganger. I dette tilfellet settes verdien til rotnoden lik verdien til nodeindeksen til et enkelt tegn)
hvis (PQ.Count = 1) så begynn
RootNode: = PQ.Dequeue;
FRoot: = RootNode ^ .hnIndex;
(ellers er det det vanlige tilfellet med mange forskjellige symboler)
(så lenge det er mer enn ett element i køen, er det nødvendig å utføre sletting av de to minste elementene, feste dem til den nye overordnede noden og legge den til i køen)
mens (PQ.Count> 1) gjør det
Node1: = PQ.Dequeue;
Node2: = PQ.Dequeue;
RootNode: = @FTree;
med RootNode ^ do
hnLeftInx: = Node1 ^ .hnIndex;
hnRightInx Node2 ^ .hnIndex;
hnCount: = Node1 ^ .hnCount + Node2 ^ .hnCount;
PQ.Enqueue (RootNode);
Vi starter med å lage en forekomst av TtdPriorityQueue-klassen. Vi sender den CompareHuffmanNodes-subrutinen. Husk at i prioritetskøen vi opprettet i kapittel 9, ble det brukt en sammenligningsrutine for å returnere varer i synkende rekkefølge. For å lage et minste utvalgssorteringstre som er nødvendig for å lage et Huffman-tre, endrer vi formålet med sammenligningsrutinen for å returnere en positiv verdi hvis det første elementet er mindre enn det andre, og negativt hvis det er større.
Når prioritetskøen er opprettet, legger vi alle noder med tellerverdier som ikke er null. Hvis det bare er én slik node, settes verdien av feltet til rotnoden til Huffman-treet lik indeksen til den enkelte noden. Ellers bruker vi Huffman-algoritmen, med den første forelderen referert til indeks 256. Ved å fjerne to noder fra køen og plassere en ny forelder i den, opprettholder vi FRoot-variabelen til å peke til den siste forelderen. Som et resultat, på slutten av prosessen, kjenner vi indeksen til elementet som representerer rotnoden til treet.
Til slutt slipper vi prioritetskøobjektet. Huffman-treet er nå ferdig bygget.
Den neste metoden som kalles i høynivåkomprimeringsrutinen er en metode som skriver Huffman-treet til utdatabitstrømmen. I hovedsak må vi bruke en eller annen algoritme som skriver nok informasjon til å kunne rekonstruere treet. Ett alternativ er å skrive tegn og deres forekomsttellingsverdier. Gitt denne informasjonen, kan reparasjonsprogrammet enkelt gjenopprette Huffman-treet ved ganske enkelt å kalle htBuild-metoden. Dette virker som en fornuftig idé, bortsett fra størrelsen på symboltabellen og antallet forekomster av dem i den komprimerte utdatastrømmen. I dette tilfellet vil hvert tegn okkupere en full byte i utdatastrømmen, og tellerverdien vil oppta et visst fast antall byte (for eksempel to byte per tegn for å telle opp til 65535 forekomster). Med 100 separate tegn i inndatastrømmen, vil hele tabellen være på 300 byte. Hvis alle mulige tegn var til stede i inndatastrømmen, ville tabellen okkupert 768 byte.
En annen mulig måte er å lagre tellerverdier for hvert tegn. I dette tilfellet kreves det to faste byte for alle tegn, inkludert de som ikke er til stede i inndatastrømmen. Som et resultat vil den totale tabellstørrelsen i alle situasjoner være 512 byte. For å være ærlig er ikke dette resultatet mye bedre enn det forrige.
Selvfølgelig, hvis inngangsstrømmen var stor nok, kan noen av telleverdiene overskride størrelsen på et 2-byte ord, og tre eller til og med fire byte må brukes for hvert tegn.
En mer rasjonell tilnærming er å ignorere karakterantallet og beholde den faktiske trestrukturen. Prefiksetreet inneholder to forskjellige typer noder: interne, med to barn, og eksterne, uten barn. Eksterne noder er noder som inneholder symboler. La oss krysse treet ved å bruke en av de vanlige traverseringene (faktisk vil vi bruke bredden-først-traverseringen). For hver nådd node vil vi skrive en nullbit hvis noden er intern, eller en enbit hvis noden er ekstern, etterfulgt av symbolet representert av noden. Liste 11-11 viser implementeringskoden for SaveToBitStream-metoden og den rekursive htSaveNode-metoden den kaller, som faktisk krysser treet og skriver informasjon til bitstrømmen.
Notering 11.11. Å skrive et Huffman-tre til en bitstrøm
prosedyre THuffmanTree.htSaveNode (aBitStream: TtdOutputBitStream;
aNode: heltall);
(hvis denne noden er intern, skriv bit null, så venstre underordnet, så høyre underordnet)
hvis (aNode> = 256) så begynn
aBitStream.WriteBit (false);
htSaveNode (aBitStream, FTree.hnLeftInx);
htSaveNode (aBitStream, FTree.hnRightInx);
(ellers er noden et blad og du må skrive en bit og deretter et tegn)
aBitStream.WriteBit (true);
aBitStream.WriteByte (aNode);
(aNode er et tegn)
prosedyre THuffmanTree.SaveToBitStream (aBitStream: TtdOutputBitStream);
htSaveNode (aBitStream, FRoot);
Hvis det var 100 separate tegn i inngangsstrømmen, ville den inneholde 99 interne noder, og det ville kun ta 199 biter å lagre informasjonen om nodene, pluss 100 byte for å lagre selve tegnene - omtrent 125 byte totalt. Hvis alle tegn var representert i inngangsstrømmen, ville det ta 511 biter å lagre nodeinformasjon, pluss plass til å lagre 256 tegn. Dermed vil totalt 320 byte være nødvendig for å lagre treet.
Den komplette koden for Huffman-trekomprimeringsrutinen kan finnes på utgiverens nettsted i materialdelen. Etter å ha lastet av materialene, finn filen TDHuffmn.pas blant dem.
Etter at vi har vurdert implementeringen av Huffman-komprimering, la oss begynne å løse problemet med datagjenoppretting. Koden for TDHuffmanDeconpress-rutinen som kontrollerer denne prosessen er vist i liste 11-12.
Notering 11.12. TDHuffmanDecoropress Rutine
prosedyre TDHuffmanDecompress (aInStream, aOutStream: TSream);
Signatur: longint;
HTree: THuffmanTree;
BitStrm: TtdInputBitStream;
(sjekk at inngangsstrømmen er en Huffman-kodet strøm)
aInStream.Seek (0, soFromBeginning);
aInStream.ReadBuffer (Signatur, sizeof (Signatur));
hvis (Signatur<>TDHuffHeader) da
raise EtdHuffmanException.Create (FmtLoadStr (tdeHuffBadEncodedStrm,));
aInStream.ReadBuffer (Størrelse, størrelse på (lengde));
(hvis det ikke er noen data å gjenopprette, gå ut av subrutinen)
hvis (Størrelse = 0) da
(forbered deg på bedring)
(opprett bitstrøm)
BitStrm: = TtdInputBitStream.Create (aInStream);
BitStrm.Name:= "Huffman komprimert strøm";
(lag et Huffman-tre)
HTree.LoadFromBitStream (BitStrm);
(hvis rotnoden til Huffman-treet er et blad, består den opprinnelige strømmen av bare repetisjoner av ett tegn)
hvis HTree.RootIsLeaf da
WriteMultipleChars (aOutStream, AnsiChar (HTree.Root), Size) (gjenopprett ellers tegnene til inngangsstrømmen ved hjelp av et Huffman-tre)
DoHuffmanDekompresjon (BitStrm, aOutStream, HTree, Size);
Først av alt sjekker vi om strømmen starter med riktig signatur. Hvis ikke, er det ikke fornuftig å fortsette prosessen siden strømmen tydelig inneholder feil.
Lengden på de ukomprimerte dataene leses så, og hvis den er null er oppgaven fullført. Ellers må det gjøres noe. I dette tilfellet lager vi en input-bitstrøm som inneholder input-strømmen. Vi lager deretter et Huffman-treobjekt som vil gjøre det meste av arbeidet, og tvinger det til å gjøre sin egen lesing fra input-bitstrømmen (ved å kalle LoadFromBitStream). Hvis Huffman-treet representerer en enkelt karakter, rekonstrueres den opprinnelige strømmen som repetisjoner av den karakteren. Ellers kaller vi DoHuffmanDecoonpression-subrutinen for å utføre datagjenoppretting. Koden for denne rutinen er vist i oppføring 11.13.
Notering 11.13. DoHuffman Dekompresjonsrutine
prosedyre DoHuffmanDecompression (aBitStream: TtdInputBitStream;
aOutStream: TSream; aHTree: THuffmanTree; aStørrelse: longint);
CharCount: longint;
Buffer: PByteArray;
BufEnd: heltall;
GetMem (Buffer, HuffmanBufferSize);
(forhåndsinnstilling av sløyfevariabler)
(Gjenta prosessen til alle tegnene er gjenopprettet)
Ch: = aHTree.DecodeNextByte (aBitStream);
Buffer ^: = Ch;
(hvis bufferen er full, må du skrive den)
if (BufEnd = HuffmanBufferSize) så begynn
aOutStream.WriteBuffer (Buffer ^, HuffmanBufferSize);
(hvis det er noen data igjen i bufferen, må du skrive det)
hvis (BufEnd<>0) da
aOutStream.WriteBuffer (Buffer ^, BufEnd);
FreeMem (Buffer, HuffmanBufferSize);
I hovedsak er en subrutine en løkke, i hvilken dekoding av byte og fylling av bufferen utføres gjentatte ganger. Når bufferen er full, skriver vi den til utdatastrømmen og begynner å fylle den opp igjen. Dekoding gjøres ved å bruke DecodeNextByte-metoden i THuffmanTree-klassen.
Notering 11.14. DecodeNextByte-metoden
function THuffmanTree.DecodeNextByte (aBitStream: TtdInputBitStream): byte;
NodeInx: heltall;
NodeInx: = FRoot;
mens (NodeInx> = 256) gjør det
hvis ikke aBitStream.ReadBit da
NodeInx: = FTree.hnLeftInx annet
NodeInx: = FTree.hnRightInx;
Resultat: = NodeInx;
Denne metoden er ekstremt enkel. Den begynner ganske enkelt å behandle ved roten av Huffman-treet, og for hver bit som leses fra inndatabitstrømmen, avhengig av om den var null eller én, hopper den til venstre eller høyre. Så snart subrutinen når bladet, returnerer den indeksen til den nådde noden (verdien vil være mindre enn eller lik 255). Denne noden er den dekodede byten.
Den komplette koden for å utføre en Huffman-trerestaurering finner du på utgiverens nettsted, i materialdelen. Etter å ha lastet av materialene, finn filen TDHuffmn.pas blant dem.
Huffman-koding
En av de første algoritmene for effektiv koding av informasjon ble foreslått av D.A. Huffman i 1952. Ideen til algoritmen er som følger: Når man kjenner sannsynlighetene til tegn i en melding, kan man beskrive prosedyren for å konstruere koder med variabel lengde som består av et helt antall biter. Det er mer sannsynlig at karakterer blir tildelt kortere koder. Huffman-koder har egenskapen til å være prefiks (det vil si at ingen kodeord er et prefiks til et annet), noe som gjør at de kan dekodes entydig.
Den klassiske Huffman-algoritmen ved inngangen mottar en tabell over frekvensen av forekomst av tegn i meldingen. Videre, basert på denne tabellen, er et Huffman-kodetre (H-tre) konstruert.
- Tegnene i inndataalfabetet danner en liste over ledige noder. Hvert ark har en vekt, som kan være lik enten sannsynligheten eller antallet forekomster av tegnet i den komprimerte meldingen.
- To frie trenoder med minst vekt er valgt.
- Forelderen deres er opprettet med en vekt lik deres totale vekt.
- Forelderen legges til gratislisten, og dens to barn fjernes fra gratislisten.
- Bit 1 er tilordnet til en bue som forlater den overordnede, bit 0 til den andre.
- Trinnene som starter fra den andre gjentas til bare én ledig node gjenstår i den ledige listen. Han vil bli betraktet som roten til treet.
La oss si at vi har følgende frekvenstabell:
| 15 | 7 | 6 | 6 | 5 |
|---|---|---|---|---|
| EN | B | V | G | D |
Denne prosessen kan representeres som å bygge et tre, hvis rot er symbolet med summen av sannsynlighetene til de kombinerte symbolene, oppnådd ved å kombinere symbolene fra det siste trinnet, dets n 0 etterkommere er symboler fra forrige trinn, osv. .
For å bestemme koden for hvert av tegnene som er inkludert i meldingen, må vi gå fra bladet på treet som tilsvarer det gjeldende tegnet til roten, og samle biter mens vi beveger oss langs grenene til treet (den første grenen i banen tilsvarer den minst signifikante biten). Sekvensen av biter oppnådd på denne måten er koden til dette symbolet, skrevet i omvendt rekkefølge.
For denne symboltabellen vil Huffman-kodene se slik ut.
| EN | B | V | G | D |
|---|---|---|---|---|
| 0 | 100 | 101 | 110 | 111 |
Siden ingen av de mottatte kodene er et prefiks til den andre, kan de dekodes unikt når de leses fra strømmen. I tillegg er det hyppigste tegnet i meldingen A kodet med færrest antall biter, og det sjeldneste tegnet D er kodet med det største.
I dette tilfellet vil den totale lengden på en melding som består av symbolene vist i tabellen være 87 biter (i gjennomsnitt 2,2308 biter per symbol). Ved bruk av enhetlig koding vil den totale meldingslengden være 117 biter (nøyaktig 3 biter per tegn). Merk at entropien til en kilde som uavhengig genererer symboler med de angitte frekvensene er ~ 2,1858 biter per symbol, dvs. redundansen til Huffman-koden konstruert for en slik kilde, forstått som forskjellen mellom gjennomsnittlig antall biter per symbol og entropien, er mindre enn 0,05 biter per symbol.
Den klassiske Huffman-algoritmen har flere betydelige ulemper. For det første, for å gjenopprette innholdet i den komprimerte meldingen, må dekoderen kjenne til frekvenstabellen som brukes av koderen. Følgelig økes lengden på den komprimerte meldingen med lengden på frekvenstabellen som skal sendes foran dataene, noe som kan oppheve alle anstrengelser for å komprimere meldingen. I tillegg krever behovet for å ha fullstendig frekvensstatistikk før du starter selve kodingen to gjennomganger gjennom meldingen: en for å bygge en meldingsmodell (frekvenstabell og H-tre), den andre for selve kodingen. For det andre forsvinner kodingsredundansen bare når sannsynlighetene for de kodede symbolene er inverse potenser på 2. For det tredje, for en kilde med entropi som ikke overstiger 1 (for eksempel for en binær kilde), er direkte bruk av Huffman-koden meningsløs.
Adaptiv kompresjon
Adaptiv komprimering gjør det mulig å ikke overføre meldingsmodellen sammen med den og å være begrenset til én gjennomgang av meldingen både under koding og dekoding.
Ved å lage en algoritme for adaptiv Huffman-koding, oppstår de største vanskelighetene når man utvikler en prosedyre for å oppdatere modellen med neste symbol. Teoretisk sett vil det være mulig å ganske enkelt sette inn en komplett konstruksjon av et Huffman-kodetre i denne prosedyren, men en slik komprimeringsalgoritme ville ha uakseptabelt lav ytelse, siden det er for mye arbeid å bygge et H-tre og det er urimelig å gjøre det. når du behandler hvert tegn. Heldigvis er det en måte å modifisere et eksisterende H-tre for å gjenspeile behandlingen av det nye symbolet.
Oppdatering av treet ved lesing av neste meldingstegn består av to operasjoner.
Den første er å øke vekten av trenodene. Først øker vi vekten på arket som tilsvarer tegnet som leses av en. Deretter øker vi vekten til forelderen for å matche de nye vektene til barna. Denne prosessen fortsetter til vi kommer til roten av treet. Gjennomsnittlig antall vektoperasjoner er lik det gjennomsnittlige antall biter som kreves for å kode et tegn.
Den andre operasjonen - permutasjon av trenoder - er nødvendig når en økning i vekten til en node fører til brudd på bestillingsegenskapen, det vil si når den økte vekten til en node har blitt større enn vekten til neste node i rekkefølge. Hvis du fortsetter å behandle vektøkningen og beveger deg mot roten av treet, vil treet ikke lenger være et Huffman-tre.
For å holde kodingstreet i orden, fungerer algoritmen som følger. La den nye økte nodevekten være W + 1. Deretter begynner vi å bevege oss gjennom listen i retning av økende vekt til vi finner den siste noden med vekt W. Omorganiser gjeldende og funnet noder seg imellom i listen, og gjenoppretter dermed rekkefølgen i treet (i dette tilfellet foreldrene av hver av nodene vil også endres). Dette fullfører permutasjonsoperasjonen.
Etter omorganiseringen fortsetter operasjonen med å øke vekten til nodene ytterligere. Den neste noden hvis vekt vil økes av algoritmen er den nye forelderen til noden hvis vektøkning forårsaket permutasjonen.
Flyte
Under driften av kompresjonsalgoritmen vokser vekten av nodene i Huffman-kodetreet jevnt og trutt. Det første problemet oppstår når vekten av roten til treet begynner å overskride kapasiteten til cellen der den er lagret. Vanligvis er dette en 16-bits verdi og kan derfor ikke være større enn 65535. Et annet problem som fortjener enda mer oppmerksomhet kan oppstå mye tidligere når størrelsen på den lengste Huffman-koden overskrider kapasiteten til cellen som brukes til å overføre den til utgangsstrømmen. Dekoderen bryr seg ikke om hvor lenge koden den dekoder, siden den beveger seg fra topp til bunn langs kodingstreet, og velger én bit fra inngangsstrømmen. Enkoderen må starte ved bladet på treet og bevege seg opp til roten og samle bitene som må overføres. Dette skjer vanligvis med en heltallsvariabel, og når lengden på Huffman-koden overstiger størrelsen på heltallet i biter, oppstår det et overløp.
Det kan bevises at maksimal lengde på Huffman-koden for meldinger med samme inngangsalfabet vil ha dersom frekvensen til symbolene danner en Fibonacci-sekvens. En melding med symbolhastigheter lik Fibonacci-tallene før Fib (18) er en fin måte å teste ytelsen til et Huffman-komprimeringsprogram på.
Skalering av vektene til nodene til Huffman-treet
Med hensyn til det ovennevnte, bør algoritmen for oppdatering av Huffman-treet endres som følger: når du øker vekten, må du sjekke den for å oppnå et akseptabelt maksimum. Hvis vi har nådd maksimum, må vi "skalere" vekten, vanligvis dele vekten av bladene med et heltall, for eksempel 2, og deretter beregne vekten til alle andre noder.
Men når du deler vekten i to, oppstår problemet at etter denne operasjonen kan treet endre form. Dette forklares med det faktum at vi deler heltall og når vi deler, forkaster vi brøkdelen.
Et velorganisert Huffman-tre etter skalering kan ha en form som er vesentlig forskjellig fra originalen. Dette er fordi skalering resulterer i tap av nøyaktighet i statistikken vår. Men med innsamlingen av ny statistikk blir konsekvensene av disse «feilene» praktisk talt til intet. Vektskalering er en ganske kostbar operasjon, da den fører til behovet for å gjenoppbygge hele kodetreet. Men siden behovet for det oppstår relativt sjelden, kan du tåle det.
Skaleringsgevinst
Skalering av vektene til trenodene med spesifikke intervaller gir uventede resultater. Selv om det er et tap av statistisk nøyaktighet ved skalering, viser tester at skalering resulterer i bedre kompresjonshastigheter enn om skalering ble utsatt. Dette kan forklares med det faktum at de nåværende symbolene til den komprimerte strømmen er mer "lik" til deres nære forgjengere enn de som ble møtt mye tidligere. Skalering fører til en reduksjon i påvirkningen av "gamle" symboler på statistikk og til en økning i påvirkningen av "nyere" symboler på den. Dette er svært vanskelig å kvantifisere, men i prinsippet har skalering en positiv effekt på komprimeringsforholdet til informasjon. Eksperimenter med skalering på ulike punkter i kompresjonsprosessen viser at kompresjonsforholdet er sterkt avhengig av vektskaleringsøyeblikket, men det er ingen regel for å velge det optimale skaleringsmomentet for et program fokusert på å komprimere alle typer informasjon.
applikasjon
Huffman-datakomprimering brukes til å komprimere foto- og videobilder (JPEG, MPEG-komprimeringsstandarder), i arkivere (PKZIP, LZH, etc.), i MNP5- og MNP7-dataoverføringsprotokollene.
Notater (rediger)
Litteratur
- Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruksjon og analyse = Introduksjon til algoritmer. - 2. utg. - M .: Williams, 2006 .-- 1296 s. - ISBN 0-07-013151-1
- D. Salomon. Komprimering av data, bilder og lyd. - M .: Technosphere, 2004 .-- 368 s. - 3000 eksemplarer. - ISBN 5-94836-027-X
- Ananiy V. Levitin. Kapittel 9. Greedy Methods: The Huffman Algorithm // Algoritmer: An Introduction to Design and Analysis = Introduction to The Design and Analysis of Aigorithms. - M .: Williams, 2006 .-- S. 392-398. - ISBN 0-201-74395-7
Lenker
- Huffman Code (WebArchive)
- Huffman-komprimering på algolist.manual.ru
| Komprimeringsmetoder | |||||||
|---|---|---|---|---|---|---|---|
| Teori | |||||||
| Ingen tap |
|
||||||
| Lyd |
|
||||||
| Bilder |
| ||||||
En av de første algoritmene for effektiv koding av informasjon ble foreslått av Huffman i 1952. Denne algoritmen ble grunnlaget for et stort antallmer. For eksempel brukes Huffman-koding i komprimeringsprogrammer ARJ, ZIP, RAR, i en grafisk komprimeringsalgoritme med tap JPEG, og er også innebygd i moderne faksmaskiner.
Effektiv Huffman-koding består i å representere de mest sannsynlige (oftest forekommende) bokstavene i binære koder med kortest lengde, og mindre sannsynlige - i koder med lengre lengde (hvis alle kodeord med kortere lengde allerede er oppbrukt). Dette gjøres på en slik måte at gjennomsnittslengden på koden per bokstav i originalmeldingen er minimal.
Før kodingen begynner, må sannsynlighetene for forekomst av hver bokstav som meldingen vil bestå av, være kjent. Basert på denne sannsynlighetstabellen bygges et Huffman-kodetre, ved hjelp av hvilket bokstavene kodes.
Bygge et Huffman-kodetre
For å illustrere Huffman-algoritmen, vurder en grafisk metode for å konstruere et kodingstre. Før det introduserer vi noen definisjoner som er tatt i bruk for å beskrive Huffman-algoritmen ved å bruke denne metoden.
Kurve- et sett med et sett med noder og et sett med buer rettet fra en node til en annen.
Tre- en graf med følgende egenskaper:
- ingen node inneholder mer enn én bue;
- bare én node ns inneholder ingen buer (denne noden kalles roten til treet);
- beveger seg langs buer fra roten, kan man komme til hvilken som helst node.
Treblad- en node som ikke en eneste bue går ut fra. V pars
noder til et tre forbundet med en bue, den som det går ut fra kalles forelder, en annen - barn.
De to nodene kalles brødre, hvis de har samme forelder.
Binært tre- et tre med nøyaktig to buer som kommer ut av alle noder, bortsett fra blader.
Et Huffman-kodetre er et binært tre der hver node har vekten, og vekten til forelderen er lik den totale vekten til hans barn. Algoritmen for å konstruere et Huffman-kodingstre er som følger:
- 1. Bokstavene i inndataalfabetet danner en liste over ledige noder til det fremtidige kodingstreet. Hver node i denne listen har en vekt lik sannsynligheten for forekomst av den tilsvarende bokstaven i meldingen.
- 2. To frie trenoder med minst vekt velges. Hvis det er mer enn to ledige noder med minst vekt, kan du ta et hvilket som helst par.
- 3. Forelderen deres er opprettet med en vekt lik deres totale vekt.
- 4. Forelderen legges til frilisten, og hans to barn fjernes fra listen.
- 5. En bue som forlater overordnet node er tildelt bit 1, den andre - 0.
- 6. Punktene 2, 3, 4, 5 gjentas til bare én node gjenstår i den ledige listen. Denne noden vil være roten til treet. Dens vekt er lik én - den totale sannsynligheten for alle bokstavene i meldingen.
Når du nå beveger deg langs kodetreet fra topp til bunn og sekvensielt skriver ut de binære sifrene som tilsvarer buene, kan du få kodene til bokstavene i inndataalfabetet.
Vurder for eksempel konstruksjonen av et Huffman-kodetre for det gitte i tabellen. 10.1 alfabet på åtte bokstaver.
Tabell 10.1
|
Sannsynlighet |
Vi begynner å bygge treet med en liste over blader (fig. 10.2) og utfører det trinn for trinn.
Ris. 10.2.
I det første trinnet velges to med den minste vekten fra bladene på treet - z 7 og zg. De er festet til overordnet node, hvis vekt er satt til 0,04 + 0,02 = 0,06. Deretter nodene z 7 og z 8 fjernet fra gratislisten. Knute z 7 matcher gren 0 forelder, node z 8- gren 1. Kodetreet etter første trinn er vist i fig. 10.3.
Ris. 10.3.
På det andre trinnet er det "letteste" paret bladet Zb og en fri knute (g 7 + z 8). En forelder med vekt vil bli opprettet for dem 0,16. Knute Zb tilsvarer gren 0 til den overordnede noden (r 7 + zg)- gren 1. På dette trinnet er kodetreet vist i fig. 10.4.
Ris. 10.4.
På det tredje trinnet er de minste sannsynlighetene zs,z *, Zj og fri knute (zb + Zi + z.g). Dermed kan du på dette trinnet opprette en forelder for z $ og (Zb + g 7 + g 8) med vekt 0,26, og dermed oppnå kodingstreet vist i fig. 10.5. Vær oppmerksom på at i denne situasjonen er flere alternativer for tilkobling av noder med de laveste vektene mulige. Dessuten vil alle slike alternativer være korrekte, selv om de kan føre til forskjellige sett med koder, som imidlertid vil ha samme effektivitet for en gitt sannsynlighetsfordeling.
Ris. 10.5.
På det fjerde trinnet er det "letteste" paret bladene c og 24- Huffman-kodingstreet er vist i fig. 10.6.
Ris. 10.6.
Ris. ti. 7.
Ris. 10.8.
På det femte trinnet velger vi nodene med minst vekt 0,22 og 0,20. Huffman-kodingstreet etter det femte trinnet er vist i fig. 10.7.
På sjette trinn er det tre frie noder med vekter 0,42, 0,32 og 0,26. Velge de minste vektene 0,32 og 0,26. Huffman-kodingstreet etter det sjette trinnet er vist i fig. 10.8.
På det syvende trinnet gjenstår det å kombinere de to gjenværende frie hjørnene, hvoretter vi får det endelige Huffman-kodingstreet vist i fig. 10.9.
Ris. 10.9.
Basert på det konstruerte treet, er bokstaver representert av koder som reflekterer banen fra rotnoden til bladet som tilsvarer ønsket bokstav. I det betraktede eksemplet er bokstavene i inndataalfabetet kodet som vist i tabellen. 10.2.
Tabell 10.2
Ris. 10.10.
Man kan se at de mest sannsynlige bokstavene er kodet med de korteste kodene, og de sjeldneste - med koder av større lengde, og kodene er konstruert på en slik måte at ingen kodekombinasjon ns faller sammen med begynnelsen av en lengre kombinasjon. Dette gjør at meldinger kan dekodes entydig uten å skille tegn.
For gitt i tabellen. 10.1 sannsynligheter, kan du konstruere andre korrekte versjoner av Huffman-kodetreet. Et av de tillatte trærne er vist i fig. 10.10. Kodene til bokstavene i inndataalfabetet for dette kodetreet er gitt i tabellen. 10.3.
Fra bordet. 10.3 kan man se at kodene også viste seg å være prefiks, og de korteste kodene tilsvarer de mest sannsynlige bokstavene.
Tabell 10.3
