Komprimering innebär att man använder någon metod för att minska
storleken på en fil. Vi skiljer mellan förlustfri komprimering
(non-lossy compression)
där det går att dekomprimera för att få tillbaka filen i ursprungligt skick
och förstörande komprimering (lossy compression) där man tar
bort data. Att det går att komprimera utan att förstöra en fil beror på
att filer oftast har redundans, dvs de innehåller mer än nödvändigt.
Varför behövs komprimering?
Vi människor samlar gärna på data och har svårt att kasta
filer vilket leder till att minnet så småningom blir fullt.
Komprimerade filer tar mindre plats.
Webbsidor innehåller ofta mycket information (t ex bilder)
som tar tid att hämta.
Komprimerade filer går snabbare att föra över.
Följdlängdskodning - RLE
I följdlängdskodning, förkortat RLE (Run-Length-Encoding), utnyttjar
man att en följd av likadana tecken kan lagras med antal istället
för att skrivas ut.
ÅÅÅÅH! JAAAAAAA! AAAAAAAAAAAAH.
Vi ersätter följderna av Å och A med
antalet följt av det upprepade tecknet:
4ÅH! J7A! 12AH.
Men om grundtexten innehåller siffror blir det svårtolkat.
Därför väljer vi ett bryttecken, t ex §, som vi är
säkra på inte kommer att förekomma i texten.
§4ÅH! J§7A! §12AH.
Algoritmen blir enkel, men tyvärr inte så användbar för textkomprimering
eftersom de flesta texter inte innehåller längre följder av samma tecken.
Huffmankodning
Om vi vet hur vanliga olika tecken är i texten kan vi ställa upp en
tabell där vi för varje tecken kan ange sannolikheten för att ett
visst tecken ska dyka upp. I David A. Huffmans metod kodar man varje
tecken med ett binärt tal, där vanligare tecken får kortare koder.
Algoritmen som beräknar vilket tecken som ska få vilken binär kod
går ut på att man ritar upp ett binärt träd, där varje
tecken ses som ett löv. Sedan numrerar man trädets grenar med 0 och 1
och följer trädet från roten ut till varje löv för att se koderna.
Sortera tecknen som ska kodas i stigande sannolikhetsordning.
Rita grenar från de två tecken som har lägst sannolikhet och låtsas att
vi har ett nytt tecken med sannolikhet som är summan av deras sannolikheter.
Numrera ena grenen med 0 och andra med 1.
Upprepa punkt 2 tills alla tecken kommit med. Roten bör få sannolikhet 1.
Börja från roten och följ grenarna ut till ett löv.
Samla nollor och ettor på vägen - dessa ger koden för lövets tecken.
Vi illustrerar algoritmen med ett exempel.
En genomgång av skräcklitteraturen ger
en fördelning enligt följande tabell:
Huffmankod
Tecken
Sannolikhet
G
0.05
R
0.05
!
0.1
.
0.15
A
0.15
H
0.2
I
0.3
Texten
HAHA!IIIIIIH!AHRG...
skulle alltså kodas som (mellanrummen gör det tydligare men finns inte i koden)
Huffmankodning är en statistisk metod. Morsealfabetet tar
också hänsyn till statistiken med korta koder för vanliga bokstäver, men
Morse var mindre smart än Huffman och kräver mellanrum mellan tecknen.
Lempel-Ziv
Bokstaven e är i särklass vanligast i engelsk text,
men alla texter följer inte statistiken.
Här följer ett utdrag ur romanen Gadsby
av Ernest Vincent Wright (1872-1939).
IF YOUTH, THROUGHOUT all history, had had a champion to stand up
for it; to show a doubting world that a child can think; and, possibly, do it
practically; you wouldn't constantly run across folks today who claim that ''a
child don't know anything.'' A child's brain starts functioning at birth; and
has, amongst its many infant convolutions, thousands of dormant atoms, into
which God has put a mystic possibility for noticing an adult's act, and
figuring out its purport.
Jacob Ziv och Abraham Lempel har uppfunnit en förutsättningslös metod
som anpassar sig till indata. Principen är att man går igenom filen
och bygger en ordlista som används för kodningen. Lempel-Ziv finns
i ett otal olika varianter: LZ77, LZSS, LZFG, LZW, LZMW, LZAP, LZY, LZP, osv.
Så här fungerar LZW (en variant gjord av T. Welch):
Stoppa först in alla bokstäver och tecken i tabellen table
och läs in första tecknet från filen i strängen s.
table = range(500)
for i in range(256):
table[i] = chr(i)
i=255
s=""
for tkn in file("Gadsby").read():
if s+tkn in table:
s = s+tkn
else:
print table.index(s)
i+=1
table[i] = s+tkn
s = tkn
print table.index(s)
Man behöver inte skicka med tabellen eftersom den bygger upp sej själv under
avkodningen!
LZ-komprimering används i många komprimeringsprogram, t ex compress,
Zip, WinZip och GZip
(här i kombination med Huffmankodning). Det har förekommit flera
patentstrider. LZW patenterades för ca 20 år sedan och patentet för USA gick ut 20 juni 2003,
flera andra länder får vänta till 2004.
Komprimering av bilder
Bilder tar plats. Det är vanligt att varje bildpunkt (pixel)
i en färgbild representeras med ett 24-bitars binärt tal
(vilket ger oss åtta bitar för vardera rött, grönt resp blått).
Då tar en färgbild 100x100 pixlar 24000 bitar, dvs 24 kB
och en bild som täcker en 600x800-skärm tar 11.5 MB.
Metoderna ovan går att använda för att komprimera bilder.
Men här kan vi också använda förstörande komprimering
för att ta bort information som ögat ändå inte ser.
GIF 24 kB
JPEG 3 kB
JPEG 1.5 kB
Vilken redundans kan finnas i en bild? Vissa färger kanske är vanligare,
så att vi kan använda Huffmankodning för att få kortare koder för dessa.
I foton är närliggande pixlar ofta lika (blå himmel t ex), likaså
i streckteckningar och grafer (bara svarta och vita pixlar).
Där kan man använda RLE genom att räkna antal vita resp svarta pixlar i följd.
Även varianter av LZW kan användas - då innehåller tabellen
pixelinfo istället för strängar!
Vi kan också använda förstörande komprimering
för att ta bort information som ögat ändå inte ser.
GIF (Graphics Interchange Format) är ett filformat för bilder där
färgkodningen görs med 8 bitar, dvs man får 28=256 färger.
Sen används en variant av LZW för att komprimera. Den komprimeringen
är förlustfri och storleken minskas med ungefär faktorn 4.
JPEG (Joint Photographic Experts Group) är bättre för foton och andra
bilder där närliggande pixlar har liknande färger.
Färgbilder delas upp i en belysningsdel och en färgdel,
där färgdelen komprimeras med förstörande komprimering
eftersom ögat är mindre känsligt för färgförändringar.
Sen används en kombination av RLE och Huffmankodning för att
koda grupper av pixlar. Komprimeringsgraden är parameter till algoritmen,
så man kan bestämma själv hur hårt man vill komprimera.
Färgkodningen görs med 24 bitar, dvs 224 (nästan 17 miljoner) färger.
Komprimering av rörliga bilder
En videofil innehåller massor av bilder och dessutom ljud
så det är extra viktigt att kunna komprimera såna.
Dekomprimeringen måste gå snabbt om man direkt ska kunna
se filmen i realtid.
Det mest kända formatet för rörliga bilder är MPEG
(Moving Picture Experts Group). MPEG är egentligen en samling
standarder för kombinationer av ljud och video.
Komprimeringen av video-delen kan delas upp i
bildkomprimering
av varje enskild bildruta och tidskomprimering
där man utnyttjar likhet mellan på varandra följande bilder.
För bildkomprimeringen används i regel JPEG. För tidskomprimeringen
finns ett antal olika metoder:
Koda likheter (att en del av bilden ser likadan ut som i förra rutan).
Koda förskjutningar (att en del av bilden har förskjutits sen förra rutan).
Koda skillnaden mellan två bildrutor.
Koda förväntad rörelse.
Tidskomprimeringen kan göra det knepigare att redigera filmen.
Komprimering av ljud
Digital lagring av ljud innebär automatiskt en komprimering
eftersom vi samplar en analog ljudkurva i ett ändligt antal
punkter. Vidare komprimering av digitala ljudfiler kan göras
med RLE eller Huffmankodning. Däremot fungerar inte LZ-metoderna
särskilt bra, eftersom de bygger på att man hittar upprepningar.
Och även om t ex ett musikstycke upprepar sig är det osannolikt
att samma upprepningar skulle återfinnas i ljudfilen efter
samplingen.
När det gäller ljud kan man också använda förstörande metoder
Två exempel på sådana är tystnadskomprimering
där man ersätter mycket svaga ljud med tystnad och
companding där man minskar ordlängden för
varje ljudpunkt (t ex från 16 till 12 bitar).
MP3 (MPEG Audio Layer-3 encoding) använder en kombination av
tekniker där man utnyttjar en modell av den mänskliga hörseln
samt Huffmankodning.
Vill man gardera sig mot fel kan man lägga till redundans
(motsatsen till komprimering). Det finns många olika sätt att göra det på,
här följer några exempel:
Kontrollsiffra (t ex sista siffran i ett personnummer).
Skicka kopior av hela meddelandet, minst tre behövs om
man ska kunna korrigera.
Paritetsbitar, att man lägger till en etta eller nolla
till ett binärt tal för att göra det udda. Ett jämnt tal
innebär att nån bit är fel.
Hammingavstånd: Lägg till så många extrabitar till koden
så att varje enbitsfel ger ett kodord som skiljer sig i en
bit från det korrumperade kodordet, men i flera bitar från
alla övriga kodord. Exempel:
A
01011
Två kodord har Hammingavstånd d
om dom skiljer sig åt i d bitar.
En kod har Hammingavstånd d om alla kodord är
minst d ifrån varann.
Givet koderna till vänster - hur ska vi tolka meddelandet
10010 01110 10101
F
10010
I
01100
N
10101
Entropi
Hur mycket kan man komprimera utan att förlora information?
Om det var möjligt att komprimera hur mycket som helst skulle vi kunna
få ner varje fil till en bit, men det kan vi uppenbarligen inte.
Det finns alltså en undre gräns för hur kompakt man kan få en fil.
Om man känner till sannolikheten för varje tecken som ska kodas
(som i skräckexemplet ovan) kan man beräkna entropin
som ger en undre gräns för medellängden hos en kod.
Anta att vi har en teckenmängd
m1, m2,...,mn
(t ex alfabetet) och att sannolikheten för att tecknet
mi ska förekomma är P(mi).
Då är L(mi)=-log(P(mi)) minimilängden för en kod
för tecknet mi och
Lmedel = P(m1)*L(m1) + ... + P(mn)*L(mn)
medellängden för koderna (entropin).
Grafer
Internet består av noder av vilka en del är förbundna med varandra.
Det matematiska begreppet graf är en mängd V
vars element kallas noder eller hörn (eng. vertices) och en mängd
E vars element kallas kanter (eng. edges) och där varje
kant förbinder ett hörn med ett annat hörn.
Det är en mycket allmän struktur med massor av praktiska tillämpningar.
Ibland har kanterna vikter (oftast ickenegativa tal) och
ibland har kanterna riktning (ritas som pilar).
Vanliga grafegenskaper är sammanhängande och
acyklisk. En oriktad graf som både är sammanhängade
och acyklisk är ett träd. Varje sammanhängande graf har ett
spännande träd som man får genom att ta bort vissa kanter.
Kortaste vägen från en nod till en annan i en viktad graf kan man
bestämma med Dijkstras algoritm.
Betrakta startnoden som stamfar i ett
problemträd och låt grannoderna vara söner etc. Vi gör en bästaförstsökning
där godhetstalet är totalavståndet från startnoden. Då får vi ut noderna
i avståndsordning. Om en nod dyker upp en andra gång är det bara att kasta
den.
För billigaste spännande träd finns två likvärda algoritmer. Båda
börjar med den billigaste kanten - den måste vara med i trädet.
Kruskal fortsätter sedan med att lägga till den
näst billigaste kanten etc, dock tar man inte med en kant som skulle
ha bildat en cykel. Under uppbyggnaden är kantmängden osammanhängande,
men till slut har man fått fram det sökta trädet. Det är den snåla
rikspolitikerns algoritm.
Prim fortsätter i stället med att lägga till den
billigaste kant som tillsammans med dom kanter man redan valt ut
bildar ett träd. Det är kommunalpampens algoritm - i varje
steg når han ytterligare en ort.
