Text Compression Contest

OK, this is similar to sebastiani's contest, except there are no rules on what type of compression you use. The target is a txt file in ascii format.

Best compression within a reasonable time limit wins.

Implement your compression as a function that accepts a pointer to a zero terminated string consisting of the entire text of War and Peace as input and a dereferenced pointer (pointer to a pointer) where it should place the output. The function must also return the number of bytes used in the output. Below is an example declaration -

Code:

---

unsigned long abachler_compress(char* Input , unsigned char** Ouput);

---

Implement your decompressor as a function that takes a pointer to an array containing the compressed data, the size of the array, and returns a pointer to the decompressed output, which must be zero terminated. An example is below -

Code:

---

char* abachler_decompress(unsigned char* Input , unsigned long InputSize);

---

Rules -
Must be written in C++, C code is fine as long as it compiles as C++.
No use of global variables.
No use of the file system.
All code must be yours, no use of 3rd party compression libraries or API calls.
If your function crashes the application for any reason you lose.
Inline assembly is fine as long as it does not jump outside the assembly block.
Runtime is limited to 1 hour maximum on a Pentium 4 3.2 GHz with HT and 2GB ram.
You may use threads.
All submissions must be made by 23:59CST (-6 GMT) on 9/30/2009

The following is the main() function that will test the application I highly suggest you use this exact code for testing as no modifications will be made to accommodate anyones code. -

Code:

---

#include <malloc.h>
#include <stdio.h>

#define SIZE_OF_WAR_AND_PEACE 0 // will be actual size of the file

unsigned long abachler_compress(char* Input , unsigned char** Ouput);
char* abachler_decompress(unsigned char* Input , unsigned long InputSize);

int main(){

        FILE* pFile = fopen("warandpeace.txt" , "r+b");

        char* pRandomVariableName = (char*)malloc(SIZE_OF_WAR_AND_PEACE);
        fread(pRandomVariableName , 1 , SIZE_OF_WAR_AND_PEACE , pFile);
        fclose(pFile);
       
        unsigned char* pCompressed;
        unsigned long DataSize = abachler_compress(pRandomVariableName , &pCompressed);

        // compressed data may be copied to a new array at this point

        char* pDecompressed = abachler_decompress(pCompressed , DataSize);
               
        return 0;
        }

---

Quote:

---

Originally Posted by abachler

All code must be yours, no use of 3rd party compression libraries or API calls.

---

You might want to clarify if use of the standard library is allowed, and if use of libraries unrelated to compression (e.g., a library for threads) is allowed as long as the relevant library files are provided (and presumably the application is rejected if a reasonable attempt to compile it fails).

Quote:

---

Originally Posted by abachler

The following is the main() function that will test the application I highly suggest you use this exact code for testing as no modifications will be made to accommodate anyones code.

---

I suggest that you change <malloc.h> to <stdlib.h> since <malloc.h> is non-standard/pre-standard. The Comeau online compiler is an example of a rather standard conformant C++ compiler that does not accept your program due to a missing header file.

Very interesting. Even if I don't submit anything, I do think this will be a neat exercise.

Quote:

---

Originally Posted by abachler

no modifications will be made to accommodate anyones code.

---

Well, with the leak intact...

Code:

---

unsigned int compress(char* text, char** compressed)
{
    *compressed = text;
    return sizeof(*compressed);
}

char* decompress(char* compressed, unsigned int /*len*/)
{
    return compressed;
}

---

Quote:

---

Originally Posted by adeyblue

Well, with the leak intact...

---

There's no leak, windows implicitly frees the memory when the process terminates.

While your entry is technically valid, I'm not even going to bother running it since it will lose to any non-smartass entry.
It also fails to decompress the data properly. The last time i checked War and Peace was longer than 4 bytes.
Consider yourself disqualified.

Quote:

---

Originally Posted by laserlight

I suggest that you change <malloc.h> to <stdlib.h> since <malloc.h> is non-standard/pre-standard. The Comeau online compiler is an example of a rather standard conformant C++ compiler that does not accept your program due to a missing header file.

---

malloc.h is present on my system, and since you are not allowed to modify main() in any case it is irrelevant. If you require specific headers you need to include them in your submission. You can use any library you want with the caveat that I will not be linking OBJ LIB or DLL files to the project, so you either have to include something that comes standard with Visual Studio 2008 Express or figure out a way to include the source code for the libraries in your submission.

I would suggest you focus on the contest and not trying to nitpick the rules.

The rules have a gaping hole, in that they don't forbid the use of the actual text of War and Peace. I could embed a reference text in my program, and output the diff between that text and the input. If I got lucky and used exactly the same text you used (from Gutenberg, right?) I might have an output size of 0 bytes while remaining within the rules.

It's actually amazing that you selected that text, because it's the same text I use as a mid-size corpus for language processing experiments. I have a LOT of experience with that text, and I know its statistics and idiosyncracies ;)

Quote:

---

Originally Posted by brewbuck

The rules have a gaping hole, in that they don't forbid the use of the actual text of War and Peace. I could embed a reference text in my program, and output the diff between that text and the input. If I got lucky and used exactly the same text you used (from Gutenberg, right?) I might have an output size of 0 bytes while remaining within the rules.

It's actually amazing that you selected that text, because it's the same text I use as a mid-size corpus for language processing experiments. I have a LOT of experience with that text, and I know its statistics and idiosyncracies ;)

---

The gaping hole runs smack into cboards upload limit of course...
so no gaping hole. I also didn't specify what language it is in.

Since it's an ASCII file I would hazard a guess it is English.

Quote:

---

Originally Posted by abachler

The gaping hole runs smack into cboards upload limit of course...
so no gaping hole. I also didn't specify what language it is in.

---

I think it would be a good idea measure the size of BOTH the compressed text and the decompresser, like the calgary challenge. That would eliminate these kind of gaping holes.

Quote:

---

Originally Posted by whiteflags

Since it's an ASCII file I would hazard a guess it is English.

---

Don't bet on it, it could be in Klingon for all you know.

Quote:

---

Originally Posted by abachler

malloc.h is present on my system, and since you are not allowed to modify main() in any case it is irrelevant.

---

It is relevant because you are going to test with that code and you "highly suggest (submitters) use this exact code for testing as no modifications will be made to accommodate anyones code" (emphasis mine). Of course, it is only a theoretical problem since one should be able to safely change <malloc.h> to <stdlib.h> without fear that the code will work on their system but not on yours.

Quote:

---

Originally Posted by abachler

I would suggest you focus on the contest and not trying to nitpick the rules.

---

Hey, I am just trying to help you improve your contest rules :)

Quote:

---

Originally Posted by laserlight

Hey, I am just trying to help you improve your contest rules :)

---

