19
nov
07

Huffman Coding

Come da richiesta proseguiamo con un classico della compressione, la codifica di Huffman. Tale algoritmo rientra in quelli statistici e si basa sul concetto di assegnare codewords più corte ai simboli più frequenti. Per farlo parte da una distribuzione di probabilità per i vari simboli dell’alfabeto e da questa crea un albero binario prefix-free (in pratica non esiste una codeword che sia prefisso di un’altra in modo da evitare ambiguità in decodifica). La procedura per la creazione di tale albero e tutti i fondamenti teorici che sono alla base di questa codifica li potete trovare alla relativa pagina di wikipedia, tuttavia i passaggi sono i seguenti:

  1. Ogni foglia rappresenta un simbolo con il suo relativo peso (probabilità).
  2. Fonde i due nodi con la probabilità più bassa in un nodo padre con peso pari alla somma dei pesi dei figli.
  3. Itera la fusione fino alla completa creazione dell’albero.

A questo punto il cammino per ogni foglia rappresenta la codeword in bit per quel simbolo. Per la codifica si procede in questo modo:

  1. Prima scansione del testo per creare la distribuzione di probabilità.
  2. Seconda scansione che per ogni simbolo scrive in output la codifica relativa, appendendo anche il dizionario usato.

Per la decodifica si procede in questo modo (una sola passata):

  1. Si preleva il dizionario dal file compresso.
  2. Si visita l’albero in funzione dei bit di input e ogni volta che si raggiunge una foglia si scrive in output il simbolo relativo.

Prima di passare all’implementazione va detto che tale codifica è ottima in caso di codifica che non prevede l’utilizzo di “frammenti” di bit come Arithmetic e PPM e che perde al massimo 1bit dall’ottimo. Senza entrare ulteriormente in dettaglio passiamo all’implementazione che sarà ancora in Python sebbene non sia proprio il linguaggio adatto in quanto non ha il BitStream nativo (che implementeremo in poche righe perdendo purtroppo 1/8 in compressione). Va tuttavia considerato che tale implementazione non prende in considerazione nessuna possibile ottimizzazione in quanto scritta al solo scopo dimostrativo. Il codice è piuttosto semplice ed ho cercato di introdurre alcuni commenti per chiarire il tutto. Per utilizzarlo la sintassi è la seguente: python Huffman.py [-e|-d] [input] [output].

"""
Created by Jonathan Masci @ Casapiddu.
Copyright (c) 2007. All rights reserved.
"""

import sys
import pickle
from struct import *
from heapq import heappush, heappop

class Huffman:
 "This class implements a very simple Huffman coding algorithm."
 def __init__(self, inputte, outputte):
 	self.inputte = inputte
 	self.outputte = outputte
 	self.symbolsTable = dict()

	def countFreqs(self):
 	"This method counts the frequencies of the symbols in the text."
 	self.t = self.f.read()
 	self.inputLength = len(self.t)
 	self.freqs = dict()
 	for c in self.t:
 		if self.freqs.has_key(c):
 			self.freqs[c] += 1
 		else:
 			self.freqs[c] = 1

	def buildProbs(self):
 	"Create an heap with the probabilities of the symbols. Using a heap to facilitate the tree construction."
 	self.heap = []
 	for c in self.freqs:
 		heappush(self.heap, ((float(self.freqs[c]) / float(self.inputLength)), c))

	def buildTree(self):
 	while len(self.heap) > 1:
 		leftChild = heappop(self.heap)
 		rightChild = heappop(self.heap)
 		parent = (leftChild[0] + rightChild[0], leftChild, rightChild)
 		heappush(self.heap, parent)

	def printHuffTree(self, huffTree, prefix = ''):
 	"Generate the codewords exploring the Huffman tree. I choose leftChild as 0 and rightChild as 1."
 	if len(huffTree) == 2:
 		self.symbolsTable[huffTree[1]] = prefix
    	else:
 		self.printHuffTree(huffTree[1], prefix + '0')
 		self.printHuffTree(huffTree[2], prefix + '1')

	def encode(self):
 	self.f = open(self.inputte, 'r')
 	self.o = open(self.outputte, 'w')

		self.countFreqs()
 	self.buildProbs()
 	self.buildTree()
 	self.printHuffTree(self.heap[0])
 	print self.symbolsTable

		# Create a string with the binary-like Huffman coding. After that i'll convert to bit version
 	# using BitCoding.
 	strout = ""
 	for c in self.t:
 		strout += self.symbolsTable[c]

		# Attach the dictionary of symbols to the compressed file.
 	# To disambiguate dictionary from encoded text i put a number to the beginning of the file
 	# so that in decoding i read this number and unpickle only that part of the data.
 	# The dictionary is inverted so that the decoder can look the key in costant time.
 	dSymbolsTable = dict()
 	for k in self.symbolsTable:
 		dSymbolsTable[self.symbolsTable[k]] = k
 	serialized = pickle.dumps(dSymbolsTable)
 	self.o.write(str(len(serialized)) + ";")
 	self.o.write(serialized)

		# Start the binary encoding. I walk in the output string in step of 7 chars and from these chars i
 	# create a ascii representation.
 	# To disambiguate i put a 1 on the most significative bit of the char. Doing this i loose 1/8 of coding
 	# but i can overcame the bit management of python. And of course is faster than using bit operators.
 	i = 0
 	while i = 0:
 		num += int(s[i]) * 2 ** (exp)
 		i -= 1
 		exp += 1
 	return num

	def getBinary(s):
 	"It reverts the coding of getAscii and remove the most significative bit we added to disambiguate."
 	bin = ''
 	if s == 0:
 		return 0
 	while s > 0:
 		bin = str(s % 2) + bin
 		s = s >> 1
 	return bin[1:8]

	getAscii = staticmethod(getAscii)
 getBinary = staticmethod(getBinary)

