Data compression

Is it possible or has it ever been theorised that data could be compressed by storing it as a unique formula or algorithm, and seed, where the formula and seed size are less than the result (i.e. the data)?

Other urls found in this thread:

en.wikipedia.org/wiki/Fractal_compression
minecraft.gamepedia.com/Far_Lands
en.wikipedia.org/wiki/Pigeonhole_principle
twitter.com/NSFWRedditVideo

Yes that is how compression works.

I'm talking about going a step further, not just how lossless works. The best explanation I can think of is imagine a procedurally generated game, where a seed generates a map. Would it be possible to work backwards and calculate a seed from data and use this to create something much larger than the formula and seed ?

Yeah not to be a dick but that's basically what compression is.

Formula = code book
Seed = coded (compressed) message

Though, it's worth pointing out that the Formula or code book need not be smaller than the 'data' you are compressing. Think of a simple palette based image format. Assume it uses 24 bit color per pixel, but only uses about 16 total colors. 16 colors means each pixel could be represented uniquely by a 4-bit number that indexes each of the 16 colors. As long as everybody who uses that image format has the same 16 colors and indexing (codebook, formula, etc) you can compress by a factor of 6. Having said that, obviously 16*24 is bigger than any one pixel prior to compression.

Thanks, I may as well go full retard on this. So to build upon my example, in Minecraft a seed generates an infinite map, if you walk in one direction it will keep generating the map as you need it. What would the limitation be of creating such a algorithm that would "compress" the data by allowing you to generate it as you need?

If information isn't there, there's no way to get it back.
Suppose I have a rectangle, 6 units by 8 units, and I ask you the area. Those numbers, plus your pre-existing knowledge of what a "rectangle" is and how to do multiplication enabled you to answer "48". Which is more compact than the original data. 1 number instead of 2.
But if tell you a rectangle has an area of 48 square units and ask for the dimensions -- you're stuck! In solving the original problem, information has been lost.

The maps in videogames are procedural, the result of algorithms building off a seed. If the seed contains less information than the original map (can be completely defined in fewer bits) then there necessarily will be losses.

There are two parts and you've only dealt with the second; reconstructing a data set from a compressed seed.
But only SOME datasets can be compressed into a seed without losses.
en.wikipedia.org/wiki/Fractal_compression
does the job but it's lossy even though you can zoom in to the image and see infinite detail. It some point, it stops matching the original.

>in Minecraft a seed generates an infinite map
False

Huh, interesting

Yes, you are exactly describing the Kolmogorov complexity. Check it out, it's interesting.

Unless its random data

What the fuck limits the size of the minecraft world? That seems so arbitrary.

2^64-1 blocks wide and long since you add one to that and it loops around to zero. Technically the minecraft world is a sphere.

>Technically the minecraft world is a sphere.
Oh really?

Probably an upper limit on numbers representable by a standard 64-bit computer.

>Keep walking in one direction
>End up back where you started
At the very least it's something homeomorphic to a sphere.

>End up back where you started
Except you don't end up where you started. There is a world border in each of the four directions.

The limitation is that many possible maps simply cannot be generated by the algorithm at all, in fact, the maximum number of maps that can be generated by a seed of bitsize n is 2 to the n, the loss is in that you cannot store many of the maps you may like to store in a small seed

Seems like that was added recently because the game would crash well before the theoretical border
minecraft.gamepedia.com/Far_Lands

Thanks, you really answered the question best

Ever heard of the field called information theory? That's the very thing it studies. And what you just described is called........ compression. So yes, compression is compression. Congrats you're gene-(You)s.

Periodicity in the rng and the underlying number representation (which is itself limited because computers are not made of infinite numbers of atoms), but also minecraft arbitrarily limits the size of generated maps much further than could be allowed.

There is no representation limit inherent to the instruction width of modern cisc processors.

i thought about it. just think about how many data is stored in pi function.
what if we use genetic algorithm to generate a function that can output desired value

ITT: niggers who haven't heard of pifs

>Yes that is how compression works.

fpbp

en.wikipedia.org/wiki/Pigeonhole_principle

If you take a square or rectangle and connect the edges to their opposites you will end up with a torus, not a sphere.