Compresión Lempel-Ziv

En el Technion de Haifa, el informático Abraham Lempel y el teórico de la información Jacob Ziv publicaron «A Universal Algorithm for Sequential Data Compression» (LZ77) en 1977, seguido de LZ78 en 1978. Su idea clave era que un compresor no necesita conocer de antemano las estadísticas de los datos: sustituye las cadenas repetidas por breves referencias a apariciones anteriores y construye su diccionario a medida que lee. El método funciona bien con casi cualquier tipo de datos y se decodifica con rapidez.

La variante de Terry Welch de 1984, LZW, impulsó las imágenes GIF, el formato TIFF y la herramienta compress de Unix, mientras que LZ77 combinado con la codificación de Huffman se convirtió en DEFLATE, el motor de ZIP, gzip, PNG y la compresión de páginas web. Casi todos los ordenadores y teléfonos ejecutan a diario métodos de Lempel–Ziv. La obra fue nombrada Hito del IEEE en 2004, y Ziv recibió la Medalla de Honor del IEEE en 2021.