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:
- Ogni foglia rappresenta un simbolo con il suo relativo peso (probabilità).
- Fonde i due nodi con la probabilità più bassa in un nodo padre con peso pari alla somma dei pesi dei figli.
- 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:
- Prima scansione del testo per creare la distribuzione di probabilità.
- 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):
- Si preleva il dizionario dal file compresso.
- 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.
0 Risposte a “Huffman Coding”