Data Compression Lc#4 2019

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