3 ms·

How does this compress data though even if you could easily find parent states? Don't you have to have at least one bit per cell (alive or dead) for your whole

How does this compress data though even if you could easily find parent states? Don't you have to have at least one bit per cell (alive or dead) for your whole grid? You have some information which is X bits long, so you turn it into a game of life board. Then you find a parent state which is still X bits long. How does that help with compression?

waltbosz 7y ago
I should explain ... the extent of my knowledge of data compression is pretty nil. I could tell you how run length encoding works, but that's about it. More than anything, it's a fantasy compression scheme. I was originally inspired by rainbow tables (https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table) . The idea would be some sort of compression where there would be a table of uncompressed data blobs that map to some sort of hash key. The compressed file would be a sequence of the key. If you're reading this and you have a working knowledge of data compression, I imagine this is throwing off all sorts of red flags in your head. Feel free to explain why it wouldn't work.
- gus_massa 7y ago
  Wikipedia is always is good start and it is better written than what I can type just now. Take a look specially at the "limitations" section. https://en.wikipedia.org/wiki/Lossless_compression#Limitations https://en.wikipedia.org/wiki/Lossless_compression#Limitatio...
- ALittleLight 7y ago
  I could see Game of Life as part of a DIY steganography scheme. E.g. I tweet a picture and have some numerals in my tweet called N. You download the picture and convert it via an agreed on protocol to a game of life board, then advance the board by N times. Then you convert the board back to bits and then to text, and find somewhere in the text a "Message begins: XXX. Message ends." Sequence. I wonder if you would be able to hide messages in superficially normal pictures like that.
1-more 7y ago
You might be able to start with a much smaller starting state. Like the R pentomino starts with a tiny starting state and runs for a very long time before entering a quiescent state. So your encoding scheme could be just enough info to say "a grid with dimensions h_0 by w_0 filled with bit pattern b_0, run for n generations, then take the bit pattern b_n from the cells in the rectangle with dimensions h_n by w_n with top left corner at x_n y_n from our initial top left corner." As long as h_0 times w_0 is pretty small compared to h_n by w_n you'll come out with compression. https://www.conwaylife.com/wiki/R-pentomino https://www.conwaylife.com/wiki/R-pentomino
- ALittleLight 7y ago
  That's really interesting and seems like it could (in theory) work, though it would be challenging and time consuming to actually compress data this way.
  - 1-more 7y ago
    oh yeah like the paper says it's doing SAT a lot of times. Nearest I can tell the time complexity for each bit of the output is O(n!) where n is the size of the (unknown and you are solving for it) input bit pattern. So total time complexity is something like O(n! * w_n * h_n) which is BIG and stupid and might make this actually not a way to beat the optimum compression ratio dictated by entropy.

waltbosz 7y ago

I should explain ... the extent of my knowledge of data compression is pretty nil. I could tell you how run length encoding works, but that's about it. More than anything, it's a fantasy compression scheme. I was originally inspired by rainbow tables (https://en.wikipedia.org/wiki/Rainbow_table https://en.wikipedia.org/wiki/Rainbow_table) . The idea would be some sort of compression where there would be a table of uncompressed data blobs that map to some sort of hash key. The compressed file would be a sequence of the key. If you're reading this and you have a working knowledge of data compression, I imagine this is throwing off all sorts of red flags in your head. Feel free to explain why it wouldn't work.

gus_massa 7y ago
Wikipedia is always is good start and it is better written than what I can type just now. Take a look specially at the "limitations" section. https://en.wikipedia.org/wiki/Lossless_compression#Limitations https://en.wikipedia.org/wiki/Lossless_compression#Limitatio...
ALittleLight 7y ago
I could see Game of Life as part of a DIY steganography scheme. E.g. I tweet a picture and have some numerals in my tweet called N. You download the picture and convert it via an agreed on protocol to a game of life board, then advance the board by N times. Then you convert the board back to bits and then to text, and find somewhere in the text a "Message begins: XXX. Message ends." Sequence. I wonder if you would be able to hide messages in superficially normal pictures like that.

1-more 7y ago

You might be able to start with a much smaller starting state. Like the R pentomino starts with a tiny starting state and runs for a very long time before entering a quiescent state. So your encoding scheme could be just enough info to say "a grid with dimensions h_0 by w_0 filled with bit pattern b_0, run for n generations, then take the bit pattern b_n from the cells in the rectangle with dimensions h_n by w_n with top left corner at x_n y_n from our initial top left corner." As long as h_0 times w_0 is pretty small compared to h_n by w_n you'll come out with compression. https://www.conwaylife.com/wiki/R-pentomino https://www.conwaylife.com/wiki/R-pentomino

ALittleLight 7y ago
That's really interesting and seems like it could (in theory) work, though it would be challenging and time consuming to actually compress data this way.
- 1-more 7y ago
  oh yeah like the paper says it's doing SAT a lot of times. Nearest I can tell the time complexity for each bit of the output is O(n!) where n is the size of the (unknown and you are solving for it) input bit pattern. So total time complexity is something like O(n! * w_n * h_n) which is BIG and stupid and might make this actually not a way to beat the optimum compression ratio dictated by entropy.