Questions tagged [huffman-coding]

The tag has no usage guidance.

2
votes
2answers
92 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 ...
2
votes
1answer
29 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 ...
2
votes
1answer
45 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 ...
0
votes
0answers
25 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 ...
5
votes
1answer
57 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 ...
4
votes
1answer
690 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 ...
1
vote
0answers
23 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 "...
3
votes
1answer
82 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 ...
1
vote
1answer
15 views

Prove the MinAveCodeLen of a product information source is less than the sum of that of the multiplicand and multiplier source?

The product of 2 independent sources $(S_A,P_A)$ and $(S_B,P_B)$ is defined as $$ (S,P)\text{ s.t. }S = \{s_As_B|s_A\in S_A,s_B\in B\}\text{ and }\ P(s_As_B) = P_A(s_A)\cdot P_B(s_B)\,\forall s_A\in ...
1
vote
2answers
58 views

Why it is not a Huffman code

I have been given several examples I the aim is to explain why it is not a Huffman code. So, for instance, the first one was: $\{00,01,10,110\}$ This code is not Huffman becuase it has just one ...
2
votes
1answer
67 views

Are Huffman codes self-synchronizing?

A code is (statistically) self-synchronizing if, given that the transmitted string is long enough, the receiver is guaranteed to eventually synchronize with the sender, even if bit flips or slips have ...
2
votes
1answer
78 views

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

When storing the encoded Huffman bit stream in bytes, in general, either the final byte gets padded or a pseudo end-of-file symbol gets used In the former case, the number of bits padded needs to be ...
2
votes
1answer
62 views

Compression algorithms for small strings - building upon / extending Huffman

I'm exploring algorithms to compress small strings like the following - every line is to be compressed individually, i.e. even those small strings should get compressed: ...
1
vote
2answers
74 views

Infinite Huffman Tree

We have to derive an optimal binary encoding for the infinite set of symbols $\{s_1, s_2, \dots \}$. They're distribution is given by $$p(s_i) = 9 \cdot 10^{-i}$$ My intuition was to use a Huffman ...
3
votes
0answers
32 views

Eke a better compression ratio out of Huffman coding by mixing 1-grams and 2-grams

Huffman coding is already doing a great job at compressing ascii bytes for data with a distribution like the following ...
0
votes
1answer
169 views

Why some Huffman codes have efficiency better than others?

Consider the alphabet $\mathcal{A}=\{a_0,a_1,a_2,a_3\}$ with the the following corresponding probabilities: $\, p_{A,1}=\{0.5,0.3,0.15,0.05\}$ $\, p_{A,2}=\{0.5,0.25,0.125,0.125\}$ The entropy for ...
2
votes
2answers
568 views

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

I am new to Huffman coding and I find myself facing a lot of confusion as to how to determine if a code is Huffman or not without having the probabilities associated to each codeword. I know one way ...
2
votes
1answer
282 views

Is huffman coding tree a heap or a trie?

I study Huffman Coding tree from "Data Structures and Algorithm Analysis" of Shaffer and it says that Huffman Coding tree is an opportunity to experience a search trie. However, the code implements it ...
1
vote
1answer
40 views

Huffman Coding - probabilities

I am having trouble understanding a question related to Huffman Coding. We haven't studied it a lot, so I am not even sure how to start. Given $n ≥ 2$ characters, with probabilities $p_{1} \geq p_{2} ...
2
votes
1answer
158 views

Weighted probability using Huffman Tree

I want to produce a value from a set, where each value has an associated weight. Eg: [(1, 4), (2, 3), (3, 3)] should give me a 40% chance of picking 1, and a 30%...
1
vote
1answer
103 views

Was my Huffman coding solution wrong?

I finished my exam a moment ago and one of the question was to calculate Huffman coding for given probabilities: A: 0.15 B: 0.2 C: 0.55 D: 0.1 I encoded them as ...
0
votes
0answers
53 views

Does Huffman Encoding produce the only optimal String?