There's nothing wrong with the rules as they are. No professional compiler would be so anal as to NOT include malloc.h if only for compatibility with pre-standard code. If your implementation doesn't support malloc.h then too bad, it's not my problem. As I said, I highly SUGGEST, you are free to do whatever you want, if it fails to run it fails to run. But, as laserlight pointed out, it is unlikely that any implementation would run with stdlib and fail to run with malloc. Since malloc is used in the main function, not in your function, you are free to include whatever headers you desire, within the limits of the contest.

As a sign of good faith, I will provide a very simple compressor. Obviously this doesn't meet the requirements of the contest, as I rolle dthe whole thing into main. it also suffers from poor compression because of a known weakness, that is each letter gets compressed by 2 bits, but every non letter, specifically spaces, eat an extra 6 bits. Overall it saved only 60KB out fo a 3MB file. Like I said its very crude compression.

Code:

---

int main(){
        char* pBuffer = (char*)malloc(1048576);

        FILE* pFile = fopen("e:\\warandpeace.txt" , "r+b");
        long BytesRead = -1;
        unsigned long ByteCount[256];
        for(int x = 0;x<256;x++) ByteCount[x] = 0;
        unsigned long TotalBytes = 0;
       
        while(BytesRead){
                BytesRead = fread(pBuffer , 1 , 1048576 , pFile);
                if(BytesRead) for(int x=0;x<BytesRead;x++) ByteCount[pBuffer[x]]++;
                TotalBytes += BytesRead;
                }

        fclose(pFile);

       
        pFile = 0;
        pFile = fopen("e:\\ByteCount.txt" , "w+b");
        long Index = 0;
        for(int x = 0;x<256;x++){
                fprintf(pFile , "%2.2x - %d%c%c" , x , ByteCount[x] , 13 , 10);
                if(ByteCount[x]) Index++;
                }
        fprintf(pFile , "%c%cTotal Symbols Used %d%c%c" , 13 , 10 , Index , 13 , 10);
        fclose(pFile);

        pBuffer = (char*)realloc(pBuffer , TotalBytes);

        pFile = fopen("e:\\warandpeace.txt" , "r+b");
        fread(pBuffer , 1 , TotalBytes , pFile);
        fclose(pFile);

        char* pOutput = (char*)malloc(TotalBytes);
        unsigned long BitCache = 0;
        long BitIndex = 0;
        Index = 0;

        pFile = fopen("e:\\warandpeace.paq" , "w+b");
        for(int x = 0;x<TotalBytes;x++){
                if((pBuffer[x] > 64) && (pBuffer[x] < 128)){
                        BitCache *= 64;
                        BitCache = BitCache & 0xFFFFFFC4;
                        BitCache = BitCache | (pBuffer[x] & 63);
                        BitIndex += 6;
                        } else {
                        BitCache *= 64;
                        BitCache = BitCache & 0xFFFFFFC4;
                        BitIndex += 6;

                        BitCache *= 256;
                        BitCache = BitCache & 0xFFFFFF00;
                        BitCache = BitCache | pBuffer[x];
                        BitIndex += 8;
                        }

                while(BitIndex > 7){
                        pOutput[Index] = BitCache & 0xFF;
                        BitCache /= 256;
                        BitCache = BitCache & 0x00FFFFFF;
                        BitIndex -= 8;
                        Index++;
                        }
                }

        while(BitIndex > 0){
                pOutput[Index] = BitCache & 0xFF;
                BitCache /= 256;
                BitCache = BitCache & 0x00FFFFFF;
                BitIndex -= 8;
                Index++;
                }
       
        fwrite(&TotalBytes , sizeof(unsigned long) , 1 , pFile);
        fwrite(&Index , sizeof(unsigned long) , 1 , pFile);
        fwrite(pOutput , 1 , Index , pFile);

        fclose(pFile);

        return 0;
        }

---

And of course, this is a "This is my contest. Take it or leave it. No comments or suggestions accepted nor welcomed" contest.

I've always wanted to make one that used a RNG to compress. The file would basically be just a set of 265 number pairs. The seed, and the skip. The seed would be the seed you need to use for the RNG to produce the required set, and the skip would be how far down that seed you need to skip before you can start using it. And also, the final size of the output file in bytes.

It would basically look like this:

Code:

---

type seedset[2][265];
for each of 256
    read pairs into seedset

for each of 256
    seed( seedset[0][x] )
    skip( seedset[1][x] ) // basically a loop to eat rand calls
    output x (where x is the current number 0 to 255 ) at rand()
    // say we're on loop 'a' ... here we skip, then we start outputting 'a' at rand()
    // position from where we last put an 'a' (or from byte 0 in the case of the first call)

---

In theory (monkeys and typewriters) it should be killer. You'd just need a quantum computer to calculate the 256 pairs you'd need to generate the correct output file.

It's still a fun idea.


Quzah.

Quote:

---

Originally Posted by quzah

I've always wanted to make one that used a RNG to compress. The file would basically be just a set of 265 number pairs. The seed, and the skip. The seed would be the seed you need to use for the RNG to produce the required set, and the skip would be how far down that seed you need to skip before you can start using it. And also, the final size of the output file in bytes.

It's still a fun idea.


Quzah.

---

So basically a bible code compressor using a an RNG with a run length of at least the factorial of 256^ length of the book. Yeah I'm thinking the seed would probably exceed the size of the original file. But it's a good idea anyway.

Quote:

---

Originally Posted by cyberfish

And of course, this is a "This is my contest. Take it or leave it. No comments or suggestions accepted nor welcomed" contest.

---

Yeah well we all know how 'some' people prefer to spend their time trying to break a contest, rather than taking part in it.

If you can't handle a difficult challenge, like writing an actual entry instead of trying to weasel the contest with return 0; entries, then you should probably just not read my contest threads. My contests generally require you to actually write code.

Quote:

---

Originally Posted by abachler

So basically a bible code compressor using a an RNG with a run length of at least the factorial of 256^ length of the book. Yeah I'm thinking the seed would probably exceed the size of the original file. But it's a good idea anyway.

---

You should be able to use digits of PI in the base of your choice. Pull a chain of how frequent each value is, and find a series of digits of _ that match that. You could set your skip bigger and wrap around from the end of the file to the start again, to get better results and fit your start/jump set in a smaller number of bites. For example, you could use 128 bits for each, and be skipping a billion digits of PI (or rand calls) per jump. In theory you should be able to pin down any file in what ... 8K? 128 * 256 * 2? Maybe my math is off, I'm tired. But considering you could do jumps in the millions if you needed to, it seams feasible. But like I said, computing it would be a lot of friggin work.


Quzah.

Quote:

---

Originally Posted by quzah

You should be able to use digits of PI in the base of your choice. Pull a chain of how frequent each value is, and find a series of digits of _ that match that.


Quzah.

---

Yes, but again, you have to store the index into pi where your sequence begins, which ostensibly will be larger than the length of the original data.

So it would work if you wanted to compress something that was found in the first umpteen bytes like the sequence 14159265, but it would not work for arbitrary data.

