Huffman kode

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. januar 2019; checks kræver 27 redigeringer .

Huffman-algoritmen er en grådig algoritme til optimal præfikskodning af et alfabet med minimal redundans . Det blev udviklet i 1952 af MIT kandidatstuderende David Huffman , mens han skrev sin semesteropgave . Bruges i øjeblikket i mange datakomprimeringsprogrammer .

I modsætning til Shannon-Fano- algoritmen forbliver Huffman-algoritmen altid optimal for sekundære alfabeter m 2 med mere end to tegn.

Denne indkodningsmetode består af to hovedtrin:

Konstruktion af et optimalt kodetræ.
Opbygning af en kode-symbol mapping baseret på det konstruerede træ.

Den klassiske Huffman-algoritme

Ideen med algoritmen er som følger: ved at kende sandsynligheden for forekomsten af tegn i meddelelsen er det muligt at beskrive proceduren til at konstruere koder med variabel længde bestående af et helt antal bits. Karakterer er mere tilbøjelige til at blive tildelt kortere koder. Huffman-koder har præfiksegenskaben (det vil sige, at intet kodeord er et præfiks for et andet), hvilket tillader dem entydigt at afkodes.

Den klassiske Huffman-algoritme modtager en tabel med tegnfrekvenser i beskeden som input. Yderligere, baseret på denne tabel, er et Huffman-kodningstræ (H-træ) konstrueret. [en]

Tegnene i inputalfabetet danner en liste over frie noder. Hvert blad har en vægt, som kan være lig med enten sandsynligheden eller antallet af forekomster af tegnet i meddelelsen, der skal komprimeres.
To frie træknuder med de mindste vægte vælges.
Deres forælder er skabt med en vægt svarende til deres samlede vægt.
Forælderen føjes til listen over ledige noder, og dens to børn fjernes fra denne liste.
Den ene bue, der udgår fra forælderen, er sat til bit 1, den anden til bit 0. Bitværdierne for grenene, der kommer fra roden, afhænger ikke af børnenes vægt.
Trin, der starter fra den anden, gentages, indtil der kun er én ledig knude tilbage på listen over ledige knudepunkter. Det vil blive betragtet som træets rod.

Lad os sige, at vi har følgende tabel over absolutte frekvenser:

Symbol	MEN	B	PÅ	G	D
Absolut frekvens	femten	7	6	6	5

Denne proces kan opfattes som at bygge et træ, hvis rod er symbolet med summen af sandsynligheden for de kombinerede symboler opnået ved at kombinere symbolerne fra det sidste trin, dets n 0 efterkommere er symbolerne fra det forrige trin, og så videre .

For at bestemme koden for hvert af tegnene, der er inkluderet i meddelelsen, skal vi gå fra bladet på træet, der svarer til det aktuelle tegn til dets rod, og akkumulere bits, når vi bevæger os gennem grenene af træet (den første gren i stien svarer til den mindst signifikante bit). Den således opnåede bitsekvens er koden for det givne tegn, skrevet i omvendt rækkefølge.

For en given tegntabel vil Huffman-koderne se sådan ud.

Symbol	MEN	B	PÅ	G	D
Koden	0	100	101	110	111

Da ingen af de modtagne koder er et præfiks for den anden, kan de entydigt afkodes, når de læses fra strømmen. Derudover er det hyppigste symbol i meddelelsen A kodet med det mindste antal bit, og det sjældneste symbol D er kodet med det største.

I dette tilfælde vil den samlede længde af meddelelsen, bestående af symbolerne i tabellen, være 87 bit (gennemsnitligt 2,2308 bit pr. symbol). Ved at bruge ensartet kodning vil den samlede meddelelseslængde være 117 bit (nøjagtig 3 bit pr. tegn). Bemærk, at entropien af en kilde, der uafhængigt genererer symboler med de specificerede frekvenser, er ~2,1858 bits pr . entropi, er mindre end 0,05 bit på et symbol.

