1
$\begingroup$

I am writing an executable compressor for small (roughly 1 kilobyte) executable files.

I am exploring compression algorithms that are well suited for this task. The amount of time required to compress and decompress is not important for my purposes, nor is the complexity of the compressor. I am limited to 4 GB of RAM while decompressing and I am chiefly concerned with maximizing the compression ratio while minimizing the size of the decompression stub.

I am currently experimenting with arithmetic encoding using various models to predict the posterior probability. This results in a decompression stub around 200 to 300 bytes in size. I have also experimented with LZ based methods, but have rejected them because their implementation is more complex and their performance is both theoretically and empirically inferior to arithmetic encoding with context modeling.

What other compression algorithms might be useful candidates for this task?

Improve this question
$\endgroup$
9
  • 1
    $\begingroup$ What research have you done? What other compression algorithms have you considered? There's been lots of study into compression and there are many standard algorithms; it sounds like you're asking us to summarize a field, which would be too broad. See e.g., en.wikipedia.org/wiki/Data_compression. LZ-based algorithms can have a very simple, small decompressor. The best way to figure out which approaches will yield good compression rates on executables is to try each of them, experimentally, and see what you find. $\endgroup$
    – D.W. ♦
    Jun 29, 2016 at 18:12
  • $\begingroup$ @D.W. Thank you for your comment. I have been researching a variety of algorithms. The common ones (LZ) also take speed into account (at the expense of my goals). Arithmetic encoding with context modeling is the best solution I have found thus far. I am not asking for a summary of the field; I am asking for people with a general knowledge of the field to offer some algorithms that might be useful for this specific task. I have not spent years researching in this field (nor do I want to) and some people might be familiar with algorithms which I am not. This is why I'm asking the question. $\endgroup$
    – Orby
    Jun 29, 2016 at 18:29
  • $\begingroup$ 1. Please edit the question to incorporate this information. We want questions to be self-contained (people shouldn't have to read the comments to understand what you are asking). 2. So what have you found in your research so far? Which algorithms specifically have you tried? Why have you rejected LZ-based approaches? Was their compression ratio worse, empirically? Something else? It'd help if you describe which algorithms you've already considered and why specifically you rejected them, so we don't waste our time suggesting something you've already tried. $\endgroup$
    – D.W. ♦
    Jun 29, 2016 at 18:31
  • 1
    $\begingroup$ Two of your three reasons for rejecting LZ-based methods seem... unconvincing/odd to me. The implementation of a LZ-based decoder is very simple (and your question states you mainly care about the size of the decompressor). And my sense is that theoretical results on performance are almost totally useless in this context. All that matters is empirical performance. What did you find in your empirical experiments? How much worse were LZ based methods in your experiments, and which LZ-based methods did you try? $\endgroup$
    – D.W. ♦
    Jun 29, 2016 at 18:50
  • 1
    $\begingroup$ Let me mention Storer, James A. "Data Compression: Methods and Theory", Computer Science Press 1988 ISBN 0-88175-161-8 (9" hardcover). Contains not only hardness results, but addresses Kolmogorov complexity directly. (If memory serves, just about any algorithm picking an optimal dictionary based on the data to compress is NP-hard.) $\endgroup$
    – greybeard
    Jul 3, 2016 at 9:06

1 Answer 1

Reset to default
1
$\begingroup$

I expect short decompressors with algorithms that do not maintain an explicit model and use "simple" encodings. An LZ encoding might use (length, offset) with Fibonacci coding, with an offset of 0 meaning a run of length literal codes, (minus) one a repetition of the last code, ….
I expect decompressor size to depend on (possibly abstract) machine - "MS Windows x64", NC4000, …
(The implied model being Things seen before are more likely than anything new, with short, local repetitions more likely than large ones from way back.)
That said, you may be after shortest length of compressed code+decompressor - Kolmogorov complexity.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.