Utilisateur:Raminagrobis/huffman

Résultats sur quelques textes

langue	texte	taille initiale	taille comprimée	% gagné
Français	Constitution fr	73128	41084	44
Français	idem - tout en minuscules	73128	39384	46
Français	Les Misérables Tome 1 Ch1	130761	74182	43
Français	article wikipedia Pétrole	48914	28549	41
Italien	Pinocchio Ch1&2	7950	4486	43
Anglais	Moby Dick ch1	12283	6723	45
Allemand	Kritik der reinen VernunftCh1&2	37783	20962	44

code python 3.4

class huffobj:
    def __init__(self, string, proba, fils1 = None, fils2=None, codage =''):
        self.string = string
        self.proba = proba
        self.fils1 = fils1
        self.fils2 = fils2
        self.codage = codage

    def getcadet(self):
        return self.fils1

    def getaine(self):
        return self.fils2
    
    def getproba(self):
        return self.proba

    def getstring(self):
        return self.string
    
    def setcode(self, digits):
        self.codage = digits

    def getcode(self):
        return self.codage

    def __str__(self ):
        return 'Caractère(s) : ' + self.string + ' proba = ' + str(self.proba) + ' codage = ' + str(self.codage)

def seeklowest(collec):
    """recherche l'object huffman avec la plus faible proba"""
    mini = collec[0].getproba()
    indicemin = 0
    for balay in range(len(collec)):
        if collec[balay].getproba()<mini:
            mini = collec[balay].getproba()
            indicemin = balay
    return indicemin

def link2lowest(collec):
    ''' crée un noeud reliant les deux noeuds les plus petits'''
    posmin = seeklowest(collec)
    petit1 = collec.pop(posmin)
    posmin = seeklowest(collec)
    petit2 = collec.pop(posmin)
    newobj = huffobj(petit1.getstring()+petit2.getstring(), petit1.getproba()+petit2.getproba(), petit1, petit2, '')
    collec.append(newobj)
    #print('=====')
    #for item in collec:
    #   print(item)
    return collec

def districodes(noeud, codenoeud):
    '''Attribue les codes aux noeuds'''
    #print(noeud.getstring())
    if len(noeud.getstring()) ==1:  #noeud singulier
        noeud.setcode(codenoeud)
        #print(noeud.getstring(), ' >> ', codenoeud)
    else:
        districodes(noeud.getcadet(), codenoeud+[True])
        districodes(noeud.getaine(), codenoeud+[False])
        
def dicocodes(noeud):
    global dico2
    #print(noeud.getstring())
    if len(noeud.getstring()) ==1:  #noeud singulier
        dico2[noeud.getstring()] = noeud.getcode()
       # print(noeud)
    else:
        dicocodes(noeud.getcadet())
        dicocodes(noeud.getaine())
                
                
f = open('constitution.txt', 'r')

mystring = f.read()
sizein = len(mystring)
print('longueur du texte initial en octets', str(sizein))

dico = {}

for mychar in mystring:
    if mychar in dico:
        dico[mychar] +=1
    else:
        dico[mychar] =1

collec= []

for item in dico:
    #print(item,dico[item]) 
    newobj = huffobj(item, dico[item])
    collec.append(newobj)
    #print(newobj)


#on fait l'arbre
while len(collec)>1:    
    collec = link2lowest(collec)

#on distribue les codes
racine = collec[0]
racine.setcode = []
districodes(racine, [])

#on fait un dico
dico2 = {}
dicocodes(racine)

#encodons
sortie = []
for mychar in mystring:
    sortie.extend(dico2[mychar])

sizeout = int((1+len(sortie))/8)
print('longueur obtenue', sizeout)
print('% de compression gagné : ', str(int(100*(1-sizeout/sizein))))