from pylab import *

def Codes_ASCII() :
    alphabet="abcdefghijklmnopqrstuvwxyz"
    
    for lettre in alphabet :
        print("code ASCII dy symbole ",lettre, ord(lettre))
        print("code ASCII dy symbole ",lettre.upper(), ord(lettre.upper()),"\n")
        
    print("Correspondances symbole <-> code \n :")
    print([[k,chr(k)] for k in range(256)])

#Codes_ASCII()  


#### CODAGE HUFFMAN ####

# Construction de l'arbre de codage à partir d'une liste L=[[symbole,frequence],...]

def Percolation(x,L) :
    """ place x au premier endroit où il faut placer dans L déjà triée """
    i=0
    while i<len(L) and L[i][1]<x[1] :
        i+=1
    return L[:i]+[x]+L[i:]



def Tri(L) :
    """ trie L selon la seconde occurrence """
    L_Temp=L.copy()
    L_Tri=[ ]
    while L_Temp != [ ] :
        L_Tri=Percolation(L_Temp.pop(),L_Tri)
    return L_Tri
    
# L=[["a",1],["b",1],["c",0],["d",2],["e",3],["f",1.5],["g", 7],["h",2],["i",-1]]
# print(Tri(L))

def Arbre(L) :
    """ construit la correspondance symbole <-> code """
    L_Temp=Tri(L).copy()
    L_Code=[[[[x[0],""]],x[1]] for x in L_Temp]
    # occurrences de L_Code de format :
    # [ [liste de [feuilles ,code]] , frequence ]
    if L_Temp==[] :
        return []
    elif len(L_Temp)==1 :
        return [L_Temp[0],[1]] # si un seul symbole, codage par 1
    else :
        while len(L_Code[0][0])!=len(L_Temp) :
            x,y=L_Code[0],L_Code[1] # les deux premiers termes
            for i in range(len(x[0])) :
                x[0][i][1]="0"+x[0][i][1] # fils gauche codé par 0
            for i in range(len(y[0])) :
                y[0][i][1]="1"+y[0][i][1] # fils droit codé par 1
            z=[x[0]+y[0],x[1]+y[1]] # concaténation des listes feuilles/code associées à une racine égale à la somme des fréquences
            L_Code=Percolation(z,L_Code[2:]) 
        return L_Code[0][0]    
            
# L=[["a",17],["b",1],["c",3],["d",3],["e",3],["f",1],["g", 2],["h",2],["i",1],["j",4]]                             
# print(Arbre(L))

# Construction de la liste [[symbole,frequence],...]

def Index(x,L) :
    """ renvoie le premier index de x dans L et -1 si x n'est pas dans L """
    i=0
    while i<len(L) and L[i] != x :
        i+=1
    if i==len(L) :
        return -1
    else :
        return i

# L=[1,3,3,3,2,2,3,2,3,7,5,7]
# for k in range(8) :
#     print(Index(k,L))
    
def Symb_Freq(message) :
    L=[]
    for x in message :
        i=Index(x,[y[0] for y in L]) 
        if i==-1 :
            L.append([x,1])
        else :
            L[i][1]+=1
    return L

# print(Symb_Freq("ceci_est_un_test."))
            
# Codage Huffman proprement dit 

def Codage_Huffman(message) :
    Table=Arbre(Symb_Freq(message))
    Code=""
    for x in message :
        i=Index(x,[y[0] for y in Table]) # index de la feuille 
        Code=Code+"".join([str(k) for k in Table[i][1]])
        
    return [Code,Table]

# message = "bonjour tout le monde !!!!"
# print(Codage_Huffman(message))

### Décodage Huffman

def Decodage_Huffman(code,table) :
    """ revoie le message en clair à partir du code et de la table """
    code_Temp=code
    message=""
    while code_Temp != "" :
        curseur=1
        i=-1
        while i==-1 :
            curseur+=1 # tant que le curseur n'est pas assez loin, on avance le curseur de lecture ; vient un moment où on tombe sur un code (qui est unique par construction)
            i=Index(code_Temp[:curseur],[y[1] for y in table])
        message=message+table[i][0]
        code_Temp=code_Temp[curseur:] # on raccourcit la lecture du code 
    return message

### essai

# message = "bonjour tout le monde !!!! Je teste un autre message"
# code,table=Codage_Huffman(message)
# print(code,table)
# print(Decodage_Huffman(code,table)) 

import os

# os.chdir("E:/Exos_A_Puiser/Huffman_En_Beamer")
# print(os.getcwd())
# fichier = open("camus_etranger.txt", "r",encoding="utf8")
# message=fichier.read()
# fichier.close()
# code,table=Codage_Huffman(message)
# print(code,table)
# print(Decodage_Huffman(code,table))

## essai avec l'exemple du Beamer

# L="ceci_est_un_test"
# 
# print(len(Codage_Huffman(L)[0]))
# print(8*len(L))


# os.chdir("E:/Exos_A_Puiser/Huffman_En_Beamer")
# print(os.getcwd())
# fichier = open("camus_etranger.txt", "r",encoding="utf8")
# message=fichier.read()
# fichier.close()
# code,table=Codage_Huffman(message)
# print(table)
# print('longueur message :',len(message))

def Extremes(L) :
    """ donne les index de L où les secondes occurrences sont extremales """
    i=0
    m,M=L[0][1],L[0][1]
    L_m,L_M=[L[0]],[L[0]]
    for k in range(1,len(L)) :
        if L[k][1]<m :
            m=L[k][1]
            L_m=[k]
        elif L[k][1]==m :
            L_m.append(k)
        elif L[k][1]>M :
            M=L[k][1]
            L_M=[k]
        elif L[k][1]==M :
            L_M.append(k)
    return [L_m,L_M]
# print(Decodage_Huffman(code,table))

# L=[[x[0],len(x[1])] for x in table]
# Resultat=Extremes(L)
# 
# print("valeurs minimales :")
# 
# print([table[k] for k in Resultat[0]])
# 
# 
# print("valeurs maximales :")
# 
# print([table[k] for k in Resultat[1]])

# message ="huffman"
# Resultat=Codage_Huffman(message)
# print(Resultat[0])
# print(Resultat[1])


def Taux_Codage(S) :
    """ calcule le taux de codage et le comparer à  l'entropie """
    L=[]
    for x in S :
        i=Index(x,[y[0] for y in L]) 
        if i==-1 :
            L.append([x,1])
        else :
            L[i][1]+=1
    Res=[[x[0],x[1]/len(S)] for x in L]
   
    
    
    print("Valeur de l'entropie : ",sum([-log(x[1])/log(2)*x[1] for x in Res]))
    
    Res_bis=Codage_Huffman(S)
    taux=0
    for k in range(len(Res)) :
        i=Index(Res[k][0],[y[0] for y in Res_bis[1]]) # place du k-ième symbole rencontré dans la table d'encodage
        taux+=Res[k][1]*len(Res_bis[1][i][1]) # fréquence du k-ième symbole * longueur du code associé
    print("Taux de codage par Huffman ",taux)
    
    
# os.chdir("E:/Exos_A_Puiser/Huffman_En_Beamer")
# print(os.getcwd())
# fichier = open("camus_etranger.txt", "r",encoding="utf8")
# message=fichier.read()
# fichier.close()
# code,table=Codage_Huffman(message)
# print(table)


os.chdir("F:/Exos_A_Puiser/Huffman_En_Beamer")

fichier = open("camus_etranger.txt", "r",encoding="utf8")
S=fichier.read()
# S="ceci_est_un_test"
Taux_Codage(S)