Huffman koder: eksempler, søknad

For øyeblikket tenker få mennesker på hvordan komprimering fungerer. Sammenlignet med fortiden har det blitt mye lettere å bruke en personlig datamaskin. Og praktisk talt alle personer som jobber med filsystemet bruker arkiver. Men få mennesker tenker på hvordan de jobber, og på hvilket prinsipp er komprimering av filer. Den aller første versjonen av denne prosessen var Huffman-kodene, og de brukes fortsatt i forskjellige populære arkiver. Mange brukere tenker ikke engang på hvor lett det er å komprimere filen og i henhold til hvilken ordning det fungerer. I denne artikkelen ser vi på hvordan komprimering fungerer, hvilke nyanser bidrar til å fremskynde og forenkle kodingsprosessen, og også forstå hva prinsippet om å bygge et kodende tre er.

Algoritmens historie

Den aller første algoritmen for effektiv koding av elektronisk informasjon var koden som ble foreslått av Huffman i midten av det tjuende århundre, nemlig i 1952. Det er for tiden det viktigste grunnelementet i de fleste programmer som er opprettet for å komprimere informasjon. For øyeblikket er en av de mest populære kildene som bruker denne koden arkiver av ZIP, ARJ, RAR og mange andre. Denne Huffman-algoritmen brukes også til å komprimere JPEG-bilder og andre grafiske objekter. Vel og alle moderne fakser bruker også kodingen, oppfunnet i 1952. Til tross for at siden koden ble opprettet, har det gått så mye tid, til i dag brukes det i de nyeste skjellene og på utstyret til de gamle og moderne typene.

Prinsippet om effektiv koding

Grunnlaget for Huffman-algoritmen er et system som lar deg erstatte de mest sannsynlige, mest opptatte symbolene med koder for det binære systemet. Og de som er mindre vanlige, erstattes av lengre koder. Overgangen til lange Huffman koder oppstår først etter at systemet bruker alle minimumsverdiene. Denne teknikken lar deg minimere kodenes lengde for hvert tegn i den opprinnelige meldingen som helhet. Et viktig poeng er at i begynnelsen av kodingen bør sannsynligheten for forekomst av bokstaver allerede være kjent. Det er fra disse at den endelige meldingen vil bli utarbeidet. Basert på disse dataene, er Huffman-kode-treet konstruert, på basis av hvilket prosessen med koding av bokstaver i arkivet vil bli utført.

Huffman kode, eksempel

For å illustrere algoritmen, la oss ta en grafisk variant av å bygge et kode tre. For å bruke denne metoden var effektiv, er det verdt å klargjøre definisjonen av noen verdier som er nødvendige for begrepet denne metoden. Sett med buer og noder som er rettet fra node til node kalles vanligvis en graf. Selve treet er en graf med et sett med visse egenskaper:

• I hver knute kan ikke komme inn mer enn en av buene;
• En av noderne må være roten til treet, det vil si at det ikke burde være noen buer i den;
• Hvis fra roten til å begynne å bevege seg langs buer, bør denne prosessen tillate å komme helt inn i noen av knutepunktene.

Det er også et slikt konsept, som er inkludert i Huffman-kodene, som et blad av et tre. Det er en knute som ingen bue burde unnslippe fra. Hvis to noder er forbundet med en buet, er en av dem forelder, det andre barnet, avhengig av hvilken node bågen kommer fra, og hvilken den er i. Hvis to noder har samme foreldre node, kalles de vanligvis brodernære noder. Hvis i tillegg til bladene er det flere buer i noderne, kalles dette treet binært. Dette er akkurat Huffmans tre. Egenheten av noder av denne konstruksjonen er at vekten av hver forelder er lik summen av vekten av alle dens nodale barn.

Algoritme for å bygge et tre ifølge Huffman

Konstruksjonen av Huffman-koden er laget av bokstavene i inngangs-alfabetet. En liste over de noder som er ledige i fremtiden, er opprettet. Vekten til hver knutepunkt i denne listen skal være den samme som sannsynligheten for forekomsten av brevet i meldingen som svarer til denne knuten. I dette tilfellet er blant de få gratis nodene til det fremtidige treet det som veier minst. På samme tid, hvis minimumsindikatorene observeres i flere noder, er det mulig å velge fritt par av parene. Deretter opprettes hovednoden, som skal veie så mye som summen av dette par noder veier. Etter dette blir foreldrene sendt til listen med gratis noder, og barna blir slettet. Samtidig mottar buene tilsvarende indekser, de og nuller. Denne prosessen gjentas nøyaktig så lenge som nødvendig for å forlate bare en knute. Deretter skrives binære tall nedover fra toppen.

Forbedre kompresjonseffektivitet

For å øke effektiviteten av komprimering er det nødvendig å bruke alle data om sannsynligheten for bokstaver som vises i en bestemt fil som er knyttet til treet, og ikke la dem spres over et stort antall tekstdokumenter når de bygger kodeordet. Hvis du først går gjennom denne filen, kan du umiddelbart beregne statistikken for hvor ofte bokstaver fra objektet som skal komprimeres, er.

Accelerasjon av kompresjonsprosessen

For å øke hastigheten på algoritmen, må bokstavene ikke bestemmes av indeksene av sannsynligheten for forekomst av et bestemt brev, men av hyppigheten av forekomsten. Takket være dette blir algoritmen enklere, og arbeidet med det er sterkt akselerert. Dette unngår også operasjonene knyttet til flytende komma og divisjon. I tillegg er den dynamiske Huffman-koden, eller snarere algoritmen selv, i bruk i denne modusen, ikke gjenstand for noen endringer. Dette skyldes hovedsakelig at sannsynlighetene er direkte proporsjonale med frekvensene. Det er verdt å være spesielt oppmerksom på at sluttvekten til filen eller den såkalte rotnoden vil være lik summen av antall bokstaver i objektet som skal behandles.

konklusjon

Huffmans koder er en enkel og langvarig algoritme som fortsatt brukes av mange kjente programmer og selskaper. Dens enkelhet og klarhet gjør det mulig å oppnå effektive komprimeringsresultater for filer av hvilken som helst størrelse og redusere betraktelig plassen de opptar på lagringsdisken. Med andre ord er Huffman-algoritmen et langt studert og godt designet skjema, hvis relevans ikke reduseres til denne dagen. Og takket være muligheten til å redusere filstørrelsen, overføre dem over nettverket eller på andre måter, blir det enklere, raskere og mer praktisk. Arbeide med algoritmen, du kan komprimere absolutt all informasjon uten å skade strukturen og kvaliteten, men med den maksimale effekten av å redusere filens vekt. Med andre ord, Huffman kode koding var og er den mest populære og faktiske metoden for filstørrelse komprimering.