Un codificador de Huffman amb Python

Hi havia una vegada un MOOC

L’afició als MOOCs està fent que dediqui menys temps al blog però també em proporciona idees per a posts.

Concretament, el d’avui té el seu origen en el MOOC de Coursera Digital Signal Processing de l’École Polytechnique Fédérale de Lausanne, que tot just he acabat. En el meu cas, el MOOC m’ha servit per refrescar coneixements de la meva època d’universitari.

Aprofito per felicitar als professors del curs per l’extraordinari esforç didàctic del MOOC.

I per agraïr-lo. M’ho he passat molt bé fent aquest curs.

A una de les “video lectures” s’explicava el format jpeg i es parlava de l’us de la codificació de Huffman dins d’aquest format.

La codificació de Huffman és un algorisme de compressió de dades que assigna codis de longitud variable als símbols d’un alfabet. Els codis són més curts per als símbols més probables i més llargs per als menys probables.

la codificació huffman també es fa servir a compressors com pkzip o, a més del jpeg, en d’altres formats d’imatge, com el png.

En defintiva, que m’han vingut ganes de fer una cosa que tenia pendent des de l’epoca de l’universitat, i que no és altre que programar la meva pròpia implementació d’un codificador/decodificador de Huffman. En Python, que com més el faig servir, més m’agrada el llenguatge.

Teoria

La wikipedia proporciona bones explicacions teòriques sobre la codificació de Huffman.
La codificació de Huffman
L’algorisme de Huffman

En resum, es parteix d’una taula que ens dona per a cada símbol d’un alfabet la seva probabilitat d’aparició.

L’alfabet a codificar

Suposo un alfabet de set símbols, amb les següents probabilitats

“A”: 0.12
“B”: 0.15
“C”: 0.15
“D”: 0.18
“E”: 0.22
“F”: 0.12
“G”: 0.06

En Python ho codifico amb un diccionari

    # symbols,probabilities table
    symbols = {"A":0.12, "B": 0.15, "C": 0.15, "D": 0.18, "E": 0.22, "F": 0.12, "G": 0.06}

Aleshores, es tracta de construir un arbre binari en el que…

Comencem, cada símbol és una fulla de l’arbre.

Creo una classe auxiliar Node que em permetrà mantenir símbol, probabilitat i informació addicional. És una classe sense mètodes, només la faré servir per encapsular dades. Com una struct de C, per entendre’ns.

class Node:
    # properties
    probability = 0.0
    symbol = ""
    encoding = ""
    visited = False
    parent = -1

Inicialitza l’arbre

Ara inicialitzo l’arbre, creant un node per a cada símbol. És el que faig amb el mètode initNodes de la classe Huffman

    def initNodes(self, probs):
        for symbol in probs:
            node = Node()
            node.symbol = symbol 
            node.probability = probs[symbol]
            node.visited = False
            self.Nodes.append(node)
            self.probs[symbol]=probs[symbol]     

Invoco aquest mètode dins del constructor de la classe.

if __name__=="__main__":
    # symbols,probabilities table
    symbols = {"A":0.12, "B": 0.15, "C": 0.15, "D": 0.18, "E": 0.22, "F": 0.12, "G": 0.06}

    # instantiate encoder
    huffman = Huffman(symbols)

Per a crear l’arbre aprofitaré una llista de nodes (llista Nodes). L’estructura de l’arbre la proporciona la propietat parent de cada Node.

L’arbre

L’arbre es construeix a buildTree:

    def buildTree(self):
        indexMin1 = self.getNodeWithMinimumProb()
        indexMin2 = self.getNodeWithMinimumProb()
        
        while indexMin1 != -1 and indexMin2 != -1:
            node = Node()
            node.symbol = "."
            node.encoding = ""
            prob1 = self.Nodes[indexMin1].probability
            prob2 = self.Nodes[indexMin2].probability
            node.probability = prob1 + prob2
            node.visited = False
            node.parent = -1
            self.Nodes.append(node)
            self.Nodes[indexMin1].parent = len(self.Nodes) - 1
            self.Nodes[indexMin2].parent = len(self.Nodes) - 1
            
            # rule: 0 to highest probability, 1 to lowest.
            if prob1 >= prob2:
                self.Nodes[indexMin1].encoding = "0"
                self.Nodes[indexMin2].encoding = "1"
            else:
                self.Nodes[indexMin1].encoding = "1"
                self.Nodes[indexMin2].encoding = "0"
            
            # self.showTree()
            
            indexMin1 = self.getNodeWithMinimumProb()
            indexMin2 = self.getNodeWithMinimumProb()

El que fa build Tree és invocar dos cops al mètode getNodeWithMinimumProb

    def getNodeWithMinimumProb(self):
        minProb = 1.0
        indexMin = -1

        for index in range(0, len(self.Nodes)):
            if (self.Nodes[index].probability < minProb  and 
               (not self.Nodes[index].visited)):
                minProb = self.Nodes[index].probability
                indexMin = index

        if indexMin != -1:
            self.Nodes[indexMin].visited = True

        return indexMin

