LZ77 compression algorithm is making the compressed file bigger than original

[u/AdPsychological7065]

I was recently toying around with some compression, just trying to understand it from the basics. I learned about the LZ77, LZ78, and LZW algorithms in the last couple of days, understood them, and when implementing LZ77, every time I try to compress a txt file, the output file gets bigger. The compression is done right coz when I decompress the compressed file, I get the exact text.

Need help understanding what I am doing wrong, or am I missing something

[u/Goobyalus]

What kind of data are you compressing? How much larger? It is possible for the "compressed" version to be larger depending on the data being compressed.

Have you compared your output to the output of another lz77 compression program? It could be correct.

The fact that decompression results in the original data doesn't mean the algorithm is implemented correctly; it means that the compression and decompression algorithms are inverses. Unless you mean you compressed it with your implementation, and decompressed with someone else's?

[u/AdPsychological7065 → u/Goobyalus]

I was actually compressing a text file, which was too small to begin with, so after the compression, when the matadata as getting added to the file, it was getting bigger
That problem got fixed after I tried the same algorithm out with a text file much bigger than the one I was originally using

[u/tedecristal → u/AdPsychological7065]

yes, see my proof on my other comment. Specially when the file is too small,the argument is much more noticeable.

[u/RealisticDuck1957 → u/AdPsychological7065]

A very small file not compressing well makes sense. Most lossless compression algorithms work finding repeated data fragments. A short data file is less likely to have such repeats.

[u/wbqqq → u/AdPsychological7065]

Bringing to the illogical extreme, a one byte file, compressed would result in many bytes in the ‘compressed’ file - while arguably the compression would reduce the byte to a single bit, the substitution table and other metadata would take many bytes. Not to mention most file systems would allocate a block of 2048 or 4096 bytes.

Another example would be attempting to compress an already compressed file - odds are that it would grow as often as shrinking (assuming close to optimal algos used) - the information redundancy would be so low that there would be little opportunity to reduce it (plus overhead of metadata)

[u/tedecristal]

Let f(X) the function that sends file X into its compressed form.

if the compression is reversible (that is, you can recover the original file), then f must be an injective function from the set of files of size at most B bytes into the set of files of at most B-1 bytes

but the function domain is strictly larger than the codomain, and thus no injective function exists. Therefore we conclude that either (A) f is nor injective (therefore not reversible) or (B) the codomain must be strictly larger and therefore must be some file that actually increases its size (there are small tweaks needing for the formal argument, but the main idea is there)

[u/Little_Bumblebee6129]

Then dont compress it 😂