I've never quite understood how its possible to create better encoders without needing a new decoder on the other end. Can anyone explain how this works? When you're writing a png decoder, why wouldn't there just be one optimal png encoder to go along with it?
Globally, because encoding and decoding are not the same thing. Encoding requires making choices about what to throw away, but decoding is just putting them back together. Mathematically you can think about encoding as converting to some matrix representation that has a lot of zeros -- the process to take that matrix and reconstruct the image doesn't depend on how many zeros there are, but the efficiency of the encoder does.
Perhaps an easier way to think about it from a programmer perspective.. a decoder is a programming language interpreter that takes a program and generates the data. The encoder is something that generates a program in that language. So you can see that the decoder is quite straight-forward, while the encoder has a lot of choices to make about how best to represent the data as a program in the decoder's language.
At least 2 people replied to you referencing the lossyness of the encoder, but that is actually completely irrelevant and unnecessary to answer your question, as it applies perfectly well to lossless compressors too.
See for example Zopfli and ZIP, which is obviously not lossy.
The situation exists because there are many alternative ways to represent a given, fixed output file, so that the job of the encoder is to seek through this search space and try to find a size-optimal solution, or a good approximation thereof.
It's best to think of many codecs ([en]CODers/DECoders) as sets of tools. The encoder "tools" can be used in many different ways (with different parameters and combinations) to produce valid encoded versions of input data. The decoder then uses various methods to take the tools and data used in the encoded version, and interpolates the encoded data into something resembling the original. Sometimes that interpolation is "lossy" (detail is lost, but may be acceptably close to the original), while other times it is "lossless" (decoded bit-for-bit to be the same as the original).
Just like there are many ways to encode data with a given codec/format, there are often many different ways (or tools used) to decode, some of which - as in the case of lossy codecs - may produce more "natural" or pleasing results than others. For example, some MPEG decoders will analyze motion vectors and interpolate extra spatial resolution that was not present in the original, thereby "upscaling" (e.g., from standard resolution to HD) the output. In this case, it's important to remember that data/detail is never created from nothing, but is instead "guessed", so it may produce nice-looking results, but it's also likely to introduce more artifacts (erroneous details that were actually not present in the original).
In lossy encoding you throw away data to get smaller file, and the art is in deciding which data you throw away.
In this case you need to do vector quantization — choose 256 colors (decoder's hard limit) that best represent thousands of different colors in the source image, e.g. you have to decide whether to use a palette entry for just a single red pixel, or maybe sacrifice that pixel and use the palette entry to improve smoothness of a more visible blue gradient.
This is a lossy encoder, which means that the image that comes out the other end doesn't contain exactly the same information as the image that goes in.
You can use all kinds of cleverness that is mostly unrelated to the actual image format itself to shrink the size of an image.
Here's one example: if an image uses millions of colours, you could drop it down to just using a few hundred colours (picking the nearest colour from your pallette to each of the pixels) and hence shrink the filesize a whole bunch. There are lots of different approaches to picking that initial pallette though - you might do it based on averaging out the pixel colours, or maybe you know something about human visual colour perception and can hence behave differently for colours that you don't think people will notice as easily.
For pngs (and lossless encoding) the thing is that the last step of encoding is a run of the deflate algorithm. It's impossible to say what exactly a stream will deflate down to without actually running your implementation of deflate. Possible encodings of an image pre-deflation are staggering, 5^height just for the filter step on all color types. I've been writing a brute force compressor (everything but the deflate step which depends on the implementation you choose) as a joke and it takes about an hour on images 10px high. For that reason encoders use heuristics to make best guesses whenever there's a choice to be made.
Oh and here's[1] a post I made about it. I decided to keep the project to myself as I'm making it into a more, uh, realistic png compressor, but that will give you an idea of all the possible descisions that need to be made while encoding.
