Text compression

Program: Implement the tree-based Huffman coding for Unicode strings, implementing the tree structure yourself.

For this first part I implemented a binary tree to find the codes for each symbol.

1. The first thing that I did was to create a frequency table.
2. Then I put in pairs the lighter weights until the end of the list.
3. I searched the tree to find the codes for each leaf

I have done a web application to display the Huffman coding in a binary tree, this is the URL:

http://huffmandemo.appspot.com/

And here is the example:

After the decoding algorithm, I did take the text file that I wrote in binary, and I found the equivalent to the tree that I had already done.

This is the example in the terminal encoding and decoding:

Analyze an experiment to determine the worst-case and typical-case complexity and compression ratio


I use texts of 3000 words, for the worst case I have done texts with the same frequency and for the typical case I take random Internet texts

Here I show some plots that I got when I did the experiment:

compression ratio

The best case is when all the probabilities of the symbols change in powers of 2. And the worst is when all the probabilities are equal.

The complexity of the algorithm is O(nlog n). Since it has an internal loop with logn complexity and then repeated n times, where n is the set of symbols.


And this is the code:

	#!/usr/bin/python
	DEBUG = True
	#DEBUG = False
	import string
	import time
	import random
	import matplotlib.pyplot as plt
	def genera_largos():
	"""
	"""
	largos = []
	for i in range(1,40):
	largos.append(i*80)
	return largos
	def genera_peor_caso(largos):
	"""
	"""
	caracteres = string.printable[:80]
	dic= {}
	cadena = ''
	for i in range(len(largos)):
	cadena = cadena + caracteres
	dic[largos[i]] = cadena
	return dic
	def probabilidad_tipica(largos):
	f = open("texto.txt")
	texto = f.read()
	texto = texto.replace("\n","")
	dic = {}
	total = len(texto)
	for i in range(len(largos)):
	inicio = random.randint(0, total/2)
	cadena = texto[inicio:(inicio+largos[i])]
	dic[largos[i]] = cadena
	return dic
	class Nodo:
	"""nodo hoja
	"""
	def __init__(self, simbolo, peso):
	self.simbolo = simbolo
	self.peso = peso
	self.der = None
	self.izq = None
	self.padre = None
	self.x = 0
	self.y = 50
	self.ancho = 3000
	self.largo = None
	def escribe_tabla(codigos):
	"""escribe el diccionario en un archivo
	"""
	f = open("tabla_frecuencias.txt", "w")
	for i in codigos:
	f.write("%s %s\n" %(i[0], i[2]))
	def escribe_frase_original(frase):
	"""escribe la frase original
	"""
	f = open("frase_original.txt", "w")
	f.write(frase)
	def escribe_codigos(frase, codigos):
	"""escribe la frase codificada
	"""
	f = open("frase_codificada.txt", "w")
	for i in frase:
	f.write("%s" %codigos[i])
	f.close()
	f = open("frase_codificada.txt")
	texto = f.read()
	return len(texto)
	def decodificar(raiz):
	"""decodifica
	"""
	f = open("frase_codificada.txt")
	frase_codificada = f.read()
	#print frase_codificada
	frase_encontrada = ""
	padre = raiz
	while len(frase_codificada)>0:
	s = str(frase_codificada[0])
	frase_codificada = frase_codificada[1:]
	if s == "0":
	raiz = raiz.der
	else:
	raiz = raiz.izq
	if raiz.der == None and raiz.izq == None:
	frase_encontrada = frase_encontrada+raiz.simbolo
	raiz = padre
	return frase_encontrada
	def codigos(hojas):
	"""obtiene los codigos haciendo un recorrido desde la
	hoja a la raiz
	"""
	lista = []
	dic = {}
	for i in hojas:
	byte = ""
	padre = i.padre
	actual = i
	while True:
	if padre:
	pass
	else:
	break
	if actual == padre.izq:
	byte = byte + "1"
	else:
	byte = byte + "0"
	actual = padre
	padre = padre.padre
	lista.append((i.simbolo, i.peso, byte[::-1]))
	dic[i.simbolo]=byte[::-1]
	if DEBUG:
	print lista, dic
	return lista, dic
	def obtiene_hojas(nodos):
	"""obtiene las hojas del arbol, recibe como entrada
	toda la lista de nodos
	"""
	hojas = []
	for nodo in nodos:
	if nodo.der == None and nodo.izq == None:
	hojas.append(nodo)
	if DEBUG:
	print "Numero de hojas %s" %(len(hojas))
	return hojas
	def recorrer(padre, lista_nodos, lista_pesos):
	"""recorrido en preorden solo para obtener la lista de
	todos los nodos
	"""
	if padre != None:
	lista_nodos.append(padre)
	lista_pesos.append(padre.peso)
	recorrer(padre.izq, lista_nodos, lista_pesos)
	recorrer(padre.der, lista_nodos, lista_pesos)
	return lista_nodos, lista_pesos
	def crea_arbol(frec, ordenados):
	"""hace el arbol de acuerdo a las frecuencias
	regresa la raiz del arbol
	"""
	nodos = []
	for i in ordenados:
	nodos.append(Nodo(i, frec[i]))
	while True:
	if len(nodos)>1:
	izq = nodos[0]
	nodos = nodos[1:]
	der = nodos[0]
	nodos = nodos[1:]
	x = Nodo(str(izq.simbolo)+str(der.simbolo), izq.peso + der.peso)
	x.izq = izq
	x.der = der
	nodos.append(x)
	der.padre = x
	izq.padre = x
	nodos = sorted(nodos, key=lambda x: x.peso)
	if DEBUG:
	print "*papa %s %s, *izq %s %s *der %s %s" %(x.peso, x.simbolo,
	x.izq.peso,x.izq.simbolo,
	x.der.peso,x.der.simbolo)
	elif len(nodos)==1:
	padre = Nodo(str(izq.simbolo)+str(der.simbolo), izq.peso + der.peso)
	padre.izq = izq
	padre.der = der
	nodos = []
	if DEBUG:
	print "*papa %s %s, *izq %s %s *der %s %s" %(padre.peso, padre.simbolo, padre.izq.peso,padre.izq.simbolo, padre.der.peso, padre.der.simbolo)
	else:
	break
	return padre
	def frecuencia(frase):
	"""obtiene la frecuencia de los simbolos
	en la frase
	"""
	frec = {}
	for l in frase:
	if not(l in frec):
	frec[l] = frase.count(l)
	ordenados = sorted(frec, key=frec.get)
	if DEBUG:
	print "Largo de la cadena %s" %len(frec)
	print "Frecuencias"
	for i in ordenados:
	print "%s: %s" %(i, frec[i])
	return frec, ordenados
	def huffman(frase):
	inicio = time.time()
	len_original = len(frase)*4
	#frase = "this is an example of a huffman tree"
	escribe_frase_original(frase)#se escribe un archivo de texto
	#frase = "j'aime aller sur le bord de l'eau les jeudis ou les jours impairs"
	frec, ordenados = frecuencia(frase) #tabla de frecuencias
	raiz = crea_arbol(frec, ordenados)
	#recorrido en preorden
	lista_pesos = []
	lista_nodos = []
	lista_nodos, lista_pesos = recorrer(raiz, lista_nodos, lista_pesos)
	print "Recorrido en preorden %s" %lista_pesos
	#obtengo hojas del arbol
	hojas = obtiene_hojas(lista_nodos)
	#se obtienen los codigos para cada simbolo
	lista_codigos, dic_codigos = codigos(hojas)
	#se escribe una tabla con sus frecuencias
	escribe_tabla(lista_codigos)
	#se pasa el texto normal a los codigos encontrados
	len_codificado = escribe_codigos(frase, dic_codigos)
	#se decodifica
	frase_decodificada = decodificar(raiz)
	print "La frase encontrada: %s" %frase_decodificada
	tiempo_total = time.time() - inicio
	return tiempo_total, len_original, len_codificado
	def main():
	"""funcion principal
	"""
	largos = genera_largos()
	dic1 = genera_peor_caso(largos)
	for i in dic1:
	print huffman(dic1[i])
	dic2 = probabilidad_tipica(largos)
	lista_malos = []
	lista_tipicos = []
	lista_m_orig = []
	lista_m_cod = []
	lista_b_orig = []
	lista_b_cod = []
	lista_b_ratio = []
	lista_m_ratio = []
	rangos = []
	for key in sorted(dic1.iterkeys()):
	rangos.append(key)
	malo, len_original_m, len_codificado_m = huffman(dic1[key])
	tipico, len_original_b, len_codificado_b = huffman(dic1[key])
	print "malo %s: %s" % (key, malo)
	print "bueno %s: %s" % (key, tipico)
	lista_malos.append(malo)
	lista_tipicos.append(tipico)
	lista_m_orig.append(len_original_m)
	lista_m_cod.append(len_codificado_m)
	lista_b_orig.append(len_original_b)
	lista_b_cod.append(len_codificado_b)
	lista_b_ratio.append(len_original_m/len_codificado_m)
	lista_m_ratio.append(len_original_b/len_codificado_b)
	#plt.plot(rangos, lista_b_orig,'r^', rangos, lista_b_cod,'g^')
	plt.plot(rangos, lista_malos,'r--', rangos, lista_tipicos,'g--')
	plt.legend(('Worst case', 'Normal case'),
	'upper center', shadow=True)
	#plt.legend(('Normal', 'Huffman'),
	# 'upper center', shadow=True)
	plt.ylabel('Time')
	plt.xlabel('Text length')
	plt.show()
	main()

view raw gistfile1.py hosted with ❤ by GitHub

References

Huffman compression

Huffman coding