T3: Text compression

Para la actividad de esta clase se creo un programa que usa el algorítmo de Huffman para hacer compresión de texto. El algorítmo de Huffman es fácil simplemente por cada letra del texto se guarda un nodo en el árbol, dicho árbol contiene todas las letras que contiene el texto, si la letra se repite en conjunto con otras letras este se le crea un nodo padre junto con la letra que se repite; Esto se hace con el propósito de que se usen de una manera casi igual a los diferentes nodos.

	import pickle
	import codecs
	from sys import argv
	#Clase del nodo
	class Node:
	def __init__(self, symbol, nodeLeft, nodeRight, frequency):
	self.label = ''
	self.symbol = symbol
	self.nodeLeft = nodeLeft
	self.nodeRight = nodeRight
	self.frequency = frequency
	return
	#impresion del simbolo y frecuencia del nodo
	def __repr__(self):
	return '( %s ) [%s] %d' % (self.label, str(self.symbol), self.frequency)
	#Se agrega un nodo al nodo padre
	def name(self, prefix):
	self.label = prefix
	if self.nodeLeft is not None:
	self.nodeLeft.name('%s1' % self.label)
	if self.nodeRight is not None:
	self.nodeRight.name('%s0' % self.label)
	return
	#Itera recursivamente el arbol regresandole el valor binario de una letra
	def decode(self, binary):
	if self.symbol is not None:
	return (self.symbol, binary)
	else:
	assert(self.nodeLeft is not None)
	assert(self.nodeRight is not None)
	bit = binary[0]
	binary = binary[1:]
	if bit == '1':
	return self.nodeLeft.decode(binary)
	elif bit == '0':
	return self.nodeRight.decode(binary)
	else:
	print 'Something is wrong.'
	return
	#nos devuelve un dictionary con todos los nodos hijos del nodo
	def insert(self, dictionary):
	if self.nodeLeft is not None:
	self.nodeLeft.insert(dictionary)
	if self.nodeRight is not None:
	self.nodeRight.insert(dictionary)
	if self.symbol is not None:
	dictionary[self.symbol] = self.label
	return
	def main():
	#se escoge la opcion de comprimir o descomprimir
	opcion = raw_input("--> Desea comprimir o descomprimir? comprimir / descomprimir / cancelar (cancel) >")
	#se obtiene el nombre del archivo
	nombre_de_archivo = raw_input("--> Ingrese el nombre del archivo >")
	#si la opcion es comprimir entonces
	if opcion == "comprimir":
	#abre un archivo del texto
	archivo = codecs.open(nombre_de_archivo, 'r', encoding='utf-8')
	#contenido del archivo se lee
	contenido = archivo.read()
	datos = ''
	#Se lee el contenido linea por linea
	for line in contenido:
	datos = '%s%s'%(datos, line)
	#Se crea el diccionario
	dictionary = dict()
	#se cierra el archivo
	archivo.close()
	#se guarda en el diccionario y se agrega un contador de frecuencias
	for s in datos:
	if s in dictionary.keys():
	dictionary[s] += 1
	else:
	dictionary[s] = 1
	#se crea una lista para contener los nodos
	node_list = list()
	#se itera cada letra para agregarla como nodo
	for d in dictionary.keys():
	node_list.append(Node(d, None, None, dictionary[d] ))
	#se itera la lista de nodos y se ordena la lista de los cuales toma el menos frecuente de los nodos
	# y los junta y crea un nuevo nodo con dos nodos combinados esto lo hace hasta que la lista quede uno
	while len(node_list) > 1:
	node_list.sort(key=lambda n: n.frequency)
	min1 = node_list.pop(0)
	min2 = node_list.pop(0)
	node_list.append(Node(None, min1, min2, min1.frequency + min2.frequency))
	# el ultimo nodo es el nodo padre
	root = node_list.pop(0)
	root.name('')
	code = dict()
	#extraemos los nodos en un dictionary
	root.insert(code)
	#se crea un archivo donde contiene el arbol de los datos
	archivo_del_objeto = open('%s.objeto'%(nombre_de_archivo),'w')
	pickle.dump(root, archivo_del_objeto)
	archivo_del_objeto.close()
	binary = ''
	#se crea el valor en "binario"
	for s in datos:
	binary = '%s%s' % (binary, code[s])
	#crea el archivo con el contenido "binario"
	nuevo_archivo = open("%s.compress"%(nombre_de_archivo),'w')
	nuevo_archivo.write(binary)
	nuevo_archivo.close()
	print "%s"%(time.clock())
	elif opcion == "descomprimir":
	#Se extrae el archivo .objeto que contiene el arbol de la informacion
	archivo_del_objeto = open('%s.objeto'%(nombre_de_archivo),'r')
	#se carga el archivp
	root = pickle.load(archivo_del_objeto)
	archivo_del_objeto.close()
	#se extrae el diccionario con la informacion
	code = dict()
	root.insert(code)
	#se abre un archivo con prefijo compress para poner ahí la información
	#comprimida
	nuevo_archivo = open("%s.compress"%(nombre_de_archivo),'r')
	binary = nuevo_archivo.read()
	nuevo_archivo.close()
	recovered = ''
	#Se extrae el texto apartir del binario por medio de una funcion
	#del mismo objeto que decodifica el contenido buscando en los nodos
	# hijos la letra correspondiente
	while len(binary) > 0:
	(symbol, binary) = root.decode(binary)
	recovered = '%s%s' % (recovered, symbol)
	# se guarda el archivo decomprimido
	nuevo_archivo = codecs.open("%s.decompress"%(nombre_de_archivo),'w', encoding="utf-8")
	nuevo_archivo.write(recovered)
	nuevo_archivo.close()
	elif opcion == "cancelar":
	print "--> BYE."
	main()

view raw huffman.py hosted with ❤ by GitHub

Para correr el programa hacemos los siguiente y nos mostrará las siguientes instrucciones:


Realmente los archivos creados al momento de comprimir fueron muy pesados porque utilice un formato de strings y esta manera se incrementa el valor de cada variable en promedio del peso de la variable de string es de 24 bytes y el de una representación binaria consta de un peso de 12 bytes esto probandoló en Python.

Ahora viendo esto si vemos los siguientes pesos de los textos comprimidos podemos ver que hay una gran diferencia de pesos pero si supones que el peso es de la mitad podemos decir que en el peor caso se encuentra el archivo pequeño ya que el archivo original pesa 1KB pero si examinamos el comprimido podremos ver que nos genera uno de 5KB luego de ver lo anterior podemos casi asegurar que su peso usando el formato binario sería de 2.5KB.

Según lo que confirme experimentando con compresiones tipos zip es que a como vaya creciendo el texto la compresión va ir reduciendo su tamaño ya que si haces una compresión con un archivo pequeño no se verá gran diferencia y al contrario de esto pasa con archivos de tamaño considerable. Aquí podemos ver un ejemplo comparativo.