GORKOFF 24 februari 2015 om 11:41 uur

Methoden voor gegevenscompressie

• Algoritmen

Mijn supervisor en ik bereiden een kleine monografie voor over beeldverwerking. Ik besloot om aan de Habra-gemeenschap een hoofdstuk te presenteren dat gewijd is aan algoritmen voor beeldcompressie. Omdat het moeilijk is om een ​​heel hoofdstuk in één bericht te passen, heb ik besloten het in drie berichten op te delen:
1. Methoden voor gegevenscompressie;
2. Lossless beeldcompressie;
3. Beeldcompressie met verlies.
Hieronder kun je het eerste bericht uit de serie lezen.

Momenteel zijn er een groot aantal verliesvrije compressie-algoritmen, die in twee grote groepen kunnen worden verdeeld:
1. Stream- en woordenboekalgoritmen. Deze groep omvat algoritmen uit de families RLE (run-length encoding), LZ*, etc.. Een kenmerk van alle algoritmen in deze groep is dat de codering geen informatie gebruikt over de frequenties van symbolen in het bericht, maar informatie over aangetroffen reeksen. eerder.
2. Algoritmen voor statistische (entropie) compressie. Deze groep algoritmen comprimeert informatie door gebruik te maken van de onregelmatige frequenties waarmee verschillende karakters in een bericht voorkomen. Algoritmen in deze groep omvatten rekenkundige en voorvoegselcoderingsalgoritmen (met behulp van Shannon-Fanno, Huffman, secansbomen).
Algoritmen voor het omzetten van informatie kunnen in een aparte groep worden ingedeeld. Algoritmen uit deze groep comprimeren informatie niet direct, maar het gebruik ervan vereenvoudigt de verdere compressie aanzienlijk met behulp van stroom-, woordenboek- en entropie-algoritmen.

Stream- en woordenboekalgoritmen

Runlengtecodering

Run-Length Encoding (RLE) is een van de eenvoudigste en meest gebruikte algoritmen voor datacompressie. In dit algoritme wordt een reeks herhaalde tekens vervangen door een teken en het aantal keren dat dit wordt herhaald.
De string “AAAAAA”, waarvoor 5 bytes moeten worden opgeslagen (ervan uitgaande dat er een byte is toegewezen voor het opslaan van één teken), kan bijvoorbeeld worden vervangen door “5A”, bestaande uit twee bytes. Het is duidelijk dat dit algoritme effectiever is naarmate de reeks herhalingen langer is.

Het grootste nadeel van dit algoritme is de extreem lage efficiëntie bij reeksen niet-herhalende karakters. Als we bijvoorbeeld de reeks “ABABAB” (6 bytes) beschouwen, zal deze na toepassing van het RLE-algoritme veranderen in “1A1B1A1B1A1B” (12 bytes). Er zijn verschillende methoden om het probleem van niet-herhalende karakters op te lossen.

De eenvoudigste methode is de volgende wijziging: de byte die het aantal herhalingen codeert, moet niet alleen informatie opslaan over het aantal herhalingen, maar ook over hun aanwezigheid. Als de eerste bit 1 is, geven de volgende 7 bits het aantal herhalingen van het overeenkomstige teken aan, en als de eerste bit 0 is, geven de volgende 7 bits het aantal tekens aan dat zonder herhaling moet worden genomen. Als we “ABABAB” coderen met deze wijziging, krijgen we “-6ABABAB” (7 bytes). Het is duidelijk dat de voorgestelde techniek de efficiëntie van het RLE-algoritme op niet-herhalende tekenreeksen aanzienlijk kan vergroten. De implementatie van de voorgestelde aanpak wordt weergegeven in Lijst 1:

