02

Module

1 OS Module 2 , Sahana K I, AP, CSE, GCEK 03 Jan 2025

 ● Lossless data compression technique
Run length ● Replacing consecutive repeated symbols (runs) with a
encoding, ●
single symbol and its count.
Example :
RLE Text ○ Word : AAAABBBCCDAA
compressio ○ Compressed one :(4,A) (3,B) (2,C) (1,D) (2,A)
○ Word : 0000001111000
n ○ Compressed : (6,0) (4,1) (3,0)
● Steps :
○ Read the first symbol.
○ Count how many times it repeats consecutively.
○ Output the count and the symbol.
○ Move to the next new symbol.
○ Repeat until the end of data.
● For text characters are : letters, spaces, or symbols
● Example : HELLO WORLD
● Compressed one : 1H1E2L1O5(sp)1W1O1R1L1D

2 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Advantages:
Pros & Cons ○ Very simple to implement
○ Fast encoding and decoding
○ Lossless compression
● Disadvantages:
○ Compression depends heavily on input data
○ Inefficient for complex or noisy data
○ Not suitable for general-purpose text
compression
○ Often increases file size

3 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Symbols are encoded based on their probabilities of
Statistical occurrence
methods- ● Prefix codes

Prefix
Codes

4 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Developed by David Huffman
Binary ● Prefix codes
Huffman ● The Huffman procedure is based on two observations
regarding optimum prefix codes:
coding ○ In an optimum code, symbols that occur more
frequently (have a higher probability of
occurrence) will have shorter codewords than
symbols that occur less frequently.
○ In an optimum code, the two symbols that occur
least frequently will have the same length.
●

5 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Let us design a Huffman code for a source that puts
Example 1 out letters from an alphabet A {a1,a2,a3,a4,a5} with
P(a1) = P(a3) = 0.2, P(a2) = 0.4, and P(a4) = P(a5) = 0.1
● Initial 5 alphabets :

● The two symbols with the lowest probability are a4

and a5.
○ c(a4) = α1 ∗ 0
○ c(a5) = α1 ∗ 1
○ Where α1 is a binary string, and ∗ denotes
concatenation.

6 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● New alphabets :
Example 1

○ c(a3) = α2 ∗ 0
○ c(a4’) = α2 ∗ 1
○ but c(a4) = α1. Therefore, α1 = α2 *1
○ Means
■ c(a4) = α2 ∗ 10
■ c(a5) = α2 ∗ 11
● New 3 letter alphabet :

7 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ○ c(a3’) = α3 ∗ 0
Example 1 ○
○
c(a1) = α3 ∗ 1
But c(a3’) = α2 so α2 = α3 *0
○ Means :
■ c(a3) = α3 ∗ 00
■ c(a4) = α3 ∗ 010
■ c(a5) = α3 ∗ 011
● Reduced 2 letter alphabet :

○ c(a3”) = 0
○ c(a2) = 1
○ which means that α3 = 0, then :
■ c(a1) = 01
■ c(a3) = 000
■ c(a4) = 0010
■ c(a5) = 0011

8 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 Final
answer

9 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Code elements come from an m-ary alphabet, and
Nonbinary m is not equal to two
Huffman ○ Symbols that occur more frequently (have a
higher probability of occurrence) will have
Codes shorter codewords than symbols that occur
less frequently, and
○ the m symbols that occur least frequently
will have the same length
● Example :
○ Generate a ternary Huffman code for a
source with a six-letter alphabet and a
probability model P(a1) = P(a3) = P(a4) = 0.2,
P(a5) = 0.25, P(a6) = 0.1, and P(a2) = 0.05. In
this case m = 3, therefore m’ is either 2 or 3.

10 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● c(a3) = α2 ∗ 0
● c(a4) = α2 ∗ 1
● c(a’6) = α2 ∗ 2
● But c(a’6) =α1. Therefore : α1 = α2 *2
● Then c(a6) = α2 *20
○ c(a2) = α2 * 21

11 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

12 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX
 1. A source emits letters from an alphabet =
