Hier is een overzicht van veelgebruikte verliesvrije binaire compressiemethoden:

1. Redundantie en patronen identificeren:

* Herhaling: De eenvoudigste vorm. Als dezelfde byte of reeks bytes meerdere keren wordt herhaald, vervangt het algoritme deze door een markering die de herhaalde reeks en het aantal herhalingen aangeeft. Dit wordt vaak Run-Length Encoding (RLE) genoemd . Bijvoorbeeld:

* Origineel:`AAAAABBBCCCDD`

* RLE gecomprimeerd:`5A3B3C2D` (5 A's, 3 B's, 3 C's, 2 D's)

* RLE is het meest effectief als er lange runs van dezelfde gegevens zijn.

* Compressie op basis van woordenboeken: Deze methode bouwt een woordenboek (of tabel) op van vaak voorkomende reeksen bytes. In plaats van elke keer de volledige reeks op te slaan, slaat het algoritme de index (of code) die die reeks vertegenwoordigt op in het woordenboek.

* LZ77 en LZ78 (en hun varianten LZW, Deflate): Dit zijn op woordenboeken gebaseerde algoritmen. Ze werken door een glijdend venster van recentelijk bekeken gegevens te behouden.

* LZ77: Zoekt naar overeenkomende reeksen *binnen* het schuifvenster. Wanneer het een overeenkomst vindt, slaat het een `(afstand, lengte)`-paar op, waarbij:

* `afstand`:Hoe ver terug in het venster de wedstrijd begint.

* `lengte`:Hoe lang de overeenkomende reeks is.

* LZ78: Bouwt een woordenboek op van *nieuwe* zinnen zodra hij deze tegenkomt. Het codeert elke nieuwe zin als `(index, karakter)`, waarbij:

* `index`:De index van het *langste* voorvoegsel van de zin die al in het woordenboek staat.

* `teken`:het teken dat het voorvoegsel uitbreidt om de nieuwe zin te creëren.

* LZW (Lempel-Ziv-Welch): Een verbetering ten opzichte van LZ78. Het begint met een vooraf geïnitialiseerd woordenboek dat alle afzonderlijke tekens bevat. Het bouwt het woordenboek dynamisch op terwijl het de gegevens verwerkt. LZW staat erom bekend dat het wordt gebruikt in het GIF-beeldformaat (hoewel patenten op LZW een tijdje voor problemen zorgden).

* Leeglopen: Combineert LZ77 met Huffman-codering (hieronder uitgelegd) voor een nog betere compressie. Het wordt gebruikt in gzip, zlib en PNG. Het is heel gebruikelijk.

2. Statistische codering (entropiecodering):

* Deze methoden analyseren de frequentie van verschillende symbolen (bytes) in de gegevens en wijzen kortere codes toe aan frequentere symbolen en langere codes aan minder frequente symbolen. Dit is gebaseerd op de informatietheorie, waarbij meer waarschijnlijke gebeurtenissen minder informatie vereisen om te verzenden.

* Huffman-codering: Een coderingsschema met variabele lengte. Het bouwt een binaire boom op basis van de frequenties van de symbolen. De vaker voorkomende symbolen worden dichter bij de wortel van de boom geplaatst, wat resulteert in kortere codelengtes.

* Het algoritme genereert een voorvoegselcode, wat betekent dat geen enkele code een voorvoegsel is van een andere code, waardoor dubbelzinnigheid tijdens het decoderen wordt voorkomen.

* Rekenkundige codering: Vertegenwoordigt de gehele gegevensstroom als een enkel gebroken getal tussen 0 en 1. De lengte van de breuk wordt bepaald door de waarschijnlijkheid van de symbolen. Rekenkundige codering bereikt vaak een betere compressie dan Huffman-codering, vooral als het gaat om symbolen met zeer verschillende waarschijnlijkheden. Het is echter rekenintensiever.

Illustratief voorbeeld (vereenvoudigd):

Stel je voor dat we de volgende gegevens hebben:`AABBBCCCAADDDEEEFFFF`

1. RLE: Kan worden gecomprimeerd tot `2A3B3C2A3D3E4F` (vermindert dit, maar niet drastisch).

2. Huffman-codering:

* Frequentieanalyse:

* EEN:5

* B:3

* C:3

* D:3

* E:3

* F:4

* Huffman-boomconstructie (voorbeeld):

* Combineer minst frequent:B (3) en C (3) -> Knooppunt BC (6)

* Combineer D (3) en E (3) -> Knooppunt DE (6)

* Combineer BC (6) en DE (6) -> Knooppunt BCDE (12)

* Combineer F (4) en A (5) -> Knooppunt AF (9)

* Combineer AF (9) en BCDE (12) -> Root (21)

* Codes toewijzen (0 voor links, 1 voor rechts bij het doorkruisen van de boom) - *dit kan variëren op basis van de implementatie!*

* EEN:00

*B:100

* C:101

* D:110

* E:111

* V:01

* Gecomprimeerde gegevens:`000010010010010110110110111111110101010101` (veel korter dan het origineel, vooral voor grote datasets!)

Belangrijke overwegingen:

* Complexiteit: Verschillende algoritmen hebben verschillende rekencomplexiteiten. Sommige zijn sneller voor het coderen/decoderen, maar bereiken lagere compressieverhoudingen. Anderen zijn langzamer maar bereiken een hogere compressie.

* Compressieverhouding: De verhouding tussen de oorspronkelijke bestandsgrootte en de gecomprimeerde bestandsgrootte. Een hogere verhouding duidt op een betere compressie.

* Geheugengebruik: Algoritmen vereisen geheugen voor buffers, woordenboeken en boomstructuren. Geheugengebruik kan een beperkende factor zijn, vooral bij het comprimeren van grote bestanden.

* Gegevenstype: Sommige algoritmen zijn beter geschikt voor specifieke soorten gegevens (bijvoorbeeld tekst, afbeeldingen, audio). Algoritmen die ruimtelijke lokaliteit exploiteren, zijn bijvoorbeeld goed voor afbeeldingen.

Samengevat werken binaire compressie-algoritmen door:

1. De gegevens analyseren: Patronen, herhalingen en statistische frequenties identificeren.

2. De gegevens efficiënter weergeven: Gebruik kortere codes voor algemene elementen en langere codes voor zeldzame elementen.

3. Metagegevens opslaan: Het opslaan van informatie die nodig is om de gegevens te decomprimeren (bijvoorbeeld woordenboeken, Huffman-bomen).

De keuze van het algoritme hangt af van de specifieke vereisten van de toepassing, inclusief de gewenste compressieverhouding, de beschikbare rekenbronnen en het type gegevens dat wordt gecomprimeerd. Vaak worden hybride benaderingen (zoals Deflate) gebruikt om de sterke punten van verschillende technieken te combineren.