I know that Huffman coding produces an optimal solution, but are there any more solutions using the same number of bits (not including just flipping the ones and zeros or switching the encoding for ...
1
vote
1answer
83 views

Problem with determining the shape and direction of the Huffman Diagram

I have the phrase "abracadabra" and I want to encode it through the Huffman method. I first took the frequencies of each letters; $$a=5$$ $$b=3$$ $$c=1$$ $$d=2$$ $$r=2$$ But I'm not sure as to how the ...
2
votes
1answer
153 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 ...
1
vote
1answer
197 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 ...
1
vote
0answers
284 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: ...
0
votes
1answer
25 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 ...
0
votes
0answers
84 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, ...
3
votes
4answers
3k 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 ...
0
votes
0answers
58 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: ...
2
votes
1answer
102 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 ...
1
vote
1answer
199 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 ...
5
votes
3answers
596 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 ...
0
votes
1answer
350 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 ...
1
vote
1answer
834 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, $...
5
votes
1answer
717 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 ...
0
votes
2answers
110 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, ...
1
vote
1answer
2k views

Is huffman-encoding with distinct frequencies of symbols unique?

Say I have following text: "abbcccddddeeeee". As you can see, each letter has a different frequency of occurence. When making a Huffman-Trie to encode this String, will this trie be unique? I thought ...
2
votes
2answers
486 views

Is It possible to change the side of 0 and 1 in Huffman tree?

When we are constructing the Huffman tree to get the Huffman codes, Is it possible to give "1" to left side and "0" to right side rather than giving "0" to left side and "1" to right side of the tree?
1
vote
0answers
166 views

Number of unique prefixes in canonical huffman tree

I am trying to implement decompression algorithm based on huffman trees. I am trying to validate my assumptions. Assume that you have alphabet of 350 symbols. Maximum encoded code length is 15 bits. ...
0
votes
1answer
390 views

exercise on Huffman encode

I have these 4 symbols with their probabilities: x P(x) -------- 1 0.3 2 0.3 3 0.2 4 0.2 I built the Huffman tree in this way: and I obtainded: ...
0
votes
1answer
420 views

Please check my Huffman tree [closed]

My professor gave an example of Huffman tree. Given inputs a 80 b 10 c 20 d 50 e 100 f 35 g 60 … then the tree will be: But when i tried to solve it at home, I ...
3
votes
1answer
4k views

When would the worst case for Huffman coding occur?

I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the ...
17
votes
4answers
5k views

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

...
2
votes
1answer
70 views

Average prefix code length of every 4-sized frequency vector is bounded at 2

I'm trying to show that for every frequency vector $(p_1, p_2, p_3, p_4)$ such that $\sum_{i=1}^4 p_i=1$, the average word length outputted by Huffman algorithm is bounded at 2: If $(w_1,w_2,w_3,w_4)$ ...
0
votes
1answer
173 views

Does Huffman algorithm generate a minimal weight of a tree?

Does Huffman algorithm generate a minimal weight of a tree? I noticed that by trying to make two different trees with the same frequencies of letters, I get different weights of the trees. We ...
1
vote
1answer
449 views

Why should I use Huffman enoding if it makes my data longer?

I have a requirement to reduce the size of the request / response XML by compressing repetitive productID data in compatible tag. My request / response xml looks something like below ...
1
vote
2answers
5k views

Huffman Coding vs LZW Algorithm

I'm trying to understand comparisons between the two. Is there ever a case where is it better to use Huffman Coding over LZW? Could the compression ratio for Huffman ever surpass that of LZW? Thanks!...
5
votes
0answers
176 views

Average redundancy in Huffman or Hu-Tucker codes on random symbol probabilities

Huffman and Hu-Tucker codes are well-known compression schemes, which both come close to the entropy lower bound. It is known that if $L_1$ and $L_2$ are the lengths of a Huffman resp. Hu-Tucker code, ...
6
votes
1answer
963 views

Huffman Code VS Hu–Tucker Code

Before I'll ask my question, let me start with my understanding of the definitions, to prevent myself with further confusion, as well as giving some background. Huffman Code is the binary-code ...