Accueil > > > COMPRESSION PAR LA METHODE DE HUFFMAN
COMPRESSION PAR LA METHODE DE HUFFMAN
Information sur la source
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
- # -*- 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')
-
# -*- 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 ^^.
Sources du même auteur
Sources de la même categorie
Commentaires et avis
Discussions en rapport avec ce code source dans le forum
Compression de fichier :Winzip et 7zip [ par HCD ]
Bonjour à tousCe qui suit s'adresse aux administrateurs du site.Lorsque l'on ajoute une nouvelle source sur le site, le fichier compressé doir comport
Déplacer méthode [ par Roro8883 ]
Bonjour à tous !Je suis débutant sous python, mais je connais assez bien le C++.J'aimerais pouvoir déplacer mes méthodes (fonctions) contenues dans me
Méthode Tabou [ par Lcapc ]
salut à tous, je dois réaliser un petit script pour récupérer les liens d'un site web. J'ai déjà récupéré les liens d'une page, maintenant je dois
Compression d'images en lignes de commande - Python [ par Elninor ]
Bonsoir, j'ai cherché sur tous les sites possibles (francophone et anglophone) mais je n'ai rien trouvé. Je recherche quelques lignes de commande perm
|
Derniers Blogs
ENUMERABLECOLLECTIONENUMERABLECOLLECTION par Matthieu MEZIL
Prenons le scénario suivant. On utilise MVVM. On a les deux classes suivantes dans le model : public class Child { } public class Parent { private ObservableCollection < Child > _children; public ObservableCollection < Child > Children { get {...
Cliquez pour lire la suite de l'article par Matthieu MEZIL [HS] CHROME 6 + MOI = COUP DE GUEULE ![HS] CHROME 6 + MOI = COUP DE GUEULE ! par JeremyJeanson
Attention, le poste qui suit n'est pas la complainte d'une personne : Qui n'aime pas Chrome. D'un anti Google. D'un développeur qui a un poil énorme dans la main. Ceux qui me fréquentent savent que je change de navigateur favori tous les 2 ou 3 mois afin ...
Cliquez pour lire la suite de l'article par JeremyJeanson [WP7] UTILISER UN WRAPPANEL DANS UNE APPLICATION WINDOWS PHONE 7[WP7] UTILISER UN WRAPPANEL DANS UNE APPLICATION WINDOWS PHONE 7 par Audrey
Lors de la réalisation de ma 2ème application Windows Phone 7, j'ai souhaité utiliser un WrapPanel pour afficher plusieurs photos. Mais le contrôle WrapPanel ne fait pas parti de la liste des contrôles inclus dans le SDK de la version Beta des outils pour...
Cliquez pour lire la suite de l'article par Audrey [WP7] BESOIN D'AVOIR DES DONNéES EN CACHE[WP7] BESOIN D'AVOIR DES DONNéES EN CACHE par Nicolas
Les développeurs ASP.NET ont l'habitude de mettre des données en cache pour éviter de requêter a chaque fois la base de données. Et il est toujours utilie de penser que vos utilisateurs mobiles n'ont pas troujours une super connexion 3G/WIFI et un for...
Cliquez pour lire la suite de l'article par Nicolas [TFS] COMMENT FORCER LA SAISIE D'UN AREA OU ITERATION[TFS] COMMENT FORCER LA SAISIE D'UN AREA OU ITERATION par cyril
Lorsque l'on créé un Work Item dans TFS, il est possible de le classer dans un "area" et dans une "iteration". Dans la plupart des types de projet, un "area" correspond à une catégorie, une "iteration" à un numéro de version. Il est possible de cré...
Cliquez pour lire la suite de l'article par cyril
Forum
RE : PYTHON 3.0RE : PYTHON 3.0 par aera group
Cliquez pour lire la suite par aera group RE : PYTHON 3.0RE : PYTHON 3.0 par xeolin
Cliquez pour lire la suite par xeolin RE : PYTHON 3.0RE : PYTHON 3.0 par aera group
Cliquez pour lire la suite par aera group
Logiciels
Bureau de Gestion - ERP Devis Facturation (2.02)BUREAU DE GESTION - ERP DEVIS FACTURATION (2.02)
- Version gratuite du 10/06/2010
Le Bureau de Gestion est un logiciel dédié à la gestion de l'en...
Cliquez pour télécharger Bureau de Gestion - ERP Devis Facturation sDEVIS-FACTURES vlPRO (3.8.0)SDEVIS-FACTURES VLPRO (3.8.0)sDEVIS-FACTURES vlPRO a été mis au point pour permettre besoins des particuliers, créateurs, entr... Cliquez pour télécharger sDEVIS-FACTURES vlPRO LettresFaciles (5.6.0)LETTRESFACILES (5.6.0)LettresFaciles est un logiciel facilitant la création et la rédaction de lettres types.
Son inte... Cliquez pour télécharger LettresFaciles MyPlanning 2010 (5.6.0)MYPLANNING 2010 (5.6.0)MyPlanning 2010 permet de créer des plannings sous la représentation de diagrammes. Plannings pré... Cliquez pour télécharger MyPlanning 2010 Emicsoft Mac DVD en iPad Convertisseur (3.1.16)EMICSOFT MAC DVD EN IPAD CONVERTISSEUR (3.1.16)Emicsoft Mac DVD en iPad Convertisseur, logiciel professionnel de convertir les fichiers DVD en i... Cliquez pour télécharger Emicsoft Mac DVD en iPad Convertisseur
|