CS13Data Compression: Huffman Coding and RLE

Data compression (AQA): “the process of reducing the storage space required for data by encoding the data using fewer bits than the original representation.”

• Compression is very common: photos, music, video, web pages and app downloads are usually compressed.
• Less storage space: more files fit on a phone, a drive or a cloud account.
• Less time to transmit: fewer bits to send, so a file downloads or uploads in less time, and streaming needs less bandwidth.
• Size limits: a compressed file may fit within an email attachment limit that the original is over.
• Less data used on a mobile contract, which can cost less.
• There are different ways to compress data. AQA names two: Huffman coding and run length encoding (RLE).

Data compression

The process of reducing the storage space required for data by encoding the data using fewer bits than the original representation.

With lossless compression, the original data can be rebuilt exactly, bit for bit.

• Huffman coding and RLE are both lossless.
• Lossless compression must be used for text, program files and other data where every bit matters: one changed bit could change a word or an instruction.
• For contrast, lossy compression permanently removes some data, such as detail people can't easily see or sounds they can't easily hear. It can make files much smaller, but the original can't be rebuilt. You don't need to know how lossy methods work.

Lossless compression

Compression where the original data can be restored exactly.

Huffman coding (AQA): “a lossless method of data compression. Huffman coding produces variable-length codes where the length of the code depends on the frequency with which a symbol appears in the original data.”

• In ASCII, every character uses 7 bits. In Huffman coding, frequent characters get short codes and rare ones get longer codes, so the total number of bits falls.
• The codes come from a Huffman tree. Characters are at the ends of the branches (the leaves). Frequent characters sit near the top, so their path is short.
• To read a character's code: start at the top (the root) and follow the branches down to the character, writing down the 0 or 1 on each branch.
• In this tree: O = 00, K = 01, E = 10, R = 110, B = 1110, P = 1111. E appears most (3 times) and has a 2-bit code; B and P appear once and have 4-bit codes.
• Trees can be drawn across the page or down it, and the branches may be labelled differently: always use the labels on the tree you are given.
• You need to read Huffman trees, not build them. (For interest: a tree is built by joining the two least frequent items again and again until one node is left.)

A Huffman tree for BOOKKEEPER. Each leaf shows a character and how often it appears; each circle shows the total below it.

Huffman coding

A lossless method of data compression that produces variable-length codes, where the length of the code depends on the frequency with which a symbol appears in the original data.

Huffman tree

A tree whose leaves are the characters; the path from the root to a character gives its code.

A Huffman-coded message is one long string of bits with no gaps. The tree tells you where each character ends.

• Start at the root. Read the bits one at a time, following the 0 or 1 branch.
• When you reach a character, write it down and go back to the root.
• Repeat until all the bits are used. If you end part-way down a branch, you've made a slip.
• No code is the start of another code, so there is only one way to split the bits.

For each character, multiply how often it appears by the length of its code. Add the results.

• Huffman bits = Σ (frequency × code length), for every different character.
• Make a table: character, frequency, code length, frequency × length. It keeps the working clear and earns method marks.
• Check: the frequencies should add up to the number of characters in the message.

To see how much Huffman coding saves, work out the size of the same text in ASCII.

• ASCII bits = number of characters × 7. Count every character, including spaces and repeated letters.
• Bits saved = ASCII bits − Huffman bits.
• Percentage saved = bits saved ÷ ASCII bits × 100.
• These calculations ignore the space needed to store the tree itself.

Run-length encoding (AQA): “a lossless method of data compression. Sequences of identical data values are replaced with a single data value and the count of its repetitions.”

• A run is a sequence of the same value one after another.
• Each run is stored as a frequency/data pair: how many times, then the value.
• AQA's example: 0000011100000011 becomes 5 0 3 1 6 0 2 1 (five 0s, three 1s, six 0s, two 1s).
• RLE works on text too: WWWWWWBBBWWWW becomes 6 W 3 B 4 W.
• To decode, write out each value the number of times shown. Check the total length is right.

The spec's own example: 16 pixels become four frequency/data pairs.

def runLengthEncode(row):
    result = ""
    count = 1
    for i in range(1, len(row)):
        if row[i] == row[i - 1]:
            count = count + 1
        else:
            result = result + str(count) + " " + row[i - 1] + " "
            count = 1
    result = result + str(count) + " " + row[len(row) - 1]
    return result

print(runLengthEncode("0000011100000011"))

Run-length encoding (RLE)

A lossless method of data compression in which sequences of identical data values are replaced with a single data value and the count of its repetitions.

Frequency/data pair

In RLE, the number of times a value repeats, followed by the value.

For a bitmap, RLE is usually done row by row: each row of pixels gets its own frequency/data pairs.

• For a black and white (1-bit) image, each pair is a run length and a colour (0 or 1).
• Write one line of pairs per row, starting from the left-hand pixel.
• Each row's run lengths must add up to the image's width: a quick check.
• In a real file, each pair is stored in a fixed number of bits, for example a 4-bit run length followed by a 1-bit colour. The question will tell you the format.
• The number of bits in the run-length field sets the longest run one pair can hold: 4 bits allow up to 15. A longer run has to be split over two pairs.

RLE only saves space when the data has long runs of the same value one after another.

• If runs are short, each single value becomes a pair (1 and the value), so the data can get bigger. ABCD becomes 1 A 1 B 1 C 1 D: twice as many items.
• Huffman coding doesn't need runs: it works on how often each character appears anywhere in the data, so it can still compress text with no repeats side by side.
• Both methods are lossless, so the choice depends only on how much each one saves for that data.