LZ77
El algoritmo LZ77, tambien conocido como LZ1, es un método de compresión de datos sin pérdida desarrollado por Abraham Lempel y Jacob Ziv en 1977. Es uno de los algoritmos de compresión más antiguos y ha servido como base para muchos otros métodos modernos como LZSS, LZ78 y LZW, así como su aplicación en compresores como gzip y en formatos de archivo como ZIP. LZ77 se basa en la idea de identificar secuencias repetidas dentro de un flujo de datos y reemplazarlas por referencias más pequeñas, lo que reduce el tamaño total del contenido comprimido.
Definición
LZ77 trabaja utilizando una "ventana deslizante" para buscar coincidencias entre el texto actual que está procesando y los datos que ya ha procesado previamente. El flujo de entrada se divide en dos partes: la ventana, que contiene una cantidad limitada de datos ya procesados, y el búfer de anticipación, que contiene el próximo texto a procesar. La compresión ocurre al identificar secuencias en el búfer de anticipación que coinciden con las secuencias encontradas en la ventana. Luego, el algoritmo codifica las repeticiones mediante tuplas de la forma (desplazamiento, longitud, carácter siguiente), donde:
- Desplazamiento: indica la distancia desde la posición actual a la coincidencia más cercana.
- Longitud: representa la cantidad de caracteres coincidentes.
- Carácter siguiente: es el carácter que sigue a la secuencia coincidente, si existe.
El algoritmo básico para comprimir se ejecuta en un ciclo que sigue los siguientes pasos:
- Establece la posición de codificación al inicio del flujo de entrada.
- El algoritmo busca en la ventana (parte procesada) una coincidencia con la cadena en el búfer de anticipación (parte por procesar) que sea lo más larga posible.
- Una vez encontrada la coincidencia más larga se genera la tupla
(desplazamiento, longitud, carácter siguiente). - Si el búfer de anticipación no está vacío, vuelve al paso 2 y se avanza una posición.
Este enfoque permite reemplazar secuencias repetitivas con referencias más compactas, logrando así la compresión de datos con patrones redundantes de manera simple y rápida. Otras variaciones del algoritmo LZ77 incluyen cambiar el tamaño de los búferes de búsqueda y anticipación. Para hacer que el búfer de búsqueda sea grande, se requiere el desarrollo de estrategias de búsqueda más efectivas. Dichas estrategias pueden implementarse de manera más eficaz si el contenido del búfer de búsqueda se almacena de manera que facilite búsquedas rápidas.
Ejemplo
Compresión:
Empezaremos con un ejemplo considerando la entrada "ABABCABAB" :
Descompresión:
LZ77 se clasifica como un algoritmo de compresión de datos sin pérdida, lo que significa que deberíamos ser capaces de recuperar completamente la cadena original.
Así vemos cómo LZ77 utiliza su forma codificada para reproducir la entrada original.
Implementación del Algoritmo
A continuación, se presenta una implementación de LZ77 en Python:
Ver implementación LZ77 en Python
import math
from bitarray import bitarray
class LZ77Compressor:
"""
A simplified implementation of the LZ77 Compression Algorithm
"""
MAX_WINDOW_SIZE = 400
def __init__(self, window_size=20):
self.window_size = min(window_size, self.MAX_WINDOW_SIZE)
self.lookahead_buffer_size = 15 # length of match is at most 4 bits
def compress(self, input_file_path, output_file_path=None, verbose=False):
"""
Given the path of an input file, its content is compressed by applying a simple
LZ77 compression algorithm.
The compressed format is:
0 bit followed by 8 bits (1 byte character) when there are no previous matches
within window
1 bit followed by 12 bits pointer (distance to the start of the match from the
current position) and 4 bits (length of the match)
If a path to the output file is provided, the compressed data is written into
a binary file. Otherwise, it is returned as a bitarray
if verbose is enabled, the compression description is printed to standard output
"""
data = None
i = 0
output_buffer = bitarray(endian='big')
# read the input file
try:
with open(input_file_path, 'rb') as input_file:
data = input_file.read()
except IOError:
print('Could not open input file ...')
raise
while i < len(data):
#print(i)
match = self.findLongestMatch(data, i)
if match:
# Add 1 bit flag, followed by 12 bit for distance, and 4 bit for the length
# of the match
(bestMatchDistance, bestMatchLength) = match
output_buffer.append(True)
output_buffer.frombytes(bytes([bestMatchDistance >> 4]))
output_buffer.frombytes(bytes([((bestMatchDistance & 0xf) << 4) | bestMatchLength]))
if verbose:
print("<1, %i, %i>" % (bestMatchDistance, bestMatchLength), end='')
i += bestMatchLength
else:
# No useful match was found. Add 0 bit flag, followed by 8 bit for the character
output_buffer.append(False)
output_buffer.frombytes(bytes([data[i]]))
if verbose:
print("<0, %s>" % data[i], end='')
i += 1
# fill the buffer with zeros if the number of bits is not a multiple of 8
output_buffer.fill()
# write the compressed data into a binary file if a path is provided
if output_file_path:
try:
with open(output_file_path, 'wb') as output_file:
output_file.write(output_buffer.tobytes())
print("File was compressed successfully and saved to output path ...")
return None
except IOError:
print('Could not write to output file path. Please check if the path is correct ...')
raise
# an output file path was not provided, return the compressed data
return output_buffer
def decompress(self, input_file_path, output_file_path=None):
"""
Given a string of the compressed file path, the data is decompressed back to its
original form, and written into the output file path if provided. If no output
file path is provided, the decompressed data is returned as a string
"""
data = bitarray(endian='big')
output_buffer = []
# read the input file
try:
with open(input_file_path, 'rb') as input_file:
data.fromfile(input_file)
except IOError:
print('Could not open input file ...')
raise
while len(data) >= 9:
flag = data.pop(0)
if not flag:
byte = data[0:8].tobytes()
output_buffer.append(byte)
del data[0:8]
else:
byte1 = ord(data[0:8].tobytes())
byte2 = ord(data[8:16].tobytes())
del data[0:16]
distance = (byte1 << 4) | (byte2 >> 4)
length = (byte2 & 0xf)
for i in range(length):
output_buffer.append(output_buffer[-distance])
out_data = b''.join(output_buffer)
if output_file_path:
try:
with open(output_file_path, 'wb') as output_file:
output_file.write(out_data)
print('File was decompressed successfully and saved to output path ...')
return None
except IOError:
print('Could not write to output file path. Please check if the path is correct ...')
raise
return out_data
def findLongestMatch(self, data, current_position):
"""
Finds the longest match to a substring starting at the current_position
in the lookahead buffer from the history window
"""
end_of_buffer = min(current_position + self.lookahead_buffer_size, len(data) + 1)
best_match_distance = -1
best_match_length = -1
# Optimization: Only consider substrings of length 2 and greater, and just
# output any substring of length 1 (8 bits uncompressed is better than 13 bits
# for the flag, distance, and length)
for j in range(current_position + 2, end_of_buffer):
start_index = max(0, current_position - self.window_size)
substring = data[current_position:j]
for i in range(start_index, current_position):
repetitions = len(substring) // (current_position - i)
last = len(substring) % (current_position - i)
matched_string = data[i:current_position] * repetitions + data[i:i+last]
if matched_string == substring and len(substring) > best_match_length:
best_match_distance = current_position - i
best_match_length = len(substring)
if best_match_distance > 0 and best_match_length > 0:
return (best_match_distance, best_match_length)
return None
- Enlace al repositorio en Github con el código completo.
Usos Comunes
LZ77 se emplea en numerosos escenarios y aplicaciones debido a su enfoque eficiente para reducir redundancias en flujos de datos:
- Compresión de Archivos: LZ77 es la base de muchos formatos de compresión populares, como gzip y ZIP, que utilizan versiones adaptadas del algoritmo para mejorar la relación de compresión en archivos.
- Compresión de Imágenes y Videos: Aunque LZ77 no suele usarse directamente en imágenes y videos, muchas técnicas modernas derivadas, como el algoritmo DEFLATE (que combina LZ77 con codificación Huffman).
- Compresión de Texto: Debido a que LZ77 funciona bien con patrones repetitivos, se ha utilizado para comprimir texto con redundancias, como en documentos o archivos de registro.
Referencias
- Ziv, J., & Lempel, A. (1977). A universal algorithm for sequential data compression. IEEE Transactions On Information Theory, 23(3), 337-343. https://doi.org/10.1109/tit.1977.1055714
- Sayood, K. (2005). Introduction to Data Compression. Elsevier.
- EcuRed. (s. f.). LZ77 - ECURed. https://www.ecured.cu/Lz77
- Leonardo Araya. (2022, 25 octubre). Algoritmo de compresión LZ77 [Vídeo]. YouTube. https://www.youtube.com/watch?v=woWY9LUnqtg
- Computerphile. (2013, 1 noviembre). Elegant Compression in Text (The LZ 77 Method) - Computerphile [Vídeo]. YouTube. https://www.youtube.com/watch?v=goOa3DGezUA
- [MS-WUSP]: LZ77 Compression Algorithm. (2023, 11 abril). Microsoft Learn. https://learn.microsoft.com/en-us/openspecs/windows_protocols/ms-wusp/fb98aa28-5cd7-407f-8869-a6cef1ff1ccb
- Budhrani, D. (2020, 10 septiembre). How LZ77 Data Compression works. HackerNoon. https://hackernoon.com/how-lz77-data-compression-works-yk113te0