What decompression algorithms have the shortest implementations? 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?
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.