Aritmetische codering
Aritmetische codering is een verliesloze compressiemethode en een vorm van entropiecodering. Het vormt een alternatief voor de Huffmancodering.
Principe
[bewerken | brontekst bewerken]Er zijn twee methoden voor aritmetische codering: uitvoering met drijvende kommagetallen, en met gehele getallen
Voorbeeld met drijvende kommagetallen
[bewerken | brontekst bewerken]
In dit voorbeeld wordt de tekst "AAABAAAC" gecomprimeerd. Eerst is het nodig te controleren hoe vaak elk teken voorkomt zodat de subintervallen berekend kunnen worden. Ter vereenvoudiging wordt een vaste waarschijnlijkheid voor alle tekens gebruikt.
| Teken | Percentage | optimaal aantal bits |
| p(A) | 75% | 0,415 |
| p(B) | 12,5% | 3 |
| p(C) | 12,5% | 3 |
Het optimale aantal bits ontstaat door de Entropie te berekenen. Hieruit volgt dat de totale informatiedichtheid van de voorbeeldtekst 8,49 bits is.
De onderstaande tabel toont de exacte subintervallen na het coderen van de losse tekens. De afbeelding hiernaast geeft dit grafisch weer.
| Interval | Interval grootte | ||
| 0 - | 1 | 1 | |
| A | 0 - | 0,75 | 0,75 |
| A | 0 - | 0,5625 | 0,5625 |
| A | 0 - | 0,421875 | 0,421875 |
| B | 0,31640625 - | 0,369140625 | 0,052734375 |
| A | 0,31640625 - | 0,35595703125 | 0,03955078125 |
| A | 0,31640625 - | 0,3460693359375 | 0,0296630859375 |
| A | 0,31640625 - | 0,338653564453125 | 0,022247314453125 |
| C | 0,335872650146484375 - | 0,338653564453125 | 0,002780914306640625 |
Nu wordt een willekeurige, maar zo kort mogelijk getal uit het laatste interval opgeslagen. Bijvoorbeeld 0,336.
Hiervoor zijn tussen 8 en 9 bits nodig om dit op te slaan. Bij het gebruik van Huffmancodering zou daarentegen 10 bits nodig zijn (1 bit voor elke A en 2 bits voor B en C).
In dit voorbeeld is de winst 10%. De winst wordt groter het daadwerkelijk voorkomen van een teken bij de Huffmancodering verder afwijkt van de optimale waarde. Dat gebeurt bijvoorbeeld als een teken extreem vaak voorkomt.
Het getal 0,336 kan ook weer gedecodeerd worden.
- Begonnen wordt met het startinterval [0; 1]. De decoder verdeelt dit in in de 3 delen zoals ook in de afbeelding zichtbaar is.
- 0,336 bevindt zich in het xubinterval A [0; 0,75]. Hieruit volgt dat het eerste teken A is.
- Het nieuwe subinterval wordt [0; 0,75]
- [0; 0,75] wordt wederom in nieuwe subintervallen verdeeld.
- 0,336 bevindt zich in het eerste interval [0; 0,5625]. Dus ook het volgende teken is een A.
- etc...
Uitvoering met gehele getallen
[bewerken | brontekst bewerken]Deze methode is vanuit het hardware-oogpunt de meest toepasbare.
Het principe van de encoder en decoder is gebaseerd op een interval dat verdeeld wordt in deelintervallen volgens de volgende eigenschappen:
- Het aantal deelintervallen is gelijk aan het aantal verschillende karakters die moeten gecodeerd worden.
- Per karakter is er een deelinterval waarvan de grootte evenredig is met het voordoen van dit karakter in aantal.
Bij het coderen van een karakter wordt het huidige interval verkleind tot een deelinterval dat overeenstemt met het deelinterval van dit karakter. Daarbij moeten de binnengrenzen van elk deelinterval opnieuw worden bepaald ten opzichte van de nieuwe onder- en bovengrenzen. De onder- en bovengrenzen van het nieuwe interval worden na elke iteratie bekeken.
Wanneer de meestbeduidende cijfers van de onder- en bovengrens gelijk zijn, kunnen deze niet meer veranderen door verdere opdeling. Bijgevolg geeft de decoder deze gegevens door, waarna de rest van de cijfers opgeschoven worden naar links (met invoeging van nullen op de vrijgekomen plaatsen). Het eerste cijfer van de onder- en bovengrens is dan gelijk en wordt doorgegeven naar de output.
Daarna worden alle grenzen van het interval opnieuw berekend, en zo het interval aangepast.