Data Compression Lec#4 PowerPoint 2018

Run-Length Encoding (RLE)
Is a simple and popular lossless data compression algorithm. The idea behind this approach to data compression is this: If a data item d occurs n consecutive times in the input stream, replace the n occurrences with the single pair nd. The n consecutive occurrences of a data item are called a run length of n, and this approach to data compression is called run-length encoding or RLE. We apply this idea first to text compression and then to image compression.

A) RLE Text Compression
Just replacing 2._all_is_too_well with 2._a2_is_t2_we2 will not work. Even the string 2._a2l_is_t2o_we2l does not solve this problem. One way to solve this problem is to precede each repetition with a special escape character. If we use the character @ as the escape character, then the string 2._a@2l_is_t@2o_we@2l can be decompressed unambiguously. However, this string is longer than the original string, because it replaces two consecutive letters with three characters. We have to adopt the convention that only three or more repetitions of the same character will be replaced with a repetition factor. The main problems with this method are the following:
1. In English text there are not many repetitions. There are many “doubles” but a “triple” is rare.
2. The character “@” may be part of the text in the input stream, in which case a different escape character must be chosen. Sometimes the input stream may contain every possible character in the alphabet. Figure 1.3a is a flowchart for such a simple run-length text compressor.
After reading the first character, the count is 1 and the character is saved. Subsequent characters are compared with the one already saved and, if they are identical to it, the repeat-count is incremented. When a different character is read, the operation depends on the value of the repeat count. If it is small, the saved character is written on the compressed file and the newly read character is saved. Otherwise, an “@” is written, followed by the repeat-count and the saved character.
Decompression is also straightforward. It is shown in Figure 1.3b. When an “@” is read, the repetition count n and the actual character are immediately read, and the character is written n times on the output stream.