Binnen de wereld van datacompressie zijn er eigenlijk maar twee soorten. Van deze 2 bestaan honderden variaties hoe dit is te implimenteren. Waarbij er dan nog weer een onderscheid te maken is in lossy of lossless compressies. Ik ga nu eerst allleen in op lossless.
De meest succesvolle compressie-algorithmes zijn de gene die aangeven wat de komende reeks aan data gaat zijn. Dit doen ze door gebruik te maken van instructies. Enkele voorbeelden hiervan zijn Run-Length encoding (RLE) of een offset length encoding variant. De ander soort van compressie maakt gebruik door te spelen met de bit diepte van de eenheid waarin een enkele waarde wordt opgeslagen. Een goed voorbeeld hiervan is de Huffmancodering.
Geen enkele compressie werkt zonder het feit dat er herhalende data voor komt in de dataset, al hoeft dit voor het oog niet direct zichtbaar te zijn.
Een heel goed voorbeeld van hehalende data is: AAAABBBBCDDDDDDEEEEEEEEEEEEE.
Data als deze is eenvoudig compacter op op te slaan met RLE.
Elk character is 1 byte groot dus deze 28 characters zijn 28 bytes groot. Een byte heeft een maximum waarde van 255. Dus je zou elke reeks vooraf kunnen laten gaan met 1 byte die aangeeft hoevaak de volgende byte moet worden herhaald.
Bijvoorbeeld: [4]A[4]B[1]C[6]D[13]E
Ondanks dat voor elk van deze reeksen een extra byte vereist is, worden er bytes bespaart. Zo is de data met de compressie maar 10 bytes ipv 28.
Hoewel offset length geen officiele benaming is voor een compressie is dit wel de duidelijkste benaming die aanheeft hoe het werkt. De werking lijkt op de RLE doordat er een instrutie vooraf gaat aan de waarde. De instructie is simpelweg een verwijzing naar al eerder ontcijferde data en dan aangeven hoelang deze reeks is. Dit wordt dan overgenomen in de ontcijferde weeks . Maar in het begin is er nog geen data dus naast deze 2 waardes moet er ook nog een indicator zijn die aangeeft of het gaat om een verwijzing of een reeks die gaat komen. Dit wordt vaak gedaan d.m.v een bitflag. In mijn voorbeeld zal ik deze aangeven of O (offset) en L (literal).
Voorbeeld data: AAAAAAAABBBBBBBAAAAAAABBBBBBBBBBBBBBBBBB
Met compressie: [L:8]AAAAAAAA[L:7]BBBBBBB[O:-14:7][O:-14:7][O:-7:7][O:-4:4]
Nu moet er in de instructie meer gegevens worden opgeslagen. Dat kost meer ruimte zo zou je voor deze instructies al 2 bytes nodig hebben 15 bytes + 6 instructies maakt 27 bytes ipv 40.
Dit is een redelijke compressie maar is nog niet wenselijk.
Is een compressie methode die werkt door variabel te zijn met de bit diepte. Zo kent het voorbeeld bij de offset-length encoding maar 2 soorten characters, dus waarom zou je hiervoor een hele byte voor gebruiken die voor 255 characters een onderscheid kan maken. Een bit diepte van 1 is in dit geval voldoende.
Daarmee krijg je 5 bytes met de volgende binaire inhoud
[00000000][11111110][00000011][11111111][11111111]
Helaas kent dit wel weer een nadeel, je hebt een woordenboek nodig om te weten dat de 0 een A is en de 1 een B. Een woordenboek met de eenvoudigste opslag voor dit voorbeeld vereist dat je 2 bytes + 3 bits nodig hebt. Afgerond een extra 3 bytes. Hiermee zou je op een totaal van 8 bytes komen. Dit lijkt veel beter dat de offset-length of de RLE. Maar bij echte data valt die tegen. Omdat het woordenboek dat groter is en er dan toch meer characters zijn. Daarom dat bij volledige algorithes zoals die voor een zip bestand dit een onderdel is maar niet de basis. Zo is deze heel goed te gebruiken ter ondersteuning van de offset-length encoding. Dit zorgt ervoor dat de instructies grotere offsetsets en lengtes kunnen gebruiken zonder hier hele grote instructies voor te moeten plaatsen in de data.