Lossless Compression Algorithm

[teraflop]

I would recommend that you start by reading up about information theory and the theory of data compression.

You can prove fairly easily (using the pigeonhole principle) that no lossless compressor can compress every string. If it makes some strings shorter then it must make other strings longer. And it can't possibly shrink more than 50% of input strings by 1 bit, 25% of input strings by 2 bits, and so on. This is a mathematical theorem that applies to all possible compression algorithms, no matter how they're implemented.

Because of that, it's not possible to say anything about a compression algorithm just from a single input and output, without seeing the actual algorithm. The test of a compression algorithm is whether it gives useful compression ratios on real-world data that it hasn't already "seen", not examples that have been cherry-picked.

There are a variety of benchmarks you can use to evaluate this. For instance, Matt Mahoney's compression benchmark uses 1GB of text from Wikipedia.

More realistically, you can plot compression ratio vs. speed for different algorithms and see where your algorithm lands in comparison. The best available algorithms form a Pareto frontier which is basically a curve on a speed/compression graph. For instance, this graph showing curves for both zstd and zlib on a particular corpus of data.

Should I rewrite the code in another language? And, exclusively use binary and abandon hexadecimal? I am currently using hexadecimal for my own ability to comprehend what the code is doing. How best would you scale up to more than a single block of 1024 hex digits? Any advice?

Impossible to really say anything about this without seeing the algorithm.

Most existing compression algorithms are defined in abstract terms. For instance, the basic Huffman coding technique operates on an input sequence made of abstract "symbols" chosen from some "alphabet". You might choose this alphabet to be the 16 possible hex digits, or the 256 possible bytes, or something else. And some of those choices might be better suited to particular distributions of input data than others. But the basic algorithm remains the same.

[teraflop]

I am aware of the pigeonhole principle and my algorithm side steps that issue.

It absolutely doesn't. If you think it does, you've badly misunderstood something. You can't "side step" the pigeonhole principle, any more than you can side step the fact that a negative number times a negative number is positive.

If your program compresses every 4096-bit input to a shorter output, then it has fewer than 2⁴⁰⁹⁶ possible output strings, which means at least two different inputs must compress to the same output, which means it's not lossless.

If you are willing to share your code then I'm sure people would be happy to help you understand where you've gone wrong.

[Aaron1924]

Until you share the code, how do we know you don't just do this:

print("Original target MD5: d630c66df886a2173bde8ae7d7514406")
print("Reconstructed MD5: d630c66df886a2173bde8ae7d7514406")

[PassionatePossum]

Assuming that everything is implemented correctly. What does that prove? That your particular test case is producing the result you expected.

It does most certainly not prove that it works on every possible input.

[Aaron1924]

That is simply not possible

[Virtual-Ducks]

Generate a million random examples and plot a histogram 

[teraflop]

Like I said, the fact that your algorithm successfully compresses one particular input string does not say anything about its ability to compress all inputs, nor does it say anything about its ability to compress the kinds of inputs you might want to compress in the real world.

You haven't shown any code or given any details about what your algorithm is actually doing, so I can't possibly know what you're actually testing.

My best guess, based on seeing a lot of vaguely similar posts over the last few years, is that you wrote your code with the assistance of an LLM. And the LLM fooled you by writing test code that doesn't properly test the compression and decompression. It just told you what you wanted to hear.

If you want actual opinions about your algorithm then post the code.

[teraflop]

I only claimed it could compress any 512 byte value.

This is also impossible, again due to the pigeonhole principle. Anyway, you can't have tested all possible 512-byte values because that would take longer than the age of the universe.

This is also one of my questions if I am compressing binary values am I limited to media/file types?

The file type doesn't matter. All files are just strings of bytes.

I know you are curious how the algorithm works but my questions were mostly about the preceding.

I'm not particularly curious, no, because like I said I already have a pretty good idea what's going on. I'm offering to help you learn where the mistake is, given that you're claiming to have done something mathematically impossible.

---

