0% found this document useful (0 votes)

12 views28 pages

Run-Length Encoding Overview

The document provides an overview of Run Length Encoding (RLE) as a data compression technique, detailing its principles, advantages, and limitations. It includes course outcomes related to data compression methods, performance metrics, and variants such as digram encoding and pattern substitution. Additionally, it presents exercises for understanding RLE and references for further reading.

Uploaded by

jamiemathew1303

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

0% found this document useful (0 votes)

12 views28 pages

Run-Length Encoding Overview

Uploaded by

jamiemathew1303

We take content rights seriously. If you suspect this is your content, claim it here.

Available Formats

Download as PDF, TXT or read online on Scribd

Run length encoding

Neena Raj N. R.

Department of Computer Science and Engineering

Mar Baselios College of Engineering and Technology, Nalanchira

January 2024
Syllabus

Module 2
Run length encoding, RLE Text compression, Statistical methods-Prefix
Codes, Binary Huffman coding, Illustration of Binary Huffman coding, Non-binary
Huffman Algorithms, Arithmetic Coding algorithm, Illustration of Arithmetic
Coding algorithm,

Neena Raj N. R. CS1U43D DCT January 2024 2 / 27

Course Outcomes

Course Outcomes
CO1 Describe the fundamental principles of data Understand
compression.
CO2 Apply
Make use of statistical and dictionary based
compression techniques for various applications
CO3 Illustrate various image compression standards. Apply
CO4 Summarize video compression mechanisms to re- Understand
duce the redundancy in video.
CO5 Use the fundamental properties of digital audio Understand
to compress audio data.

Neena Raj N. R. CS1U43D DCT January 2024 3 / 27

Run length encoding

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.
For example, consider a screen containing plain black text on a solid
white background. There will be many long runs of white pixels in the
blank space and many short runs of black pixels within the text.
WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWW
WWBWWWWWWWWWWWWWW

Neena Raj N. R. CS1U43D DCT January 2024 4 / 27

Run length encoding

With a run–length encoding (RLE) data compression algorithm

applied to the above hypothetical scan line, it can be rendered as
12W1B12W3B24W1B14W. This can be interpreted as a sequence of
twelve W’s, one B, twelve W’s, three B’s, etc.

Neena Raj N. R. CS1U43D DCT January 2024 5 / 27

Run length encoding

Advantages
Since there is no loss in this type of data compression, the original
data can be fully retrieved upon decompression.
The algorithm’s flexibility in both the encoding (compression) and
decoding (decompression) processes is one of its most appealing
qualities.

Neena Raj N. R. CS1U43D DCT January 2024 6 / 27

RLE Text Compression

Demerit : It replaces two consecutive characters with three characters

Neena Raj N. R. CS1U43D DCT January 2024 7 / 27

RLE Text Compression

Fig. RLE. Part I: Compression.

Neena Raj N. R. CS1U43D DCT January 2024 8 / 27

RLE Text Compression

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.

Neena Raj N. R. CS1U43D DCT January 2024 9 / 27

RLE Text Compression

Fig. RLE. Part II: Decompression.

Neena Raj N. R. CS1U43D DCT January 2024 10 / 27

RLE Text Compression

Decompression is also straightforward.

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.

Neena Raj N. R. CS1U43D DCT January 2024 11 / 27

RLE Text Compression

The main problems with this method are the following:

In plain English text there are not many repetitions.
There are many “doubles” but a “triple” is rare.
The most repetitive character is the space.
Dashes or asterisks may also repeat sometimes.
In mathematical texts, some digits may repeat.
Example. The abbott from Abruzzi accedes to the demands of all
abbesses from Narra- gansett and Abbevilles from Abyssinia. He will
accommodate them, abbreviate his sabbatical, and be an
accomplished accessory.

Neena Raj N. R. CS1U43D DCT January 2024 12 / 27

RLE Text Compression

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.
An example is an object file, the result of compiling a program. Such
a file contains machine instructions and can be thought of as a string
of bytes that can have any values.

Neena Raj N. R. CS1U43D DCT January 2024 13 / 27

RLE Text Compression

Since the repetition count is written on the output stream as a byte,

it is limited to counts of up to 255.
This limitation can be softened somewhat when we realize that the
existence of a repetition count means that there is a repetition (at
least three identical consecutive characters).
We may adopt the convention that a repeat count of 0 means three
repeat characters.
This implies that a repeat count of 255 means a run of 258 identical
characters.

Neena Raj N. R. CS1U43D DCT January 2024 14 / 27

RLE Text Compression Performance

Performance

Assume a string of N characters that needs to be compressed.

Assume that the string contains M repetitions of average length L
each.
Each of the M repetitions is replaced by 3 characters (escape, count,
and data).
Size of the compressed string is N − M × L + M × 3 = N − M(L − 3)
N
Compression factor is N−M(L−3)

Neena Raj N. R. CS1U43D DCT January 2024 15 / 27

RLE Text Compression Performance

Performance

Examples:
N = 1000, M = 10, L = 4 yield a compression factor of 1000/[1000 - 10(4
- 3)] = 1.01.
A better result is obtained in the case
N = 1000, M = 50, L = 10, where the factor is 1000/[1000 - 50(10 - 3)]
= 1.538.

Neena Raj N. R. CS1U43D DCT January 2024 16 / 27

RLE Text Compression Digram Encoding

Digram Encoding

A variant of run length encoding for text is digram encoding.

This method is suitable for cases where the data to be compressed
consists only of certain characters, e.g., just letters, digits, and
punctuation.
The idea is to identify commonly occurring pairs of characters and to
replace a pair (a diagram) with one of the characters that cannot
occur in the data.(e.g., one of the ASCII control characters).
Good results can be obtained if the data can be analyzed beforehand.

Neena Raj N. R. CS1U43D DCT January 2024 17 / 27

RLE Text Compression Pattern substitution

Pattern substitution

A similar variant is pattern substitution. This is suitable for

compressing computer programs, where certain words, such as for,
repeat, and print, occur often.
Each such word is replaced with a control character or, if there are
many such words, with an escape character followed by a code
character.
Example : Assuming that code “a” is assigned to the word print, the
text “m:tprint,b,a;” will be compressed to “m:t@a,b,a;”.