A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [huffman-coding]

The tag has no usage guidance.

55 questions
Filter by
Sorted by
Tagged with
28 views

### Is arithmetic coding restricted to powers of $2$ in denominator equivalent to Huffman coding?

With restriction to $\frac{k}{2^n}$ as line segment ends, does arithmetic coding degrade to Huffman coding? As far as I can tell, each symbol will be encoded with an integer amount of bits, which is ...
25 views

What are the advantages and drawbacks of considering ever longer block lengths or context lengths, if one was to work with estimated probabilities(measuring on the fly: aka "adaptive") rather than ...
74 views

### Codeword constructed by Huffman's algorithm has average length of at most log n

I am interested in the following question: Prove that the average length of a codeword constructed by Huffman's algorithm has average length at most $\log n$, where $n$ is the number of codewords. ...
62 views

### Efficient serialization/deserialization of huffman tree

I have implemented huffman encoding in the form ...
188 views

### Average codeword length in a Huffman tree is $\Omega(\log n)$

Prove that the average codeword length in a Huffman tree is $\Omega(\log n)$, where $n$ is the number of characters. My try: I think that the worst case is when the tree is full and all the ...
127 views

### Kraft's inequality for Huffman coding

Is it true to say that Huffman codes always satisfy Kraft's inequality with strict equality? At first, I thought the statement is wrong since for Huffman coding there is no assumptions on the ...
80 views

### When Huffman coding is inefficient?

I have a question regarding the redundancy of Huffman coding. I know that for a general prefix code we have the following inequality: $$H(X) \le R \le H(X) + 1$$ $R$ being the rate (average ...
26 views

### Huffman - Upperbound Depth Given an alphabet with probabilities

Given an alphabet $\Sigma = \{C_1, ..., C_k\}$ where the probability of the letter $C_k$ is given by $Pr(C_k)$. The probabilities satisfy $Pr(C_1)> ... >P(C_k)$ (i.e all probabilities are ...
101 views

### Optimal prefix-free binary code with several codewords already assigned

The classic Huffman algorithm, as Wikipedia states, finds an optimal prefix-free binary code with minimum expected codewords length, given a set of symbols and their weights. Now, suppose codewords ...
720 views

### How does a predictive coding aid in lossless compression?

I'm working on this lab where we need to apply a lossless predictive coding to an image before compressing it (with Huffman, or some other lossless compression algorithm). From the example seen ...
24 views

### Difference between a regular and a stationary source?

As far as I understand a stationary source is a regular source but it's not necessarily true the other way around. And a stationary source is a source for which its distribution is unaffected by a "...
156 views

### Length of shortest codeword in Huffman encoding

Under Huffman Encoding, if one character occurs more than 1/3rd of the time, is it guaranteed that there will be at least one character whose codeword is of length 1? I thought of 2 cases where this ...
17 views

185 views

### monotonically increasing codeword length in optimal (maybe Huffman) code for alphabet with monotonically decreasing frequencies

I'm working on exercise 16.3-5 of CLRS: Prove that if we order the characters in an alphabet so that their frequencies are monotonically decreasing, then there exists an optimal code whose codeword ...
242 views

### How to prove that for a full binary tree $T$ there's a series of frequencies such that Huffman alg. will produce $T$?

How to prove that for a full (each node that's not a leaf has 2 nodes) binary tree $T$ of $n$ leaves there's a series of frequencies $f_1,f_2,...,f_n$ such that if we use Huffman algorithm on the ...
342 views

### How does adaptative Huffman coding (Vitter algorithm) work?

I have implemented Vitter algorithm thanks to the Wikipedia article. However I don't really understand how some parts of the algorithm make the algorithm more efficient: ...
29 views

### Info about dataset from which a Huffman tree was generated

I know that given the following huffman tree: you can say that C occurs most in the dataset from which it was generated and D and B occur the least. Can you also say that the left most leaf on a ...
106 views

### How well does DEFLATE perform, compared to the theoretical optimum?

I know that there is an inherent limit to how much you can compress data using lossless compression. Basically, the only thing lossless compression can do is reduce dependencies between symbols, ...
4k views

### Maximum size of Huffman codes for an alphabet containing 256 letters

I made a Huffman algorithm for data compression: it takes the content of a file as an input and outputs a compressed string. More important, it generates optimal prefix codes (made of 0 and 1) for ...
65 views

### Can the following Huffman tree be extended to include more letters?

The following table shows a possible set of Huffman codes to be used for lossless compression of a text consisting only of the eight letters shown: ...
126 views

### Kraft's inequality and Shannon's noiseless coding theorem for an encoding

A discrete memoryless source W has words $w_1,w_2,w_3,w_4,w_5,w_6$ that occur with probablilities $0.05,0.05,0.15,0.2,0.25,0.3$ respectivley. Does there exist a compact instantaneous binary encoding ...
237 views

### “Huffman coding is unsuitable for text files”?

My lecturer for information theory says that "Huffman coding produces efficient codes but is unsuitable for text files where the letters are represented by a fixed length ASCII code". I do not ...
720 views

### Arithmetic coding and “the optimal compression ratio”

Trying to learn more about compression techniques and found something in the wikipedia article on arithmetic coding that I'm not sure I fully grok. In describing how Huffman Coding can sometimes be ...
400 views

### What is a Huffman tree for a Block-Code?

We have the word "w = aabceefgeebdaabbceeffghdcbbeefbbbbghhie ". I have created a Huffman tree for the string w. We get the following table: Now I want to create a Huffman tree for a Block-Code ...