Questions tagged [huffman-coding]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
25 views

Adaptive arithmetic coding confusion

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 ...
0
votes
0answers
14 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{...
1
vote
3answers
135 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 ...
0
votes
0answers
30 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 ...
2
votes
1answer
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 (...
1
vote
0answers
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 ...
0
votes
1answer
51 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, ...
1
vote
2answers
44 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 ...
1
vote
0answers
193 views

Advantages/Disadvantages of adaptive contexual arithmetic coding

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 ...
1
vote
1answer
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. ...
0
votes
1answer
165 views

Efficient serialization/deserialization of huffman tree

I have implemented huffman encoding in the form ...
2
votes
2answers
262 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
250 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
105 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 ...
5
votes
1answer
129 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
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 ...
1
vote
0answers
32 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
252 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
23 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
159 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
165 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
214 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 ...
3
votes
2answers
296 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: ...
2
votes
2answers
126 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
36 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
1k 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
2k 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
655 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
43 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
185 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
164 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
63 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
121 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
246 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
266 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
382 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
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 ...
0
votes
0answers
123 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
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 ...
0
votes
0answers
67 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
136 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
277 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 ...
6
votes
3answers
879 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
455 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
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, $...
5
votes
1answer
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 ...
0
votes
2answers
148 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
771 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
217 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. ...