53 votes
Accepted

Huffman encoding: why is there no need for a separator?

You don't need a separator because Huffman codes are prefix-free codes (also, unhelpfully, known as "prefix codes"). This means that no codeword is a prefix of any other codeword. For example, the ...
David Richerby's user avatar
13 votes

Huffman encoding: why is there no need for a separator?

It's helpful to imagine it as a tree. You are simply traversing the tree until you hit a leaf node, and then restarting from the root. From the algorithm which does huffman coding, you can see that ...
crackpotHouseplant's user avatar
9 votes

Huffman Coding vs LZW Algorithm

In a gist LZW is about frequency of repetitions and Huffman is about frequency of single byte occurrence. Take the string 123123123. (The following is an oversimplification but will make the point) ...
Mirko's user avatar
  • 191
8 votes

Maximum size of Huffman codes for an alphabet containing 256 letters

I don't see how to approach the problem. OK, here is how you can approach the problem. Can you solve this problem if you replace the number 256 with the number 3? How about 4? 5? Try solving ...
D.W.'s user avatar
  • 159k
7 votes

How does a predictive coding aid in lossless compression?

Huffman coding, as usually applied, only considers the distribution of singletons. If $X$ is the distribution of a random singleton, then Huffman coding uses between $H(X)$ and $H(X)+1$ bits per ...
Yuval Filmus's user avatar
6 votes

Huffman Coding vs LZW Algorithm