Say we use 128 bit keys. 2^128th is a pretty big number. Therefore, you could pick a starting digit of PI anywhere in there, and a skip number, anywhere in 2^128. All you need is a sequence of numbers that fall anywhere in 2^128 and repeats at a GCD that falls anywhere in 2^128 more jumps. But I don't know anything about cryptology, or compression (it's not interesting to me), it just seems like you could get the math to work, since those are absurdly big numbers.


Quzah.

Quote:

---

Originally Posted by quzah

Say we use 128 bit keys. 2^128th is a pretty big number. Therefore, you could pick a starting digit of PI anywhere in there, and a skip number, anywhere in 2^128. All you need is a sequence of numbers that fall anywhere in 2^128 and repeats at a GCD that falls anywhere in 2^128 more jumps. But I don't know anything about cryptology, or compression (it's not interesting to me), it just seems like you could get the math to work, since those are absurdly big numbers.


Quzah.

---

Your idea is interesting, and something I've pondered myself. But let's consider the conditions imposed on pi, if this were true. It would mean that it takes fewer than N digits to describe the offset within pi of any arbitrary N-digit sequence (this is the only way you can achieve compression). It's late, and I've had a few beers. But something tells me that such a number is a logical impossibility (whether that number is pi or otherwise).

the problem is that you arent compressing a single byte, you are compressing a sequence of bytes or bits either way, and to have a sequence with every possible subsequence of size N you need a minimum run length. e.g.

say I want to compress a series of 2 numbers with values ranging from 0 to 3. Ostensibly you can directly represent that with 4 bits. But to have a sequence with every possible run of 2 digits 0 to 3 takes

[00102031121312232330]010203112131223233

or 19 digits, since the start point can be anywhere from 0-18 it takes ln 19/ln 2 binary digits or 4.2479 bits just to represent the index, and you still need to represent the run length, which even if we assume is known to be 2 and takes no additional bits, still leaves you with a larger index than the original data.

Now that said, if we assume that we always use 2 bit sequences, we can achieve parity with any arbitrary bit sequence using

[0110]11

requiring 2 bits for the index (ln 4/ln 2)

with 1 bit we get parity as well. Since any arbitrary sequence of bits can be reduced to 1 or 2 bit sequences, we can always achieve parity by reduction, but with bit lengths longer than 2 it is not possible to fully represent every sequence of N bits in fewer than 2^N bits, which is the maximum index size that would achieve parity of compression.

If such a thing were possible it would be possible to achieve arbitrarily high compression ratios by simply compressing the compressed data repeatedly. So the challenge then to prove P or NP is to find a sequence of 2^N-1 bits that contain every possible combination of N bits.

It is sufficient to search for a sequence of 2^N-1 because any shorter sequence that properly encoded every combination could just be padded with 0's or 1's and would be a valid solution of 2^N-1 length.

Now I posit that there exists for any positive integer N a sequence of 2^N bits that contains every possible combination of N bits, if you allow wrapping from the end to the beginning, but that there exists no shorter sequence that fulfills the same requirement.

1 - 01
2 - 0011
3 - 00111010

Think of it as absurd RLE. But instead of a length of continuous characters, it's the distance you skip until you encounter the same character. I think. Anyway, I started to do something to see if it was possible, and the number gets insane very fast, and I'm probably off, because I'm being lazy and don't care to find an optimum way to do it.

Make an array of 1000 characters. That's our file, yeah, it's small. "fill it" by calling rand() %256, and only plotting the 'a' characters that result.

Code:

---

for( x = 0; x < 1000; x++ )
    array[ x ] = rand() % 256 == 'a' ? 'a' : 0;

---

