Brainscape's Knowledge GenomeTM


Top Flashcards (Certified)
All Flashcards

C 949: Data Structures and Algorithms > 1.8 Huffman compression > Flashcards

1.8 Huffman compression Flashcards

1
Q

What is the basic idea of compression?

A

To encode frequently-occurring items using fewer bits.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

How many bits does uncompressed ASCII characters use?

A

8 bits each.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Compress the text ‘AAA Go’ using Huffman coding.

A

0 0 0 10 110 111.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How many bits does the compressed version of ‘AAA Go’ use?

A

11 bits.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What does the dictionary in Huffman compression do?

A

It assigns shorter codes to frequent items.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is the compressed code for the ASCII string ‘00000000 00000000 11111111 00000100’ using the given dictionary?

A

00 00 01 111.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Is any code in the provided dictionary a prefix of another code?

A

No.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the output for decompressing the code ‘00 01 00’?

A

00000000 11111111 00000000.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a character frequency table?

A

A table that contains each distinct character from the input string and each character’s number of occurrences.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What does the pseudocode ‘BuildCharacterFrequencyTable’ do?

A

It builds a frequency table for characters in an input string.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What character frequency is assigned to the letter ‘A’ in the string ‘APPLES AND BANANAS’?

A

5.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

What is Huffman coding?

A

A common compression technique that assigns fewer bits to frequent items using a binary tree.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the first step in Huffman coding?

A

Determine the frequencies of each item.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is the compressed output for the text ‘aabbbaaccd’ using Huffman coding?

A

0 0 10 10 10 0 0 110 110 111.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

How is the encoding for each leaf node obtained in Huffman coding?

A

By traversing from the top node to the leaf, appending 0 for left branches and 1 for right branches.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Fill in the blank: Prior to compression, a _______ must be built for an input string.

A

character frequency table.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

What occurs when a character appears for the first time in the frequency table?

A

Its frequency is set to 1.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
18
Q

What happens to the frequency of a character when it appears again in the frequency table?

A

The existing frequency is incremented.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
19
Q

What is the total frequency count of the string ‘seems he fleed’ for the letter ‘e’?

A

3.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
20
Q

True or False: In Huffman coding, the merging of nodes continues until only one node exists.

A

True.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
21
Q

What is the first merge in Huffman coding for the frequencies D: 3 and E: 3?

A

D and E: 6

This merge yields the smallest sum: 3 + 3 = 6.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
22
Q

What is the second merge in Huffman coding after merging D and E?

A

DE and B: 10

DE is 6 (from the first merge). B is 4. So 6 + 4 = 10.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
23
Q

What is the third merge in Huffman coding after DE and B?

A

DEB and C: 50

DEB is 10 (from the second merge). C is 40. So 10 + 40 = 50.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
24
Q

What is the fourth merge in Huffman coding after DEB and C?

A

DEBC and A: 100

