Processing math: 100%

CSC 201 Data Structures

Chapter 6 Binary Trees

Show Source | | About « 6.12. Array Implementation for Complete Binary Trees :: Contents :: 6.14. Binary Search Trees »

6.13. Huffman Coding¶

6.13.1. Huffman Coding¶

6.13.1.1. Coding¶

ASCII codes are fixed length (7 + 1 bits)

In general, $n$ bits can store $2^n$ codes

An alternative is variable-length coding

The relative frequencies for eight selected letters.

$\begin{split}\begin{array}{|c|cccccccc|} \hline \textrm Letter & C & D & E & K & L & M & U & Z\\ \textrm Frequency & 32 & 42 & 120 & 7 & 42 & 24 & 37 & 2\\ \hline \end{array}\end{split}$

6.13.1.2. Huffman Coding Trees¶

1 / 16 Settings
<<<>>>

av_c1

32
C
42
D
120
E
7
K
42
L
24
M
37
U
2
Z

Saving...
Server Error
Resubmit

6.13.1.3. Assigning Codes¶

1 / 16 Settings
<<<>>>

av_c6

32
C
42
D
120
E
7
K
42
L
24
M
37
U
2
Z
9
2
Z
7
K
33
9
2
Z
7
K
24
M
65
32
C
33
9
2
Z
7
K
24
M
79
37
U
42
D
107
42
L
65
32
C
33
9
2
Z
7
K
24
M
186
79
37
U
42
D
107
42
L
65
32
C
33
9
2
Z
7
K
24
M
306
120
E
186
79
37
U
42
D
107
42
L
65
32
C
33
9
2
Z
7
K
24
M
0
1
0
0
1
1
0
1
0
1
0
0
1
1

Saving...
Server Error
Resubmit

6.13.1.4. Using Codes¶

1 / 11 Settings
<<<>>>

av_c6

32
C
42
D
120
E
7
K
42
L
24
M
37
U
2
Z
9
2
Z
7
K
33
9
2
Z
7
K
24
M
65
32
C
33
9
2
Z
7
K
24
M
79
37
U
42
D
107
42
L
65
32
C
33
9
2
Z
7
K
24
M
186
79
37
U
42
D
107
42
L
65
32
C
33
9
2
Z
7
K
24
M
306
120
E
186
79
37
U
42
D
107
42
L
65
32
C
33
9
2
Z
7
K
24
M
0
1
0
0
1
1
0
1
0
1
0
0
1
1
Char
Freq
Code
Bits
C
32
1110
4
D
42
101
3
E
120
0
1
K
7
111101
6
L
42
110
3
M
24
11111
5
U
37
100
3
Z
2
111100
6

Saving...
Server Error
Resubmit

6.13.1.5. Decoding¶

1 / 17 Settings
<<<>>>

av_c8

E
120
L
42
C
32
M
24
U
37
D
42
Z
2
K
7
0
1
0
0
1
1
0
1
0
1
1
0
0
1

Saving...
Server Error
Resubmit

Contact Us || Privacy | | License « 6.12. Array Implementation for Complete Binary Trees :: Contents :: 6.14. Binary Search Trees »