1. type
2. functie RLEEncode(InMsg: ShortString): TRLEEncodedString;
3. MatchFl: boolean;
4. MatchCount: shortint;
5. EncodedString: TRLEEncodedString;
6. N, ik: byte;
7. beginnen
8. N:=0;
9. SetLength(EncodedString, 2 * lengte(InMsg) );
10. terwijl lengte (InMsg) >= 1 do
11. beginnen
12. MatchFl : = (lengte(InMsg) > 1 ) en (InMsg[ 1 ] = InMsg[ 2 ] );
13. MatchCount: = 1;
14. terwijl (MatchCount<= 126 ) and (MatchCount < length(InMsg) ) and ((InMsg[ MatchCount] = InMsg[ MatchCount + 1 ] ) = MatchFl) do
15. MatchCount: = MatchCount + 1;
16. als MatchFl dan
17. beginnen
18. N:=N+2;
19. EncodedString[ N - 2 ] : = MatchCount + 128 ;
20. EncodedString[ N - 1 ] : = ord (InMsg[ 1 ] );
21. anders
22. beginnen
23. als MatchCount<>lengte(InMsg) dan
24. MatchCount: = MatchCount - 1;
25. N: = N + 1 + MatchCount;
26. EncodedString[ N - 1 - MatchCount] : = - MatchCount + 128 ;
27. voor i: = 1 om MatchCount te doen
28. EncodedString[ N - 1 - MatchCount + i] : = ord (InMsg[ i] );
29. einde ;
30. verwijderen(InMsg, 1, MatchCount) ;
31. einde ;
32. SetLength(GecodeerdeString, N) ;
33. RLEEncode := GecodeerdeString;
34. einde ;

Het decoderen van een gecomprimeerd bericht is heel eenvoudig en komt neer op één enkele passage door het gecomprimeerde bericht, zie Lijst 2:

1. type
2. TRLEEncodedString = array van bytes;
3. functie RLEDecode(InMsg: TRLEEncodedString): ShortString;
4. HerhaalAantal: shortint ;
5. ik, j: woord ;
6. OutMsg: ShortString;
7. beginnen
8. OutMsg : = "" ;
9. ik := 0 ;
10. terwijl ik< length(InMsg) do
11. beginnen
12. RepeatCount: = InMsg[i] - 128;
13. ik : = ik + 1 ;
14. als RepeatCount< 0 then
15. beginnen
16. RepeatCount:= abs (RepeatCount);
17. voor j: = i tot i + RepeatCount - 1 do
18. UitMsg: = UitMsg + chr (InMsg[j] );
19. ik: = ik + HerhaalAantal;
20. anders
21. beginnen
22. voor j: = 1 tot RepeatCount doen
23. OutMsg: = OutMsg + chr (InMsg[i] );
24. ik : = ik + 1 ;
25. einde ;
26. einde ;
27. RLEDecode:= OutMsg;
28. einde ;

De tweede methode om de efficiëntie van het RLE-algoritme te vergroten is het gebruik van algoritmen voor informatietransformatie die de gegevens niet direct comprimeren, maar deze in een vorm brengen die handiger is voor compressie. Als voorbeeld van een dergelijk algoritme zullen we de BWT-permutatie beschouwen, genoemd naar de uitvinders van de Burrows-Wheeler-transformatie. Deze permutatie verandert de karakters zelf niet, maar verandert alleen hun volgorde in de string, terwijl herhaalde substrings na toepassing van de permutatie worden verzameld in dichte groepen, die veel beter worden gecomprimeerd met behulp van het RLE-algoritme. Directe BWT-conversie komt neer op de volgende stappen:
1. Aan de originele string een speciaal regeleindteken toevoegen dat nergens anders voorkomt;
2. Het verkrijgen van alle cyclische permutaties van de originele string;
3. Sorteren van de ontvangen strings in lexicografische volgorde;
4. Het retourneren van de laatste kolom van de resulterende matrix.
Een implementatie van dit algoritme wordt getoond in Listing 3.

