Text Compression: Examples Huffman coding: go go gophers
“abcde” in the different formats ASCII 3 bits Huffman
Encodings ASCII: g 103 1100111 000 00
01100001011000100110001101100100… o 111 1101111 001 01
13
ASCII: 8 bits/character p 112 1110000 010 1100
Fixed: h 104 1101000 011 1101 6 7
Unicode: 16 bits/character
000001010011100 e 101 1100101 100 1110 3 4
10 g o
r 114 1110010 101 1111
Symbol ASCII Fixed Var. 3 3 s * 2 2
s 115 1110011 110 101
length length 0 1 sp. 32 1000000 111 101 1
0 0 2
a 01100001 000 000 p h e r
0 1 0 1
0
Encoding uses tree: 1 1 1 1
b 01100010 001 11 0 left/1 right
a b c d e 6
Var:
c 01100011 010 01 How many bits? 37!! 4
000110100110 g o
0 1 Savings? Worth it?
d 01100100 011 001 2 2 3 3
3
e 01100101 100 10 0 1 0 1
p h e r
c e b 1 1 1 s *
0 1 1
1 2
CPS 100 a d 8.1 CPS 100 8.2
Huffman Coding Building a Huffman tree
D.A Huffman in early 1950’s Begin with a forest of single-node trees (leaves)
Before compressing data, analyze the input stream Each node/tree/leaf is weighted with character count
Represent data using variable length codes Node stores two values: character and count
Variable length codes though Prefix codes There are n nodes in forest, n is size of alphabet?
Each letter is assigned a codeword
Codeword is for a given letter is produced by traversing Repeat until there is only one node left: root of tree
the Huffman tree Remove two minimally weighted trees from forest
Property: No codeword produced is the prefix of another Create new tree with minimal trees as children,
Letters appearing frequently have short codewords, • New tree root's weight: sum of children (character ignored)
while those that appear rarely have longer ones
Huffman coding is optimal per-character coding method Does this process terminate? How do we get minimal trees?
Remove minimal trees, hummm……
CPS 100 8.3 CPS 100 8.4
Building a tree Building a tree
“A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS” “A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS”
1 1
F C
11 6 5 5 4 4 3 3 3 3 2 2 2 2 2 1 1 1 11 6 5 5 4 4 3 3 3 3 2 2 2 2 2 2 1
CPS 100 8.5 CPS 100 8.6
I E N S M A B O T G D L R U P F C I E N S M A B O T G D L R U P
Building a tree Building a tree
“A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS” “A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS”
2 3 2 3 2 2
L R
1 1 1 2 1 1 1 2
C F P U C F P U
11 6 5 5 4 4 3 3 3 3 3 2 2 2 2 2 11 6 5 5 4 4 4 3 3 3 3 3 2 2 2
CPS 100 8.7 CPS 100 8.8
I E N S M A B O T G D L R I E N S M A B O T G D
Building a tree Building a tree
“A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS” “A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS”
23 37 23
21 16 12 11 21 16 12 11
10 11 8 8 6 6 10 11 8 8 6 6
I I
5 5 5 6 4 4 4 4 3 3 5 5 5 6 4 4 4 4 3 3
E N S M A B E N S M A B
3 2 3 3 2 2 2 2 3 2 3 3 2 2 2 2
O T G D L R O T G D L R
1 1 1 2 1 1 1 2
C F P U C F P U
23 21 16 37 23
CPS 100 8.9 CPS 100 8.10
Building a tree Mary Shaw
Software engineering and
software architecture
“A SIMPLE STRING TO BE ENCODED USING A MINIMAL NUMBER OF BITS”
Tools for constructing
60 large software systems
Development is a small
37 23 piece of total cost,
maintenance is larger,
21 16 12 11
depends on well-designed
and developed techniques
10 11 8 8 6 6
I Interested in computer
5 5 5 6 4 4 4 4 3 3
science, programming,
E N S M A B curricula, and canoeing,
3 2 3 3 2 2 2 2 health-care costs
O T G D L R ACM Fellow, Alan Perlis
1 1 1 2
Professor of Compsci at CMU
C F P U
60
CPS 100 8.11 CPS 100 8.12
Huffman Complexities Writing code out to file
How do we measure? Size of input file, size of alphabet How do we go from characters to encodings?
Which is typically bigger? Build Huffman tree
Root-to-leaf path generates encoding
Accumulating character counts: ______
How can we do this in O(1) time, though not really Need way of writing bits out to file
Building the heap/priority queue from counts ____ Platform dependent?
Initializing heap guaranteed Complicated to write bits and read in same ordering
Building Huffman tree ____
Why? See BitInputStream and BitOutputStream classes
Create table of encodings from tree ____ Depend on each other, bit ordering preserved
Why?
Write tree and compressed file _____ How do we know bits come from compressed file?
Store a magic number
CPS 100 8.13 CPS 100 8.14
Decoding a message Decoding a message
01100000100001001101 1100000100001001101
60 60
37 23 37 23
21 16 12 11 21 16 12 11
10 11 8 8 6 6 10 11 8 8 6 6
I I
5 5 5 6 4 4 4 4 3 3 5 5 5 6 4 4 4 4 3 3
E N S M A B E N S M A B
3 2 3 3 2 2 2 2 3 2 3 3 2 2 2 2
O T G D L R O T G D L R
1 1 1 2 1 1 1 2
C F P U C F P U
CPS 100 8.15 CPS 100 8.16
Decoding a message Decoding a message
100000100001001101 00000100001001101
60 60
37 23 37 23
21 16 12 11 21 16 12 11
10 11 8 8 6 6 10 11 8 8 6 6
I I
5 5 5 6 4 4 4 4 3 3 5 5 5 6 4 4 4 4 3 3
E N S M A B E N S M A B
3 2 3 3 2 2 2 2 3 2 3 3 2 2 2 2
O T G D L R O T G D L R
1 1 1 2 1 1 1 2
C F P U C F P U
CPS 100 8.17 CPS 100 8.18
Decoding a message Decoding a message
0000100001001101 1
60 60
37 23 37 23
21 16 12 11 21 16 12 11
10 11 8 8 6 6 10 11 8 8 6 6
I I
5 5 5 6 4 4 4 4 3 3 5 5 5 6 4 4 4 4 3 3
E N S M A B E N S M A B
3 2 3 3 2 2 2 2 3 2 3 3 2 2 2 2
O T G D L R O T G D L R
1 1 1 2 1 1 1 2
C F P U C F P U
CPS 100 G 8.19 CPS 100 GOOD 8.20
Decoding a message Huffman coding: go go gophers
ASCII 3 bits Huffman
g 103 1100111 000 ?? g o p h e r s *
01100000100001001101 o 111 1101111 001 ?? 3 3 1 1 1 1 1 2
p 112 1110000 010
60 h 104 1101000 011 2 2 3
e 101 1100101 100
37 23 r 114 1110010 101 p h e r s *
s 115 1110011 110 1 1
21 16 12 11 1 1 1 2
sp. 32 1000000 111
choose two smallest weights
10 11 8 8 6 6
combine nodes + weights
I
Repeat
5 5 5 6 4 4 4 4 3 3
Priority queue? 4 6
E N S M A B
3 2 3 3 2 2 2 2 Encoding uses tree: 2 2 g o
O T G D L R 0 left/1 right
3 3
1 1 1 2 How many bits? p h e r
C F P U 1 1 1 1
CPS 100 GOOD 8.21 CPS 100 8.22
Huffman Tree 2 Huffman Tree 2
“A SIMPLE STRING TO BE ENCODED USING A “A SIMPLE STRING TO BE ENCODED USING A
MINIMAL NUMBER OF BITS” MINIMAL NUMBER OF BITS”
E.g. “ A SIMPLE” ⇔ E.g. “ A SIMPLE” ⇔
“10101101001000101001110011100000” “10101101001000101001110011100000”
CPS 100 8.23 CPS 100 8.24
Huffman Tree 2 Huffman Tree 2
“A SIMPLE STRING TO BE ENCODED USING A “A SIMPLE STRING TO BE ENCODED USING A
MINIMAL NUMBER OF BITS” MINIMAL NUMBER OF BITS”
E.g. “ A SIMPLE” ⇔ E.g. “ A SIMPLE” ⇔
“10101101001000101001110011100000” “10101101001000101001110011100000”
CPS 100 8.25 CPS 100 8.26
Huffman Tree 2 Huffman Tree 2
“A SIMPLE STRING TO BE ENCODED USING A “A SIMPLE STRING TO BE ENCODED USING A
MINIMAL NUMBER OF BITS” MINIMAL NUMBER OF BITS”
E.g. “ A SIMPLE” ⇔ E.g. “ A SIMPLE” ⇔
“10101101001000101001110011100000” “10101101001000101001110011100000”
CPS 100 8.27 CPS 100 8.28
Huffman Tree 2 Huffman Tree 2
“A SIMPLE STRING TO BE ENCODED USING A “A SIMPLE STRING TO BE ENCODED USING A
MINIMAL NUMBER OF BITS” MINIMAL NUMBER OF BITS”
E.g. “ A SIMPLE” ⇔ E.g. “ A SIMPLE” ⇔
“10101101001000101001110011100000” “10101101001000101001110011100000”
CPS 100 8.29 CPS 100 8.30
Huffman Tree 2 Other methods
“A SIMPLE STRING TO BE ENCODED USING A Adaptive Huffman coding
MINIMAL NUMBER OF BITS” Lempel-Ziv algorithms
E.g. “ A SIMPLE” ⇔ Build the coding table on the fly while reading
“10101101001000101001110011100000” document
Coding table changes dynamically
Protocol between encoder and decoder so that everyone
is always using the right coding scheme
Works well in practice (compress, gzip, etc.)
More complicated methods
Burrows-Wheeler (bunzip2)
PPM statistical methods
CPS 100 8.31 CPS 100 8.32
