El algoritmo de compresión lz77 pertenece a la familia de compresores sin pérdida, también llamados compresores de texto, a los cuales se les llama así porque no omiten información del archivo al comprimirlo, al contrario que los compresores que utilizan algoritmos del tipo lossy, que omiten algo de información pero que disminuyen considerablemente el tamaño del archivo original, el cual es el caso de los archivos MP3, MPG, jpeg, etc.
Los compresores basados en algoritmos sin pérdida se utilizan cuando la información a comprimir es crítica y no se puede perder información, por ejemplo en los archivos ejecutables, tablas de bases de datos, o cualquier tipo de información que no admita pérdida.
El modelo lz77 es muy usado porque es fácil de implementar y es bastante eficiente.
En 1977 Abraham Lempel y Jacob Ziv presentaron su modelo de compresión basado en diccionario, para compresión de texto –compresión de texto se refiere a compresión sin pérdida para cualquier tipo de datos–. Hasta la fecha todos los algoritmos de compresión desarrollados eran básicamente compresores estáticos. El nuevo modelo fue llamado lz77 (por razones obvias). La salida consistía siempre en desplazamientos o corrimientos y tamaños del texto visto anteriormente. También se incluía en la salida el siguiente byte después de una coincidencia, porque el contexto (últimos bytes vistos) de este byte es la frase, y si no era parte de la frase (la coincidencia), luego tal vez no se había comprimido, así que, ¿Para que desperdiciar tiempo tratando de encontrar una coincidencia (o espacio) para él?
En 1982 James Storer y Thomas Szymanski basados en el trabajo de Lempel y Ziv, presentaron su modelo, el lzss. La diferencia principal es en la salida, lz77 siempre daba un para desplazamiento/tamaño, aún si la coincidencia era de un solo byte (en cuyo caso usaban más de ocho bits para representar un byte) de manera que el LZSS usa otro truco para mejorarlo: usa banderas (flags), que ocupan un solo bit y nos informan de lo que viene luego: una literal o un par desplazamiento/tamaño y este algoritmo es el que actualmente usamos, pero el lzss es comúnmente llamado lz77, así que lo llamaremos lz77 de este punto en adelante, pero es importante recordar que también puede ser llamado LZSS. LZSS también puede usar árboles binarios o árboles de sufijos para hacer búsquedas más eficientes.
La teoría es muy simple e intuitiva. Cuando se haya una coincidencia (también llamada frase o conjunto de bytes que ya han sido vistos en el archivo de entrada) en lugar de escribir dichos bytes se escribe el desplazamiento o tamaño de la repetición: dónde está y su longitud.
Éste es un modelo basado en diccionario, porque se mantiene un diccionario (que en este caso se conoce como “Ventana Corrediza”) y se hace referencia a ella con pares desplazamiento/tamaño. Esta versión de lz77, usa una ventana corrediza, la cual tiene un tamaño máximo, de manera que la ventana no puede ser el archivo completo, en su lugar, la ventana corrediza mantiene los últimos bytes “vistos”.
Imaginemos que estamos comprimiendo el texto “ab ab”, leemos hasta “ab ” y lo escribimos sin comprimir, luego leemos “ab” y escribimos lo siguiente: con el “desplazamiento” de 0 se halló una coincidencia de dos bytes repetidos.
Bien, aqui la implementación en python:
Compresor :
#Autor: determx
#Fecha: 14/11/2009
#Version : 1.0.0
import os
import string
#Funcion que devuelve el archivo de texto en una lista
def Leer_Fichero(Ruta):
if os.path.exists(Ruta):
archivo = open(Ruta)
datos = []
for linea in archivo:
datos.append(linea)
archivo.close()
return datos
#Funcion para escribir texto comprimido en archivo
def Escribe_Fichero(Ruta,Texto,lInsp,lMem):
archivo = open(Ruta,"w")
archivo.write(str(lInsp) + '\n')
archivo.write(str(lMem) + '\n')
archivo.write(Texto)
archivo.close()
#Function para codificar
def _encode(prim,cnt):
aux = '(' + str(hex(prim))[2:] + ',' + str(hex(cnt))[2:] + ')'
return aux
#Cadena con espacios
def _blancos(Cad,Cantidad):
Cad = Cad + " " * Cantidad
return Cad
#Inserta blancos al frente
def _fblancos(Cad,Cantidad):
Cad = " " * Cantidad + Cad
return Cad
#Mueve caracteres a la ventana de inspeccion
def _toshift(Vdel,Vins,cantidad):
Vins = Vins[cantidad:] + Vdel[:cantidad]
Vdel = Vdel[cantidad:]
return Vdel,Vins
#Funcion para buscar coincidencias
def _matches(mem,insp):
while insp != '':
pos = string.find(mem,insp)
if pos != -1:
break
else:
insp = insp[:-1]
return pos,len(insp)
#Funcion que devuelve un texto comprimido
def Comprimir(Texto,TamInsp,TamMem):
V_Mem = ''
V_Insp = ''
V_Mem = _blancos(V_Mem,TamMem)
V_Insp = _blancos(V_Insp,TamInsp)
Comprimido = [] #Array donde junto el texto a guardar
for L in Texto:
cant = len(L)
cont = 1
shcant = cont
L_Comp = "" #Linea a comprimir
L, V_Insp = _toshift(L,V_Insp,szInsp)#Inicializo mi ventana insp
L = _blancos(L,szInsp)
while cont < cant:
inicio,fin = _matches(V_Mem,V_Insp)
#Unicamente se codificaran las coincidencias
#mayores a la codificacion
if (fin - inicio) < len(str(szMem)*2)+3:
L_Comp = L_Comp[:] + V_Insp[0]
#Muevo un solo caracter del texto a inspeccion
shcant = 1
cont += shcant
else:
L_Comp = L_Comp[:] + _encode(inicio,fin)
shcant = fin
cont += shcant
V_Insp, V_Mem = _toshift(V_Insp,V_Mem,shcant)
V_Insp = _fblancos(V_Insp,shcant)
L, V_Insp = _toshift(L,V_Insp,shcant)
L = _blancos(L,szInsp)
Comprimido.append(L_Comp)
return '\n'.join(Comprimido)
#Main
Ruta = raw_input('Ruta de archivo a comprimir>')
Dest = raw_input('Ruta destino de compresion>')
Documento = Leer_Fichero(Ruta);
szInsp = int(raw_input('Tamaño ventana inspeccion>'))
szMem = int(raw_input('Tamaño ventana memoria>'))
if Documento != None:
Txt_Comp = Comprimir(Documento,szInsp,szMem)
Escribe_Fichero(Dest,Txt_Comp,szInsp,szMem)
print ('GOOD!')
else:
print "NO EXISTE EL ARCHIVO/ARCHIVO VACIO"
Descompresor:
#Autor: determx
#Fecha: 14/11/2009
#Version : 1.0.0
import os
import string
#Funcion que devuelve el archivo de texto en una lista
def Leer_Fichero(Ruta):
if os.path.exists(Ruta):
archivo = open(Ruta)
datos = []
for linea in archivo:
datos.append(linea)
archivo.close()
return datos
#Funcion para escribir texto comprimido en archivo
def Escribe_Fichero(Ruta,Texto):
archivo = open(Ruta,"w")
archivo.write(Texto)
archivo.close()
#Funcion que devuelve inicio y fin en enteros
def _decode(Coded):
poscoma = string.find(Coded,',')
if poscoma != -1:
try:
ini = int(Coded[1 : poscoma],16)
except:
return 0,0
try:
fin = int(Coded[poscoma + 1: len(Coded)-1],16)
except:
return 0,0
return ini,fin
else:
return 0,0
#Cadena con espacios
def _blancos(Cad,Cantidad):
Cad = Cad + " " * Cantidad
return Cad
def Descomprime(Texto):
szInsp = int(Texto[0])
szMem = int(Texto[1])
Texto = Texto[2:]
l_Descomp = []
V_Mem =''
V_Mem = _blancos(V_Mem,szMem)
for l in Texto:
s_Descomp = ''
while l != '\n' and l!= '':
if l[0] != '(':
V_Mem = V_Mem[1:] + l[0]
s_Descomp = s_Descomp + l[0]
l = l[1:]
else:
PosFin = string.find(l,')')
Encoded = l[0:PosFin+1]
i,f = _decode(Encoded)
if (i != 0 or f !=0):
s_Descomp = s_Descomp + V_Mem[i:i+f]
V_Mem = V_Mem[f:] + V_Mem[i:i+f]
l = l[PosFin+1:]
else:
V_Mem = V_Mem[1:] + l[0]
s_Descomp = s_Descomp + l[0]
l = l[1:]
l_Descomp.append(s_Descomp)
return '\n'.join(l_Descomp)
#MAIN
Path = raw_input('Ingresa ruta archivo comprimido>')
Dest = raw_input('Ruta destino de compresion>')
Documento = Leer_Fichero(Path)
toArchivo = Descomprime(Documento)
Escribe_Fichero(Dest,toArchivo)
print('GOOD!')
Por supuesto, hacen falta muchas mejoras, me gustaría su opinión.
Mostrar Temas
Alguien tiene idea?