| Current Forum: Homework 4 - Huffman Trees (Part 1) |
| Date: Sat Oct 6 2001 2:39 pm |
| Author: Cipriani, Jason A. <jac4@andrew.cmu.edu> |
| Subject: Re: Best way to store the code table |
|
|
uh... no, that is incorrect. i generated a test file that builds a huffman tree that is 35 levels deep. the only reason i couldn't make it go deeper is disk space requirements and it took a long time.
if the optimized tree looks like this:
*
/ \
* A
/ \
* B
/ \
* C
/ \
* D
/ \
* E
/ \
* F
/ \
* G
/ \
* H
/ \
* I
/ \
J K
then the code for K is 0000000001 -- 10 bits. and 10 is greater then 8.... unless i'm doing something REALLY stupid that i can't see.
the following frequency table would generate a tree like that:
A - 177
B - 109
C - 67
D - 41
E - 25
F - 15
G - 9
H - 5
I - 3
J - 1
K - 1
i know its a weird sequence, but its the one i used to test my stuff because i knew it was the only one that could make a real deep tree. it's like the fibonacci sequence, but you add an extra 1 to each term.
so... uh... yeah.
jason |
|