Initial setup(upset)
One day I was sitting idle and was thinking of why I can't compress my file after a certain level. So I came up with an Idea that we can divide a byte to two parts and then apply compression algorithm. I know that was stupidity but I tried it. I coded in c and divided each byte of a file into two parts four bits each. To understand what good will happen by doing so you must know about law of probability. Suppose a byte can have 8 bits so there can be 256 different combinations possible from 8 bits, thus it will become harder to find a pattern in the file( and FYI most compression mechanisms find pattern).
So I though that 4 bits will reduce the possible cases to only 16 different combinations which will increase pattern finding capability by 16 times( I guess), while just increasing the file size by two times. I found that though it does help in compression(mostly) but always increased compression ratio. Finally I gave up thinking that file compression is not possible this way, but I learned a good lesson. If 1 Mb file (suppose abc.xyz) is compressed to zip it becomes 0.8 Mb file, while when it is passed through my algorithm it makes abc.psl of file size 2Mb but when it is zipped it will give a 1 Mb(approx.) file.
functions to convert byte to bits and dividing it to twochar*byteToBits(char byte){
unsigned char i;
unsigned char *bits;
bits=(char *)malloc(8);
for(i=0;i<8;i++){
bits[i]=byte>>(7-i);
bits[i]=bits[i]<<7;
bits[i]=bits[i]>>7;
}
return bits;
}
char*byteToTwo(char byte){
unsigned char i;
unsigned char *bits;
bits=(char *)malloc(2);
bits[0]=byte>>4;
bits[1]=byte<<4;
bits[1]=bits[1]>>4;
return bits;
}
New approach
After a while I again started concentrating on files/bits/bytes. This time I experimented on many different files. I had two different ideas in my mind. But before that I will discuss my experiment:
This graph is just like all other graphs my initial experiment drew. This graph is having values of count of each value from 0-15. In this experiment I came to know that in general every file has some top contributing hexadecimal values while other just contribute to the very least. Taking top four values will make 70-80%(approx.) of the total file. So we can have an opportunity to reduce the file size by rearranging bits of the file. But for that You have to get out of 8bit=1byte model. Think a file as a large array of ones and zeroes i.e bits, divide this array into four-four bit chunks. You will get an array whose data will always vary from 0-15. Now you will get an opportunity to reduce file size by having some encoding formula by which you can shrink these 4 bits. My first Idea was :
- To compress 4 bit number the only way was to compress it in 3 bits; if I do so, I can only do this on selected 4 numbers.
- The total frequency of those select 4 numbers must be greater than total frequency of rest of the hexadecimal(4 bit) numbers.
- To pack four bits into 3 bits the first bit will be used for distinguishing between others and top 4 frequent hexadecimal numbers.
- First two bytes of the file will have these four numbers.
- To represent rest of the numbers we will use 5 bits and first bit will be used for distinguishing.
Now lets start with an example the good old one "The quick brown fox jumps over the lazy dog".
The above line has 44 characters, and when byte 1 byte to two 4 bits number each I got:
5 4 6 8 6 5 2 0 7 1 7 5 6 9 6 3 6 11 2 0 6 2 7 2 6 15 7 7 6 14 2 0 6 6 6 15 7 8 2 0 6 10 7 5 6 13 7 0 7 3 2 0 6 15 7 6 6 5 7 2 2 0 7 4 6 8 6 5 2 0 6 12 6 1 7 10 7 9 2 0 6 4 6 15 6 7 0 10
When I counted frequency and arranged them in decreasing order I got:
6 23
7 15
2 11
0 10
5 6
15 4
4 3
8 3
10 3
1 2
3 2
9 2
11 1
12 1
13 1
14 1
thus I got 88 numbers in total and sum of top four numbers will be 23+15+11+10=59. Thus I got frequency of top four numbers greater than 50% of 88. When I will write compressed file It will be in following format:
67 20 [0]5 [0]4 [100] [0]8 [100] [0]5 [110] [111] [101] [0]1 [101] [0]5 [100] [0]9 [100] [0]3 [100] [0]11 [110] [111] [100] [110] [101] [110] [100] [0]15 [101] [101] [100] [0]14 [110] [111] [100] [100] [100] [0]15 [101] [0]8 [110] [111] [100] [0]10 [101] [0]5 [100] [0]13 [101] [111] [101] [0]3 [110] [111] [100] [0]15 [101] [100] [100] [0]5 [101] [110] [110] [111] [101] [0]4 [100] [0]8 [100] [0]5 [110] [111] [100] [0]12 [100] [0]1 [101] [0]10 [101] [0]9 [110] [111] [100] [0]4 [100] [0]15 [100] [101] [111] [0]10
numbers in square bracket represent bits
thus using this approach I was able to save 30 bits i.e. 3 bytes when huffman encoding failed to do so. I will post my second Idea and other ideas relating to this type of compression in upcoming blogs.
to be continued....
No comments:
Post a Comment