question 2

[brian p kennedy]

I have a problem with question 2.

it says that there is a sequence of letters for which Reverse Adaptive
produces an output that is atleast 10 times smaller than by static
Huffman. But the minimum amount of bits used to transmit a 16 bit
sequence would be 16. Is it even possible for there to be a 160 bit
output using just 3 letters and 16 bits?

[srinivas]

Yea, that was exactly what i was thinking too...3 letters and 16 symbols can
not give u an output that is 160 bits long. In static huffman, the max no.
of bits u cud get with tht wud be 23, which is something like 8 A's, 7 B's
and 1 C. So that means 1 bit to encode an A, and 2 bits to encode B's and
C's each.
Sid

Post by brian p kennedy
I have a problem with question 2.
it says that there is a sequence of letters for which Reverse Adaptive
produces an output that is atleast 10 times smaller than by static
Huffman. But the minimum amount of bits used to transmit a 16 bit
sequence would be 16. Is it even possible for there to be a 160 bit
output using just 3 letters and 16 bits?

[Usenet user]

Post by srinivas
Yea, that was exactly what i was thinking too...3 letters and 16 symbols can
not give u an output that is 160 bits long. In static huffman, the max no.
of bits u cud get with tht wud be 23, which is something like 8 A's, 7 B's
and 1 C. So that means 1 bit to encode an A, and 2 bits to encode B's and
C's each.
Sid

[quoted text muted]

Actually, the max for static huffman seems to be when you have 6 A's, 5
B's, and 5 C's; that would be 26 bits. Nontheless, this is not even close
to the 160 bits required to be 10x larger than any reverse adaptive

[Seven]

You guys aren't thinking about how the Reverse Adaptive formula works. A
header is sent that includes the frequencies which can be summed to get the
length of the file. For example, if a file has only one character, then
only the header will be transmitted and no data since the decoder sees there
is only one characater in the file and knows the length (sum of
frequencies).

[brian p kennedy]

Post by Seven
You guys aren't thinking about how the Reverse Adaptive formula works. A
header is sent that includes the frequencies which can be summed to get the
length of the file. For example, if a file has only one character, then
only the header will be transmitted and no data since the decoder sees there
is only one characater in the file and knows the length (sum of
frequencies).

But the question asks about the OUTPUT length being 10 times smaller
than that produced by the static, and not the length of the file.

[brian p kennedy]

Post by brian p kennedy

Post by Seven
You guys aren't thinking about how the Reverse Adaptive formula
works. A header is sent that includes the frequencies which can be
summed to get the length of the file. For example, if a file has only
one character, then only the header will be transmitted and no data
since the decoder sees there is only one characater in the file and
knows the length (sum of frequencies).

But the question asks about the OUTPUT length being 10 times smaller
than that produced by the static, and not the length of the file.

me = stupid = now i get it
thanks

[Dariush Griffin]

I noticed the same thing. I just generated a string that used 16 bits for
the Reverse Adaptive and 26 bits for static Huffman. Don't really know if
thats right.

Post by brian p kennedy
I have a problem with question 2.
it says that there is a sequence of letters for which Reverse Adaptive
produces an output that is atleast 10 times smaller than by static
Huffman. But the minimum amount of bits used to transmit a 16 bit
sequence would be 16. Is it even possible for there to be a 160 bit
output using just 3 letters and 16 bits?

---
Outgoing mail is certified Virus Free.
Checked by AVG anti-virus system (http://www.grisoft.com).
Version: 6.0.859 / Virus Database: 585 - Release Date: 2/14/2005

[Jack]

I think the idea is that if you know the frequencies-and thus the file
size- if the reverse adaptive algorithm has a tree with only one character
left in it, you can simply quit, because the decoder knows how many more of
that character need to be spat out.

Post by brian p kennedy
I have a problem with question 2.
it says that there is a sequence of letters for which Reverse Adaptive
produces an output that is atleast 10 times smaller than by static
Huffman. But the minimum amount of bits used to transmit a 16 bit
sequence would be 16. Is it even possible for there to be a 160 bit
output using just 3 letters and 16 bits?