Datakompression
Från Rilpedia
Datakomprimering eller datakompression är när data omkodas på ett sätt som gör att färre informationsbärande enheter (oftast bitar) behöver användas. Det finns ett flertal fall då detta är önskvärt. Exempel inkluderar:
- Då man vill spara lagringsutrymme på disk.
- Då man snabbare vill överföra information via en länk som har begränsad bandbredd.
När datasekvenser komprimeras brukar man kalla det att sekvensen kodas (engelska encode). Att avkoda (engelska decode) är att översätta den kodade sekvensen till den ursprungliga datasekvensen. Data som komprimeras benämns ursprungssignal eller klartext. Kodad text sägs vara kodtext.
Det finns två huvudtyper av datakomprimering, ickedestruktiv komprimering och destruktiv komprimering (eller förstörande komprimering). Då en komprimering är ickedestruktiv går det alltid att utifrån den komprimerade datan återskapa den ursprungliga datan. Om man bara kan återställa något som approximerar den ursprungliga datan har man destruktiv komprimering.
Algoritmer för ickedestruktiv komprimering kodar om klartexten så att mängden statistiskt redundant data minskas. Någon informationsförlust sker dock inte. Destruktiva komprimeringsmetoder används då en viss informationsförlust är acceptabel – exempelvis för multimedia. Vanliga förstörande komprimeringsmetoder för ljud, film eller bild bygger på det faktum att människans sinnen inte är perfekta, varför man kan skala bort en del information (och därmed vid dekomprimering få en förvrängd variant av ursprungssignalen) utan att det märks särskilt mycket.
Innehåll |
Icke-destruktiv komprimering
Det finns ett flertal algoritmer för ickedestruktiv komprimering. I fullständiga komprimeringssystem används dessa ofta i kombination med varandra för att uppnå bättre resultat. Ibland utför man även transformationer på klartexten för att få indata till komprimeringen i en form som är smidigare att komprimera. Ickedestruktiva komprimeringsalgoritmer används också ofta som en del i destruktiva komprimeringsmetoder, för att komprimera ytterligare.
Data är lämpligt för icke-destruktiv komprimering om det har låg entropi. Försöker man komprimera högentropisk data, kommer det inte att lyckas. Komprimering resulterar i utmatning med högre entropi än inmatningen, och detta är anledningen till att det inte går att komprimera välkomprimerade data igen. Försök att göra så kommer att resultera i utmatning minst lika stor som inmatningen. Om en skapligt bra krypteringsalgoritm har använts på datat innan komprimering, kommer datat inte heller då att krympas.
Nedan följer en kort beskrivning av några vanliga metoder.
Ett enkelt exempel
Man kan enkelt uppnå en viss komprimeringsgrad av lämplig data utan att ta till särskilt avancerade metoder. Man kan till exempel göra det så enkelt för sig att man hittar på en komprimeringsalgoritm som går ut på att byta ut alla instanser av ordet "komprimering" i ovanstående stycket mot bokstaven Q. Eftersom bokstaven inte förekommer i stycket, finns det inga risker för missförstånd. Om vi har ett program för komprimering som byter ut ordet "komprimering" mot Q, och ett för dekomprimering som byter ut bokstaven Q mot ordet "komprimering"", har vi ett fullständigt komprimeringssystem – om än ganska primitivt. Liknande metoder kan dock vara användbara även i verkligheten, om datat man har är av förutsägbar natur. Eftersom metoder som denna är okomplicerade, kräver de inte särskilt mycket beräkningskraft. Avvägningar mellan komprimeringsgrad och beräkningskraft som behövs för komprimering är något som ibland är nödvändigt – varken beräkningskraft eller lagringskapacitet är obegränsade resurser.
Skurlängdskodning
En komprimeringsmetod som är vanlig, då man har data där samma tecken ofta uppträder flera gånger i följd, är skurlängdskodning (en.Run Length Encoding, RLE). En sekvens med upprepningar av samma tecken brukar kallas skurlängd (en. run-length). I skurlängdskodning utförs komprimeringen genom att finna skurlängder av tecken och ersätta dessa med koder i kortare längder för att uppnå komprimering. Ett vanligt sätt att bestämma sina koder, är att man bestämmer att ett visst tecken betyder "det här är en kod", sedan följs det tecknet av ett annat, som anger vilket tecken det handlar om. Sedan anges hur många gånger tecknet upprepas.
Antag att vi bestämmer att kodtecknet ska vara 3. Sedan vill vi skurlängdskoda följande data:
1 2 2 2 2 5 5 5 5 5 5 1 1 1
Kodningen ger då utmatning:
1 3 2 4 3 5 6 3 1 3
Utmatningen avkodas på följande vis:
- Tecknet 1, 1 i avkodningen.
- Tecknet 3, kodtecknet. Här börjar en upprepning...
- ...av tecknet 2...
- ...och det upprepas 4 gånger – avkodas alltså till 2222.
- o.s.v
Entropikodning
Redan Samuel Morse var entropikodning på spåren, när han skapade morsealfabetet för bruk vid telegrafering. Han gav de vanligast förekommande bokstäverna i engelsk text korta koder, och längre koder tilldelades mindre vanliga bokstäver. Morsekod består av kombinationer av långa och korta signaler, bokstaven e, som är allra vanligast förekommande i engelska, har kortast möjliga kod; en enda kort signal.
Entropikodning går ut på att man gör en statistisk analys av teckenfrekvensen i sin indata, och tilldelar de vanligast förekommande tecknen kortast koder. Teckenfrekvensen kan antingen vara förutbestämd, eller en del av komprimeringens utdata. Det förstnämnda kan vara lämpligt för data där de vanligast förekommande tecknen är ungefär de samma varje gång, exempelvis text. Det senare är lämpligt för mer generell komprimering som används till många olika typer av data – då frekvenserna varierar från gång till gång. Det finns även adaptiva metoder, som bygger upp och justerar frekvenstabellen under komprimering.
Det är mycket vanligt att komprimeringsverktyg, destruktiva som ickedestruktiva, avslutar med en entropikodning. MPEG, JPEG och MP3 är alla destruktiva komprimeringsmetoder som använder Huffmankodning i sista fasen.
Huffmankodning är den vanligaste entropikodningen. Det är matematiskt bevisat att denna metod är optimal – så länge man arbetar med begränsningen att varje symbol måste kodas med minst en hel bit. En metod som komprimerar aningen bättre är aritmetisk kodning. På grund av att den är patenterad av IBM används den mer sällan. Utmatningen från aritmetisk kodning är ett enda stort tal med inmatningstecknen inkodade, till skillnad från Huffmankodning som utmatar en särskild bitsymbol av variabel längd (vanligare tecken – kortare symbol) för varje inmatningstecken.
Lempel-Ziv
Jacob Ziv och Abraham Lempel presenterade i slutet av 1970-talet en algoritm för ickedestruktiv komprimering, som blivit en hel familj – LZ-familjen av komprimeringsalgoritmer. Många av de populäraste generella komprimeringsverktygen använder någon av de metoderna i kombination med entropikodning. Exempel: Zip.
Förenklat kan man säga att metoden söker efter datablock som upprepas flera gånger, och ersätter i kodtexten sådana block med en kod som refererar till första förekomsten av blocket.
En LZ-variant som heter LZW (för Lempel-Ziv-Welch) används bland annat vid komprimering av GIF-bilder. Detta orsakade kontrovers då Unisys trädde fram och förklarade att de hade patent på metoden.
Transformeringar
Vissa komprimeringsmetoder transformerar datat innan komprimering, för att göra det lämpligare för komprimering. Ett vanligt exempel på en sådan transformering är Burrows-Wheeler-transformeringen. Den går i korta drag ut på att sortera datat (på ett återställbart sätt) så att samma tecken ofta hamnar nära varandra. Datat blir då lämpligare för komprimering med något av ovan nämnda metoder. Ett välkänt program som använder BWT är bzip2, som ofta har bättre komprimering än exempelvis Zip.
Begränsningar
Distortionsfri datakompression begränsas av matematikens lagar. Claude Shannon bevisade att det är omöjligt att skapa en algoritm som kan krympa en godtycklig datamängd ens en enda bit, oavsett mängdens storlek. Alla distortionsfria algoritmer kommer därför att endast kunna komprimera data av en viss typ med vissa mönster. Försöker man använda dem på andra typer av data kommer datamängden obönhörligt att växa. Att skapa en generell distortionsfri kompressionsmetod har länge varit en slags datavetenskapens evighetsmaskin, i det att nya lycksökare gång på gång tror, eller låtsas för att lura investerare, att de kommit på något som alla andra missat. Se även extern länk Incredible Claims in data compression nedan.
Destruktiv komprimering
Destruktiv komprimering är högst beroende av vad det är som ska komprimeras. För att lyckas destruktivt komprimera någonting, måste man ha en uppfattning om vad som kan tänkas vara lämpligt att skala bort. Destruktiva komprimeringsmetoder brukar vara byggda efter en grov uppfattning om vilka aspekter av datat människans sinnen kan uppfatta. Därför är det exempelvis meningslöst att försöka komprimera musik med en komprimeringsmetod för bilder.
Dn hr txtn r fllt lslig
Texten ovan kan sägas vara destruktivt komprimerad. Man kan utläsa vad det står, trots att vissa bokstäver fallit bort.
Metoder
Det finns två huvudtyper av destruktiv datakompression:
- Transformerande kodare – Brukar fungera så att indata delas in i mindre segment, transformeras till en ny bas och kvantiseras. Det hela brukar avslutas med en entropikodning.
- Prediktiva kodare – Försöker gissa, baserat på föregående eller kommande data, nästa bildruta eller ljudsekvens som ska dyka upp. Felet mellan förutsägelsen och det verkliga värdet (samt övrig information som behövs för att approximera korrekt data) kvantiseras och lagras i kodtexten.
Exempel på format som använder förstörande komprimering
- JPEG (bilder)
- MP3 (ljud)
- MPEG (film)
- Ogg Vorbis (ljud)
Program för kompression
Kända komprimeringsprogram inkluderar WinZip, WinRAR och WinAce för Windows, StuffIt Expander för Macintosh samt gzip och bzip2 för Unix m.fl.
Se även
Externa länkar
- Datacompression.info - Mark Nelsons sidor om datakompression
- Datacompression.info/Links - länksamling till sidor om olika kompressionsformat
- Incredible Claims in data compression - en imponerande samling av misslyckade "revolutionerande" metoder för datakompression. Vissa företag har bränt upp stora kapital från investerare innan de havererat.
