Data
Compression
Algorithms
What is it
  • Encoding of bits to generate a smaller file
  • Two types of compression. Lossy and Lossless

Why

do we

use it

  • Storage Space
  • What’s the Catch?

Where

do we

use it

audio, video, images, text, ...pretty much everything.
So many algorithms….

ASCII Encoding
ASCII Encoding
"Mississippi river"

"01001101 01001001 01010011 01010011 01001001
01010011 01010011 01001001 01010000 01010000
01001001 00100000 01010010 01001001 01010110
01000101 01010010"

17 char
x8 bit
========
136 bit

Can we do better?

Huffman coding
  • Discovered as term assignment
  • Uses STATISTICAL approach

  • "Mississippi river"

    Character Appearance
    'M' 1
    'i' 5
    's' 4
    'p' 2
    'r' 2
    'v' 1
    'e' 1
    _ 1

"Mississippi river"

M I S S I S S I P P I _ R I V E R Total
1100 00 01 01 00 01 01 00 100 100 00 1111 101 00 1101 1110 101 46 BIT
LZ77 - “Today is Cyber Monday”
LZ78 - “abracadabra”
OutPut Index String
<0 , c(a)> 1 a
<0 , c(b)> 2 b
<0 , c(r)> 3 r
<1 , c(c)> 4 ac
<1 , c(d)> 5 ad
<1 , c(b)> 6 ab
<3 , c(a)> 7 ra

<0 , c(a)> , <0 , c(b)>, <0 , c(r)>, <1 , c(c)>, <1 , c(d)>, <1 , c(b)>, <3 , c(a)>

Conclusion

Thank

You!

Questions