# Questions tagged [huffman-coding]

The tag has no usage guidance.

62 questions
Filter by
Sorted by
Tagged with
35 views

### When is Huffman code the most unoptimal?

By giving an Huffman coding tree and the total frequency of the characters. how can I find the most unoptimal frequencies for each character such that the size of the code will require the most ...
27 views

I'm confused about the point of adaptive arithmetic coding. I understand that static arithmetic coding involves using preset probabilities of symbols that remain static during the whole process. I ...
15 views

### Total weight of Huffman Code

We are given the following letters with the respective frequencies: \begin{equation*}\begin{matrix}a/2 & b/4 & c/7 & d/6 & e/4 & f/5 & g/8 & h/10 & i/3 & j/11\end{...
139 views

### What is implied probability, in the context of universal codes?

From Wikipedia: Each universal code, like each other self-delimiting (prefix) binary code, has its own "implied probability distribution" given by $p(i) ={2}^{-\ell(i)}$ where $\ell(i)$ is ...
31 views

### How do you work out the Huffman code for an extension?

I have worked out the following: v = 1101 0010 1101 0101 0100 1000 P(0) = 0.54 P(1) = 0.46 A = {0,1} I have also worked out question (c) to be: H(A^2) = 1.991 and H(A^3) = 2.9859 I am having ...
26 views

### on-the-fly decompress a flat-file database

I'm facing the following problem. I have a flat-file database (e.g. CSV). Since it's relatively large to store in memory, I'd like to compress it. Given a key, I need to return the uncompressed text (...
45 views

### Is using Fibonacci Heaps in Huffman Code, better than a regular Min-heap?

When using Huffman Code, to generate prefix-code trees for a sequence of letters, CLRS choose to use a normal Min-heap data structure. Using Fibonacci-heaps instead, are we not able to achieve a ...
52 views

### Prove that in an optimal code, if the letter frequencies are increasing, the encoding lengths are monotonically decreasing

I am trying to prove that, in an optimal encoding (possibly Huffman?), if letter frequencies are increasing, their encoding lengths are monotonically decreasing. It is intuitive that this makes sense, ...
53 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 ...
263 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 ...
100 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. ...
179 views

### Efficient serialization/deserialization of huffman tree

I have implemented huffman encoding in the form ...
281 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 ...
274 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 ...
111 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 ...
133 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 ...
731 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 ...
34 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 "...
279 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 ...
23 views

252 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 ...
267 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 ...
396 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: ...
31 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 ...
126 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, ...
5k 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 ...
73 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: ...
141 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 ...
280 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 ...
944 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 ...
469 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 ...
1k views

### What is a recursion for Huffman encoding?

If I had to write the Huffman encoding as a recursion in terms of the cost $C_{ij}$, given weights/frequencies $W = [w_1,\ldots,w_n]$, how would I do it? (where this is creating a minimum cost tree, \$...
1k views

### Are Huffman trees and optimal binary search trees for solving the same problems?

Huffman trees are used in a specific application - Huffman coding - for finding the minimum-expected-length binary-coding for a set of strings, with respect to a probability distribution over the ...
149 views

### Compression of a text that contains only the 5 first letters of the alphabet?

So the question is: "Imagine the compression of a text written only with the first 5 characters of the alphabet (a, b, c, d, e). Knowing that their apparition's frequency is 1)e, 2)a, 3)c, 4)d, 5)b, ...