Para el que le interese, hay articulos muy buenos sobre el tema en muchas revistas de difusión y en internet.
Por ejemplo, uno de los algoritmos más antiguos es el Hoffman (creo que se escribía así) y tambien de los más eficientes: es el único capaz de llegar a la entropía (limite en el que teóricamente es imposible comprimir más), pero sólo en limitados casos, es muy lento, y requiere capacidades de calculo importantes. Una cosa curiosa de este algoritmo es que en archivos pequeños es muy poco eficiente, llegando incluso a ocupar más espacio los archivos comprimidos que los originales (me refiero a pequeños de verdad, del orden de pocos bytes).
Luego está el archiconocido Lempel-Ziv y su variante Lempel-Ziv-Welch (LZW). Este algoritmo no es el más eficiente, pero si que es muy rápido comprimiendo y descomprimiendo, hecho por el cual todos los módems lo utilizan para transferencias de datos. Tambien se utilizan en los archivos GIF y en el compresor de Linux GZIP. Desconozco si el ZIP esta basado en esto. Teoricamente la patente es propiedad de Unisys, por lo cual el GIF no es un formato libre (hay que pagar por usarlo), pero por suerte decidió no cobrar derechos de patentes a las librerías libres que aparecieron con anterioridad, por eso el GZIP y otros programas de Linux siguen siendo libres.
Y por ultimo esta el BZIP2, que no se que algoritmo usará, pero que es bastante más eficiente que GZIP y que ZIP. Sólo hay que mirar la lista de kernels de kernel.org para darse cuenta de la diferencia. Pero eso si, es mucho más lento.
Todo se basa en lo mismo, seguir patrones de repetición. Un ejemplo muy bueno sacado (curiosamente) de una novela de Michel Crichton, si tenemos una foto de una rosa, en vez de guardar un archivo que diga: pixel 1 rosa, pixel 2 rosa, pixel 3 rosa... guardamos un archivo que diga: pixel del 1 al 236 rosa.