Qbasicnews.com

QbasicNews.Com => Challenges => Topic started by: aetherfox on January 07, 2005, 09:44:49 AM



Title: Basic Compression Challenge
Post by: aetherfox on January 07, 2005, 09:44:49 AM
It's been almost quiet here...so I decided to start this challenge.

Your task is to write a compression alogrithm and a simple test program to showcase the features.

The compression alogrithm must be written entirely without external libraries or links.  You can do it in either freeBASIC or QB.

The sample program can be a simple commandline program that asks for a string and the compression ratio or whatever.

I'm not looking for RAR-level compression, even if you shave of 5% that will be good.

Also, if the code was commented with an explanation of how the compression works, that would be really nice.

To tell you the truth I know almost nothing about compression, and this is a way for me to learn.

Good luck!


Title: Basic Compression Challenge
Post by: shiftLynx on January 07, 2005, 01:40:20 PM
You say "write an algorithm"... do you mean invent one, or use an existing one?

-shiftLynx


Title: Basic Compression Challenge
Post by: DrV on January 08, 2005, 02:12:21 PM
Does it need to have a decompressor as well, or can we just chop off the last 20 bytes and say "It's 20 bytes smaller! I r0x0rz!"?


Title: Basic Compression Challenge
Post by: aetherfox on January 08, 2005, 02:44:39 PM
By write an alogrithm, I meant you can invent one if you like ( :o good luck :D) or implement an existing one.

And yes, obviously it should be able to decompress, I thought that was fairly obvious.


Title: Basic Compression Challenge
Post by: Diroga on January 09, 2005, 12:45:03 AM
doesnt compression look for patterens in data that it can represent in a smaller way?


Title: Basic Compression Challenge
Post by: Z!re on January 09, 2005, 01:12:51 AM
When testing the algos, on what files will it be done?

Flat files?
Repeating files?
Random files?

Flat means, for example, 10MB of chr0
Repeating means: ABCABCABCABCABC[...]
Random.. take a wild guess...


One algo might do wonders on flat files (RLE for example) but the same algo might not work at all on random files (RLE can't do shit about random files, and can even result in negative compression...)


So when testing/judging, you should try the algo on all three files, or have it categorized, like:
Best flat compressor by: [Author] [compress %]
Best repeating compressor by: [Author] [compress %]
Best random compressor by: [Author] [compress %]


Title: Basic Compression Challenge
Post by: aetherfox on January 09, 2005, 09:32:01 AM
Oh ok cool, I didn't know there was so much to it.

Revised rules :

Create a small commandline program in either QB or fB that will demonstrate the use of a compression/decompression alogrithm you have coded (invented or implemented) on flat, repeated and random data.  The program should give information about the compression rate for the given files.

Sample output:

Avi's Sample Compression Program
Coded in freeBASIC.

Compressing: Flatfile
Decompressing...Done!

Compressing: Repeated
Decompressing...Done!

Compressing: Random
Decompressing...Done!

Compression Ratios:
Flat: ##%
Repeated: ##%
Random: ##%


Title: Basic Compression Challenge
Post by: Neo on January 14, 2005, 01:52:22 PM
http://www.qbnz.com/harsoft/NeoCL.zip


Title: Basic Compression Challenge
Post by: Spotted Cheetah on January 14, 2005, 08:31:08 PM
I think i will not win, but can i sign in with our QBasic Sprite Editor's PCX compressor? (I know it is not a hard think but i worked a lot on it to optimize everything for x sizes not dividable by 8. Try saving some PCXs with it...) You can download the sprite editor with source on our page, just create some image, or import a 16 color BMP, and test it's compression ratio or compare to some usual commercial programs. It was written almost a half year ago, so i do not know now where is the compressor in the code, but it is somewhere in one piece (not divided into SUBs).