Que fa exactament això que diu el seu nom. Busca el node de mínima probabilitat i quan el troba, en retorna l’index i marca el node com a visitat, de forma que no el tindrà en compte en passades posteriors

buildTree invoca dos cops getNodeWithMinimumProb, és dir, obté els dos Nodes de probabilitat més baixa. Al de probabilitat més alta li assigna un zero, i al de més baixa un u.

Val a dir que aquesta assignació és arbitrària i simplement busca provocar que el node de probabilitat més alta tingui la codificació numèricament més petita, i el de probabilitat més baixa, la més alta. En realitat, com que estic generant un codi binari, el que realment compta és la longitud de la codificació, és dir, quants bits per símbol. Si en comptes de seguir el criteri indicat seguís el contrari, la codificació huffman que obtindria tindria la mateixa longitud en bits: els símbols de major probabilitat tindrien menys bits de codificació, i els de menor, al contrari, més bits.

És dir, el codi huffman em permet trobar codis òptims pel que fa a la longitus en bits de la codificació dels símbols. L’algorisme de Huffman no diu res sobre assignacions de zeros i uns, això depèn de la implementació.

En aquesta implementació, doncs, el criteri és assignar un 0 al node de major probabilitat i un1 al de menor.

Tenint en compte tot l’anterior, es crea un nou node amb probabilitat suma de les probabilitats dels nodes trobats, i afegeix el node a la taula Nodes.

Els nodes fills apunten la propietat parent al nou node creat.

El procés es repeteix fins que només queda el node arrel.

Simplificant: diccionari de símbols i codificacions

Un cop arribats a aquest punt, ja en tindria prou, però per simplificar els mètodes de codificació i decodificació, he afegit un pas addicional que construeix la taula de codificacions dictEncoder, que associa cada símbol amb la seva codificació binària. Això ho faig amb buildDictionary

    def buildDictionary(self):
        for symbol in self.probs:
            encoding = self.showSymbolEncoding(symbol)
            self.dictEncoder[symbol] = encoding

Que invoca showSymbolEncoding, que per a cada símbol torna la seva codificació.

    def showSymbolEncoding(self, symbol):
        found = False
        index = 0
        encoding = ""

        for i  in range(0, len(self.Nodes)):
            if self.Nodes[i].symbol == symbol:
                found = True
                index = i
                break 
        
        if found:
            while index != -1:
                encoding = "%s%s" % (self.Nodes[index].encoding, encoding)      
                index = self.Nodes[index].parent
        else:
            encoding = "Unknown symbol"

        return encoding

Encoder i Decoder

Un cop disposo del diccionari de simbols la codificació i la decodificació són trivials:

    def encode(self, plain):
        encoded = ""
        for symbol in plain:
            encoded = "%s%s" % (encoded, self.dictEncoder[symbol])

        return encoded 

    def decode(self, encoded):
        index = 0
        decoded = ""

        while index < len(encoded):
            founf = False
            aux = encoded[index:]
            for symbol in self.probs:
                if aux.startswith(self.dictEncoder[symbol]):
                    decoded = "%s%s" % (decoded, symbol)
                    index = index + len(self.dictEncoder[symbol])
                    break 
        
        return decoded

Provem-ho

I, per descomptat, tot plegat funciona

albert@atenea:~/Baixades$ python huffman.py 
show symbols
Symbol: A; encoding: 110
Symbol: C; encoding: 010
Symbol: B; encoding: 001
Symbol: E; encoding: 10
Symbol: D; encoding: 000
Symbol: G; encoding: 111
Symbol: F; encoding: 011
test: ABABCCFDADDEDAG; encoded: 11000111000101001001100011000000010000110111
encoded: 11000111000101001001100011000000010000110111; decoded: ABABCCFDADDEDAG
Success!
albert@atenea:~/Baixades$ 

GitHub

el codi complet es pot descarregar del GitHub

Algunes idees per seguir

El codificador de Huffman amb python que he presentat es pot ampliar per fer un compressor. Algunes idees: Es podria afegir un mètode que llegís el fitxer a comprimir i que calculés les freqüències dels símbols (màxim de 255 símbols), el fitxer comprimit hauria de desar un primer bloc amb la taula de probabilitats (Potser seria més pràctic desar el diccionari de codificació) i, a continuació el fitxer comprimit. Evidentment, caldria traduir la cadena de caràcters de zeros i uns a bits i agrupar en bytes (no tindria cap sentit desar cadenes de caràcters de ‘0’ i ‘1’!).

També, en una altre línia, és podria fer un mètode que calcules l’estalvi de bits que suposa fer servir aquest compressor en comptes de la codificació a 8 bits per caràcter. O també un mètode que calculés l’entropia de l’alfabet original i la comparés amb la longitud mitja dels bits del codi huffman generat.

En resum i per acabar, avui he presentat un codificador de Huffman que pot servir de base per a desenvolupaments més interessants i que pot il·lustar alguns elements de teoria de la informació.