Now, count up all the times you ran into an 'a' (or just simply print out the index of x when that happens. I got four, which is what we should expect. Multiply all of those indexes together.

Now, I think that if I start at the first one, and count ahead <sum> places, allowing for wrap, I should be able to stamp down an X at the first one, and again when I count <sum> more places, again, and again, and again, and have it just have filled in all four 'a's. Right? I donno, it's like 25,000,000,000,000 and some change, so it'll take a long ass time to find out. (GCD is what I'm thinking, I can't think right now, so that's probably wrong.)

Anyway, if that's true, all we should need is:

<byte value we're placing>, start position, skip value, number of 'a's in the file.

You wouldn't want to do this for small files, because the "rebuild" file would take up more space than a small file.
You actually wouldn't want to use it on huge files, because it would take forever to calculate the math to find out where everything ends up.

But, for the sake of argument, let's pretend we can do it (the math, and the jumps) instantly. Time isn't anything we care about. Could you, given where to start, how far to jump, and how many jumps it takes, fill in all of the 'a's in a file this way? It seems right in theory.

Edit: I think my math isn't working out with just multiplying them together. I'll fiddle with it later maybe. But I like the idea. It might be completely absurd, but I still like the idea.

Quzah.

Quote:

---

Originally Posted by quzah

But, for the sake of argument, let's pretend we can do it (the math, and the jumps) instantly. Time isn't anything we care about. Could you, given where to start, how far to jump, and how many jumps it takes, fill in all of the 'a's in a file this way? It seems right in theory.


Quzah.

---

That's what I was trying to explain in my post, its not possible, because no matter what sequence of bits you use, even pi, or any other constant, there exists no sequence of bits shorter than 2^N that encodes every combination of N bits., and since it takes at LEAST ln 2^N/ln 2 (i.e. N) bits to index into a bitfield of length 2^N, you can never achieve compression of arbitrary data.

I don't know. You can make it easier if you allow higher values to overwrite lower ones; this way you only have to have 'perfect encoding' of roughly half. Ok let's say this is our file:

01234869482348523198340

I start zero filled, so I don't need to actually store zeros. All I need are 1s that fit:

XY???????????????Y????X

So say my 1s produce:

X111???11???1??1?1??1?X

My 2s need to produce:

XXY???????Y????Y?X????X

And so on. Until finally we have to get an exact:

XXXXXXXYXXXXXXXXXXYXXXX

The stored values don't have to know anything about the rules that got them there. I really don't know the math involved here, for the required number of bits and such, to be quite honest, it never interested me enough. But it does seem that you don't need to put down what hits you have to get in the file. You just need to put the value that provided those hits, and leave figuring out what it means to your decoder.

See, even though I'm plotting 'a's in my file, it doesn't need to actually care anything about what it's plotting. All it needs to know is countX, countY times. Your de/encoder handles all the rules of checking if it can or cannot plot there. Hell you could even do that backwards. We know it's the hardest to get our last set, 9s in this example. Write them first. Now playing by the rule of "don't overwrite anything higher than you", plot in all the 8s. The run of 8s maybe includes stops on 9s. It counts them as having been placed, but it doesn't actually place anything. But to get to the final matching set of 8s, it can count some stops on 9s as valid stops along the way. We're still just saying "countX Y times".

Ah well, all the fun stuff is impossible to do anyway.


Quzah.

Look I don't need an explanation as to what you mean, I know what you mean, I'm saying it won't work because it is mathematically impossible to produce ANY sequence small enough that it would take fewer bits to encode the INDEX into that sequence than the total number of subsequences it could possibly encode. Using random sequences, or perfectly formed sequences does not matter, the best you can EVER achieve mathematically using that method is parity because the INDEX must be AT LEAST as large as the total number of possible initial combinations, or you cannot uniquely represent every possible combination. That is, if you have 8 possible symbols to compress you must have at least 8 possible index values, which must all be unique. You cant encode 8 symbols with only 7 index values, its mathematically impossible, at least for lossless compression which text compression must be. The compression methods that work generally operate on the principle that with the raw data, you don't need to encode very possible sequence, for example, in war and peace, nowhere does there occur the sequence of letters 'Obama is a Muslim', therefore that combination can be discarded as a possible output, reducing the library size, and thus the index needed.

I don't need to encode the sequence. All I need to do is tell it to count X Y number of times. That's the sequence. If I tell you to count to 1000, 10 times, I don't need to have 10 bytes to tell you to count 10 times. I need 1 byte to tell you to count 10 times, and another N bytes to tell you what number to count to. What happens when you count that many times is handled by the program decoding that. That's my whole point. You count the same number a set number of times. That's all. The decryption program can take 100 petabytes for all I care.


Quzah.

Quote:

---

Originally Posted by quzah

I don't need to encode the sequence. All I need to do is tell it to count X Y number of times. That's the sequence. If I tell you to count to 1000, 10 times, I don't need to have 10 bytes to tell you to count 10 times. I need 1 byte to tell you to count 10 times, and another N bytes to tell you what number to count to. What happens when you count that many times is handled by the program decoding that. That's my whole point. You count the same number a set number of times. That's all. The decryption program can take 100 petabytes for all I care.


Quzah.

---

No arbitrary sequence can be guaranteed to occur within N bits, with N being the size of your index, hence no compression.

You are missing the point entirely. I'm not sayign you cannot FIND the sequence, and then produce an index that points to it, liek a pointer, I am saying that the Index, your 1000 tiem 10, will take more space than the original data.

Sure, you can find a single case where it wont, but you will not find every possible sequence, hence arbitrary, within that index size, hence you cannot acheive arbitrary compression. You woudl be limited to only those sequences found within N bits, adn coudl never use any sequence that was not within N bits.

To prove it to you -

using pi

3.14159265358979323846264338327950

just encoding the single digits 0-9

say you want to encode the number 7, you cannot find an index value lower than 14 that encodes it, the first instance of '7' is at place 14 hence you need ln 14/ln 2 bits to represent JUST the numbers 1-9, also adding 0 takes you out even further,

since you can arbitrarily represent 10 symbols with ln 10/ln 2 bits, and index of size ln 14/ln 2 will ALWAYS AND FOREVER UNTIL THE END OF TIME be larger and thus take more space and achieve no compression. In fact, even if you form a PERFECT hand made sequence that reduces all redundancy the best you can achieve is parity.

You cannot achieve lossless compression of arbitrary data with that method, it is impossible, no matte how many tricks you try, it is mathematically impossible. You might as well try to prove that 7 is more than 8.

Well, 7 is larger than 8 for sufficiently large values of 7! :D


Quzah.

Quote:

---

Originally Posted by quzah

Well, 7 is larger than 8 for sufficiently large values of 7! :D


Quzah.

---

I just lost all respect for you. I go through the effort of trying to explain one of the fundamental principles of information compression and all you can do is make jokes....

Quote:

---

Originally Posted by abachler

I just lost all respect for you. I go through the effort of trying to explain one of the fundamental principles of information compression and all you can do is make jokes....

---

I'm sorry you have no sense of humor; that's a pretty standard mathematics joke. Frankly, I don't care if anyone here "respects" me or not. Honestly the opinions of "Random Internet Guy" mean nothing to me.

But I was not following the math. That's not why I made the joke, it just fit right in with the "prove 7 is larger than 8". It was a given. It would have been remiss of me not to make the joke.

Anyway, I can't see why if I can chain X numbers together by saying do Y Z times, that that must take more bytes. It doesn't make sense to me. If I can look at a sequence of numbers (indexes), and say, "Oh, hey, jump N places M times, and you'll hit all those squares!", why expressing doN*M must take up more bits than N values. Saying "Move 1000 spaces 10 times", does not up 10 bytes. It barely takes twice that for me to actually type "move 1000 spaces 10 times". So why is it that: sizeof( short ) + sizeof( char ) must be bigger than sizeof( char ) * 10? It isn't!


Quzah.

then by all means show me a sequence of fewer than 10 digits that contains every number from 0-9. Because that is what you are claiming is possible. Your index will always take more bits, because you cant say well, I found 14159 at index 2 so my index only takes 2 bits. Because you cannot find arbitrary sequences, that means any sequence I happen to need compressed, such as 27894 using only a 2 bit index, therefore your index must mathematically be large enough to contain an index sufficient to find ALL possible sequences of say 5 numbers. Plus you have to somehow encode the run length, either by having all symbols be of fixed length, or by encoding it as part of the index. Even in those cases you can never achieve better than parity. If you had actually read my previous posts you would understand why.

It's not that I'm counting every digit from 0 to 9. It's that I'm counting X of Y digit by counting Z moves. Here, let's craft a file, it's not going to be compression at this point, because using a small file costs you (go .zip an empty text file, and the header makes the file bigger than it would be if you didn't 'compress' it). But it should prove the idea I'm trying to get across.

<some random size>
10 7
20 8
33 145
5 128
7 345
8 1
11 34
17 256
89 12045

There's our file. We don't store zeros, because we zero fill the output file first, <some random size> bytes.

Next, we call function f, 10 times, with 7 as its argument.

Code:

---

for( x = 0; x < y; x++ )
    f(7);

---

Then we call it 20 times, with 8.
Then 33 times with 145.
And so on.

Now, what we've done is popped through all the spots in our output file, and in the end, have possibly written the sum of column B number of bytes, where the byte written is dependent on where we were in the file at the time we read the instructions. For example, f(7), was our 1s. f(8) was our 2s. And so on.

I don't care about storing 0-9 in less than 10 digits. I don't need to. All I'm writing an output file based on a predetermined series of described jumps. That's all. That's the "compression".

It's the same idea as RLE. RLE says, "write out X of Y". That's all. That's what RLE does. This is the same thing, except how we obtain what we write is far more complex to derive. Once you figure the math of how far you have to jump, and how many jumps you need, it's output file is smaller than its input file, assuming you don't do something stupid, and try to "zip up a zero byte file".

Yes, there is "header overhead". Yeah, I'm going to have a line for each value I want to write. Yeah, each spot is going to have how many times I try to write, and how far I jump before the next write. But, beyond that, I'm not seeing why it's guaranteed to be bigger than what I'm writing.

The resource consuming part is finding out what number you have to have to describe your jumps, how many and how far. It's like searching for prime numbers. You know there are prime numbers. You just don't know where the next one is. It's there some place.

Think of it as how you can grab N numbers and find their GCD, LCD, GCF, WTF. That's there, you can compute it. Then the idea is that given N numbers, you should be able to describe a relationship between those numbers where X moves of Y in a boundary of Z.

Maybe I'm way off, but I'm not seeing it.

[edit]
I suppose I could describe the file's size by replacing the top line with: <size> 1, which would say "write 0, size times, in jumps of 1." (Just to make all of your reads standard...

Code:

---

for( x = 0; fgets( .. ) != EOF; x++ )
{
    sscanf count and jumps
    for( ... )
        f(jumps,x)

---

Something to that effect.
[edit]


Quzah.

Go back and actually read my post, it explains it, you obviously didn't read them or you wouldn't keep insisting you can represent 2^N unique symbols in fewer than N bits.

For the purposes of your method each 'symbol' is a unique position in teh sequence i.e. pi or whatever you use. Each unique value to encode must have a UNIQUE position in pi, and therefore a UNIQUE index. For lossless compression there must be a ONE TO ONE mapping from compressed data to uncompressed data. therefore once again -

YOU CANNOT REPRESENT 2^N UNIQUE SYMBOLS WITH AN INDEX SIZE OF FEWER THAN N BITS.

It doesn't matter how you represent your index, as a straight number, or as some multiplication problem, it will still occupy at least as many bits as the original data.
If your index is 3 bits you can only represent AT MOST 8 positions in the sequence, meaning you can encode AT MOST 8 symbols, meaning you achieve ZERO COMPRESSION, ZIP NADA NOTHING.

If you cannot understand that, then I'm about to start spoon feeding you by making you answer question like, do you even know what a bit is?

I'm not compressing the index of 0-9 lower than 10. I'm compressing the NUMBER OF EACH. Watch, I can compress 500 integers into 4 characters. Ready? Really ready for this? Because I don't think you are, but I'm going to do it anyway!

Code:

---

2,500

---

There. See that? That's four bytes if we ignore the separator. Want to know what I just compressed? All the multiples of 2 up to 1000.

That's pretty neat huh? I just compressed every multiple of 2, up to 1000 into five characters. Want to know how I generate the output file for that? I run that through a ........ing function!

Code:

---

fun(2,500)

---

BAM!

Do you understand yet?


Quzah.

Quote:

---

Originally Posted by quzah

I'm not compressing the index of 0-9 lower than 10. I'm compressing the NUMBER OF EACH. Watch, I can compress 500 integers into 4 characters. Ready? Really ready for this? Because I don't think you are, but I'm going to do it anyway!

Code:

---

2,500

---

There. See that? That's four bytes if we ignore the separator. Want to know what I just compressed? All the multiples of 2 up to 1000.

That's pretty neat huh? I just compressed every multiple of 2, up to 1000 into five characters. Want to know how I generate the output file for that? I run that through a ........ing function!

Code:

---

fun(2,500)

---

BAM!

Do you understand yet?


Quzah.

---

now compress a random sequence of NOT 500 same symbols in a row, yeah, your theory doesn't work so well with ARBITRARY data does it.

That's my whole point! Just like you can find the least common denominator, you should be able to describe the relationship between N numbers, where the distance between them is described as X moves of Y.

I said from the start that it might be impossible, but that in theory I think you should be able to describe it as such. Consider hashing. Ideally, you want no collisions. You want a number that when you drop it in the bucket, fills each bucket equally. But the numbers you are dropping in are random pretty much. So what happens? You pick a prime number, or something fun, and hop around in your buckets and fill them up. It's kinda the same idea.

I didn't say *I* could do the math for it. That's why I said you'd need a quantum computer to calculate the math involved.

I want to hit spots 1 5 and 8 out of 11 buckets. All of those numbers were chosen randomly.

ABCDEFGHIJK
1...5..8...

I describe these moves as "starting at zero, move x--, 2 times". That fits, right?

04--2

Hey, I'm only 1 byte off from being even! What if I assume that -- is a given? Well now I'm:

042

What if I assume that everything starts at 0?

Now I'm at:

42

I've just just compressed something, because I could see a relationship between those random numbers. The problem is that when you're talking about a huge number of them, it scales really badly. I couldn't tell you the relationship between 50 random numbers. But in theory, there should be one.

I can't do the math for it. But the theory is that there's a sequence of numbers where by moving X moves of Y you will hit each of those spots in an array of Z elements, wrapping if needed, ingoreing stuff you stamp over, if needed, writing over what you stamp over, if needed. You could describe the rules in the function, and the output file doesn't need to know those rules necessarily. That's what I was trying to illustrate above. It would be fun to be able to run through ... digits of pie, rand(seed(x)), whatever, and have your program spit out relationship jumps. That's what my first post was all about.

Quzah.

Quote:

---

Originally Posted by abachler

now compress a random sequence of NOT 500 same symbols in a row, yeah, your theory doesn't work so well with ARBITRARY data does it.

---

Who cares about arbitrary? You said you couldn't compress N in less than N/FOO bytes. I just did. Maybe you didn't express it clearly enough, specifying that it had to be arbitrary, but the fact is, you CAN describe how to compress N values in less than N bytes of description, as I've just proven with 2,500.

And yes, we're primarily talking about arbitrary numbers. But you repeatedly said you CAN NEVER ... and well, yes, you can.


Quzah.

The only reason numbers are random is because you can't see a connection between them.


Quzah.

Quote:

---

Originally Posted by quzah

Who cares about arbitrary? You said you couldn't compress N in less than N/FOO bytes. I just did. Maybe you didn't express it clearly enough, specifying that it had to be arbitrary, but the fact is, you CAN describe how to compress N values in less than N bytes of description, as I've just proven with 2,500.

And yes, we're primarily talking about arbitrary numbers. But you repeatedly said you CAN NEVER ... and well, yes, you can.


Quzah.

---

I believe I did express that fact, in big bold all capital underlined letters. I'm sorry you missed it. Here it is again -

Quote:

---

Originally Posted by He who must have a masochistic urge to spoon feed the noob

YOU CANNOT REPRESENT 2^N UNIQUE SYMBOLS WITH AN INDEX SIZE OF FEWER THAN N BITS.

---

I even added italics this time so maybe you wont miss it.

It's irrelevant. You don't need to compress the whole file.

Quote:

---

Originally Posted by abachler

I believe I did express that fact, in big bold all capital underlined letters. I'm sorry you missed it. Here it is again -


I even added italics this time so maybe you wont miss it.

---

Um yeah, except you missed the whole part where I JUST DID with my three characters. It's not "N unique characters in N bits". I'm not trying to compress 3 unique characters to 3 BITS. I'm compressing three characters to 2 characters. I don't see how what you keep shouting is relevant. Explain it clearer than "3 unique characters in less than 3 BITS", because I'm not trying to compress 3 unique characters in 3 BITS. I'm compressing 3 characters in 2 bytes. You're saying I'm trying to do:
1,5,8 = 11 (bits, both set). I'm not. I'm not trying to fit three characters into three BITS.

I'm fitting 3 characters in TWO BYTES. That's compression. Compressing three characters into two is compressing it. I'm not sure how that has anything to do with whatever it is you're babbling on about.

I don't have to compress unique characters into smaller bits. I'm compressing the number of X I find into less than X * sizeof( X ) bytes. Other than that, I'm not sure what you're trying to get at. It's not that I'm not reading it, it's that just because you make it bold, doesn't mean your explanation is clear.

If I take a file, and compress all of the 'a' characters in that file into some nifty RLE-esque sequence, that says "start here, skip N places, and wherever you land, place an 'a'", and that's all I do, and my description of "start here, skip..." takes up less than 'a' * total times 'a' appears in the file, then I have just COMPRESSED IT!

I don't care whatever you're babbling about fitting 'a' into 1 bit. I'm not trying to do that. No one is trying to fit the numbers 0 - 9 into less than 10 bits (Oh, FYI, 0-9 (10 digits) is actually 4 bits, so what ... it's automatically compressing itself, because 4 is less than 10!? Seriously, instead of shouting over and over that the sky is green, tell me what makes it green, and how that relates to me saying there's a moon.)

Edit: As Mario said, unless he's talking to me, in which case, I don't understand the point either of you are making: I don't have to compress every aspect of a file to achieve compression. I can compress one part of it, and if I describe that expression in less bytes than what I'm compressing, then YES I HAVE JUST ACHIEVED COMPRESSION.

So, if you're planning on trying to explain this again, do it like you're talking to someone about someone who has never heard of math. Because the way you are saying it doesn't make any sense to me.


Quzah.

Quote:

---

Originally Posted by quzah

So, if you're planning on trying to explain this again, do it like you're talking to someone about someone who has never heard of math. Because the way you are saying it doesn't make any sense to me.


Quzah.

---

Explain to us what you think a bit is.

Think of it this way: If I look at a file, and say: "Hey, every N characters, there is an 'a'!", and so I remove every N characters and put at the top of the file (or the end, whatever):

'a',N

And when I "uncompress the file", I simply do:

Code:

---

for( x = 0; (c = fgetc( in )) != EOF; x++ )
{
    if( x % N == 0 )
    {
        fputc( out, 'a' )
    }
    fputc( out, c );
}

---

Then no matter what you babble on about N in N bits, it doesn't matter. I've just uncompressed this file. If you can say that by doing f(N), it produces an output, and describing f(N) in the file takes up less space than all of N, then you've just achieved compression. You don't have to compress every single different unique character. All you have to do is compress the total number of occurrences of X into a description of f(N), where that description takes up less space in the file than the total number of times X appears, and you've just achieved compression.

None of your bits-vs-bytes-vs-unique characters matters. If it does, you're TERRIBLE at explaining how. Because I can PROVE that saying f(N) takes up less space than all of the number of X in a file.


Quzah.

You guys are both right, yet are completely misunderstanding each other.

Quzah's technique will work. It will not work with completely arbitrary, random data. But it will work with data that follows some sort of pattern. The trick is figuring out what the pattern is.

Abachler is saying that Quzah's technique will not work with completely arbitrary, random data. This is true, because by definition, random data doesn't have a pattern. Can anything be completely random though?

See, you're both right.

Quote:

---

Originally Posted by abachler

Explain to us what you think a bit is.

---

It's the internal representation of a value that means either 1 or 0. Combine two of them, and you can now count to four. Combine three of them, and you can count to eight. Combine four of them, and you can now count to sixteen. Etc.

Let's say that every N bits in a file is 1. That pattern, 1 appearing every N bits, in a file can be expressed as f(N). I say ... anywhere ... f(N). Me saying f(N) takes up 32 bits (assuming I'm expressing it in clear actual readable text, f parenthesis N parentheis). If N is bigger than 32, then I have just compressed my file.

It doesn't matter if to uncompress my file if I have to use all the computers in the world, and all the power produced by all the power plants in the world to computer that decompression. None of that matters. If my output file is smaller than my input file, that's compression. Period.


Quzah.

Quote:

---

Originally Posted by bithub

You guys are both right, yet are completely misunderstanding each other.

Quzah's technique will work. It will not work with completely arbitrary, random data. But it will work with data that follows some sort of pattern. The trick is figuring out what the pattern is.

Abachler is saying that Quzah's technique will not work with completely arbitrary, random data. This is true, because by definition, random data doesn't have a pattern. Can anything be completely random though?

See, you're both right.

---

That's exactly the point I was trying to make. Specifically, when I simply posted:

"Numbers are only random because we cannot see a connection between them."

If you CAN express a connection between them, and saying that "HEY! Every N is X!" takes up less room in the file then actually leaving all of them there, then that's compression.

Thank you. That's exactly what I've been trying to say this entire time!


Quzah.

The challenge was to do with War and Peace, which probably contains <50000 different words. AFAICT just googling around, of course you get better compression if you are compressing text in a particular language. If this were not true, you could impose endless compression:

myfile.gz.gz.gz.gz

etc, each time the file gets smaller. Obviously this is not true -- at some point, all the patterns in the text have been reduced to the point where they are not patterns anymore, they are symbols of various instances (or some version of same)*.

My "cub car" idea was to create a dictionary, meaning 95% of the words could be represented with a short int (then I needed an extra byte for each word to represent the state of the local punctuation). But on average that is only going to compress like 50-60%.

* okay, maybe that's a sketchy-inaccurate description but pretty sure my aim is true here

>> The challenge was to do with War and Peace, which probably contains <50000 different words. AFAICT just googling around, of course you get better compression if you are compressing text in a particular language.

I don't think the language matters much. As long as you can find some pattern, there is an opportunity for compression.

>> If this were not true, you could impose endless compression:

That just depends on the particular algorithm, and how it creates mappings between symbols. Reprocessing the output doesn't generally lead to compression, but that isn't always necessarily the case. Obviously, once the data reaches (or starts out in) a maximum state of entropy, further compression isn't possible. Just keep in mind that one algorithm's entropy is another's orderly distribution - it's a relative thing, really.

>> My "cub car" idea was to create a dictionary, meaning 95% of the words could be represented with a short int (then I needed an extra byte for each word to represent the state of the local punctuation). But on average that is only going to compress like 50-60%

That's basically how LZW (the basis of WinZIP, et al) works. The biggest drawback to that algorithm is that it usually requires quite a bit of memory, and the amount needed can grow rather rapidly (most implementations just flush the dictionary at some predetermined point to deal with that, though). It's a pretty useful algorithm, though. It generally compresses things like text quite well, is extremely fast, and is adaptive, meaning you don't have to transmit the compression model (something that could easily take up to 2048 bytes).

It will be hard to come up with anything meaningful that hasn't bee done already. That's what makes Qzah idea a whole lot more interesting.

In any case, any submissions already?
If there's a week extension to the deadline, I'd join in. Otherwise I hope you rot in hell.

There haven't been any serious entries yet, so i guess its extended.

Very well then. I'll be working on it this weekend. Cheers.
While I will not come up with anything revolutionary (as if!), it will at least be something new... and serious.

Quote:

---

Originally Posted by Sebastiani

>> The challenge was to do with War and Peace, which probably contains <50000 different words. AFAICT just googling around, of course you get better compression if you are compressing text in a particular language.

I don't think the language matters much. As long as you can find some pattern, there is an opportunity for compression.

---

Except that a huge portion of the dictionary could be hard-coded, saving much time in analyzing the text, and also reducing the filesize.

That isn't really compression, though, per se, as much as it is an indexing scheme. Think of it this way: if you had to transmit the data somewhere that didn't have access to the database, the receiver couldn't reconstruct the original message.

Meanwhile the requirements for the context don't allow any kind of on disk file access. The database would have to stay in memory and the application would have to stay open after compression in order for it to be able to decompress.

Quote:

---

Originally Posted by Sebastiani

That isn't really compression, though, per se, as much as it is an indexing scheme. Think of it this way: if you had to transmit the data somewhere that didn't have access to the database, the receiver couldn't reconstruct the original message.

---

Well, if you gzipped something and sent it somewhere that didn't have gzip, you'd be out of luck there too. The idea, obviously, is to include a small dictionary (say 40000 words, 200k) in the application.

However, I don't think this is necessarily a good idea; just it was my idea :p

>> Well, if you gzipped something and sent it somewhere that didn't have gzip, you'd be out of luck there too. The idea, obviously, is to include a small dictionary (say 40000 words, 200k) in the application.

But gzip is just an algorithm. What you're talking about is just a form of 'data hiding'. Consider this: if I asked you to design a program that rendered 3d-graphics, and you simply created images using photoshop and imbedded them into your application, would that really count? The point is, you're storing the 'result' somewhere, pretending that it's part of the algorithm.

Quote:

---

Originally Posted by Sebastiani

But gzip is just an algorithm. What you're talking about is just a form of 'data hiding'. Consider this: if I asked you to design a program that rendered 3d-graphics, and you simply created images using photoshop and imbedded them into your application, would that really count? The point is, you're storing the 'result' somewhere, pretending that it's part of the algorithm.

---

Pretty sure I would not be violating the rules, altho it is unlikely to win anyway.

But I disagree with your analogy. Your compression technique must presume something about about a file, eg, that it contains text or even that it is byte-structured. Since the rule was for ascii, you could further presume certain things. The 3D app with embedded photographs is unlikely to be useful because of the specificity of the content and the infinity of possibilities, but the English language is standardized and finite. If you are dealing with published material, you can also assume the spelling is mostly correct and a hard-coded dictionary of common words (could) be very useful.

So it is not totally crazy. Certainly, it might significantly reduce the task of pattern matching, however that applies to whatever algorithm.

And the gzip algorithm is "hard-coded" in gzip, so again, the distinction is on a certain level but not absolute IMO.

>> Your compression technique must presume something about about a file, eg, that it contains text or even that it is byte-structured.

Not at all! One (perhaps unspoken) heuristic is that a true compression algorithm should be able to encode any sequence of input (optimally or otherwise), regardless of the format. And it may operate on a 'byte level' but that has nothing to do with the actual nature of the input. You could store 300 8-byte double-precision numbers in a file, and as far as the compressor is concerned, it's just a plain string of 2400 bytes.

>> The 3D app with embedded photographs is unlikely to be useful because of the specificity of the content and the infinity of possibilities, but the English language is standardized and finite.

And what you're proposing is designed specifically for an English-language translation of 'War and Peace' in pure ASCII format. Furthermore, English is hardly 'standardized and finite'. What if the compressed the data was discovered 100 years from now? Wouldn't they need a 2009 dictionary to decode it?

>> And the gzip algorithm is "hard-coded" in gzip, so again, the distinction is on a certain level but not absolute IMO.

You're comparing apples to oranges. Gzip is a general purpose, universal, and time-independant algorithm. What you're proposing is a special-purpose, specific, and time-sensitive combination of data and algorithm. I'm afraid that the only way to turn your Pinoccio into a real boy would be to transmit the dictionary along with the data. Of course, then you really *would* need a miracle to achieve any compression with that.

Quote:

---

Originally Posted by Sebastiani

And what you're proposing is designed specifically for an English-language translation of 'War and Peace' in pure ASCII format. Furthermore, English is hardly 'standardized and finite'.

---

No, it would be designed specifically for the English language. You may notice we use standardized tools such as spell checkers that use pre-defined dictionaries and there is nothing wrong with those.

Quote:

---

Originally Posted by Sebastiani

You could store 300 8-byte double-precision numbers in a file, and as far as the compressor is concerned, it's just a plain string of 2400 bytes.

---

What I meant was you are then ASSUMING an 8 bit = byte structure. Unless the compression works on a bit level and makes no further distinctions, it must apply a "pre-defined" strategy, so your idea that this means the compression can be used on "any data" is false. You are just resting on the status quo, as it were. So, I'm placing the status quo on a higher level: the English language. This is more limiting, but it may also allow further optimization.

Quote:

---

Originally Posted by Sebastiani

I'm afraid that the only way to turn your Pinoccio into a real boy would be to transmit the dictionary along with the data. Of course, then you really *would* need a miracle to achieve any compression with that.

---

Well, I did not claim it was in the same category as the real boy ;) However, I will defend the claim that the dictionary can be included in the application AND NOT THE FILE. When you spell check a document, you use the exact same dictionary as you use on every other document. You do not have to save the dictionary along with the file -- that would be dunderheaded.

Anyway, once again, I agree it is not very promising. However, I am sure you could achieve 50-75% compression that way, which is compression. If you want to redefine the word "compression" to mean "only compression which is performed according to my criteria" then I would point you to a dictionary.

Quote:

---

com⋅pres⋅sion
  –noun
1. the act of compressing.
2. the state of being compressed.
3. the effect, result, or consequence of being compressed.
4. (in internal-combustion engines) the reduction in volume and increase of pressure of the air or combustible mixture in the cylinder prior to ignition, produced by the motion of the piston toward the cylinder head after intake.
5. Also called data compression. reduction of the storage space required for data by changing its format.

---

>> However, I will defend the claim that the dictionary can be included in the application AND NOT THE FILE.

Following that logic, why not just store an index into all of the books ever published up to 2009? That could be done in just a handful of bytes. Or better yet, just store the whole book. Then you could achieve perfect compression. The point is, you're not making the all important distinction between algorithm and data.

>> What I meant was you are then ASSUMING an 8 bit = byte structure. Unless the compression works on a bit level and makes no further distinctions, it must apply a "pre-defined" strategy, so your idea that this means the compression can be used on "any data" is false.

Programmers assume 8-bit bytes simply because that's the conventional size used on most machines. Even so, internally they may analize and process them in various bit-widths. At any rate, a true compression algorithm (including gzip) can be easily modified to, say, work with 10-bit bytes (in fact the Huffman compressor I posted the other day allows you to do just that without even altering the source code; it's a template parameter).

Quote:

---

Originally Posted by Sebastiani

Following that logic, why not just store an index into all of the books ever published up to 2009? That could be done in just a handful of bytes. Or better yet, just store the whole book. Then you could achieve perfect compression. The point is, you're not making the all important distinction between algorithm and data.

---

A short dictionary of common words, like I mentioned in a previous post, is 50-100k. Notice, War and Peace is 30-60 times that size. So, "algorithmically speaking", what I suggested makes sense. You are just being silly.

I do make the "all important" distinction. I have identified the data as data that is "encoded" in the English language, which there are many many millions and billions of documents to which this could apply. There are surely more documents written in English than all of the computer programs ever written and that ratio will be drastic. I am not saying I will just make my algortithm == the data. That is like saying the dictionary == Shakespeare, which is ridiculous.

Quote:

---

Programmers assume 8-bit bytes simply because that's the conventional size used on most machines. Even so, internally they may analize and process them in various bit-widths. At any rate, a true compression algorithm (including gzip) can be easily modified to, say, work with 10-bit bytes (in fact the Huffman compressor I posted the other day allows you to do just that without even altering the source code; it's a template parameter).

