# Tag Info

53

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 codeword for "e" in your example is 10, and you can see that no other codewords begin with the digits 10. This means that you can decode greedily by reading the ...

14

Let's look at a slightly different way of thinking about Huffman coding. Suppose you have an alphabet of three symbols, A, B, and C, with probabilities 0.5, 0.25, and 0.25. Because the probabilities are all inverse powers of two, this has a Huffman code which is optimal (i.e. it's identical to arithmetic coding). We will use the canonical code 0, 10, 11 for ...

13

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 this sort of structure is created in the process. https://en.wikipedia.org/wiki/File:HuffmanCodeAlg.png

8

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 those special cases, then see if you spot a pattern... This is a useful, general pattern. When a problem is too hard, try to find a simpler version of it and ...

7

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 singleton, where $H(\cdot)$ is the (log 2) entropy function. In contrast, predictive coding can take into account correlations across data points. As a simple ...

6

Let me give you a real-world example, that's very similar to something I wrote once. Let's say you're implementing a library catalogue system. A library catalogue is conceptually a collection of documents (perhaps in MARC format). A user of this system might enter a query, as in any search engine, and get a set of documents in return. The user would like to ...

6

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) LZW will identify that 123 is repeated three times and essentially create a dictionary of codes for sequences. It will esentially say when I say A I mean 123 ...

6

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 comes with -- you should really think of it as "the best compression ratio that is achievable, under a certain set of assumptions" (or "the best compression ...

6

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 $X$ and a probability distribution $\pi$ over $X$, and then you are presented an unknown item $x \sim \pi$. Your task is to discover $x$ using the least expected ...

5

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 example, the letters q and Q are almost always followed by u. Comma and period are almost always followed by a space character, and period space is almost always ...

4

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 (the data is a stream of symbols in more or less random order), LZW isn't going to be able to compress the data very well. By contrast, Huffman Coding could ...

4

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 4 to partner with: either the original 5, or the one formed by 2+3.

4

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 was proposed by Gallager in this paper . So if you apply his algorithm, you will see that you obtain exactly the same answer you proposed.  Gallager, R., &...

4

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 character $s\in\Sigma$, let $p(s)$ be the most common character to occur immediately after $s$ in your dataset. To compress the string $X=x_1\dots x_N$, you ...

3

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 practice, if you compress let's say a document of 1 Gigabyte, no character can have a probability less than $2^{-30}$, so the maximum length would be 30 bits. And ...

3

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 .... This get encoded as: 1 01 001 0001 ... <255 0 bits>1

3

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, since $1/4+1/4+1/16+1/16+1/32+1/32 < 1$. Shannon's noiseless coding theorem states that when optimally encoding large blocks, in the limit the average ...

3

The optimal compression ratio is the entropy, which is the optimal compression ratio due to the source coding theorem.

3

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 this and other relations see Alex Vinokur's note on Fibonacci numbers, Lucas numbers and Huffman codes. According to Alex Vinokur a sample Huffman encoding ...

3

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, where you wouldn't know what to do if you find three zeroes. Look at your encoded string: 0000101100000... You read the first zero. You know the code is one of E,...

3

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: While there is more than one symbol, choose (in an unspecified way) two leaves of minimum total probability, and merge then (in an unspecified order). Any ...

3

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 items with minimal probability, and merge them.

3

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 code. You can replace the code 110 with 11. (I am quite sure you can prove that for any prefix code, the sum is ≤ 1. And I'm quite sure you can prove that if the ...

3

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 encoded symbol, we pad with the first bits of a symbol that is encoded as 8 or more bits, the decoder will stop in the middle of decoding when the bit stream ...

2

Yes, You can. But you'll need the Huffman tree to decode since the placing of left child and right child is arbitrary. If you're given an encoded string and ask you to decode, you can't do that since you don't know the exact algorithm which is used in building the Huffman Tree.

2

You can assign the $1$ and $0$ as you like, but be consistent. Only your code change, i.e. a 1011 becomes a 0100.

2

A quick way to check whether your answer has a chance of being correct is to compute the average code length. Your encoding gives the average length of $2.1$, which is greater than using a code of fixed length $2$, so it can't be correct. If you follow the priority queue algorithm from the source you cite, then you would notice that after merging nodes 3 ...

2

The average codeword length of your professor's code is $2.577$. The average codeword length of your code is $2.662$. Huffman's algorithm produces a code minimizing the average codeword length. You draw the conclusions.

2

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 created by concatenating 5 of the original symbols, each with probability 1/243. Which is much closer to 1/256. The optimal Huffman encoding will encode 13 of ...

2

If you normalize the frequencies so that they add to 1, then the weight of the tree is just the average codeword length, which is exactly what Huffman's algorithm tries to minimize. Check this section of the Wikipedia article you link to.

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