Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

What is the running time and space complexity of a huffman decode algorithm?

Say we started with a text file like:

a 00 
b 01
c 10
d 11

00000001011011

The algorithm would be the typical one where you use the prefixes to build a Huffman tree, read in the encoded bits while traversing the tree until you reach a leaf, then returning the character in at that leaf.

Could someone explain how I would determine the running time and space complexity?

like image 661
atkayla Avatar asked Dec 12 '22 09:12

atkayla


1 Answers

Basically there are three methods on a Huffman Tree, construction, encoding, and decoding. The time complexity may vary from each other.

We should first notice that (see Wikipedia [link]):

In many cases, time complexity is not very important in the choice of algorithm here, since n here is the number of symbols in the alphabet, which is typically a very small number (compared to the length of the message to be encoded); whereas complexity analysis concerns the behavior when n grows to be very large.

  1. The complexity of construction is linear (O(n)) if input probabilities are sorted, see this paper. In most cases, we use a greedy O(n*log(n)) construction method: http://www.siggraph.org/education/materials/HyperGraph/video/mpeg/mpegfaq/huffman_tutorial.html
  2. If you build a bidirection hashtable for all symbols, both encoding and decoding would be constant (O(1)).
like image 96
Tao HE Avatar answered May 16 '23 08:05

Tao HE