---

Keyword: modified. As I said, you assume the status quo ("conventional size") and you are right to do so! By the same reasoning, I am assuming English is, in fact, a standardized, conventional language. SAME reasoning.

Anyway, it would be compressed. The average word is 5 characters. A short int is two bytes. Then I think one byte for state information -- but that could be optimized, so the compression will be 50-75%. COMPRESSION.

Theres no need to hard code the dictionary, just build it at run time from teh acual words and phrases present in the document.

Quote:

---

Originally Posted by abachler

Theres no need to hard code the dictionary, just build it at run time from teh acual words and phrases present in the document.

---

Well but this way I shave off some kb and some analysis. Is there much point in identifying patterns like this:

they
it
always
also
tumor
satisfactory

I mean if you can assume there are 8 bits in a byte, you might as well assume an English language document is in English.

Then you just identify words/patterns that repeat that are not pre-defined ("Dracula" "Cervantes" "muttonhead", "royale", "nOOb",etc). This may be a dead-end (as Mario pointed out, it is all done by now! none of you will come up with anything new that is better that what already is either) but it is not invalid.

Besides, I was going to pull the dictionary from War & Peace anyway :p but now I will just sulk.

>> A short dictionary of common words, like I mentioned in a previous post, is 50-100k. Notice, War and Peace is 30-60 times that size. So, "algorithmically speaking", what I suggested makes sense. You are just being silly.

