Multiple choiceQuestion 1 · Recall
Loading…
By the end you can explain how a text file can be compressed using dictionary-based compression and RLE, and why text is always compressed losslessly.
Change one letter and "I can now come" becomes "I can not come". Ouch.
So text is always compressed losslessly: the decompressed file must match the original, character for character.
RLE needs runs of identical characters, and normal writing barely has any (the "ss" in "mess" is about as good as it gets). RLE does help with text that has long runs, such as rows of spaces used to line up columns.
What ordinary text has lots of is repeated words and phrases: "the", "and", "compression"… That's what dictionary-based compression exploits.
Dictionary-based compression
A lossless method that stores the words (or patterns) that occur in a text once, in a dictionary, each with an index. Every occurrence in the text is replaced by its index. The dictionary is kept with the compressed file so the text can be rebuilt exactly.
Worked example: How much does it save?
Compress the 69-character tongue twister above. Assume each character takes 1 byte, each index takes 1 byte, the dictionary stores each word followed by a 1-byte end marker, and the decoder puts a space between words automatically.