Aritmetisk kodning
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 12. marts 2013; checks kræver 30 redigeringer .Aritmetisk kodning er en af entropikomprimeringsalgoritmerne .
I modsætning til Huffman-algoritmen har den ikke en hård konstant korrespondance af inputtegn til grupper af bit i outputstrømmen. Dette giver algoritmen mere fleksibilitet til at repræsentere brøktegnsfrekvenser.
Som regel overgår den Huffman-algoritmen med hensyn til komprimeringseffektivitet, giver dig mulighed for at komprimere data med entropi mindre end 1 bit pr. kodet tegn, men nogle versioner har patentrestriktioner fra IBM . [en]
Karakteristika
Giver næsten optimalt kompressionsforhold i forhold til Shannon-kodningsentropi-estimat. Der kræves næsten en smule for hvert symbol, hvor er kildens informationsentropi .
I modsætning til Huffman-algoritmen viser den aritmetiske kodningsmetode høj effektivitet for brøkdele af uensartede intervaller af sandsynlighedsfordelingen af de kodede symboler. Men i tilfælde af en ligesandsynlig fordeling af tegn, for eksempel for en streng af bit 010101…0101 af længden s , nærmer den aritmetiske kodningsmetode sig præfikset Huffman-koden og kan endda tage en bit mere. [2]
Sådan virker det
Lad der være et bestemt alfabet, samt data om hyppigheden af brug af tegn (valgfrit). Betragt derefter linjestykket fra 0 til 1 på koordinatlinjen.
Lad os kalde dette segment for arbejde. Lad os arrangere punkterne på det på en sådan måde, at længderne af de dannede segmenter vil være lig med hyppigheden af at bruge symbolet, og hvert sådant segment vil svare til et symbol.
Lad os nu tage et symbol fra strømmen og finde et segment til det blandt de nydannede, nu er segmentet for dette symbol blevet til at fungere. Lad os opdele det på samme måde, som vi deler segmentet fra 0 til 1. Lad os udføre denne operation for et vist antal på hinanden følgende tegn. Derefter vælger vi et hvilket som helst tal fra arbejdssegmentet. Bittene af dette nummer, sammen med længden af dets bitrecord, er resultatet af den aritmetiske kodning af de anvendte strømsymboler.
Et eksempel på, hvordan den aritmetiske kodningsmetode fungerer
Probabilistisk model
Ved hjælp af den aritmetiske kodningsmetode kan man opnå en næsten optimal repræsentation for et givet sæt af symboler og deres sandsynligheder (ifølge Shannons kildeentropikodningsteori vil den optimale repræsentation have en tendens til at være −log 2 P bits pr. symbol, hvis sandsynlighed er P ). Datakomprimeringsalgoritmer, der bruger den aritmetiske kodningsmetode i deres arbejde, danner inden direkte kodning en inputdatamodel baseret på kvantitative eller statistiske karakteristika, såvel som enhver yderligere information, der findes i den kodede sekvens af gentagelser eller mønstre - enhver yderligere information, der tillader dig at afklare sandsynligheden for udseendet af symbolet P i indkodningsprocessen. Det er klart, at jo mere nøjagtigt symbolsandsynligheden bestemmes eller forudsiges, jo højere er kompressionseffektiviteten.
Overvej det enkleste tilfælde af en statisk model til kodning af information, der kommer fra et signalbehandlingssystem. Signaltyper og deres tilsvarende sandsynligheder er fordelt som følger:
- 60 % chance for en neutral signalværdi eller NEUTRAL.
- 20 % chance for en positiv signalværdi, eller POSITIV.
- 10 % chance for en negativ signalværdi, eller NEGATIV.
- 10 % chance for et ende-på-sekvens-tegn eller END-OF-DATA.
Fremkomsten af det sidste symbol for dekoderen betyder, at hele sekvensen er blevet afkodet med succes (som en alternativ fremgangsmåde, men ikke nødvendigvis mere vellykket, kan en blokalgoritme med fast længde anvendes) .
Det skal også bemærkes, at ethvert sæt af symboler kan betragtes som alfabetet i den probabilistiske model af metoden, baseret på egenskaberne ved det problem, der skal løses. Mere heuristiske tilgange anvender dynamiske eller adaptive modeller ved at bruge det grundlæggende skema for den aritmetiske kodningsmetode . Ideen med disse metoder er at forfine sandsynligheden for det kodede tegn ved at tage højde for sandsynligheden for den tidligere eller fremtidige kontekst (det vil sige sandsynligheden for forekomsten af det kodede tegn efter et vist k-te antal tegn til venstre eller højre, hvor k er rækkefølgen af konteksten).
Meddelelseskodning
Lad os tage følgende sekvens som et eksempel:
NEUTRAL NEGATIV SLUT-PÅ-DATA
Lad os først opdele segmentet fra 0 til 1 i henhold til signalernes frekvenser. Vi vil bryde segmentet i rækkefølgen angivet ovenfor: NEUTRAL - fra 0 til 0,6; NEGATIV - fra 0,6 til 0,8; END-OF-DATA - fra 0,8 til 1.
Lad os nu begynde at kode fra det første tegn. Det første tegn - NEUTRAL svarer til et segment fra 0 til 0,6. Lad os opdele dette segment på samme måde som segmentet fra 0 til 1.
Lad os kode det andet tegn - NEGATIV. På segmentet fra 0 til 0,6 svarer det til segmentet fra 0,48 til 0,54. Lad os opdele dette segment på samme måde som segmentet fra 0 til 1.
Lad os kode det tredje tegn - END-OF-DATA. På segmentet fra 0,48 til 0,54 svarer det til segmentet fra 0,534 til 0,54.
Da dette var det sidste tegn, er kodningen færdig. Den kodede meddelelse er et segment fra 0,534 til 0,54 eller et hvilket som helst tal fra den, for eksempel 0,538.
Meddelelsesafkodning
Antag, at vi skal afkode en besked ved hjælp af den aritmetiske kodningsmetode i henhold til modellen beskrevet ovenfor. Den kodede meddelelse er repræsenteret af brøkværdien 0,538 (for nemheds skyld bruges decimalrepræsentationen af brøken i stedet for den binære base). Det antages, at den kodede meddelelse indeholder nøjagtigt så mange tegn i det betragtede antal som nødvendigt for entydigt at gendanne de originale data.
Starttilstanden af afkodningsprocessen falder sammen med indkodningsprocessen, og intervallet [0,1) tages i betragtning. Baseret på den kendte probabilistiske model falder brøkværdien 0,538 inden for intervallet [0, 0,6). Dette giver dig mulighed for at bestemme det første tegn, der blev valgt af indkoderen, så dets værdi udlæses som det første tegn i den afkodede besked.
Noter
- ↑ Historien om udviklingen af informationskomprimeringsteori Arkivkopi af 28. december 2010 på Wayback Machine / Compression.ru, Sarmin Alexey, 10. marts 2011
- ↑ Dr. Dobbs nyhedsbrev om datakomprimering arkiveret 11. december 2017 på Wayback Machine 13. august 2001
Links
| Kompressionsmetoder _ | |||||||
|---|---|---|---|---|---|---|---|
| Teori |
| ||||||
| Tabsfri |
| ||||||
| Lyd |
| ||||||
| Billeder |
| ||||||
| Video |
| ||||||