Den klassiske Huffman-algoritme har en række væsentlige ulemper. For det første, for at gendanne indholdet af den komprimerede meddelelse, skal dekoderen kende den frekvenstabel, der anvendes af indkoderen. Derfor øges længden af den komprimerede meddelelse med længden af frekvenstabellen, der skal sendes forud for dataene, hvilket kan ophæve enhver indsats for at komprimere meddelelsen. Derudover kræver behovet for at have fuldstændig frekvensstatistik, før den egentlige indkodning starter, to gennemløb af meddelelsen: en til opbygning af meddelelsesmodellen (frekvenstabel og H-træ), den anden til den faktiske kodning. For det andet forsvinder kodningsredundansen kun i de tilfælde, hvor sandsynligheden for de kodede symboler er inverse potenser af 2. For det tredje, for en kilde med entropi, der ikke overstiger 1 (f.eks. for en binær kilde), den direkte anvendelse af Huffman-koden er meningsløst.

Adaptiv komprimering

Adaptiv komprimering giver dig mulighed for ikke at overføre meddelelsesmodellen sammen med den og begrænse dig til én gennemgang af meddelelsen både under indkodning og afkodning.

Ved at skabe en adaptiv Huffman-kodningsalgoritme opstår de største vanskeligheder, når man udvikler en procedure til opdatering af modellen med det næste tegn. Teoretisk set kunne man ganske enkelt indsætte den komplette konstruktion af Huffman-kodningstræet i denne procedure, men en sådan komprimeringsalgoritme ville have en uacceptabel lav ydeevne, da det er for meget arbejde at bygge et H-træ, og det er urimeligt at gøre det under behandling hver karakter. Heldigvis er der en måde at ændre et allerede eksisterende H-træ for at afspejle behandlingen af en ny karakter. De bedst kendte genopbygningsalgoritmer er Voller-Gallagher-Knuth (FGK) algoritmen og Witter algoritmen.

Alle algoritmer til at genopbygge træet ved læsning af det næste tegn inkluderer to operationer:

Den første er at øge vægten af træknuder. Først øger vi vægten af arket svarende til det læste tegn med én. Så øger vi forældrenes vægt for at bringe den i overensstemmelse med børnenes nye vægte. Denne proces fortsætter, indtil vi kommer til roden af træet. Det gennemsnitlige antal vægtstigninger er lig med det gennemsnitlige antal bits, der er nødvendige for at kode et tegn.

Den anden operation - permutation af træknuder - er påkrævet, når en stigning i vægten af en knude fører til en krænkelse af bestillingsegenskaben, det vil sige, når den øgede vægt af knudepunktet er blevet større end vægten af den næste knude i bestille. Hvis vi fortsætter med at bearbejde vægtstigningen, bevæger vi os mod roden af træet, så vil træet ikke længere være et Huffman-træ.

For at holde rækkefølgen af kodningstræet fungerer algoritmen som følger. Lad den nye øgede nodevægt være W+1. Derefter begynder vi at bevæge os langs listen i retning af stigende vægt, indtil vi finder den sidste node med vægt W. Lad os omarrangere de nuværende og fundne noder indbyrdes på listen, og dermed genoprette rækkefølgen i træet (i dette tilfælde forældrene af hver af noderne vil også ændre sig). Dette afslutter swap-operationen.

Efter permutationen fortsætter operationen med at øge vægten af noderne yderligere. Den næste knude, der skal øges i vægt af algoritmen, er den nye forælder til knudepunktet, hvis vægtstigning forårsagede permutationen.

Kanoniske Huffman-koder

Problemet med den konventionelle Huffman-komprimeringsalgoritme er ikke-determinisme. For lignende sekvenser kan forskellige træer vise sig, og et træ uden korrekt serialisering kan svare til forskellige sekvenser. For at undgå at bruge kanoniske Huffman-koder.

Denne algoritme bygger ikke et Huffman-træ [2] .

Består af to faser:

Beregning af kodens længde for et eller andet tegn
Skrive kode.

Længdeberegning

