Compression

Compression

A level OCR Computer Science

Introduction

•Compression is the process of reducing the size of a data file whilst still retaining most, or even all, of the original information. You can compress most types of file, including documents, music files, video and image files.

•Data streaming services compress their files to reduce the amount of bandwidth needed to transfer files. If they used uncompressed files, the service would be very slow.

Why do we compress files? The main reasons are:

•Less storage space required for files

•Faster download and uploads

•Smaller file attachments for email

•Coping with slow links when streaming

Open Ended

What are the 4 reasons for compressing data?

Pattern Recognition

Compression depends on patterns being present in the information. This is true of text, image, video or music data. A pattern implies that some of the data is identical or very similar. For example, a text file that contains the same statement over and over again.

Compression

The original data file has 100 words in it. But the information (as opposed to the data) is really only the first sentence containing the ten words "All work and no play makes Jack a dull boy". This sentence is repeated 10 times.

A text compression algorithm would spot this pattern and create a file that effectively only contains the first 10 words plus some instructions about repeating it.

Therefore 100 words becomes 10 along with a few additional details. As a result, this has compressed the file by a factor of almost ten.

Compression ratios

The efficiency of compression is a simple formula.

Compression is also used by video and music streaming services to reduce the bit rate per second. The compression formula then becomes measured in bit rates.

Multiple Choice

Which is the correct formula for compression rate?

• original data / compressed data size

• compressed data size/original data size

• compressed data * original data size

• original data size * compressed data size

Lossy Compression

If file size is an issue, then it may be acceptable to discard some of the original information. That way, less data needs to be stored. This is called 'lossy compression'.

Lossy compression depends on patterns being present within the information. The algorithm looks at the data, tries to identify the patterns and decides how much it can throw away without noticeably affecting the quality of the data.

Lossy compression is irreversible. Once the data bytes are thrown away, they cannot be recovered. Lossy compression always involves loss of quality.

If you re-compress the same file more than once, more and more information will be lost. For example if a raw image was converted to a lossy jpeg file, that file should not be opened and re-compressed again as the degradation becomes noticable.

Lossy Compression - Music

An uncompressed 3-minute CD-quality stereo music file would need 31MB of storage. And yet a typical MP3 song is only 3MB, ten times smaller. This reduction in file size is possible due to lossy compression.

The uncompressed music recording includes data for frequencies that the human ear cannot hear. Those frequencies can be safely discarded without the listener ever noticing their absence. Also, people cannot hear a quiet sound the instant before or after a loud sound. So the data for the quiet sound can be discarded. This effect is called 'masking'.

MPEG level 3 (MP3) is a widely-used lossy algorithm for compressing music. It makes use of these effects and more. It can reduce CD music from 1.4Mbit/s down to 128 kbit/s with almost no degradation in audio quality - a compression ratio of better than 10.

Lossy compression - Images

A very popular lossy compression algorithm for reducing the size of an image file is the JPEG (Joint Photographic Expert Group) standard. This examines the image and works out the less critical parts it can throw away. For example it looks for edges of light and dark tones and discards some of the data there. The effect of this is a slight blurryness to the compressed file.

Image compression

Would you say that the 45% quality jpeg is much worse than the 100% quality one?

It is slightly more blurry, but probably not enough to matter in most circumstances.

But losing the information has resulted in the file size being reduced from 75Kb down to 13Kb. This means it would take up a lot less storage space on your device and also, if you were opening a webpage, it would render 5 times faster.

Lossy compression - video

Uncompressed video files can be huge and so they benefit from lossy compression algorithms being applied. This also applies to video streams to reduce the bit rate required.

A very popular lossy algorithm is the H.264 standard, otherwise known as MP4.

An uncompressed video has 24 frames per second. Each frame is a complete image made up of millions of pixels. This video data is compressed by using 'key frames'. These are single complete images taken every so often from the video source. Between the key-frames, only the data for the pixels that change is recorded. Eventually a fresh key frame is selected and then frames are varianced from that one.

Keyframes allow for a very high amount of compression if the image is mostly unchanging background with just a few pixels changing at a time. The compression is less effective if almost every pixel changes frame-to-frame.

Multiple Choice

What is a key feature of lossy compression?

• The removed data can be put back into the file

• Removed data is lost permanently

Multiple Choice

How does lossy compression work generally?

• It removes data at the beginning and the end that won't be noticed

• It looks for patterns and removes some repeating parts

• It removes data that is erroneous

Multiple Choice

What type of file can be compressed using masking?

• music

• images

• video

Multiple Choice

What compression ratio is possible with MP3?

• 2 times smaller

• 10 times smaller

• 100 times smnaller

• 1000 times smaller

Multiple Choice

What is the common name for the compression method H.264

• MP3

• JPG

• MP4

Multiple Choice

What is the common name for this compression method H.246

• MP3

• JPG

• MP4

Lossless Compression

What if you need to make a file smaller while keeping everything?

The answer is to use lossless compression.

Lossless compression reduces a file's size and yet retains all the data. It is less effective at reducing file sizes than lossy compression, but it is reversible unlike lossy compression.

Lossless compression is done by using patterns within the data which allows the algorithm to encode the data more efficiently than the raw data. There are two widely used algorithms, run length encoding and huffman encoding.

The following is an example of run length encoding:

Lossless File Formats

PNG is an example of a lossless image format

WAV and FLAC are lossless audio formats

There are very few lossless video formats - lossy compression is much more popular here as even with compression, lossless video files can be huge.

A very popular lossless compression format for storing any kind of file is .ZIP.

Variable length encoding

The method above uses fixed length codewords to represent longer sequences. A refinement of this is to use variable length codewords as well. The most frequent symbols are given very short codewords and the rarer ones use longer codewords. The Huffman algorithm as used in the very popular ZIP format makes use of variable length encoding.

Multiple Choice

What is a main feature of lossless compression?

• Data is permanently lost

• Data is not permanently lost

Multiple Choice

Which file type is an example of a lossless image file type?

• JPG

• GIF

• PNG