In [ ]:
'''
Implementad en Java un compresor/descompresor de datos binarios mediante el algoritmo LZ-77. Debe cumplir las siguientes
especificaciones:
1. Formato de entrada y salida de datos: String binaria (unos y ceros) de longitud arbitraria.
2. Posibilidad de configurar a longitud de la Ventana de Entrada (Ment) y Ventana Deslizante (Mdes) variables.
3. Control de configuración válida; Ment y Mdes deben ser:
potencias de 2
Ment<=Mdes
Mdes+Ment<= longitud datos a comprimir
4. Formato datos comprimidos: String binaria con
1. Cabecera con los primeros “Mdes” bits de los datos de entrada
2. Almacenar TODAS las coincidencias (L,D) (incluso las de L=1) en formato binario de longitud fija (log2(Ment) + log2(Mdes) bits en total)
Ejemplo: si Ment = 4 y Mdes = 8
(1,1) se guarda como “01 001”
(2,6) se guarda como “10 110”
(3,8) se guarda como “11 000”
(4,5) se guarda como “00 101”
3. La búsqueda de coincidencias finaliza cuando los bits que quedan por procesar són menos que Ment.
En tal caso, guardar estos bits restantes al final de la cadena comprimida.
In [1]:
import numpy as np
# * * * * * * * * * * * * * * * * * * * * *
# * TECNOLOGIES MULTIMEDIA *
# * - - - - - - - - - - - - - - - - - - - *
# * Compression Alg based on Lempel-Ziv *
# * @Vicent Roig Ripoll *
# * * * * * * * * * * * * * * * * * * * * *
class Compressor:
def __init__(self):
self.MentLength = 4 #tamaño ventana de entrada
self.MdesLength = 8 #tamaño ventana deslizante
self.pr = int(np.log2(self.MentLength))
self.pt = int(np.log2(self.MdesLength))
def compress(self, data, MentLength = None, MdesLength = None):
"""Compresses text data using the LZ77 algorithm."""
if MentLength == None:
MentLength = self.MentLength
if MdesLength == None:
MdesLength = self.MdesLength
if ((self.__is_power2(MentLength)==False) or (self.__is_power2(MdesLength)==False)):
raise Exception(">> MdesLenght AND MentLength MUST be a power of 2")
if MentLength > MdesLength:
raise Exception(">> MdesLenght(%d) should be GREATER than MentLength(%d)" % (MdesLength, MentLength))
if MdesLength+MentLength > len(data):
raise Exception(">> MdesLenght AND MentLength overflows data input")
pos = 0
lastPos = len(data)
compressed = ''.join(str(e) for e in data[pos : pos + MdesLength]) #compression saved initial sliding window values
while pos < lastPos:
#end condition
if len(data[pos + MdesLength :]) < MentLength:
compressed += ''.join(str(e) for e in data[pos + MdesLength :])
break
mdes = data[pos : pos + MdesLength]
str1 = ''.join(str(e) for e in mdes)
ment = data[pos + MdesLength : pos + MdesLength + MentLength]
for i in range(len(ment)):
#print mdes, ment[:len(ment)-i]
str2 = ''.join(str(e) for e in ment[:len(ment)-i])
index = str1.rfind(str2)
if (index!=-1):
#print (len(str2), len(str1)-index)#, format(len(str2), '0'+str(self.pr)+'b')[-self.pr::], format(len(str1)-index, '0'+str(self.pt)+'b')[-self.pt::]
compressed += format(len(str2), '0'+str(self.pr)+'b')[-self.pr::] + format(len(str1)-index, '0'+str(self.pt)+'b')[-self.pt::]
pos += len(str2)
break
return compressed
def decompress(self, data):
"""Decompresses LZ77 compressed text data"""
data = list(data)
lastPos = len(data)
decompressed = []
for i in range(self.MdesLength):
decompressed += data.pop(0)
while len(data)>1:
if(len(data) > (2**self.pr-1)):
L = [int(i) for i in data[:self.pr]]
D = [int(i) for i in data[self.pr:self.pr+self.pt]]
for i in range(self.pr+self.pt):
data.pop(0)
#controls if we need to add new MSB to 1
if(sum(L)==0):
L = ['1']+L
if(sum(D)==0):
D = ['1']+D
# retrieve decimal lenght and distance from binary string
L = int(''.join(str(e) for e in L), 2)
D = int(''.join(str(e) for e in D), 2)
#print (L,D), decompressed, decompressed[-D:][:L]#decompressed[-D:-D+L]
decompressed += decompressed[-D:][:L]
else:
decompressed += data
break
return ''.join(str(e) for e in decompressed)
def __is_power2(self, num):
'states if a number is a power of two'
return num != 0 and ((num & (num - 1)) == 0)
In [2]:
#Testing:
#data = [1,1,0,1,1,1,1,0,1,0,1,0,0,1,1,1,1,0,1,0,1,0,0,0,1,0,0,0,1] #Exc. 3 as an example
N = 25
data = np.random.choice([0, 1], size=N)
data[0] = 1 #let's set 10 the first 2 bits to avoid homegeneous initial slideWin
data[1] = 0
compressor = Compressor();
compr = compressor.compress(data)
dcompr = compressor.decompress(compr)
print 'Input:\t\t', ''.join(str(e) for e in data), len(data)
print 'Compressed:\t', compr, len(compr)
print 'Decompressed:\t', dcompr, len(dcompr)
Utilizad el programa anterior para determinar si es posible, ajustando los valores de Mdes y Ment, conseguir comprimir datos aleatorios mediante LZ77 (es decir, que la cadena de datos originales sea más larga que la cadena comprimida).¿Por qué? ¿Cuál es la máxima compresión que lográis? ¿Con qué valores? (Ayuda: utilizad una cadena de datos de entrada de, por lo menos, 10000 bits aleatorios. Ajustad Mdes y Ment entre 2 y 2048).
In [130]:
#Testing:
N = 10000
data = np.random.choice([1,0], size=N)
data[0] = 1 #let's set to 10 the first bits avoiding homegeneous initial slideWin
data[1] = 0
compressor = Compressor();
print 'Input length:\t', len(data)
print 'Compressed:\t', len(compressor.compress(data, 512, 1024))
Observamos que para una cadena relativamente pequeña de bits aleatorios (<200), el algoritmo LZ77 no nos proporciona capacidad de compresión en la gran mayoría de casos (distribución heterogéneos de bits). Esto es debido a que la propia codificación requiere guardar la información que nos permita recuperar los datos originales, y en caso de existir baja redundancia, en los casos en los que tenemos ventanas pequeñas no seremos capaces de detectar patrones largos y ésta información generada acabará ocupando más que que los datos propiamente dichos.
Esto tiene sentido debido a que la búqueda de patrones en tan pocos bits con un tamaño tan pequeño para las ventanas hace que podamos encontrar pocos "hits" a comprimir. Aún así si probamos con un vector de 1's o 0's comprobaremos que efectivamente si puede comprimir con éxito (recordemos que establecemos lo dos bits distintos inicialmente para evitar problemas), aunque obviamente no es un test realista.
La máxima compresión en repetidos ensayos para cadenas de más de 5000bits se situa en un ~40%. Una compresión muy aceptable.