Encoding

Question 1

What is encoding?

Answer 1

Given a set of items n, encode them using an amount of characters

Question 2

What is fixed length, fixed encoding?

Answer 2

The amount of bits used to encode each item is the same, and the characters used to encode is the same

Question 3

How many bits are in a file with n-bit binary encoding?

Answer 3

n * the amount of items

Question 4

What is variable length, fixed encoding?

Answer 4

The amount of bits used varies by how frequently an item appears in the set, but the characters used to encode are the same

Question 5

What is an example of variable length, fixed encoding?

Answer 5

Morse Code

Question 6

What is the most common form of variable length, variable encoding?

Answer 6

Huffman encoding

Question 7

What are the key features of Huffman encoding?

Answer 7

No code is a prefix of another, it can used to compress any kind of file, the length and encoding depend on the file itself

Question 8

What is required to decode something that has been Huffman encoded?

Answer 8

The Huffman tree that was used to encode it must be sent with the compressed file

Question 9

What are the steps for Huffman encoding?

Answer 9

1. Count the item frequency
2. Sort items by frequency, least to most
3. Build binary Huffman tree, starting with each item as a single node tree
4. Combine the two trees with the smallest values, with the left child as the smaller, right as the larger, and parent as the sum of both
5. Repeat until all only one tree remains

Question 10

How do you use a Huffman tree to encode something?

Answer 10

Assign each “edge” of the tree a value (usually 0 and 1) and trace down the branches to each item. The values passed, in order, is the encoded item

Question 11

What are the two approaches for implementing Huffman’s algorithm, and which is better?

Answer 11

MinHeap or 2 Queues
Same time complexity for both, 2 Queues easier to implement

Question 12

How do you find the average number of bits per item?

Answer 12

Sum of the bits*freq for each item, by the sum of all the frequencies

Question 13

How do you find the Compression Ratio for a Huffman encoded file?

Answer 13

F-A/F * 100
F = Bits for fixed representation
A = Average number of bits

Question 14

What is one benefit of Huffman encoding?

Answer 14

It guarantees the smallest binary encoding possible