CODEWITHSUNDEEP
arraysalgorithmio
Ahmed Fwela
Ahmed Fwela

Reputation: 973

logically Understanding a compression algorithm

this idea had been flowing in my head for 3 years and i am having problems to apply it i wanted to create a compression algorithm that cuts the file size in half

e.g. 8 mb to 4 mb

and with some searching and experience in programming i understood the following.
let's take a .txt file with letters (a,b,c,d)

using the IO.File.ReadAllBytes function , it gives the following array of bytes : ( 97 | 98 | 99 | 100 ) , which according to this : https://en.wikipedia.org/wiki/ASCII#ASCII_control_code_chart is the decimal value of the letter.

what i thought about was : how to mathematically cut this 4-membered-array to only 2-membered-array by combining each 2 members into a single member but you can't simply mathematically combine two numbers and simply reverse them back as you have many possibilities,e.g.
80 | 90 : 90+80=170 but there is no way to know that 170 was the result of 80+90 not like 100+70 or 110+60.
and even if you could overcome that , you would be limited by the maximum value of bytes (255 bytes) in a single member of the array.

i understand that most of the compression algorithms use the binary compression and they were successful,but imagine cutting a file size in half , i would like to hear your ideas on this.

Best Regards.

Upvotes: 0

Views: 58

Answers (1)

Matt Timmermans
Matt Timmermans

Reputation: 59154

It's impossible to make a compression algorithm that makes every file shorter. The proof is called the "counting argument", and it's easy:

There are 256^L possible files of length L.

Lets say there are N(L) possible files with length < L.

If you do the math, you find that 256^L = 255*N(L)+1

So. You obviously cannot compress every file of length L, because there just aren't enough shorter files to hold them uniquely. If you made a compressor that always shortened a file of length L, then MANY files would have to compress to the same shorter file, and of course you could only get one of them back on decompression.

In fact, there are more than 255 times as many files of length L as there are shorter files, so you can't even compress most files of length L. Only a small proportion can actually get shorter.

This is explained pretty well (again) in the comp.compression FAQ: http://www.faqs.org/faqs/compression-faq/part1/section-8.html

EDIT: So maybe you're now wondering what this compression stuff is all about...

Well, the vast majority of those "all possible files of length L" are random garbage. Lossless data compression works by assigning shorter representations (the output files) to the files we actually use.

For example, Huffman encoding works character by character and uses fewer bits to write the most common characters. "e" occurs in text more often than "q", for example, so it might spend only 3 bits to write "e"s, but 7 bits to write "q"s. bytes that hardly ever occur, like character 131 may be written with 9 or 10 bits -- longer than the 8-bit bytes they came from. On average you can compress simple English text by almost half this way.

LZ and similar compressors (like PKZIP, etc) remember all the strings that occur in the file, and assign shorter encodings to strings that have already occurred, and longer encodings to strings that have not yet been seen. This works even better since it takes into account more information about the context of every character encoded. On average, it will take fewer bits to write "boy" than "boe", because "boy" occurs more often, even though "e" is more common than "y".

Since it's all about predicting the characteristics of the files you actually use, it's a bit of a black art, and different kinds of compressors work better or worse on different kinds of data -- that's why there are so many different algorithms.

Upvotes: 2

Related Questions