New Wave Compression

First of all; Have you implemented this? If you are the creator, you should supply "evidence". I get the feeling you are waiting for somebody else to implement this for you.

Second; If you really want to get "our kind" intressted in your idea you need to provide alot more technical data & specs. Prove your algorithm!

(Other than that, it looks intresting :-) )

You seem to think that your algorithm can losslessly compress all files of a sufficiently large size. Unfortunately, such algorithms are provably impossible (there are less files of length (0..n-1) than there are files of length n).

Let''s try out your algorithm:

Input is: 134665747 (base 10)

1. Convert data to Base 6.
Input is: 21210204311 (base 6)

2. Choose the most commonly occuring number, from 0-5, and record.
Most common number is 1.
Output: 1

3. Convert data to Base 2...
Input is: 1000000001101101011000010011 (base 2)

...and scan the data converting the chosen number to 11. This converts a 3 bit number to 2 bit.
Output is: 1, 110000000011110111101101111000011001111

I did what you said, but I don''t think it''s what you meant.

Look up huffman encoding. It replaces fixed-length data chunks with variable-length ones, and is pretty good.

Elkas, I have revised the document with a worked example.

Beer Hunter, Yes that is the method I meant. I don't understand what you mean by there are less files of length (0..n-1). The larger the data, the more chosen number repeats will occur and the more space will be saved. As long as there are more than 3 chosen numbers, the data will be smaller, and recursively this will be good news.

BTW, I'm not aware of the Huffman Algorithm, I will look around for it.

R


Stop Spam!



[edited by - reaction on October 29, 2002 7:08:54 AM]

Hi

I just tried to compress a 32-bit-number with your compression rule, but it didn''t seem work (or I just did something wrong ):

base10: 3965247645
base2 : 11101100 01011000 11100000 10011101
base6 :   1 x 2176782336 + 4 x 362797056 + 5 x 60466176 +
          3 x 10077696 + 2 x 1679616 + 4 x 279936 +  5 x 46656 +
          0 x 7776 + 0 x 1296 + 3 x 216 + 5 x 36 + 5 x 6 + 3 x 1
        1453245003553

most popular number: 5

base6 to base2:  001 100 101 011 010 100 101 000 000 011 101 101 011     (39 bits)
replace 101   :  001 100 11  011 010 100 11  000 000 011 11  11  011     (35 bits > 32 bits )
 

And maybe you should check your example once again. In part 1 step 5 your base6-number is wrong (54524554 instead of 545424554). I didn''t take a look at the other parts yet

Hi Eimer, apologies for the mistake, I''m in a real hothouse at the mo.

I realise the error caused by your example is caused by the increase in bit count caused by the unconventional conversion from Base 6 to Base 2, where 32 bits = 39 bits.

I''m working on this and will reply when I know the answer.

R

Worth a try though

*smart_idiot is reminded of the horrors of the mp3 beating compression thread

The problem with the method is the increase in size of the bit stream in the conversion from Base 6 to Base 2.

It appears that for every 2 Base 6 digits, the bit stream will be 1 bit longer.

If this is constant, then a chosen number would have to occur once for every 2 Base 6 digits to create a bit stream of equal size. The chance of compression is less than 0.3333

If the occurence of chosen numbers is higher, compression will occur.

I suspect some sort of bias mechanism could cheaply throw the chosen number bias. Some sort of binary partition might help here also.

I'm having trouble calculating the Base 6 conversion though, as I've only got a 32 bit computer (that's about as good as they get around here ).

Alternatvely, the 11 trigger could be used to designate pattern repeats etc, without having to store the address of the repeat, which could be a large number, in a separate area of the compressed file.

R

Stop Spam!


[edited by - reaction on October 29, 2002 3:09:43 PM]

quote:

---

Original post by smart_idiot
*smart_idiot is reminded of the horrors of the mp3 beating compression thread

---

And there was that Lack of Knack guy who thought that it wasn''t possible to prove that that type of compression was impossible.

quote:

---

Original post by reaction
I suspect some sort of bias mechanism could cheaply throw the chosen number bias. Some sort of binary partition might help here also.

---

Sounding more and more like Huffman.

Hasn''t it been proven that Huffman is _the_ optimal compression for the class of entropy coding in a memoryless system?

Those who do not learn from history are doomed to repeat it.


Mike

"The state is that great fiction by which everyone tries to live at the expense of everyone else." - Frederick Bastiat, The Law