Binära kompressionsalgoritmer fungerar genom att identifiera och utnyttja mönster, uppsägningar och statistiska sannolikheter inom de binära data i en fil. De uppnår detta genom en mängd olika tekniker, i stort sett kategoriserade som förlustfri och förlustig komprimering. Vi kommer att fokusera på förlustfri komprimering, eftersom den används för att bevara den exakta originaldata.
Här är en uppdelning av vanliga förlustfria binära komprimeringsmetoder:
1. Identifiera redundans &mönster:
* Repetition: Den enklaste formen. Om samma byte eller sekvens av byte upprepar flera gånger, ersätter algoritmen dem med en markör som indikerar den upprepade sekvensen och antalet repetitioner. Detta kallas ofta run-Length Encoding (RLE) . Till exempel:
* ORIGINAL:`AAAAABBBCCCDD`
* RLE komprimerad:`5A3B3C2D` (5 A, 3 B, 3 C, 2 DS)
* RLE är mest effektiv när det finns långa körningar av samma data.
* ordbokbaserad komprimering: Denna metod bygger en ordbok (eller tabell) för ofta förekommande sekvenser av byte. Istället för att lagra hela sekvensen varje gång, lagrar algoritmen indexet (eller koden) som representerar den sekvensen i ordboken.
* LZ77 och LZ78 (och deras varianter lzw, deflate): Dessa är hörnstenens ordbokbaserade algoritmer. De fungerar genom att upprätthålla ett skjutfönster med nyligen sett data.
* lz77: Letar efter matchande sekvenser * inom * skjutfönstret. När den hittar en match lagrar den en `(avstånd, längd)` par, där:
* `Avstånd ':Hur långt tillbaka i fönstret startar matchen.
* `Längd ':Hur länge den matchande sekvensen är.
* lz78: Bygger en ordbok med * nya * fraser när det möter dem. Den kodar varje ny fras som `(index, karaktär)`, var:
* `Index ':Indexet för * längsta * prefixet för frasen som redan är i ordboken.
* 'Karaktär':Karaktären som utvidgar prefixet för att skapa den nya frasen.
* LZW (Lempel-Ziv-Welch): En förbättring av LZ78. Det börjar med en förinitialiserad ordbok som innehåller alla enstaka tecken. Den bygger ordboken dynamiskt när den bearbetar data. LZW är känd för att användas i GIF -bildformatet (även om patent på LZW orsakade problem ett tag).
* deflate: Kombinerar LZ77 med Huffman -kodning (förklaras nedan) för ännu bättre komprimering. Det används i Gzip, Zlib och PNG. Det är väldigt vanligt.
2. Statistisk kodning (entropikodning):
* Dessa metoder analyserar frekvensen för olika symboler (byte) i data och tilldelar kortare koder till mer frekventa symboler och längre koder till mindre frekventa. Detta är baserat på informationsteori, där mer troliga händelser kräver mindre information för att överföra.
* huffman kodning: Ett kodningsschema med variabel längd. Det bygger ett binärt träd baserat på symbolens frekvenser. De mer frekventa symbolerna placeras närmare trädets rot, vilket resulterar i kortare kodlängder.
* Algoritmen genererar ett prefixkod, vilket innebär att ingen kod är ett prefix av en annan kod, vilket förhindrar tvetydighet under avkodning.
* aritmetisk kodning: Representerar hela dataströmmen som ett enda fraktionsnummer mellan 0 och 1. Fraktionens längd bestäms av symbolens sannolikheter. Aritmetisk kodning uppnår ofta bättre komprimering än Huffman -kodning, särskilt när man hanterar symboler som har mycket olika sannolikheter. Det är dock mer beräkningsintensivt.
illustrativt exempel (förenklad):
Föreställ dig att vi har följande data:`aabbcccaadddeeeffff`
1. rle: Kan komprimera till `2A3B3C2A3D3E4F` (minskar det, men inte drastiskt).
2. huffman kodning:
* Frekvensanalys:
* A:5
* B:3
* C:3
* D:3
* E:3
* F:4
* Huffman Tree Construction (exempel):
* Kombinera minst ofta:B (3) och C (3) -> Nod BC (6)
* Kombinera d (3) och e (3) -> nod de (6)
* Kombinera BC (6) och DE (6) -> Nod BCDE (12)
* Kombinera F (4) och A (5) -> Node AF (9)
* Kombinera AF (9) och BCDE (12) -> rot (21)
* Tilldela koder (0 för vänster, 1 för höger korsning av trädet) - * Detta kan variera baserat på implementering! *
* A:00
* B:100
* C:101
* D:110
* E:111
* F:01
* Komprimerade data:`00001001001001011101101101111111110101010101` (mycket kortare än originalet, särskilt för stora datasätt!)
Nyckelöverväganden:
* Komplexitet: Olika algoritmer har olika beräkningskomplexiteter. Vissa är snabbare för kodning/avkodning men uppnår lägre kompressionsförhållanden. Andra är långsammare men uppnår högre komprimering.
* kompressionsförhållande: Förhållandet mellan den ursprungliga filstorleken och den komprimerade filstorleken. Ett högre förhållande indikerar bättre komprimering.
* Minnesanvändning: Algoritmer kräver minne för buffertar, ordböcker och trädstrukturer. Minnesanvändning kan vara en begränsande faktor, särskilt när du komprimerar stora filer.
* Datatyp: Vissa algoritmer är bättre lämpade för specifika typer av data (t.ex. text, bilder, ljud). Till exempel är algoritmer som utnyttjar rumslig lokalitet bra för bilder.
Sammanfattningsvis fungerar binära komprimeringsalgoritmer av:
1. Analysera uppgifterna: Identifiera mönster, repetitioner och statistiska frekvenser.
2. som representerar uppgifterna mer effektivt: Använda kortare koder för vanliga element och längre koder för sällsynta element.
3. lagring av metadata: Lagring av information som behövs för att dekomprimera uppgifterna (t.ex. ordböcker, Huffman -träd).
Valet av algoritm beror på de specifika kraven i applikationen, inklusive önskat kompressionsförhållande, tillgängliga beräkningsresurser och typen av data som komprimeras. Ofta används hybridmetoder (som deflat) för att kombinera styrkorna hos olika tekniker.