I don't see how it's silly that such a distinction between code and data should be drawn. It makes perfect sense to me.

>> I do make the "all important" distinction. I have identified the data as data that is "encoded" in the English language, which there are many many millions and billions of documents to which this could apply.

Fine, but that still not compression - it's just "mapping words to indexes" and vice versa.

>> There are surely more documents written in English than all of the computer programs ever written and that ratio will be drastic. I am not saying I will just make my algortithm == the data. That is like saying the dictionary == Shakespeare, which is ridiculous.

All I'm saying is that your program should work on anything. Executables, plain text, xml, images - whatever. Raw data. No assumptions. No predefined data. No artificial constraints. No hints. That's my definition of a true compression algorithm. Anything else is merely a curiosity, IMO.

>> Keyword: modified. As I said, you assume the status quo ("conventional size") and you are right to do so! By the same reasoning, I am assuming English is, in fact, a standardized, conventional language. SAME reasoning.

Yes, modified - once (and anyway, this is just an artifact of short-sighted design - it could have just as easily been done that way from the very beginning). So I really don't see how the two compare at all.

Except the document isn't guaranteed to be in english, as I previously stated, it could be in Klingon or Esperanto for all you know.

I think it is a "true" compression algorithm. Just that, for non-English content, the compressed size will be slightly larger than uncompressed. But that applies to all algorithms. There is always input whose compressed output will be larger, simply because you cannot represent all possible combinations of N bits with less than N bits. All compression algorithms need to make assumptions about the content. If the content matches the assumption, compressed size will be smaller, otherwise bigger.