1. const
2. EOMsg = "|" ;
3. functie BWTEncode(InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. Laatste teken: ANSIChar;
6. N, ik: woord ;
7. beginnen
8. InMsg: = InMsg + EOMsg;
9. N: = lengte(InMsg);
10. ShiftTabel[ 1]: = InMsg;
11. voor i : = 2 tot N doen
12. beginnen
13. LaatsteChar: = InMsg[N];
14. InMsg: = LaatsteChar + kopie(InMsg, 1, N - 1);
15. ShiftTabel[i] : = InMsg;
16. einde ;
17. Sorteren(ShiftTabel) ;
18. OutMsg : = "" ;
19. voor i : = 1 tot N doen
20. OutMsg: = OutMsg + ShiftTable[ i] [N] ;
21. BWTEncode:= OutMsg;
22. einde ;

De eenvoudigste manier om deze transformatie uit te leggen is met een specifiek voorbeeld. Laten we de tekenreeks “ANANAS” nemen en afspreken dat het einde van het tekenreeksteken het teken “|” is. Alle cyclische permutaties van deze reeks en het resultaat van hun lexicografische sortering worden gegeven in Tabel. 1.

Die. Het resultaat van een directe conversie is de string "|NNAAAC". Het is gemakkelijk in te zien dat deze string door het RLE-algoritme veel beter wordt gecomprimeerd dan de originele, omdat het bevat lange reeksen herhaalde letters.
Een soortgelijk effect kan worden bereikt met andere transformaties, maar het voordeel van de BWT-transformatie is dat deze omkeerbaar is, hoewel de omgekeerde transformatie ingewikkelder is dan de directe. Om de originele string te herstellen, moet u de volgende stappen uitvoeren:
Maak een lege matrix met de grootte n*n, waarbij n het aantal tekens in het gecodeerde bericht is;
Vul de meest rechtse lege kolom met het gecodeerde bericht;
Sorteer tabelrijen in lexicografische volgorde;
Herhaal stap 2-3 zolang er lege kolommen zijn;
Retourneert de tekenreeks die eindigt met het teken voor het einde van de regel.

Het implementeren van de omgekeerde conversie is op het eerste gezicht niet moeilijk en een van de implementatieopties wordt weergegeven in Lijst 4.

1. const
2. EOMsg = "|" ;
3. functie BWTDecode(InMsg: ShortString): ShortString;
4. OutMsg: ShortString;
5. ShiftTable: array van ShortString;
6. N, i, j: woord ;
7. beginnen
8. OutMsg : = "" ;
9. N: = lengte(InMsg);
10. SetLengte(ShiftTabel, N + 1 ) ;
11. voor i : = 0 tot N doen
12. ShiftTabel[ i] : = "" ;
13. voor i : = 1 tot N doen
14. beginnen
15. voor j := 1 tot N doen
16. ShiftTabel[j] : = InMsg[j] + ShiftTabel[j] ;
17. Sorteren(ShiftTabel) ;
18. einde ;
19. voor i : = 1 tot N doen
20. als ShiftTable[ i] [N] = EOMsg dan
21. OutMsg : = ShiftTabel[ i] ;
22. verwijderen(OutMsg, N, 1 );
23. BWTDecode:= OutMsg;
24. einde ;

Maar in de praktijk hangt de efficiëntie af van het gekozen sorteeralgoritme. Triviale algoritmen met kwadratische complexiteit zullen uiteraard een zeer negatieve invloed hebben op de prestaties, dus het wordt aanbevolen om efficiënte algoritmen te gebruiken.

Na het sorteren van de tabel die u in de zevende stap hebt verkregen, moet u een rij uit de tabel selecteren die eindigt met het teken “|”. Het is gemakkelijk in te zien dat dit de enige regel is. Dat. We hebben de BWT-transformatie bekeken aan de hand van een specifiek voorbeeld.

Samenvattend kunnen we zeggen dat het belangrijkste voordeel van de RLE-groep van algoritmen de eenvoud en snelheid van werken is (inclusief decoderingssnelheid), en het belangrijkste nadeel is inefficiëntie bij niet-herhalende tekensets. Het gebruik van speciale permutaties verhoogt de efficiëntie van het algoritme, maar verlengt ook de looptijd (vooral decodering) aanzienlijk.

Woordenboekcompressie (LZ-algoritmen)

De groep woordenboekalgoritmen codeert, in tegenstelling tot de algoritmen van de RLE-groep, niet het aantal herhalingen van tekens, maar eerder aangetroffen reeksen tekens. Terwijl de betreffende algoritmen actief zijn, wordt er dynamisch een tabel gemaakt met een lijst van reeds aangetroffen reeksen en hun bijbehorende codes. Deze tabel wordt vaak een woordenboek genoemd, en de overeenkomstige groep algoritmen wordt woordenboek genoemd.

De eenvoudigste versie van het woordenboekalgoritme wordt hieronder beschreven:
Initialiseer het woordenboek waarbij alle tekens in de invoerreeks verschijnen;
Zoek in het woordenboek de langste reeks (S) die overeenkomt met het begin van het gecodeerde bericht;
Druk de code van de gevonden reeks af en verwijder deze uit het begin van het gecodeerde bericht;
Als het einde van het bericht nog niet is bereikt, lees dan het volgende teken en voeg Sc toe aan het woordenboek. Ga naar stap 2. Sluit anders af.

Het nieuw geïnitialiseerde woordenboek voor de zinsnede “CUCKOOKOOKUSHONKOOKUPILAKAHOOD” wordt bijvoorbeeld weergegeven in de tabel. 3:

Tijdens het compressieproces wordt het woordenboek aangevuld met reeksen uit het bericht. Het proces voor het bijwerken van het woordenboek wordt gegeven in Tabel. 4.

Bij de beschrijving van het algoritme is bewust afgezien van een beschrijving van de situatie wanneer het woordenboek volledig gevuld is. Afhankelijk van de variant van het algoritme is ander gedrag mogelijk: het volledig of gedeeltelijk leegmaken van het woordenboek, het stoppen met het vullen van het woordenboek of het uitbreiden van het woordenboek met een overeenkomstige toename van de codecapaciteit. Elk van deze benaderingen heeft bepaalde nadelen. Het stoppen van het aanvullen van het woordenboek kan bijvoorbeeld leiden tot een situatie waarin het woordenboek reeksen opslaat die aan het begin van de gecomprimeerde reeks voorkomen, maar daarna niet meer voorkomen. Tegelijkertijd kan het opschonen van het woordenboek leiden tot het verwijderen van veel voorkomende reeksen. De meeste van de gebruikte implementaties beginnen bij het vullen van het woordenboek het compressieniveau te controleren, en wanneer dit onder een bepaald niveau daalt, wordt het woordenboek opnieuw opgebouwd. Vervolgens zullen we de eenvoudigste implementatie bekijken die stopt met het bijwerken van het woordenboek wanneer het vol is.

Laten we eerst een woordenboek definiëren als een record waarin niet alleen de aangetroffen subtekenreeksen worden opgeslagen, maar ook het aantal subtekenreeksen dat in het woordenboek is opgeslagen:

Eerder aangetroffen subreeksen worden opgeslagen in de Words-array en hun code is de subreeksnummers in deze array.
We zullen ook de functies definiëren van zoeken in het woordenboek en toevoegen aan het woordenboek:

1. const
2. MAX_DICT_LENGTH = 256;
3. functie FindInDict(D: TDictionary; str: ShortString) : geheel getal ;
4. r:geheel getal;
5. ik:geheel getal;
6. fl:booleaans ;
7. beginnen
8. r: = - 1;
9. als D. WordCount > 0 dan
10. beginnen
11. ik := D. WordCount;
12. fl := onwaar ;
13. terwijl (niet fl) en (i >= 0 ) dat wel doen
14. beginnen
15. ik : = ik - 1 ;
16. fl : = D. Woorden [ i] = str;
17. einde ;
18. einde ;
19. als fl dan
20. r := ik;
21. VindInDict := r;
22. einde ;
23. procedure AddToDict(var D: TDictionary; str: ShortString) ;
24. beginnen
25. als D. WordCount< MAX_DICT_LENGTH then
26. beginnen
27. D. Woordentelling : = D. Woordentelling + 1 ;
28. SetLength(D. Woorden, D. WordCount) ;
29. D. Woorden [ D. WordCount - 1 ] : = str;
30. einde ;
31. einde ;

Met behulp van deze functies kan het coderingsproces volgens het beschreven algoritme als volgt worden geïmplementeerd:

1. functie LZWEncode(InMsg: ShortString): TEncodedString;
2. OutMsg: TEncodedString;
3. tmpstr: ShortString;
4. D: TWoordenboek;
5. ik, N: byte;
6. beginnen
7. SetLength(OutMsg, lengte(InMsg) ) ;
8. N:=0;
9. InitDict(D) ;
10. terwijl lengte (InMsg) > 0 wel
11. beginnen
12. tmpstr: = InMsg[1];
13. terwijl (FindInDict(D, tmpstr) >= 0 ) en (length(InMsg) > lengte(tmpstr) doen
14. tmpstr: = tmpstr + InMsg[lengte(tmpstr) + 1] ;
15. if FindInDict(D, tmpstr)< 0 then
16. verwijder(tmpstr, lengte(tmpstr) , 1 );
17. OutMsg[N] : = FindInDict(D, tmpstr) ;
18. N:=N+1;
19. delete(InMsg, 1, lengte(tmpstr) ) ;
20. als lengte (InMsg) > 0 dan
21. AddToDict(D, tmpstr + InMsg[1] );
22. einde ;
23. SetLengte(OutMsg, N) ;
24. LZWEncode:= OutMsg;
25. einde ;

Het resultaat van de codering is het aantal woorden in het woordenboek.
Het decoderingsproces wordt beperkt tot het direct decoderen van codes, en het is niet nodig om het gemaakte woordenboek over te dragen; het is voldoende dat tijdens het decoderen het woordenboek op dezelfde manier wordt geïnitialiseerd als tijdens het coderen. Vervolgens wordt het woordenboek direct tijdens het decoderingsproces volledig hersteld door de vorige deelreeks en het huidige symbool aan elkaar te koppelen.

Het enige probleem is mogelijk in de volgende situatie: wanneer het nodig is een deelreeks te decoderen die nog niet in het woordenboek staat. Het is gemakkelijk in te zien dat dit alleen mogelijk is in het geval dat het nodig is om een ​​subtekenreeks te extraheren die bij de huidige stap moet worden toegevoegd. Dit betekent dat de substring voldoet aan het cSc-patroon, d.w.z. begint en eindigt met hetzelfde teken. In dit geval is cS de subtekenreeks die in de vorige stap is toegevoegd. De beschouwde situatie is de enige waarin het nodig is een regel te decoderen die nog niet is toegevoegd. Gezien het bovenstaande kunnen we de volgende optie voorstellen voor het decoderen van een gecomprimeerde string:

1. functie LZWDecode(InMsg: TEncodedString): ShortString;
2. D: TWoordenboek;
3. OutMsg, tmpstr: ShortString;
4. ik: byte;
5. beginnen
6. OutMsg : = "" ;
7. tmpstr: = "";
8. InitDict(D) ;
9. voor i: = 0 tot lengte(InMsg) - 1 do
10. beginnen
11. als InMsg[ i] >= D. WordCount dan
12. tmpstr: = D. Woorden [ InMsg[ i - 1 ] ] + D. Woorden [ InMsg [ i - 1 ] ] [ 1 ]
13. anders
14. tmpstr: = D. Woorden [InMsg[i]];
15. UitMsg: = UitMsg + tmpstr;
16. als ik > 0 dan
17. AddToDict(D, D. Woorden [ InMsg[ i - 1 ] ] + tmpstr[ 1 ] ) ;
18. einde ;
19. LZWDecode:= OutMsg;
20. einde ;

De voordelen van woordenboekalgoritmen zijn onder meer hun grotere compressie-efficiëntie vergeleken met RLE. Het moet echter duidelijk zijn dat het daadwerkelijke gebruik van deze algoritmen enkele implementatieproblemen met zich meebrengt.

Entropie codering

Codering met behulp van Shannon-Fano-bomen

Het Shannon-Fano-algoritme is een van de eerste compressie-algoritmen die zijn ontwikkeld. Het algoritme is gebaseerd op het idee om vaker voorkomende karakters weer te geven met behulp van kortere codes. Bovendien hebben codes verkregen met behulp van het Shannon-Fano-algoritme de eigenschap van prefixiteit: dat wil zeggen geen enkele code is het begin van een andere code. De eigenschap prefix zorgt ervoor dat de codering één-op-één is. Het algoritme voor het construeren van Shannon-Fano-codes wordt hieronder weergegeven:
1. Verdeel het alfabet in twee delen, waarbij de totale kansen van de symbolen zo dicht mogelijk bij elkaar liggen.
2. Voeg 0 toe aan de prefixcode van het eerste deel van de karakters, voeg 1 toe aan de prefixcode van het tweede deel van de karakters.
3. Voer voor elk deel (dat minimaal twee tekens bevat) de stappen 1-3 recursief uit.
Ondanks zijn relatieve eenvoud is het Shannon-Fano-algoritme niet zonder nadelen, waarvan de niet-optimale codering de belangrijkste is. Hoewel de partitie bij elke stap optimaal is, garandeert het algoritme als geheel geen optimaal resultaat. Beschouw bijvoorbeeld de volgende tekenreeks: "AAABVGDEJ". De overeenkomstige Shannon-Fano-boom en de op basis daarvan verkregen codes worden weergegeven in Fig. 1:

Zonder codering te gebruiken, zal het bericht 40 bits in beslag nemen (op voorwaarde dat elk teken met 4 bits is gecodeerd), en met behulp van het Shannon-Fano-algoritme 4*2+2+4+4+3+3+3=27 bits. Het berichtenvolume daalde met 32,5%, maar hieronder laten we zien dat dit resultaat aanzienlijk verbeterd kan worden.

Coderen met Huffman Trees

Het Huffman-coderingsalgoritme, dat enkele jaren na het Shannon-Fano-algoritme is ontwikkeld, heeft ook de eigenschap van voorvoegsel en bovendien een bewezen minimale redundantie, wat de extreem brede verspreiding ervan bepaalt. Gebruik het volgende algoritme om Huffman-codes te verkrijgen:
1. Alle tekens van het alfabet worden weergegeven als vrije knooppunten, en het gewicht van het knooppunt is evenredig met de frequentie van het teken in het bericht;
2. Uit de set vrije knooppunten worden twee knooppunten met minimaal gewicht geselecteerd en wordt een nieuw (bovenliggend) knooppunt gemaakt met een gewicht gelijk aan de som van de gewichten van de geselecteerde knooppunten;
3. De geselecteerde knooppunten worden uit de vrije lijst verwijderd en het bovenliggende knooppunt dat op basis daarvan is gemaakt, wordt aan deze lijst toegevoegd;
4. Stappen 2-3 worden herhaald totdat er meer dan één knooppunt in de vrije lijst staat;
5. Op basis van de geconstrueerde boom wordt aan elk teken van het alfabet een voorvoegselcode toegewezen;
6. Het bericht wordt gecodeerd met de ontvangen codes.

Laten we hetzelfde voorbeeld bekijken als in het geval van het Shannon-Fano-algoritme. De Huffman-boom en codes verkregen voor het bericht “AAAABVGDEJ” worden weergegeven in Fig. 2:

Het is eenvoudig te berekenen dat het volume van het gecodeerde bericht 26 bits zal zijn, wat minder is dan in het Shannon-Fano-algoritme. Los daarvan is het vermeldenswaard dat er vanwege de populariteit van het Huffman-algoritme momenteel veel opties zijn voor Huffman-codering, inclusief adaptieve codering, waarvoor geen overdracht van symboolfrequenties vereist is.
Tot de nadelen van het Huffman-algoritme behoren voor een aanzienlijk deel problemen die verband houden met de complexiteit van de implementatie. Het gebruik van symbolen van reële variabelen om frequenties op te slaan gaat gepaard met een verlies aan precisie, dus in de praktijk worden vaak integer-variabelen gebruikt, maar aangezien Het gewicht van de ouderknooppunten groeit voortdurend, vroeg of laat treedt er een overflow op. Ondanks de eenvoud van het algoritme kan de correcte implementatie ervan dus nog steeds enkele problemen veroorzaken, vooral bij grote alfabetten.

Codering met secansfunctiebomen

Codering met behulp van secansfuncties is een door de auteurs ontwikkeld algoritme waarmee u prefixcodes kunt verkrijgen. Het algoritme is gebaseerd op het idee om een ​​boom te construeren, waarvan elk knooppunt een secansfunctie bevat. Om het algoritme in meer detail te beschrijven, is het noodzakelijk om verschillende definities te introduceren.
Een woord is een geordende reeks van m bits (het aantal m wordt de woordcapaciteit genoemd).
Een letterlijke secans is een paar in de vorm van een cijfer-cijferwaarde. De letterlijke (4,1) betekent bijvoorbeeld dat bit 4 van het woord 1 moet zijn. Als aan de voorwaarde van de letterlijke waarde is voldaan, wordt de letterlijke als waar beschouwd, anders is deze onwaar.
Een k-bit secans is een reeks k letterlijke waarden. Als alle letterlijke waarden waar zijn, dan is de secansfunctie zelf waar, anders is deze onwaar.

De boom is zo geconstrueerd dat elk knooppunt het alfabet in zo dicht mogelijke delen verdeelt. In afb. Figuur 3 toont een voorbeeld van een secansboom:

Een boom van secansfuncties garandeert in het algemeen geen optimale codering, maar biedt extreem hoge snelheid vanwege de eenvoud van bewerkingen in knooppunten.

Rekenkundige codering

Rekenkundige codering is een van de meest effectieve manieren om informatie te comprimeren. In tegenstelling tot het Huffman-algoritme maakt rekenkundige codering het mogelijk berichten te coderen met een entropie van minder dan 1 bit per teken. Omdat De meeste rekenkundige coderingsalgoritmen zijn beschermd door patenten; de basisideeën zullen hieronder worden beschreven.
Laten we aannemen dat het gebruikte alfabet N symbolen a_1,…,a_N bevat, met respectievelijk de frequenties p_1,…,p_N. Het rekenkundige coderingsalgoritme ziet er dan als volgt uit:
Neem ) als een werkhalfinterval)