30.24. Huffman Coding¶

30.24.1. Huffman Coding¶

30.24.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}$

30.24.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

30.24.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

30.24.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

30.24.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

30.24.1.6. Tree vs. Trie (1)¶

0 / 0 Settings
<<<>>>

We now add 18 to the tree. A split is made at 18.

36
18
0
70
36
18

Saving...
Server Error
Resubmit

30.24.1.7. Tree vs. Trie (2)¶

0 / 0 Settings
<<<>>>

We now want to add 45. This requires two splits. The first split is at value 48.

32
16
48
7
19
38
0
64
38
32
19
16
7
48

Saving...
Server Error
Resubmit

OpenDSA Modules Collection with Slides

Chapter 30 Slides

30.24. Huffman Coding¶

30.24.1. Huffman Coding¶

30.24.1.1. Coding¶

30.24.1.2. Huffman Coding Trees¶

30.24.1.3. Assigning Codes¶

30.24.1.4. Using Codes¶

30.24.1.5. Decoding¶

30.24.1.6. Tree vs. Trie (1)¶

30.24.1.7. Tree vs. Trie (2)¶