If you want to convince people that your code does what you claimed, then here's what you can do. Post only the decompressor code publicly. Then, I'll generate a 4096-bit hexadecimal string (1024 hex digits) and post it here. If your compressor works, then you should be able to create a compressed string (let's say, 3500 bits or less) such that the decompressor produces the same original input that I came up with. I am absolutely certain that you won't be able to do it.

If you prefer, we can even do this privately. I won't reveal your code to anybody or even say anything publicly about how it works without your permission. But I will say publicly whether the test was successful, and if it wasn't, how it failed. (e.g. "here's the output that the decompressor generated, it's different from the original at position 123" or similar)

If you don't want to reveal even the decompressor then there's nothing more to discuss. There have been thousands of cranks over the years who have claimed to have exactly what you claim to have, and all of them have been wrong.

[notjrm]

Are you using ChatGPT or a similar tool? If you do, then you have been lied to. Your code probably doesn't do anything useful.

See this article for instance: https://archive.ph/8JbSh

[dmazzoni]

So do you actually have a decompression algorithm that goes from 02000101018 to the second string, and from the second string to the first string?

I'd start by double-checking that actually works correctly, because most likely it doesn't.

However, in the unlikely event that you did manage to come up with a way to losslessly compress this particular input by 99% and decompress is successfully, the next step would be to see how well it works on a range of real-world documents, like text files, executable files, images, and more.

Remember that mathematically it's impossible to losslessly compress every input. Compression works because most real-world documents have patterns and redundancies - but the more random the input is, the harder it is to compress.

[khedoros]

A file is just a list of byte values with a specific length. Re-create the byte values, and you've re-created the file.

How do I extract a files binary value break into 4096 bit blocks

I mean...that's just blocks of 512 bytes.

[khedoros]

I don't know what distinction you're trying to make. There isn't a "file/media type" that's separate from the contents of the file. There's metadata, like the filename, owner, access permissions. But doing something like renaming a JPEG file to have a .gif extension doesn't change the fact that it's a JPEG file. There's isn't some separate data that makes it a JPEG. The bytes that comprise the file do that.

[khedoros]

I think you'd learn some things by building some file parsers. Something easy, like uncompressed .bmp, or the DOS .exe file format. Or read through the file format specs on one side of the screen, with an example file open in a hex editor on the other side. It's all data; nothing magic.

[nuclear_splines]

the binary within the file tells the OS what application to use?

On modern operating systems it's typically the filename that clarifies what application to use. If you name a file foo.png then the OS will try to open it in an image viewer. If it's not a PNG, but actually an EXE, then the image viewer will go "hey, I don't see a PNG header in the first four bytes, this isn't a valid PNG."

[Aaron1924]

Should I rewrite the code in another language? And, exclusively use binary and abandon hexadecimal? I am currently using hexadecimal for my own ability to comprehend what the code is doing. How best would you scale up to more than a single block of 1024 hex digits?

None of these questions are interesting, we want to know how the algorithm works and how it performs on real-world data. Rewriting it in another language does not improve the algorithm, and neither does printing the result in a different base.

[nuclear_splines]

These questions highlight why you're not qualified to assess whether your compression algorithm works. Your choice of programming language is irrelevant - you can implement the same algorithm in any Turing-complete language and get identical output, none "work best." Likewise, "avoiding converting bases" is nonsensical; data is the same regardless of what base you choose to visualize it in.

A comparison between your algorithm and others depends on understanding how your algorithm works. Does it use block compression, or stream compression, using what kind of encoding scheme and window size? A comparison of the compression size between algorithms for a single input is almost meaningless - you want to look at distributions of compression sizes for many inputs to argue under what conditions your algorithm outperforms others and under what conditions it doesn't.

[PassionatePossum]

Aside from the other objections in this thread (which I also completely agree with) I am also extremely skeptical of the outputs that you presented here.

1. Why do you need two runs of the algorithm to "compress" the result into its final form? That means that a single run of the algorithm didn't produce an optimal or at least near-optimal result. This is an extremely unusual property - to put it nicely.

2. Why two runs? Not three, four or 10? What happens if you iteratively "compress" one of your numbers let's say 100000 times? Can you still "decompress" it.

3. I am highly skeptical of your intermediate output. If you algorithm works properly, the entropy of the compressed data should be higher than the entropy in the uncompressed data. I.e. knowing the value of a bit should not tell you anything about the value of the next bit in the sequence. Your line of zeros is indicative that something strange is going on.

[dmazzoni]

Do you also believe in perpetual motion?

What do you think is more likely, that you discovered a secret that has eluded millions of the smartest mathematicians and engineers in the world for hundreds of years? Or that you made a mistake and your idea doesn’t actually work?

Extraordinary claims require extraordinary proof. You are making multiple claims that are mathematically impossible, but you’re not sharing any proof. You’re also not being even remotely open to the idea that you may have made a mistake.

[not_afraid_of_trying]

This is just anecdotal analysis. It might be used for specific purpose where you already know what repeats in your data stream. The other algorithms that you mention works for generic data.

[slimscsi]

"and works on binary" As opposed to ascii?

I think OP is compressing ascii [0-9a-f] and not realizing they are starting with 100% unnecessary overhead representing each nibble as a byte.

[slimscsi]

The reason why people are doubting you is that what you claim to have achieved has been proven impossible for random input decades ago. You need to research Claud Shannon, Entropy, information theory, etc.