Beregn frekvensen for hvert tegn
Sorter dem i leksikografisk rækkefølge.
Lad os skrive frekvensen af hvert bogstav ind i arrayet.
Til venstre tildeler vi et array af samme længde, men med serienumre fra det højre array. Det venstre array opnås som en liste over pointere til elementerne i højre side.
På venstre side laver vi en ikke -tiltagende pyramide . Men heapen vil ikke være efter værdien af array-elementerne, men efter værdien af det refererede array-element.
Elementet længst til venstre peger på tegnet fra højre array med den laveste frekvens. Det kan fjernes sådan her:
1. Rør ikke ved den højre halvdel
2. Vi erstatter det første element i arrayet med elementet længst til højre i det venstre array, hvilket angiveligt flytter adskillelsesgrænsen.
3. Vi kontrollerer betingelserne for pyramidens rigtighed, hvis noget er galt, skal vi gentage "hipiseringen".
4. Det første element i venstre side af arrayet fjernes, og det tidligere fjernede element kombineres. Summen af deres frekvenser skrives til grænsen mellem venstre og højre array.
5. I stedet for det slettede element på venstre side, skrives array-indekset, hvor summen af frekvenserne blev tilføjet ved sidste trin.
6. På grund af det faktum, at to elementer blev kombineret, er det nødvendigt at ændre værdierne for disse elementer i arrayet med en reference til den overordnede, hvor de blev placeret.
Vi gentager, der vil ikke være 1 element tilbage i heapen.
På højre side af arrayet fik vi links til elementer, der kombinerer 2 tegn. Derfor går vi gennem arrayet ved hjælp af links, hvilket øger niveauet af fordybelse.
Antallet af klik på linkene vil være længden af Huffman-koden.

Kodekompilering

Arranger elementerne i leksikografisk rækkefølge.
Lad os lave en tabel bestående af blokke, startende med den største kodelængde. Hver blok vil indeholde elementer med samme kodelængde.
Det allerførste tegn i tabellen er kodet med nuller.
I hver blok vil tegnene være i leksikografisk rækkefølge.
Koderne i blokken vil være binære og afvige med 1.
Når du flytter til næste blok, skæres kodebits af det seneste tegn fra, og 1 tilføjes.

Bigram model

Der er en variation af Huffman-algoritmen, der bruger kontekst. I dette tilfælde er størrelsen af konteksten lig med én (bigram - to tegn, trigram - tre, og så videre). Dette er en metode til at konstruere en præfikskode til højere-ordens modeller, ikke længere en hukommelsesløs kilde. Den bruger resultatet af den (tidligere operation) operation på det forrige bogstav sammen med det aktuelle bogstav. Den er bygget på basis af en Markov-kæde med afhængighedsdybde . [3] $r=1$

Algoritme

En tabel er konstrueret i form af et kvadrat - sandsynlighedsfordelingen på bigrammer. Startskemaet beregnes straks, ved hjælp af hvilket kun det første bogstav vil blive kodet. Rækkerne i tabellen er for eksempel de foregående bogstaver, og kolonnerne er de nuværende.
Sandsynligheder beregnes for kodetræer for sammenhænge.
Længdekonteksterne bruges til at bygge de resterende kodetræer, ved hjælp af hvilke alle andre tegn (undtagen det første) bliver kodet. $r=1$
Kodning udføres, det første tegn kodes i henhold til startskemaet, alle efterfølgende tegn kodes baseret på kodetræer for kontekster (det forrige tegn).

Afkodning udføres på lignende måde: fra startkodeskemaet får vi den første kontekst og går derefter til det tilsvarende kodetræ. Desuden har dekoderen brug for en sandsynlighedsfordelingstabel.

Eksempel

Lad os sige, at beskeden, der skal kodes, er "abcabcabc" . Vi kender symbolfrekvenstabellen på forhånd (baseret på andre data, f.eks. ordbogsstatistik).

	-en	b	c	Sum
-en	${\tfrac {3}{16}}$	${\tfrac {1}{16}}$	${\tfrac {1}{16}}$	${\tfrac {5}{16}}$
b	${\tfrac {1}{8))$	${\tfrac {1}{16}}$	${\tfrac {1}{8))$	${\tfrac {5}{16}}$
c	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {6}{16}}$

Vi har en startordning: . Sorter i faldende rækkefølge: og byg et Huffman-kodetræ. $(a={\tfrac {5}{16}},b={\tfrac {5}{16}},c={\tfrac {6}{16}})$ $(c={\tfrac {6}{16}},a={\tfrac {5}{16}},b={\tfrac {5}{16}})$

For kontekst " a " har vi:

$p(a/a)=p(a,a)/p(a)={\tfrac {3}{16}}\div {\tfrac {5}{16}}={\tfrac {3 }{5}}$ ,
$p(b/a)=p(b,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 }{5}}$ ,
$p(c/a)=p(c,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 }{5}}$ .

For kontekst " b " har vi:

$p(a/b)=p(a,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2 }{5}}$ ,
$p(b/b)=p(b,b)/p(b)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 }{5}}$ ,
$p(c/b)=p(c,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2 }{5}}$ .