LZW is dictionary-based - as it encodes the input data, it achieves compression by replacing sub-strings that have occurred previously with references into the dictionary. If phrases do not repeat (...
500 - Internal Server Error's user avatar
6 votes

Is huffman-encoding with distinct frequencies of symbols unique?

2 3 4 5 is a counterexample: 4 5 5 (combine 2 and 3 to make 5, and reorder) Now there are 2 choices for ...
j_random_hacker's user avatar
6 votes

Arithmetic coding and "the optimal compression ratio"

Beware: The phrase "optimal compression ratio" is perhaps a bit misleading. It is intended to make you think of "the best compression ratio that is achievable", but there are some assumptions that it ...
D.W.'s user avatar
  • 159k
6 votes

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

Both Huffman trees and optimal binary decision trees can be though of as mechanisms for playing the (probabilistic) 20 questions game optimally. In the 20 questions game you are given a set of items $...
Yuval Filmus's user avatar
6 votes
Accepted

Average codeword length in Huffman encoding at most log n

Huffman's algorithm is known to be optimal, that is, produce a code which minimizes the average codeword length (with respect to the input distribution). Let us notice now that there is a code in ...
Yuval Filmus's user avatar
6 votes
Accepted

Why does the Huffman coding algorithm produce a valid tree?

Let $v$ be a vertex of the tree. If $\pi_v$ is the path from the root of the tree to $v$, then the string $s(v)$ constructed from the labels of $\pi_v$ is unique (if you really want, you can prove ...
Steven's user avatar
  • 29.4k
5 votes

"Huffman coding is unsuitable for text files"?

It's not unsuitable, it is just not optimal. That's because letters in human readable text are not independent, but quite strongly correlated. That correlation can be used to get huge savings. For ...
gnasher729's user avatar
5 votes
Accepted

Is huffman coding tree a heap or a trie?

A Huffman tree is a trie: its edges are labeled by $0,1$, and its paths spell out binary words. Huffman's algorithm uses a min-heap to construct the Huffman tree. At each step, we choose the two ...
Yuval Filmus's user avatar
4 votes

When would the worst case for Huffman coding occur?

According to NIST: The worst case for Huffman coding (or, equivalently, the longest Huffman coding for a set of characters) is when the distribution of frequencies follows the Fibonacci numbers. For ...
Johan's user avatar
  • 1,070
4 votes
Accepted

How to know if a code is Huffman or not without having the probability of each codeword?

If you have a Huffman code, and the codes have lengths $l_i$, then the sum over $2^{-l_i}$ must be equal to 1. In your case, that sum is 1/4 + 1/4 + 1/4 + 1/8 = 7/8 < 1, therefore not a Huffman ...
gnasher729's user avatar
4 votes
Accepted

Infinite Huffman Tree

I don't think there is an algorithm that works for any infinite probability distribution. However, you have taken the case of a geometric distribution for which there happens to be a neat answer. It ...
sudeep5221's user avatar
4 votes

Compression algorithms for small strings - building upon / extending Huffman

A simple variant of Huffman is due, I believe, to David Wheeler. Suppose the alphabet is $\Sigma = \{s_1, \dots, s_n\}$ and let $\star$ be some new character that's not in $\Sigma$. For each ...
David Richerby's user avatar
4 votes
Accepted

How to avoid having to store extra information about padding (for byte size alignment) with Huffman coding

There's a way that neither needs to store the number of padded bits, nor - in most real life scenarios *) - add a pseudo symbol. The idea is this: The maximum padding is 7 bits, so if after the last ...
Evgeniy Berezovsky's user avatar
4 votes
Accepted

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

This answer assumes that by average you mean just that – the sum of all codeword lengths divided by $n$. Let us show that any prefix code satisfies your property. Consider any prefix code whose ...
Yuval Filmus's user avatar
4 votes
Accepted

How many Huffman codes can be written for a set of n characters?

A non-redundant prefix code on $n$ elements (which seems to be what your textbook means by Huffman code) is the same as a binary tree with $n$ leaves, and those are counted by Catalan numbers.
Yuval Filmus's user avatar
3 votes

Maximum size of Huffman codes for an alphabet containing 256 letters

In theory, 256 characters can have probabilities $2^{-1}$, $2^{-2}$, ..., $2^{-255}$, $2^{-255}$ (yes, the last one is $2^{-255}$, not $2^{-256}$), so there could be two codes of 255 bits. In ...
gnasher729's user avatar
3 votes

Maximum size of Huffman codes for an alphabet containing 256 letters

The maximum possible code size for a 256 symbol alphabet is 256 bits. Consider the case when the most frequent symbol has frequency 1/2, the next most frequent symbol has frequency 1/4, then 1/8 .... ...
CWallach's user avatar
3 votes

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

I don't know what a "compact instantaneous binary encoding" is, but I'm guessing it's a prefix code that saturates Kraft's inequality. If so, your numbers don't correspond to a compact prefix code, ...
Yuval Filmus's user avatar
3 votes
Accepted

Arithmetic coding and "the optimal compression ratio"

The optimal compression ratio is the entropy, which is the optimal compression ratio due to the source coding theorem.
Yuval Filmus's user avatar
3 votes

Huffman encoding: why is there no need for a separator?

No code other than E starts with 0000. No code other than i starts with 0001. And so on. As an extreme case, no code other than e starts with 01. You don't have things like E = 0000, space = 000, ...
gnasher729's user avatar
3 votes
Accepted

Was my Huffman coding solution wrong?

Huffman's algorithm is actually an "algorithm scheme", that is, a specification for an entire class of algorithms. Roughly speaking, Huffman's algorithm is any instantiation of the following scheme: ...
Yuval Filmus's user avatar
3 votes

Kraft's inequality for Huffman coding

All Huffman codes satisfy Kraft’s inequality with strict equality. We will give two proofs of this fact, one specific to Huffman codes, and the other applying to all minimum redundancy codes. First ...
Yuval Filmus's user avatar
3 votes
Accepted

Huffman Coding as optimal

Given a probability distribution $\mu$ on a (usually) finite set $X$ and an alphabet $\Sigma$, a prefix code consists of an assignment of a word $c(x)$ over $\Sigma$ for each $x \in X$, such that no $...
Yuval Filmus's user avatar
2 votes

Huffman Code VS Hu–Tucker Code

Let's say you wanted to compress a dictionary using Huffman Algorithm, yes it would be small, but all the ordering would disappear. So if you wanted to get the definition of for example the word '...
Shrenik's user avatar
  • 21
2 votes

Is there a generalization of Huffman Coding to Arithmetic coding?

As a simple example, if you had three symbols with probability 1/3rd each, your optimal Huffman encoding would use the three symbols 0, 10 and 11 with an average of 5/3rd bits. There are 243 symbols ...
gnasher729's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible