Computer Systems 2
05. File Compression
Outline
• The Problem
• The Solution
• Data Compression Strategies
• Lossy vs Lossless
• How Does It Work
The problem
• As computers became more • The problem is that these data
widespread, les started storing formats take up much more space
binary data that contained more than than simple text
text
• E.g. 1 minute of WAV encoded
• Images audio is approx. 10MB
• Audio • Even though storage is getting
bigger and cheaper, the amount of
data we are storing is also increasing
• Video
• There are issues surrounding
network transmission too - we want
to send less information over the
internet and therefore get it faster!
fi
The solution
• We want to reduce the size of
les/data without
compromising quality/integrity
• Essentially we want to
“compress” the data
• This is a non-trivial task!
• This involves encoding the data
using a compression algorithm
• And decoding it
(decompressing) it later
fi
Compression
How Do Zip Files Work (2017) - WASTETIME (6m 40s)
[Link]
Data Compression Strategies
• Data compression strategies t into two categories
• Lossless data compression algorithms exploit repeating patterns or statistical
redundancy so that the data can be compressed without losing any information.
• The data can be decompressed back into its original form
• Examples: HEIF images, FLAC audio. Lempel-Ziv (LZ).
• Lossy data compression involves the removal of non-essential information
• It cannot be regained when decompressed - the data is lost (this can be acceptable)
• Examples: JPG image. MP3 audio.
fi
Lossless vs Lossy
• There are advantages and
disadvantages to both
• Lossy algorithms are often
simpler to encode/decode and
can results in greatly reduced
le size
• Lossless algorithms guarantee
data integrity
• Example: Butter y Image of
Lossless vs Lossy PNG https://
[Link]/wiki/
File:Lossless_versus_Lossy.png
fi
fl
Lossy vs Lossless
• Example: Heaven by Niall
Horan (20 seconds)
• WAV (lossless) 3.6MB
• MP3 128kbps (lossy) 337KB
• MP3 32kbps (very lossy) 90KB
How Does It Work - Theory
• Each compression algorithm has its own method
• These are usually mathematically based
• Example. First Order Model statistical compression (for text encoding)
• Let m be the size of the alphabet and let pi be the probability of the i-th
letter in the alphabet.
• However, in order to use compression, we don’t need to fully understand the
mathematics of how the algorithm works
How Does It Work - Practise
• Here is a simple grammar-based • "ask" appears two times
redundancy encoding example:
• “what" appears two times
• "ask not what your country can do for
you -- ask what you can do for your
• "your" appears two times
country.”
• “country" appears two times
• The quote has 17 words, made up of 61
letters, 16 spaces, one dash and one
period. If each letter, space or punctuation • "can" appears two times
mark takes up one unit of memory, we get
a total le size of 79 units.
• "do" appears two times
• "for" appears two times
• "you" appears two times
fi
How Does It Work - Practise
• Using a variation of the LZ adaptive dictionary based algorithm, we can make
the following dictionary:
1 ask 5 can
2 what 6 do
3 your 7 for
4 country 8 you
• Our sentence now reads: "1 not 2 3 4 5 6 7 8 -- 1 2 8 5 6 7 3 4”
How Does It Work - Practise
• Our initial sentence took up 79 units
• Our new sentence takes up 37 units
• This saves over 50% space
• However, we must also save the dictionary, which also takes up 37 units
• So 37 + 37 = 74 units. There isn’t a huge saving in this instance.
• However, we are only dealing with one sentence. Imagine a whole book?
• This is a LOSSLESS algorithm - no data is irrevocably lost
How Does It Work - Exercise
Pease porridge hot,
Pease porridge cold, Pease porridge in the pot, Nine days old.
Some like it hot,
Some like it cold, Some like it in the pot, Nine days old.
• How could this be compressed using a LZ adaptive dictionary based
algorithm?
How Does It Work - Lossy Algorithms
• Lossy algorithm are often more complicated
• For example, MP3 employs psychoacoustics (the study of how human being perceive
sound) and is founded on 3 principals
• There are certain sounds that the human ear cannot hear.
• There are certain sounds that the human ear hears much better than others.
• If there are two sounds playing simultaneously, we hear the louder one but cannot
hear the softer one.
• This technique is called perceptual noise shaping
• 128kpbs MP3 reduces le size to around 10% of uncompressed WAV
fi
How Does It Work - Lossy Algorithms
• Digital imaging is made
possible through lossy
compression
• The loss of a certain
amount of data is
perfectly acceptable for
average users
• Image Source: http://
[Link].
com/wp-content/uploads/
sites/123/2013/09/
Raw_vs_jpeg_how_many_
shots_can_you_take_phot
ography_cheat_sheet2.jpg
Compression
Compression (2013) - Computerphile (7m 37s)
[Link]
Summary
• Data compression is an
algorithmic method of reducing
the volume required to store
particular data
• Strategies include lossless and
lossy techniques
• Lossless is preferable
• Lossy is acceptable in certain
cases
More Information
• Digital Compression (explained by Aloe Blacc) [Link]
v=By30SCp-Tsw
• HowStu Works - File Compression. [Link] [Link]/ le-
[Link]
• Benchmarked: What’s the Best File Compression Format? http://
[Link]/200698/benchmarked-whats-the-best- le-compression-
format/
• Understanding File Compression and Archives [Link]
tutorials/understanding- le-compression-and-archives/
• Introduction to Data Compression. Guy. E. Blelloch. 2013. Carnegie Mellon
University. [Link]
ff
fi
ff
fi
fi
Bibliography
• Blank, Steve (Google TechTalks), “The Secret History of • Bryson, B., 2003. “A Short History of Nearly Everything.”
Silicon Valley” - [Link] Doubleday
v=hFSPHfZQpIQ
• Dampier, W.C., 1929. “A history of science and its relations
• Bakhshi, Bahador, “Linux File System”. Amirkabir University with philosophy & religion.” Cambridge
of Technology. [Link]
• Forouzan, B. 2014, “Foundations of Computer Science (3nd
• Bigioi, Petronel. “File Management.” National University of Ed).” Cengage.
Ireland, Galway. [Link] /pbigioi/
• Hard, M. & Jamison A., 2005. “Hubris and hybrids : a cultural
• Columbia University, Hollerith 1890 Census Tabulator - http:// history of technology and science.” Oxford
[Link]/acis/history/[Link]
• Null, L. and Lobur, J. 2003. “The Essentials of Computer
• Doyle, Martin. “What is the Di erence Between Data and Organisation and Architecture”. Jones and Bartlett Computer
Information?” [Link] Science.
strategy/di erence-data-
information-0967136#JJLDE52p4gfDw3PU.99
• White M., 2001. “Rivals : con ict as the fuel of science.”
Secker & Warburg
• The History of Computing Project - [Link]
• Internet History of Science Sourcebook - http://
• The Computer Chronicles - [Link] [Link]/halsall/science/[Link]
ex/compsci/articles/[Link]
• Wikipedia, [Link]
• Bragg M., 1998. “On Giant’s Shoulders.” Sceptre
ff
fl
ff
ff