Exercise 1 {a1,a2,a3,a4,a5} with probabilities P(a1) =0.15,P(a2)=0.04,
P(a3) = 0.26, P(a4) = 0.05, and P(a5) = 0.50.
a. Calculate the entropy of this source.
b. Find a Huffman code for this source.
2. For an alphabet = {a1,a2,a3,a4} with probabilities P(a1) =
0.1, P(a2) = 0.3, P(a3) = 0.25, and P(a4) = 0.35, find a
Huffman code
3. With a help of flowchart discuss the RLE text
compression for text data given below :
‘ABBBBBBBBBCDEEEEF’
4. Using RLE encoding techniques generate the compressed
sequence for the input :
‘aaaaaaaaabbbbbbecececececececececdddddddddddddd
ddecb’ and justify whether the compression is efficient?

13 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Represents an entire message as a single fractional
Arithmetic number between 0 and 1
Coding ●
●
It achieves compression close to the source entropy
A unique identifier or tag is generated for the
algorithm sequence
● Two steps :
○ A unique identifier or tag is generated
○ This tag is then given a unique binary code
● L = L+(H-L) * CL
● H=L+(H-L) *CH

14 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Code = BAC
Example ● Range of B = [0.5 , 0.8)
○ New Low = 0.0 + (1.0 − 0.0) × 0.5 = 0.5
○ New High = 0.0 + (1.0 − 0.0) × 0.8 = 0.8
● Current interval: [0.5 , 0.8)
● Range of A = [0.0 , 0.5)
Symbol Probability Range ○ New Low = 0.5 + (0.8 − 0.5) × 0.0 = 0.5
○ New High = 0.5 + (0.8 − 0.5) × 0.5 = 0.65
● Current interval: [0.5 , 0.65)
A 0.5 [0.0 , ● Range of C = [0.8 , 1.0)
0.5) ○ New Low = 0.5 + (0.65 − 0.5) × 0.8 = 0.62
○ New High = 0.5 + (0.65 − 0.5) × 1.0 = 0.65
B 0.3 [0.5 , ● Final interval: [0.62 , 0.65)
0.8) ● Any number between 0.62 and 0.65 uniquely
represents "BAC" eXAMPLE : 0.63
C 0.2 [0.8 ,
1.0)

15 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● Code = 0.63 3 SYMBOLS
DECODING ● Low = 0.0
● High = 1.0
● Code = 0.63
● 0.63 Lies in the interval of B so first symbol = B
● Update interval:
Symbol Probability Range ○ Low = 0.0 + (1.0 − 0.0) × 0.5 = 0.5
○ High = 0.0 + (1.0 − 0.0) × 0.8 = 0.8
● New interval: [0.5 , 0.8)
A 0.5 [0.0 , ● Normalize the code:
0.5) ○ Scaled value = (0.63 − 0.5) / (0.8 − 0.5)
○ = 0.13 / 0.3
B 0.3 [0.5 , ○ ≈ 0.433
0.8) ● Second symbol = A
● Update interval:
C 0.2 [0.8 , ○ Low = 0.5 + (0.8 − 0.5) × 0.0 = 0.5
1.0) ○ High = 0.5 + (0.8 − 0.5) × 0.5 = 0.65

16 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 ● New interval: [0.5 , 0.65)
DECODING ● Normalize again:
○ Scaled value = (0.63 − 0.5) / (0.65 − 0.5)
○ = 0.13 / 0.15
○ ≈ 0.867
● Third symbol = C
Symbol Probability Range ● Decoded message : BAC

A 0.5 [0.0 ,
0.5)

B 0.3 [0.5 ,
0.8)

C 0.2 [0.8 ,
1.0)

17 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX

 1. Given the probability model in Table 4.9, find the real
valued tag for the sequence a1 a1 a3 a2 a3 a1.
Exercise 2. For the probability model in Table 4.9, decode a sequence
of length 10 with the tag 0.63215699
3. Consider a data sequence which contains characters with
the following probabilities: A – 0.4, B – 0.3, C – 0.2 and D –
0.1. It is given that the tags generated for the sequence is
0.516928, if so decode the sequence using the Arithmetic
coding technique.
4. Encode the message “CAB”and generate the corresponding
binary arithmetic code.
Symb Probab Symb Proba 5. An arithmetic decoder receives the code 0.73. Decode the
ol ility ol bility message of length 3.
6. In Example 4.4.4, repeat the encoding using m = 6.
A 0.4 A 0.5 Comment on your results.
B 0.35 B 0.25
C 0.25 C 0.25

18 OS Module 2 , Sahana K I, AP, CSE, GCEK Month 20XX