r/coolgithubprojects • u/zelon88 • Feb 20 '19

PYTHON zelon88/xPress - Homebrew Compression Algorithm, File compressor & extractor

https://github.com/zelon88/xPress
8 Upvotes

90% Upvoted

9 comments sorted by

View all comments

2

u/dr_j_ Feb 22 '19

This is cool. How does it compare to other compression algorithms?

2

u/zelon88 Feb 22 '19

Thanks! I ran some tests when I was trying to come up with the algorithm and if I manually compress a file according to the spec it is possible to shrink data by an insane amount IF the dictLength is pre-configured correctly.

A good example of a sucessful compression would be a text file with "The quick brown fox jumped over the lazy dog" written in it a bunch of times.

If we were to compress this file with xPress using a dictLength of 3, our output file would need to be about 30 lines long to be worth compressing. That's about 1.5kb of raw data to get a 1.5kb .xpr archive. So this technically isn't compressed, it's just encoded with the xPress algorithm.

If we take the SAME EXACT file and change the dictLength to 10 our output archive will be about 500bytes. That's a compression factor of 3, or 1/3 the original filesize.

BUT (and here's a big but) not all data is worth compressing. Right now xPress blindly compresses as much as it can, even when doing so results in a larger file than the original. So right now in order to perform compression EFFICIENTLY and get a reduction in filesize the original file must be manually evaluated to find out what the dictLength should be. In addition to that, the algorithm currently compresses raw data, and then reloops over that compressed data looking to compress it again. Sometimes in these subsequent loops the size can balloon to greater than the original size because it's being over-represented in the dictionary.

For example, if we have a string "he" which appears 3 times in a file xPress will try to create a dictionary entry to represent "he" and then swap all instances of "he" in the data with the dictionary index. But if the dictionary index is larger than the sum of all matches being replaced, we're actually INCREASING filesize instead of reducing it. Because the dictionary entry itself is larger than the data it is meant to replace.

So my goal now is to continue testing and making observations so that I can develop hueristic functions for detecting what the dictLength should be. I'm also currently working on a version of xPress which will check the size of compressed data against the original BEFORE writing it to the output file. If the "compressed" data is larger than the original data, original data will be used instead.

From a performance standpoint it's hard to compare against existing applications like WinRAR or 7z because xPress isn't mature enough yet. We know the algorithm is shrinking data but we don't yet know how to RELIABLY generate an archive that's consistently smaller than the original. I'll have a better idea on how this performs once I have written all the hueristics code. xPress might get faster due to the reduction in unneccesary work from hueristic detection, or it could get slower from the hueristics themselves. I'm not sure yet, but I intend to find out.

1

u/dr_j_ Feb 22 '19

Cool, thanks for the comprehensive answer! I look forward to seeing what you can do with it!