>> I mean if you can assume there are 8 bits in a byte, you might as well assume an English language document is in English.

Again, the assumption there is completely unnecessary.

>> as Mario pointed out, it is all done by now! none of you will come up with anything new that is better that what already is either

That's like saying there is nothing left to be discovered in physics - it's simply not true. In fact, when I was working on the Huffman algorithm I discovered a new technique for transmitting the compression model that reduced the lower bound from 256 bytes to just 3! Granted, that's just an improvement on a very old algorithm, but the point is, there will always be as-yet undiscovered techniques.

>> But that applies to all algorithms. There is always input whose compressed output will be larger, simply because you cannot represent all possible combinations of N bits with less than N bits.

Sure, for any single algorithm, that is of course true.

>> All compression algorithms need to make assumptions about the content. If the content matches the assumption, compressed size will be smaller, otherwise bigger.

Assumptions, no. Optimized for a particular set of input, absolutely.

Quote:

---

Originally Posted by Sebastiani

That's like saying there is nothing left to be discovered in physics - it's simply not true.

---

What I meant in fact is that it's highly unlikely anyone in here will come up with anything new and meaningful, and not that it can't be made. It may be possible. Just not here and just not in this contest. So we agree, but I felt I needed that to be clear.

Meanwhile the -- already annoying -- dictionary approach has a few problems like what you describe. What it makes particularly annoying in this contest is that we were specifically told by the contest rules we can't access the file system. So:

