CODEWITHSUNDEEP
theoryhuffman-code
Dylan Forsyth
Dylan Forsyth

Reputation: 57

Valid Huffman Codes?

I'm trying to solve a Huffman Coding problem, but I'm not completely sure I understand the topic completely. I am trying to figure out if the following are is a valid Huffman Code:

A: 0  
B: 01  
C: 11  
D: 110  
E: 111

What I'm thinking is that it is not valid, because A, or 1, would infringe on B, or 01. I'm not positive though. Could someone enlighten me on this?

Edit: I'm sorry I meant to type A as 0 and not 1.

Upvotes: 1

Views: 3188

Answers (1)

Mark Adler
Mark Adler

Reputation: 112239

No. A Huffman code is a prefix code, which means that no code can be a prefix of any other code. In your example, A is a prefix of B, and C is a prefix of both D and E.

A valid prefix code would be:

A: 0
B: 10
C: 11

That's as far as you can go with codes of length 1, 2, and 2. Any other codes would be a prefix of those. It is not possible to have a prefix code with lengths 1, 2, 2, 3, and 3.

This is a valid prefix code for five symbols:

A: 0
B: 10
C: 110
D: 1110
E: 1111

as is this:

A: 00
B: 01
C: 10
D: 110
E: 111

Upvotes: 2

Related Questions