Be sure you carefully review the limitations of any compression algorithm you consider. Some compression schemes can be lossy (jpeg); some (lossless) preserve the original data.

I think this might actually be possible without having to save a bunch of states for the window. What you need is some kind of "random.previous" function (as opposed to the traditional "random.next" function found in most languages). However as far as I know no programming language supports this. I would recommend programming your own PRNG from scratch for this task. Assign each window it's own random class and once it needs to be put back together just throw the PRNG in reverse.

Any where exactly are you planning to get the random number to reverse from, given the existing game state?

Plus of course any random number generator using a modulus can't have a previous method, since data is lost at each iteration.