if __name__ == '__main__':
    main()

Ovviamente in tutto quello che ho scritto c’è almeno un errore.

About these ads

2 Responses to “Huffman Coding”


  1. 18 luglio 2013 alle 21:43:20

    Starting with baseload electricity prices, rises in coal and oil costs pushed up longer-term prices, as expectations
    are that both these markets will continue to rise.
    Many wholesale suppliers require a minimum order of 200 pieces,
    for example, but others only require less than 10 pieces per order.

    The information and descriptions about the products is the key
    to selling each one of them.

  2. 24 luglio 2013 alle 23:15:10

    The problem is that since they don’t actually stock their own products it often takes longer for you to receive your order, or they might be out of stock. We all know how unattractive a desperate-seeming person is. Should you get the top ranking on Google, Yahoo and MSN for your keywords, nobody can knock you off unless they do a better optimization job than you do.


Rispondi

Inserisci i tuoi dati qui sotto o clicca su un'icona per effettuare l'accesso:

Logo WordPress.com

Stai commentando usando il tuo account WordPress.com. Chiudi sessione / Modifica )

Foto Twitter

Stai commentando usando il tuo account Twitter. Chiudi sessione / Modifica )

Foto di Facebook

Stai commentando usando il tuo account Facebook. Chiudi sessione / Modifica )

Google+ photo

Stai commentando usando il tuo account Google+. Chiudi sessione / Modifica )

Connessione a %s...


Difendi Rebeldia!

Aggiungi ai tuoi feed

 RSS Feed
Add to Google
Add to My Yahoo!
Add to Technorati Favorites!
Add to netvibes

Blog Stats

  • 239,704 hits

Pidduisti on-line

hit counters


Made on a Mac
Last.fm
Giveaway of the Day
highlightInterests("ProfileMusica");
Musicatable.lfmWidget8f0839bdbf919d97305135788e54986d td {margin:0 !important;padding:0 !important;border:0 !important;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmHead a:hover {background:url(http://cdn.last.fm/widgets/images/en/header/chart/weeklytracks_regular_blue.png) no-repeat 0 0 !important;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmEmbed object {float:left;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmFoot td.lfmConfig a:hover {background:url(http://cdn.last.fm/widgets/images/en/footer/blue.png) no-repeat 0px 0 !important;;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmFoot td.lfmView a:hover {background:url(http://cdn.last.fm/widgets/images/en/footer/blue.png) no-repeat -85px 0 !important;}table.lfmWidget8f0839bdbf919d97305135788e54986d tr.lfmFoot td.lfmPopup a:hover {background:url(http://cdn.last.fm/widgets/images/en/footer/blue.png) no-repeat -159px 0 !important;}

pages

novembre: 2007
L M M G V S D
« ott   dic »
 1234
567891011
12131415161718
19202122232425
2627282930  

Iscriviti

Ricevi al tuo indirizzo email tutti i nuovi post del sito.

%d blogger cliccano Mi Piace per questo: