1. Accueil
  2. Python
  3. Sources Python
  4. Sources Math & Algorithmes
  5. Compression par la methode de huffman

Compression par la methode de huffman

Soyez le premier à donner votre avis sur cette source.

Vue 11 321 fois - Téléchargée 821 fois

Télécharger le projet
Commenter

Description

Voila une petite classe utilisant l'algorithme de compression de Huffman.

Bien sur ce type de compression reste tres simple et ne peut pas permettre de passer sous la barre des 12.5% par rapport à loriginal (et encore ça natteint ces 12.5% que lorsque que le fichier contient tjrs les memes octets). Et ça ne fait pas bcp gagner en realité pour les autres fichiers ^^.

C'etait juste histoire de voir comment ça fonctionnait.

utilisation :
Huffman.py c test.mo test.comp
Huffman.py d test.comp test.decomp

Source / Exemple : 


# -*- coding: cp1252 -*-
import Arbre, struct, sys

class HuffmanError(Exception):
    pass

class Huffman:
    """classe de compression/decompression par la methode d'Huffman
    """
    def __loop(self, arbre, node, carTable, cur):
        dirs=arbre.GetDir(node)
        for i in range(len(dirs)):
            if(dirs[i].getType()=='feuille'):
                carTable[dirs[i].getValue()]=''.join(cur)+str(i)
            else:
                newcur=[k for k in cur] #pour que ça se chamboule âs ds la recursivite
                newcur.append(str(i))
                carTable=self.__loop(arbre, dirs[i], carTable, newcur)
        return carTable
            
    def __makeArbreFromTable(self, table, tot):
        n=0
        while 1:
            #on prend les deux plus petites occurences
            oc=[(tot, None, None), (tot, None, None)]
            for key, dat in table.items():
                data=dat[0]
                for i in range(2):
                    if(data<=oc[i][0]):
                        if(i==0) :
                            ancien=oc[0]
                            oc[1]=ancien
                            oc[0]=(dat[0], dat[1], key)
                            break
                        else:
                            oc[1]=(dat[0], dat[1], key)
                            break
            node=Arbre.Node(1, oc[0][1], oc[1][1])
            del(table[oc[0][2]])
            del(table[oc[1][2]])
            table['node'+str(n)]=[oc[0][0]+oc[1][0], node]
            if(len(table)==1) : break
            n+=1
        a=Arbre.Arbre()
        a.SetRacine(table['node'+str(n)][1])
        
        #parcourt de larbre pour noter le chemin pour chaque car
        chem=self.__loop(a, table['node'+str(n)][1], {}, [])
        
        return a, chem

    def getBits(self, chem, car):
        return chem[car]

    def getOctet(self, bits, full=0):
        """si full a 1 on rempli la fin par des zero"""
        if(len(bits)!=8 and full==1) : bits+='0'*(8-len(bits))
        m=128
        octet=0
        for bit in bits:
            octet+=int(bit)*m
            m=m/2
        return struct.pack('B', octet)
                        
    def compress(self, f1, f2):
        """f1 doit avoir la methode read et f2 la methode write"""
        #creation de la table
        table={}
        tot=0.0
        while 1:
            buf=f1.read(1024*256)
            if not buf :
                table['eof']=[1, 'eof']
                tot+=1
                break
            else:
                for car in buf:
                    if table.has_key(car)==True : table[car][0]+=1
                    else : table[car]=[1, car]
                    tot+=1
        
        #creation de larbre et du chemin des car
        arbre, chem=self.__makeArbreFromTable(table.copy(), tot)

        #fabrication du fichier, header:
        header=''
        header+=struct.pack('c', 'H') #identification du fichier
        header+=struct.pack('c', 'U')
        header+=struct.pack('L', len(table)-1) #elements de la table (sans le eof)
        header+=struct.pack('L', tot) #total cars
        header+=struct.pack('L', 14+len(table)*5-5) #offset data
        f2.write(header)
        
        #ecriture de la table sans le eof qui est tjrs a 1 de tte facon
        Table=''
        for key, data in table.items():
            if(key!='eof'):
                Table+=struct.pack('c', key)
                Table+=struct.pack('L', data[0])
        f2.write(Table)
        
        #ecriture du fichier compresse
        f1.seek(0)
        curbit=''
        outbuf=''
        while 1:
            buf=f1.read(1024*16)
            if not buf :
                bits=self.getBits(chem, 'eof')
                if(len(curbit+bits)<=8):
                    f2.write(self.getOctet(curbit+bits, 1))
                elif(len(curbit+bits)>8):
                    towrite=curbit+bits
                    for i in range(0, (len(towrite)/8)+1):
                        if(i==len(towrite)/8) : f2.write(self.getOctet(towrite[i*8:], 1))
                        else: f2.write(self.getOctet(towrite[i*8:i*8+8]))
                break
            else:
                for c in buf:
                    bits=self.getBits(chem, c)
                    if(len(curbit+bits)<=8):
                        curbit=curbit+bits
                    elif(len(curbit+bits)>8):
                        towrite=curbit+bits
                        for i in range(0, (len(towrite)/8)+1):
                            if(i==len(towrite)/8) : curbit=towrite[i*8:]
                            else: outbuf+=self.getOctet(towrite[i*8:i*8+8])
                f2.write(outbuf)
                outbuf=''
        f1.close()
        f2.close()
    def decompress(self, f1, f2):
        #dabord lecture des infos:
        if(f1.read(2)!='HU') : raise HuffmanError, 'This file has not been compressed by me'
        elem=struct.unpack('L', f1.read(4))[0]
        totcars=struct.unpack('L', f1.read(4))[0]
        offset=struct.unpack('L', f1.read(4))[0]
        
        ###lecture de la table
        table={}
        for i in range(elem):
            el=f1.read(5)
            key=struct.unpack('c', el[0])[0]
            table[key]=[struct.unpack('L', el[1:])[0], key]
        table['eof']=[1, 'eof']
        
        #creation de larbre et des chemins
        arbre, chem=self.__makeArbreFromTable(table.copy(), totcars)
        
        racine=arbre.getRacine()
        curnode=racine
        f1.seek(offset)
        while 1:
            buf=f1.read(1024*256)
            if not buf : break #preventif
            else:
                for car in buf:
                    for i in range(8):
                        bit=ord(car)&(0x80>>i)
                        if(bit!=0) : bit=1
                        item=arbre.GetDir(curnode)[bit]
                        if(item.getType()=='feuille') :
                            if(item.getValue()!='eof') : f2.write(item.getValue()); curnode=racine
                            else : break
                        else : curnode=item
        f1.close()
        f2.close()

if __name__=='__main__':
    if(len(sys.argv)!=4) : print 'usage : Huffman.py mode source dest
    h=Huffman()
    a=open(sys.argv[2], 'rb')
    b=open(sys.argv[3], 'wb')
    if(sys.argv[1]=='c') : h.compress(a, b)
    else : h.decompress(a, b)
    raw_input('operation finie')

Conclusion :


Le code est surement tres tres optimisable puisqu'il savere vraiment tres tres lent ^^.
Télécharger le projet

Codes Sources

A voir également

Ajouter un commentaire

Commentaire

Signaler
Messages postés
74
Date d'inscription
dimanche 2 novembre 2003
Statut
Membre
Dernière intervention
6 septembre 2008
 1
Voila ou lutilisation que jai utilisé pour ce code : http://www.alphabeta-net.com/Huffman.html
S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (cs_Bl0tCh)