Lecture 6
Lecture 6
Lecture 6
File Compression
Content Content
Introduction to Compression Methods in Data Compression Run-Length Coding Huffman Coding
File Compression
File Organization
168
File Organization
169
File Compression
File Organization
170
File Compression
special run-length code indicator(e.g. 0xFF) pixel value repeated the number of times that value is repeated
Example: 22 23 24 24 24 24 24 24 24 25 26 26 26 26 26 26 25 24
RL-coded stream: 22 23 ff 24 07 25 ff 26 06 25 24
File Organization
171
File Compression
File Organization
172
File Compression
Huffman coding
base on probability of occurrence
determine probabilities of each value occurring build binary tree with search path for each value more frequently occurring values are given shorter search paths in tree
File Organization
173
File Compression
File Organization
174
a(1)
File Compression
00
01
b(010) c(011)
000
001
d(0000)
File Organization
e(0001)
f(0010)
g(0011)
175
File Compression
File Organization
176
Example Example
Let us look at an example for an alphabet having only two letters:
6 File Compression
aaababbbaaabaaaaaaabaabb
Rule Separate this stream of characters into pieces of text so that each piece is the shortest string of characters that we have not seen yet.
File Organization
177
a|aa|b|ab|bb|aaa|ba|aaaa|aab|aabb
1. We see a 2. a has been seen, we now see aa 3. We see b 4. a has been seen, we now see ab 5. b has been seen, we now see bb 6. aa has been seen, we now see aaa 7. b has been seen, we now see ba 8. aaa has been seen, we now see aaaa 9. aa has been seen, we now see aab 10. aab has been seen, we now see aabb
File Organization 178
File Compression
Index Index
We have index values from 1 to n For the previous example
6 File Compression
12 34 5 6 7 8 9 10 a|aa|b|ab|bb|aaa|ba|aaaa|aab|aabb
Encoding
1 2 3 4 5 6 7 8 9 10 0a|1a|0b|1b|3b|2a|3a|6a|2b|9b
File Organization 179
File Compression
File Organization
180
File Compression
12 34 5 6 7 8 9 10 a|aa|b|ab|bb|aaa|ba|aaaa|aab|aabb
File Organization
181
Exercise # 1 Exercise # 1
encode the file containing the following characters, drawing the corresponding digital tree
File Compression 6
aaabbcbcdddeab
File Organization
182
Solution Solution
File Compression
12 34 5 67 8 a|aa|b|bc|bcd|d|de|ab
0a|1a|0b|2c|4d|0d|6e|1b
File Organization 183
d 6 e 7 12 34 5 67 8 a|aa|b|bc|bcd|d|de|ab 0a|1a|0b|2c|4d|0d|6e|1b
184
File Compression
Exercise # 2 Exercise # 2
Encode the file containing the following characters, drawing the corresponding digital tree
6 File Compression
I AM SAM. SAM I AM
File Organization
185
Solution Solution
123 4
File Compression 6
5 6
7 8
10 11
File Organization
186
I 1 b 10 2 S 5 A 8
b A 3 M 6 . 11
File Compression
M 4 b 9
. 7
File Organization
File Compression
Speech compression
voice coding (the lost information is of no little or no value)
File Organization
188