DEBC is 50 (from the third merge), and A is 50. So 50 + 50 = 100.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
25
What is the fifth merge in Huffman coding?
None ## Footnote Only one node remains: DEBCA. No more merges are possible.
26
What is the code for character A in Huffman coding?
0 ## Footnote A is one branch to the left. A left branch appends a 0 to the code.
27
What is the code for character C in Huffman coding?
10 ## Footnote C is a right branch (1) and then a left branch (0), yielding 10.
28
What is the code for character B in Huffman coding?
110 ## Footnote Right, right, left yields 1, 1, 0, or 110.
29
What is the code for character D in Huffman coding?
1110 ## Footnote Right, right, right, left yields 1, 1, 1, 0, or 1110.
30
What is the code for character E in Huffman coding?
1111 ## Footnote Right, right, right, right yields 1111.
31
If 5 unique characters can each be uniquely encoded in 3 bits, how many bits are needed for a 100-character text?
300 ## Footnote 100 * 3 = 300.
32
For the Huffman code determined, how many bits are needed for the 100-character text with frequencies A: 1, C: 2, B: 3, D: 4, E: 4?
166 ## Footnote 50*1 + 40*2 + 4*3 + 3*4 + 3*4 = 166.
33
What data members do leaf nodes in a Huffman tree have?
A character and an integer frequency. ## Footnote Leaf nodes represent individual characters and their frequencies.
34
What data members do internal nodes in a Huffman tree have?
Left and right child nodes, and an integer frequency value. ## Footnote Internal nodes represent the sum of the frequencies of their child nodes.
35
What is the first step in building a Huffman tree?
Build the frequency table. ## Footnote This table lists the frequency of each character in the input string.
36
How are parent nodes created in a Huffman tree?
By dequeuing the two lowest-priority nodes and creating a new parent node. ## Footnote The parent's frequency is the sum of the child frequencies.
37
What does the function HuffmanGetCodes do?
It builds Huffman codes for each character. ## Footnote The codes are generated by tracing a path from the root to each character's leaf node.
38
What is the output of the HuffmanGetCodes function when called on a tree with root node 7?
A: 0, S: 101, B: 100, N: 11 ## Footnote The output is a dictionary mapping characters to their respective Huffman codes.
39
How many entries does the character frequency table have for the string 'zyBooks'?
6 ## Footnote One entry exists per distinct character.
40
What is the frequency of the parent node for nodes B and k in the priority queue?
2 ## Footnote The parent's frequency is the sum of the child frequencies, which are both 1.
41
What is the purpose of the HuffmanGetCodes function?
To generate Huffman codes for each character based on the tree structure ## Footnote The codes are built recursively; left branches add a 0, and right branches add a 1.
42
What is the Huffman code for character A in the tree built from 'BANANAS'?
0 ## Footnote A's leaf node is reached via a left branch from the root.
43
What is the Huffman code for character B in the tree built from 'BANANAS'?
100 ## Footnote B's code is determined by traversing left and right branches from the root.
44
What is the Huffman code for character S in the tree built from 'BANANAS'?
101 ## Footnote S is reached by moving right from node 4 then left.
45
What is the Huffman code for character N in the tree built from 'BANANAS'?
11 ## Footnote N is reached by following the right branches after reaching node 4.
46
What is the maximum length of a Huffman code in the tree built from 'BANANAS'?
4 ## Footnote This length corresponds to the longest path from the root to a leaf.
47
What is the first step in compressing data using Huffman coding?
Obtain Huffman codes for each character ## Footnote Codes are generated based on the frequency of characters in the input string.
48
Fill in the blank: The result of HuffmanCompress function is a _______.
compressed binary string ## Footnote The result is formed by concatenating bit codes corresponding to each character.
49
What does the HuffmanDecompress function do?
Decompresses Huffman encoded data by tracing the tree based on bit values ## Footnote It starts at the root and follows left or right based on each bit until a leaf is reached.
50
What is the output of HuffmanCompress('BANANAS')?
111 0 10 0 10 0 110 ## Footnote This result reflects the frequency of characters in the input string.
51
True or False: Each distinct character in a Huffman tree has a unique code.
True ## Footnote This uniqueness follows from the properties of the Huffman coding algorithm.
52
What is the Huffman code for character P in the tree built from 'APPLES AND BANANAS'?
011 ## Footnote The path to P's leaf involves moving left and right from the root.
53
What is the length of the longest Huffman code from the tree built from 'APPLES AND BANANAS'?
4 ## Footnote The longest path from root to leaf determines the maximum code length.
54
Fill in the blank: To decompress a Huffman coded string, one must start at the _______.
root of the Huffman tree ## Footnote Traversal follows the left or right child based on the bit value until reaching a leaf.
55
What character does the bit sequence '00' represent in the decompression process?
space ## Footnote The space character is represented by a specific leaf in the Huffman tree.
56
What is the first step in the HuffmanDecompress function?
Initialize node to treeRoot and result to an empty string
57
In the HuffmanDecompress function, what does the bit value determine?
It determines whether to go to the left or right child
58
What happens when a leaf node is reached in the HuffmanDecompress function?
The character is added to the result and the node is reset to treeRoot
59
Fill in the blank: The function HuffmanDecompress takes _______ and _______ as parameters.
[compressedString], [treeRoot]
60
What is the first decoded character from the compressed string 0111101000101 using the provided tree?
D
61
What does the bit sequence '11' correspond to in the decompression process?
It corresponds to the character O
62
What is the second decoded character from the compressed string 0111101000101?
O
63
What character is reached after decoding '100'?
A
64
What is the complete decoded text from the sequence 0111101000101?
DOODADS
65
True or False: The HuffmanDecompress function only processes bits until it reaches a non-leaf node.
False

C 949: Data Structures and Algorithms (13 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2025 Bold Learning Solutions. Terms and Conditions