Frankly, learning about LZW[0][1] and the Burrows-Wheeler Transform[2] was probably one of the highlights of my first undergrad algorithms course. The latter certainly made me feel like an idiot, too.

[0] http://en.wikipedia.org/wiki/Lempel%E2%80%93Ziv%E2%80%93Welc...

[1] For the record, LZW isn't used in gzip; it was the patent-encumbered compression format used in GIF.

[2] http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transfo... (used in bzip2)