- The dictionary would have to either travel with the compressed data and lost when decompressed, or remain in memory for both operations. Because we don't even have access to the caller (on this case, main), we have to build the dictionary twice. Once on each function, or carry it with the compressed data. Crude.

- I agree with MK27 on one thing though, there's no requirement for a wide purpose compression algorithm. Only to achieve the highest compression possible (in the fastest way) with our own code. We can't make no assumptions about the language of the text... but we do know it's an ascii file.

>> What I meant in fact is that it's highly unlikely anyone in here will come up with anything new and meaningful, and not that it can't be made. It may be possible. Just not here and just not in this contest. So we agree, but I felt I needed that to be clear.

Maybe. But then again...:p

Seriously, though, even without inventing a new algorithm, an improvement upon an existing one is a worthwhile endeavor, in my book.

Quote:

---

Originally Posted by Mario F.

We can't make no assumptions about the language of the text... but we do know it's an ascii file.

---

Good point; altho I don't know how many languages (besides English) that it could be, and still be an ascii file...so someone could gamble and HARDCODE a dictionary.

Quote:

---

Originally Posted by MK27

Good point; altho I don't know how many languages (besides English) that it could be, and still be an ascii file...so someone could gamble and HARDCODE a dictionary.

---

Most languages have a latinized translation.
It's not english, that's all Ill say.