New Wave Compression

[reaction]

Hello!

I have posted an article on my website http://www.optionalreaction.net about 3 Bit Compression.

As far as I'm aware, this has never been used before.

Regards,
OptionalReaction

[galathaea]

I can get to your link, but the site seems to not show anything to me until my mouse hovers over. Then, those links don't seem to work (in fact they seem to have alternating \ / directions on path...). Well, viewing on a mac, so I'll try PC tomorrow. Wish I coulda seen it, though. You intrigued me.

[reaction]

Thnanks galathaea,

All I know is that it works OK using IE6.

I might have to simplify the website.

[Simon666]

What do you mean with "scan the data converting the chosen
number to 11"?

[reaction]

Hi,

What I mean is ...

If the 'chosen number', i.e. the most popular number, is found, whilst scanning the bit stream 3 bits at a time, replace the 3 bit number with the 2 bit combo, 11.

[Simon666]

Aha, after thinking a bit over it (forgive my slowness, I'm not a programmer by education) I think I understand now. If I type "3 bit compression" on Google, there is not much information, but it seems it has been done before. What compression rates do you expect compared to zipping for example?

[galathaea]

After battling through on my mac I have some most unfortunate news. Your algorithm is not as good as a standard huffman coding, and actually falls under the general systematics of substitution codings of which there are many resources. But do not let this discourage you. I once found this great multisection theorem on hypergeometric functions. I was so proud I brought it to one of my previous math professors who promptly pulled a book of his shelf and showed me it had been found in the mid 1800's. Such are the consequences of having a curious mind, and you'll find you will encounter this many more times in the future. But that is what has to happen if you really want to find new things.

[reaction]

I have revised the document with a worked example.

On large data samples, the method will be very good.

As long as there are more than 3 occurences of the chosen number, the data, post compression, will be smaller, and recursivly, this will accumulate.

R

[Yves M]

Well, you should maybe choose an example that actually compresses, rather than expands ;) (your example goes from 25 bits uncompressed to 29 bits "compressed" ;))

Anyways, as galathea has pointed out, the algorithm is unfortunately not very good. In case you haven't you should check out what Huffmann coding is and how it works.

[reaction]

Hello Yves,

I realise the error of the expanding compression. I have modified my statement.

What I am looking for is a reliable method to compress a bit stream to even 1 bit smaller, as this would, recursivly, mean good compression. I'm not looking for speed of compression and not necessarily decompression, but minimum compressed data size.

The expansion is caused by the original data size being to small, causing inefficient ratios (e.g. not enough chosen numbers to justify the record of the chosen number), and bad luck causing badly fitting number within the structure.

It appears that for every 2 Base 6 digits, the comparative data size will expand by 1 bit. This means to get a comapartive data size difference of zero, there needs to be a chosen number every 2 Base 6 numbers (ignoring the storage of the chosen number).

I'm considering possibly jogging the origin data to fit the structure better, and a larger data set would give more room for this.

My biggest problem at the moment is converting to Base 6, as 6^65536 is a large number.

R

BTW, I notice you are a Moderator. I wonder if it would be OK to link to this thread from my website?

[Yves M]

Originally posted by reaction
BTW, I notice you are a Moderator. I wonder if it would be OK to link to this thread from my website?
Sure :) Go ahead.

Well, the problem is not that easy. Compression depends a lot on the data it is working on. For any algorithm, you can come up with a dataset that is either made larger or left exactly the same size as the original. This makes sense, since otherwise any data could be compressed to 0 bits :p

So having to expand some data is OK and is found in most compression algorithms. Other algorithms expand the data set by appending some information used by the decompression routine.

I still strongly suggest you read about Huffmann compression. It is based on a similar idea and is a bit more efficient than your solution.

[reaction]

Yves,

Thanks for your reply. I was kinda thinking out loud here.

The chance of compression is actually less than 0.3333, and useless.

I'll look at the Huffman method and continue.

R