For kontekst " c " har vi:

$p(a/c)=p(a,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 }{3}}$ ,
$p(b/c)=p(b,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 }{3}}$ ,
$p(c/c)=p(c,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 }{3}}$ .

Bemærk: her er p(x, y) ikke lig med p(y, x) .

Vi bygger kodetræer til hver kontekst. Vi udfører kodning og har en kodet besked: (00, 10, 01, 11, 10, 01, 11, 10, 01).

00 - fra koden for bogstavet "a" for startordningen,
10 - fra koden for bogstavet "b" for konteksten "a" ,
01 - fra koden for bogstavet "c" for konteksten "b" ,
11 - fra koden for bogstavet "a" for konteksten "c" .

Overløb

Mens komprimeringsalgoritmen kører, vokser vægten af noderne i Huffman-kodningstræet støt. Det første problem opstår, når vægten af træets rod begynder at overstige kapaciteten af den celle, hvori den er opbevaret. Typisk er dette en 16-bit værdi og kan derfor ikke være større end 65535. Et andet problem, der fortjener mere opmærksomhed, kan opstå meget tidligere, når størrelsen af den længste Huffman-kode overstiger kapaciteten af den celle, der bruges til at overføre den til outputstrømmen. Dekoderen er ligeglad med, hvor lang tid koden den afkoder, da den bevæger sig fra top til bund langs indkodningstræet og vælger en bit ad gangen fra inputstrømmen. Encoderen skal på den anden side starte ved træets blad og bevæge sig op til roden og samle de bits, der skal transmitteres. Dette sker normalt med en heltalstypevariabel, og når længden af Huffman-koden overstiger størrelsen af heltalstypen i bit, opstår der et overløb.

Det kan bevises, at Huffman-koden for beskeder med det samme inputalfabet vil have den maksimale længde, hvis symbolfrekvenserne danner Fibonacci-sekvensen . En besked med symbolfrekvenser svarende til Fibonacci-tal op til Fib(18) er en fantastisk måde at teste, hvordan et Huffman-komprimeringsprogram fungerer.

Skalering af nodevægtene for et Huffman-træ

Under hensyntagen til ovenstående bør algoritmen til opdatering af Huffman-træet ændres på følgende måde: efterhånden som vægten stiger, skal den kontrolleres for at nå det tilladte maksimum. Hvis vi har nået maksimum, så skal vi "skalere" vægten, normalt ved at dividere vægten af bladene med et heltal, for eksempel 2, og derefter genberegne vægten af alle andre noder.

Men når man deler vægten i halvdelen, er der et problem forbundet med det faktum, at træet efter at have udført denne operation kan ændre sin form. Dette forklares ved, at når man dividerer heltal, kasseres brøkdelen.

Et korrekt organiseret Huffman-træ efter skalering kan have en form, der er væsentligt anderledes end den originale. Dette skyldes, at skalering resulterer i et tab af præcision i statistikken. Men med indsamlingen af nye statistikker er konsekvenserne af disse "fejl" praktisk talt ved at forsvinde. Vægtskalering er en ret dyr operation, da den fører til behovet for at genopbygge hele kodningstræet. Men da behovet for det opstår relativt sjældent, så kan du godt tåle det.

Skaleringsfordele

Skalering af vægten af træknuder med bestemte intervaller giver et uventet resultat. Mens der er et tab af statistisk præcision med skalering, viser test, at skalering resulterer i bedre kompressionsydelse, end hvis skalering var forsinket. Dette kan forklares med det faktum, at de nuværende symboler for den komprimerbare strøm er mere "lignende" til deres nære forgængere end dem, der opstod meget tidligere. Skalering resulterer i et fald i indflydelsen af "gamle" symboler på statistik og en stigning i indflydelsen af "nylige" symboler på den. Dette er meget svært at kvantificere, men i princippet har skalering en positiv effekt på graden af informationskomprimering. Forsøg med skalering på forskellige punkter i komprimeringsprocessen viser, at komprimeringsgraden i høj grad afhænger af tidspunktet for skalering af vægten, men der er ingen regel for at vælge det optimale skaleringsmoment for et program, der fokuserer på at komprimere enhver form for information.

Ansøgning

Huffman-kodning bruges i vid udstrækning til datakomprimering, herunder foto- og videokomprimering ( JPEG , MPEG ), i populære arkivere ( PKZIP , LZH osv.), i HTTP ( Deflate ), MNP5 og MNP7 dataoverførselsprotokoller og andre.

