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?