PDA

View Full Version : Project - Compression Utility


Rogue
09-11-2004, 06:55 PM
I have to do a project for one of my classes, and stuff that I'll be doing is somewhat interesting.

I have to create compression utility.

Most of us use WinZip and other compression utilities all the time, but have you ever asked your self how does really compression utility works? (Well, before this class I did not either).

So to start, simple question, any idea how all this works?

ps. This topics is aimed to learn some new stuff, help me to review and make sure my algorithm, planning and other stuff works. Later I'll add what are specifications and requirements for the project, but this should be enough for start.

:cheers:

Wael
09-11-2004, 07:27 PM
ftp://rtfm.mit.edu/pub/usenet/news.answers/compression-faq/
A data compression FAQ in three parts

http://datacompression.info/Compression.shtml
Data compression books, links etc...

http://www.hn.is.uec.ac.jp/~arimura/compression_links.html
Data compression links

Did a little search,

Hope it helps...

Braindead
09-11-2004, 08:04 PM
I think the easiest way of compressing something is to use Huffman btrees and it actually also returns you with a very good compression rate, although building the tree can be a bit slow... :)

Caged
09-11-2004, 09:04 PM
hehe, this guy is a genious. He asks an interesting question and all is good and fun while abandonians do his homework, LOL.

I salute you you master expert!

Rogue
10-11-2004, 01:45 AM
Originally posted by Caged@Nov 9 2004, 10:04 PM
hehe, this guy is a genious. He asks an interesting question and all is good and fun while abandonians do his homework, LOL.

I salute you you master expert!
I did not ask for any code or help with homework. :blink: you are wery wrong... :bleh:

All I like to do is to make this interesting topic (because I think it is interesting) that will help people better understand programming, coding, algorithms, etc...

I have almost done planning stage, and will post it later.

Now, back to requirements:

Program should be made my using Huffman encoding and binary threes.

To start lets first take a look how does computer stores files.

Smallest piece of information that program stores is 1 byte, which is made of 8 bites. Each bite can have one of two values: 1 (true) or 0 (false). Combining these you can get 256 different characters out of 8 bits (28).
As example, I attached table with bits, values and then example how different combination of bits creates different numbers (which refer to ASCII table).

So each character in text file is represent by single byte, and with Huffman encoding and binary three we will change the most frequent characters to be represent with couple bits, while less used characters will be represent with more bits. This way we will save a lot of space.

So this is some sort of introduction.

Wael, thanks for the links. I'll check them tomorrow.

Eagle of Fire
10-11-2004, 03:52 AM
Most of us use WinZip and other compression utilities all the time, but have you ever asked your self how does really compression utility works?

Well, in fact I did. I am no expect so I did not come up with a good answer, but I always thought that compression utilities were only reducing a file into it's most primitive definition, just like they teach you at school with algebra (taking an algoritm and reducing it at it's simpliest form).

I however have no idea whatsoever on how this could truely be done in practice...

Wael
10-11-2004, 04:51 AM
Originally posted by Anubis@Nov 10 2004, 02:45 AM
Wael, thanks for the links. I'll check them tomorrow.
Yes...

Donīt know if they help though,
my knowledge in this area is quite weak-