Ændringer

I 2013 blev der foreslået en modifikation af Huffman-algoritmen, som tillader kodning af tegn med et brøktal af bit - ANS [4] [5] . Baseret på denne modifikation er Zstandard (Zstd, Facebook, 2015—2016) [6] og LZFSE (Apple, OS X 10.11, iOS 9, 2016) [7] [8] [9] [10] komprimeringsalgoritmer er implementeret .

Noter

↑ D. Mastryukov. Monitor 7-8.93 Arkiveret 17. maj 2018 på Wayback Machine
↑ Algoritmen er detaljeret med eksempler i Managing Gigabytes af Witten, Moffat, Bell på side 68.
↑ Shmuel T. Klein og Dana Shapira. Huffman-kodning med ikke-sorterede frekvenser (2008). Dato for adgang: 2. januar 2016. Arkiveret fra originalen 4. marts 2016. (ubestemt)
↑ Arkiveret kopi . Hentet 2. januar 2016. Arkiveret fra originalen 5. marts 2016. (ubestemt)
↑ Arkiveret kopi . Hentet 2. januar 2016. Arkiveret fra originalen 11. september 2016. (ubestemt)
↑ Facebook offentliggjorde implementeringen af Zstandard 1.0-komprimeringsalgoritmen Arkiveret 2. september 2016 på Wayback Machine / Opennet.ru, 09/01/2016
↑ Apple har åbnet implementeringen af LZFSE tabsfri kompressionsalgoritme
↑ Apple åbner sin nye kompressionsalgoritme LZFSE . Hentet 1. september 2016. Arkiveret fra originalen 11. september 2016. (ubestemt)
↑ Datakomprimering
↑ GitHub - lzfse/lzfse: LZFSE-komprimeringsbibliotek og kommandolinjeværktøj . Hentet 1. september 2016. Arkiveret fra originalen 28. november 2020. (ubestemt)

Litteratur

Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmer: konstruktion og analyse = Introduktion til algoritmer. - 2. udg. — M .: Williams , 2006. — 1296 s. — ISBN 0-07-013151-1 .
D. Salomon. Komprimering af data, billeder og lyd. - M . : Technosfera, 2004. - 368 s. - 3000 eksemplarer. — ISBN 5-94836-027-X .
Ian H. Witten, Alistair Moffat, Timothy C. Bell. Håndtering af Gigabytes: Komprimering og indeksering af dokumenter og billeder. - 1999. - 551 s. — ISBN 1558605703 .
Levitin A. V. Kapitel 9. Grådige metoder: Huffman-algoritmen // Algoritmer. Introduktion til udvikling og analyse - M . : Williams , 2006. - S. 392-398. — 576 s. — ISBN 978-5-8459-0987-9

Markov A. A. Introduktion til kodningsteori. — M .: Nauka, 1982. — 192 s.

Links

Kompressionsmetoder _

Teori

Information	Egen Gensidig Entropi Betinget entropi Kompleksitet Redundans
Enheder	Bit Nat Nappe Hartley Hartley formel

Tabsfri

Entropi kompression	Asymmetriske talsystemer Huffman algoritme Adaptiv Huffman-algoritme Shannon-Fano algoritme Shannons algoritme Aritmetisk kodning ( interval ) Golomb koder Delta Universel kode Elias fibonacci
Ordbogsmetoder	RLE Tøm luften ud LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Andet	RLE CTW BWT MTF PPM DMC

Lyd

Teori	Konvolution PCM Aliasing Prøveudtagning Kotelnikovs teorem
Metoder	LPC LAR LSP WLPC CELP ACELP En lov μ-lov ADPCM MDCT Fourier transformation Psykoakustisk model
Andet	Audio kompressor Talekompression Båndkodning

Billeder

Vilkår	farverum Pixel Mætningsundersampling Kompressionsartefakter
Metoder	RLE DPCM fraktal wavelet EZW SPIHT LP Forbered PCL
Andet	Bitrate Standard testbillede PSNR Kvantisering

Video

Vilkår	Video egenskaber Ramme Rammetyper Videokvalitet
Metoder	Bevægelseskompensation Forbered Kvantisering wavelet
Andet	Video codec Teori om prisforvrængning CBR ABR VBR