【精品】PPT课件 010.141 Engineering Mathematics IILecture pression.ppt

Engineering Mathematics IILecture pression
Bob McKay
School puter Science and Engineering
College of Engineering
Seoul National University
1
Outline
pression
Huffman & Shannon-Fano
pression
The LZ Family of Algorithms
pression
pression
pression
pression
2
pression
Lossless encoding methods guarantee to reproduce exactly the same data as was input to them
3
Run Length Encoding
4
Relative Encoding
Useful when there are sequences of runs of data that vary only slightly from one run to the next:
eg the lines of a fax
The position of each change is denoted relative to the start of the line
Position indicator can be followed by a numeric count indicating the number of essive changes
For pression, the position of the next change can be denoted relative to the previous
5
pression
For the examples below, we will use a simple alphabet with the following frequencies of occurrence (after Held)
Character
Probability
X1

X2

X3

X4

X5

X6

X7

6
Huffman Encoding
Arrange the character set in order of decreasing probability
While there is more than one probability class:
Merge the two lowest probability classes and add their probabilities to obtain posite probability
At each branch of the binary tree, allocate a '0' to one branch and a '1' to the other
The code for each character is found by traversing the tree from the root node to that character
7
Huffman Encoding
8
Shannon-Fano Algorithm
Arrange the character set in order of decreasing probability
While a probability class contains more than one symbol:
Divide the probability class in two
so that the probabilities in the two halves are as nearly as possible equal
Assign a '1' to the first probability class, and a '0' to the second
9
Shannon-Fano Encoding
10