Knowing the frequencies of each symbol, is it possible to determine the maximum height of the tree without applying the Huffman algorithm? Is there a formula that gives this tree height?
$\begingroup$
$\endgroup$
7
-
1$\begingroup$ Try playing around with a few examples, and see if you can find any useful criterion. That's what I would do if I were trying to answer your question, but it's probably better for you to do it yourself... $\endgroup$– Yuval FilmusFeb 6, 2014 at 19:14
-
$\begingroup$ Yes, I've already tried with a lot of examples, but I'm looking for a litteral expression, for instance an asymptotic bound, function of the number of symbols... $\endgroup$– user7060Feb 6, 2014 at 19:35
-
1$\begingroup$ In terms of the number of symbols, you can't do anything better than $n-1$ on the one hand, and $\lceil \log_2 n \rceil$ on the other. $\endgroup$– Yuval FilmusFeb 6, 2014 at 21:20
-
$\begingroup$ Sorry. I was thinking about the number of symbols and their frequencies. For instance, maybe it is possible to give the maximal depth by looking simply the lowest frequency among all the symbols ? $n-1$ is a rought bound on the depth, I'm interested in a tight bound. $\endgroup$– user7060Feb 6, 2014 at 21:24
-
$\begingroup$ I would try to look at $\max -\log_2 p_i$ and see if it's related to the depth. You can also try to come up with the recursion corresponding to the actual algorithm, and see if it gives you anything. $\endgroup$– Yuval FilmusFeb 6, 2014 at 22:32
|
Show 2 more comments
3 Answers
$\begingroup$
$\endgroup$
Huffman coding (asymptotically) gets within one bit of the entropy of the sequence. This means that if you calculate the entropy of your symbol frequencies, you will be (asymptotically) within one bit of the average length (i.e. height) of your code. You can use this average to bound the longest length (on average), or you can use combinatorial methods to get determinsitic bounds.
$\begingroup$
$\endgroup$
2
The pathological case would be when the sorted symbol frequency resembles that of Fibonacci sequence. N:= # of symbols. for N>2, max possible height: N-1. for N == 1 or 2: 1
-
1$\begingroup$ This is not what the question asks. $\endgroup$ Jul 28, 2016 at 7:32
-
$\begingroup$ Indeed. The question asks for any-case whil you talk about worst-case. $\endgroup$– Raphael ♦Jul 28, 2016 at 7:37
$\begingroup$
$\endgroup$
According to this paper,
it is shown that if $p$ is the range $0<p\leq 1/2$, and if $K$ is the unique index such that $1/F_{K+3}< p \leq 1/F_{K+2}$, where $F_K$ denotes the $K$-th Fibonacci number, then the longest Huffman codeword for a source whose least probability is $p$ is at most $K$, and no better bound is possible.
use std::io;
fn find_k(p: f64) -> Option<usize> {
let (mut a, mut b, mut c) = (0, 1, 1); // starting with the first three Fibonacci numbers
let mut i = 0;
loop {
if (1.0/c as f64) < p && p <= (1.0/b as f64) {
return Some(i - 1);
}
// rolling the Fibonacci sequence
let temp_a = b;
let temp_b = c;
c = b + c;
a = temp_a;
b = temp_b;
i += 1;
// if i > 1e299 as usize { // added a safety measure to prevent potential infinite loops
// break;
// }
}
return None; // K not found for given constraints
}
fn main() {
let mut input = String::new();
io::stdin().read_line(&mut input).unwrap();
let p: f64 = input.trim().parse().unwrap();
input.clear();
match find_k(p) {
Some(k) => println!("{}", k),
None => println!("No suitable K found.")
}
}
