Re: A85: Compress levels

[Prev][Next][Index][Thread]

Re: A85: Compress levels


You description of how Huffman coding works is not completely correct, for
exampel take the following symbols with the shown probabilities.

A 1/4 
B 1/4
C 1/8
D 1/8
E 1/8 
F 1/8

Your method would give somthing like this

A = 1 B = 10 C = 110 D = 1110 E=11110 F = 111110

(Average code length : 2/8+4/8+3/8+4/8+5/8+6/8 =(2+4+3+4+5+6)/8 = 3)

"Normal" huffman coding would give something like this

A = 10 B = 11 C=010 D = 011 E = 000 F = 001

(Average code length : 4/8+4/8+3/8+3/8+3/8+3/8 = (4+4+3+3+3+3)/8 = 2.5)

As you can see your method gives a result which is longer then the
"normal" Huffman coding. (The entropy of the sequence is 2.5 and Huffman
coding reaches entropy when the probabilities is a power of 1/2 so 2.5 is
the correct result.)

Dines

BTW PkZip uses LZ coding as far as I know, not Huffman.
-----Original Message-----
From: Jon Olson <morph@jmss.com>
To: assembly-85@lists.ticalc.org <assembly-85@lists.ticalc.org>
Date: 21. marts 1998 18:25
Subject: Re: A85: Compress levels


>
>
>In case the guy doesn't release the source to hufflib - here's how
>huffman compression works.
>
>Basically, first it finds out what the most common bit combination is.
For
>example, let's say we're working with an alphanumeric string.
>
>ABCDEFABCDEABCDABCABA
>
>Huffman would go through and find the most common letter, second, third,
>etc.
>
>In this string, A is the most common letter, so it would be assigned the
>bit pattern: 0
>that way it only takes up 1 bit.
>
>Next most comon is B, B would be assigned 10
>C 110
>D 1110
>E 11110
>F 111110
>
>This way, the most commonly used letters (or in your case, bytes) will
>only take up 1 or 2 bits instead of the full 8. It's fairly efficient
>compression. (This is part of what pkZip uses).
>
>-- Jon Olson
>
>
>On Sat, 21 Mar 1998, Michael Pearce wrote:
>
>> 
>> My game levels will be very irregular since there is no scrolling.
>> every thing is on screen at once.  would you release the source to
>> hufflib (or send me the source)?  BTW, i should have a new beta of
>> solomon's key out by the end of spring break with 90% of the features.
>> i was planning on finishing the game this spring break, but lots of
>> stuff has come up lately.
>> 
>> >
>> >A lot better than RLE (which PCX uses) if the level is irregular
>> >(ie lot of details). A level which is less details (ie, only
>> >the important stuff like bricks, blocks, earth etc) could
>> >be better using RLE, but I doubt it.
>> >
>> >--
>> >Real name: Jimmy Mårdell                 
>> >IRC......: Yarin                         
>> >Email....: mailto:yarin@acc.umu.se      <-- NEW E-MAIL ADDRESS!!!!
>> >Homepage.: http://www.algonet.se/~mja/
>> >
>> 
>> 
>> -mike
>>  mgp4007@omega.uta.edu
>> 
>
>

_______________________________________

Dines Justesen
Email: dines@post1.com or
       c958362@student.dtu.dk
WWW  : http://www.gbar.dtu.dk/~c958362/
_______________________________________
Follow-Ups: