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ó.

Anuncis

Una reflexió sobre els MOOC (again)

Fa un parell de mesos vaig cursar (i superar, amb els corresponents certificats) un parell de MOOC de MiríadaX: “Android: Programación de Aplicaciones“, per la Universitat Politècnica de València i el “Curso Fundamental de Microeconomía“, per la Universidad Rey Juan Carlos de Madrid. També, per la plataforma MOOC de la UNED, “La Contabilidad, el lenguaje de los negocios” del que també he obtingut el certificat corresponent.

Tots aquests MOOC es feien en castellà. Una cosa que tenia pendent era provar els MOOC de Coursera, en anglès.

Em picava la curiositat dels MOOC en anglès i vaig decidir de començar amb alguna cosa “fàcil” en la que em sentís còmode. Un curs de Python tenia tot l’aspecte de ser el candidat ideal. Dit i fet, em vaig apuntar al MOOC “An Introduction to Interactive Programming in Python” de la Rice University de Houston, Texas.

El curs ha estat molt divertit, i també he obtingut una acreditació conforme l’he superat. La cosa ha anat de fer videojocs com Pong, Asteroids, o BlackJack amb una versió online i educativa de Pyhton desenvolupada amb JavaScript: el CodeSkulptor (http://www.codeskulptor.org/).

Divertit. Però si en comptes de portar un munt d’anys programant en llenguatges diversos; i que el Python, de fet, no era un llenguatge desconegut per mi, segurament no m’hauria divertit tant. Opino que el curs era prou fort com per a intimidar a un neòfit, i que per molta experiència prèvia que es tingués, calien hores de feina per a completar els treballs proposats.

Poc després d’encetar el curs de Python, em vaig apuntar al MOOC Finance (https://venture-lab.org/finance13/index) de la Stanford University a la plataforma Venture-Lab, perquè al temari es tocava un tema que m’interessava laboralment.

Bé, doncs tampoc ha estat “tan fàcil” (també he obtingut un certificat de participació).

M’ha agradat la dinàmica de formació continua dels MOOC. Actualment estic apuntat a un parell de MOOC, actualment en curs: “Introduction to Finance” (https://class.coursera.org/introfinance-003/class/index) de la University of Michigan (ja que el curs d’Stanford m’ha fet adonar que em calia reforçar aquest tema); i “Startup Engineering” (https://class.coursera.org/startup-001/class/index) de la Stanford University, però ara per Coursera.

Les vacances seran un bon moment per dedicar a la formació.

No són cursos trivials i és el correcte. Després d’haver fet MOOC a MiríadaX, Venture-Lab i Coursera m’adono que els MOOC han de tenir nivell d’exigència.

És fonamental que siguin exigents per al seu èxit.

El nivell d’exigència que he trobat als MOOC americans ha estat clarament superior al que he trobat a MiríadaX, o al COMA de la UNED. Crec que l’èxit dels MOOC nord-americans és, justament, que se’ls prenen seriosament tant les universitats que els imparteixen com els estudiants que els segueixen. L’èxit és l’exigència.

Perquè el model de negoci està en crear marca, no en regalar certificats.

Marca, per les universitats que ofereixen MOOC, són estudiants que han après de forma sòlida, que són capaços de posar aquests coneixements en pràctica i que les empreses constaten que, efectivament, aquests estudiants aporten coneixement útil.

Des de la meva experiència, crec que els MOOC són ideals per a professionals en actiu que poden prendre un o dos cursos durant un parell de mesos sobre alguna qüestió concreta fins obtenir un nivell de suficiència o, àdhuc, un nivell superior.

Aquests professionals potser voldran, posteriorment, prendre cursos amb acreditació oficial; o les empreses poden demanar cursos específics a les universitats; o els estudiants d’un MOOC específic poden ser “oferts” en una base de dades amb la garantia de la “marca” de la universitat.

Hi ha un retorn per a les Universitats que ofereixen aquesta formació gratuïta.

No només hi ha model de negoci per a les Universitats, encara més important, hi ha un aprenentatge real per als estudiants. A Rice, a Michigan a Stanford, al MIT… ho saben. No en tenen cap dubte. Els cursos, encara que gratuïts, tenen un nivell d’exigència alt.

No es regalen els certificats. Un certificat amb la “marca” de la universitat ha de ser merescut. L’estudiant ha d’esforçar-se. Si no està preparat, no obté la certificació. Ara bé, l’estudiant aprèn i, si no ho ha aconseguit ara, pot tornar a intentar-ho en un futur. No ha perdut diners. No se’l frustra. Si vols aprendre, aprens.

En cap cas un certificat de participació (o d’aprofitament, en diversos graus) en un MOOC és un títol oficial. Però els MOOC creen un ecosistema formatiu en que el títol oficial no és tan important. En canvi, el reconeixement comunitari, sí que ho és. Els MOOC creen i ofereixen el reconeixement comunitari. No debades en la presentació dels cursos sempre insisteixen en la participació als fòrums. Estem enmig del procés de construcció de les marques Coursera, EdX, Venture-Lab…

Els MOOC són socials, però tot aprenentatge és individual. Fins i tot quan s’assisteix a classes presencials, és l’estudiant, i només l’estudiant, el que decideix prestar atenció, estudiar, fer els exercicis o meditar sobre els conceptes apresos. El MOOC, per tant, demana l’esforç individual. La millora és que aporta interacció social útil a l’estudiant.

La combinació en plataformes d’aprenentatge de calendaris, programes de curs, examens… de material didàctic com vídeos, apunts, exercicis, qüestionaris… i xarxes socials, de fòrums, d’equips de treball distribuïts coordinats per xats i hangouts… és un espai social virtual en el que el guiatge i la consulta al professor es substitueix per la consulta a la comunitat i uns programes ben apamats.

Aquesta esforç individual sobre una combinació de recursos online s’ha anat refinant amb el temps i és el que s’estava prefigurant amb, per exemple, eines com Moodle, que ja té alguns anys

La novetat és que s’ha descobert com obtenir un retorn econòmic d’aquest servei formatiu gratuït i que les universitats, sobretot les nord-americanes, han decidit entrar en el joc. El resultat és una explosió de les plataformes MOOC.

A més, és el moment. crec que als EUA, sobretot, han entès que la forma de mantenir el lideratge en un món globalitzat és alliberant el màxim de coneixement, fer-lo circular, crear xarxa, i captar talent. El lideratge passa per una societat amb molta formació. És una frase que es repeteix molt, però pocs se la creuen. Els MOOC van en la línia d’incrementar el nivell formatiu de la societat. S’integren en el vector de canvi social que és la formació en línia.

Això dels MOOC és seriós. És una amenaça? Potser sí. És una amenaça per a la visió de l’educació com a producte empaquetat, com objecte de luxe, o com privilegi de classe. De forma semblant al que passa a la indústria editorial. Es tracta de vells negocis del segle XX que amb la xarxa veuen que el seu plantejament original s’enfonsa.

Les “indústries” educatives, editorials, culturals… Han de reinventar-se per al segle XXI, i adaptar-se a les xarxes i a la intel·ligència col·lectiva.

Els MOOC són una amenaça? Només si es tem el canvi. Només si no es pot oferir quelcom millor.

Aquest article de la UOC és molt interessant: “La irrupció dels MOOC sacseja el debat sobre els ensenyaments en línia

En reprodueixo aquest paràgraf clau: “El passat mes de setembre, durant la inauguració oficial del curs universitari català, el conseller d’Economia i Coneixement, Andreu Mas-Colell, es va referir als MOOC com una amenaça ja que «les grans universitats del món se’ns ficaran a casa sense crear cap lloc de treball. Cal anticipar-se aquí, i una altra vegada la col·laboració entre universitats pot ser essencial». De fet, Coursera ja ha signat amb més de disset universitats de prestigi, la majoria dels Estats Units, com ara la Universitat Brown i la Universitat de Colúmbia, per oferir els seus cursos a prop d’1,35 milions d’estudiants, situats en un 61,5% fora dels Estats Units.”

En definitiva, els MOOC una amenaça? Ho plantejo així: l’educació lliure, gratuita i de qualitat és una amenaça?

Temem la globalització o en som protagonistes?

Una bona Notícia: la Universitat Autònoma de Barcelona ja ofereix MOOC a Coursera. Ben fet. de moment, en castellà. Espero que aviat en anglès. La Universitat Pompeu Fabra i la Universitat de Girona ofereixen MOOC a MiríadaX.

Més enllà del negoci, només aquells que creuen profundament en el poder de l’educació i de la formació són prou lúcids per crear plataformes de formació lliure, gratuita i de qualitat.

Aprofito per afegir la secció MOOC al curriculum vitae. També els poso al LinkedIn.

I poso, un cop més, la llista de les principals plataformes MOOC:

Agregador de MOOC:
http://www.class-central.com/

Plataformes principalment en anglès (es poden trobar MOOC en altres idiomes):
https://www.coursera.org/
https://venture-lab.org/
https://www.edx.org/
http://eportfolio.saylor.org/
https://www.canvas.net/
https://www.khanacademy.org/

Plataformes MOOC en castellà:
http://miriadax.net/
https://unedcoma.es/

MOOC realitzat: “Android: Programación de Aplicaciones” de la UPV, a MiríadaX

Tot just he acabt el MOOC “Android: Programación de Aplicaciones” de la Universitat Politècnica de València, sobre la plataforma MiríadaX.

De moment, només dir que ja tinc el meu primer “badge“, que ve a ser el reconeixement de participació al MOOC que fa MiríadaX.EL reconeixement per badges admet graduacions i em temo que el que fa MiríadaX és el més bàsic. No té en compte, per exemple, les puntuacions obtingudes als tests, o els exercicis realitzats.

Per a un proper post queda pendent, ara des de l’experiència de primera ma que dona haver-ne fet un, explicar com ha anat la cosa. En un parell de setmanes, a més he d’acabar algun altre MOOC que també estic realitzant o sigui que, a més, podré donar també una opinió comparada.

En tot cas, he trobat aquesta experiència positiva i enriquidora. No era el primer cop que feia formacions online i tenia una idea prèvia del que em trobaria. Però ha superat les expectatives. He de dir que el curs de la UPV ha estat, amb diferència, el millor en que he participat en format online: 10 mòduls, amb abundants exercicis pràctics, tests i un examen per cada mòdul. Una novetat per mi: les “correccions” comunitàries d’exercicis als fòrums i , brillant, les classes de repàs amb àudio i vídeo en directe fent servir els hangouts de Google+. Déu n’hi do. Afegim bon material de vídeo i, potser, escàs material escrit, però enllaçat si més no.

Bé, ara ja soc un especialista en desenvolupament amb Android 😉 que era una mica la idea de fer aquest MOOC.

El MOOC. Un enorme camp de possibilitats d’auto-formació i de dissenyar un currículum a mida.

El següent pas: revisar l’oferta de Coursera.