TP5-ThInfo-Correction
Posted on Mon 30 March 2020 in posts
TP 5 : Compression¶
Let but de ce TP est de constater qu'en enlevant les séquences les moins probable, on peut se permettre une petite erreur pour compresser le signal
Question
Correction
Remarques
Sujet
import numpy as np
import scipy.special
import matplotlib.pyplot as plt
Commencez par tracer la loi binomial, de paramètre $N=100$ et $p=0.1$. Vous tracerez la courbe sur une échelle linéaire puis sur une échelle log.
- Que constatez vous sur la probabilité de séquence de variables de Bernoulli, de paramètre $p=0.1$ comportant beaucoup de $1$ ?
- Si on fixe un seuil à $10^{-5}$ pour la probabilité, combien de $1$ pourront contenir les séquence possibles ??
- Combien faut-il générer de séquence suivant cette loi pour espérer obtenir une séquence dont la probabilité est environ de $10^{-5}$
Question
# plot de la binomial
# TODO
Correction
Version 0
# plot de la binomial
def plot_bin(n,p1):
x = []
y = []
for i in range(n):
x.append(i)
y.append( scipy.special.binom(n,i) * p1**i * (1-p1)**(n-i) )
return x,y
x,y = plot_bin(100,0.2)
f,ax = plt.subplots(1,2,figsize=(15,5))
ax[0].plot(x,y)
ax[1].semilogy(x,y)
Version 1
def binom(n, p1):
l = [scipy.special.binom(n,i) * p1**i * (1-p1)**(n-i) for i in range(n)]
return l
N = 100
p1 = 0.1
x = list(range(N))
y = binom(N, p1)
f,ax = plt.subplots(1,2,figsize=(15,5))
ax[0].plot(x, y)
ax[0].set_ylabel('P(X=k)')
ax[0].set_xlabel('k')
ax[0].set_title('Binomial law (p={p1}, N={N})'.format(**locals()))
#Log
ax[1].semilogy(x, y)
ax[1].set_ylabel('P(X=k)')
ax[1].set_xlabel('k')
ax[1].set_title('Binomial law [logscale] (p={p1}, N={N})'.format(**locals()))
plt.show()
Question
- Si on fixe un seuil à $10^{-5}$ pour la probabilité, combien de $1$ pourront contenir les séquence possibles ??
Correction
answer_t = np.where(np.array(y)>10**(-5))
answer = answer_t[0]
s = ",".join([str(a) for a in answer])
print(f"with 1e-5 proba we can have sequences containing [{s}] 1 and the rest is 0")
Remarques
N = 100
p1 = 0.1
x = list(range(N))
y = binom(N, p1)
f,ax = plt.subplots(1,2,figsize=(15,5))
ax[0].plot(x, y)
ax[0].hlines(1e-5, 0, 100, label='1e-5')
ax[0].set_ylabel('P(X=k)')
ax[0].set_xlabel('k')
ax[0].set_title('Binomial law (p={p1}, N={N})'.format(**locals()))
ax[0].legend()
#Log
ax[1].semilogy(x, y)
ax[1].hlines(1e-5, 0, 100, label='1e-5')
ax[1].set_ylabel('P(X=k)')
ax[1].set_xlabel('k')
ax[1].set_title('Binomial law [logscale] (p={p1}, N={N})'.format(**locals()))
ax[1].legend()
plt.show()
Question
- Combien faut-il générer de séquence suivant cette loi pour espérer obtenir une séquence dont la probabilité est environ de $10^{-5}$
Correction
proba = np.array(y)
where_small_proba = np.where(np.array(y)<1e-5)[0]
small_proba = proba[where_small_proba]
proba_total_small = np.sum(small_proba)
print(proba_total_small)
Sujet
Ecrire la fonction suivante (pour un $N$ et un $p$ donné):
- Pour chaque $i$, vous compterez le nombre de séquence existant ainsi que la probabilité de l'ensemble des séquences.
- Vous calculerez alors pour chaque $i$ le nombre de séquence cumulé (le nombre de séquence ayant un nombre de $1$ compris entre $0$ et $i$.
- Vous calculerez également le poids (en probabilité) de ces séquences pour chaque $i$.
- Afficher pour $N=10,20,50,100,200,500,1000$, la courbe : $2^N - \# \text{seq}$, versus la probabilité cumulée
Note : vous utiliserez la fonction "coef_bin(k,n)" (k<=n) pour calculer le coefficient de la loi binomial $\mathcal{C}^k_n$.
Question
# coef binomial C^k_n
def coef_bin(k,n):
return np.math.factorial(n) // (np.math.factorial(k)*np.math.factorial(n-k))
- On veut compter combien il existe de séquence donc la somme est égale à $i$, pour $i$ allant de $0$ à $N$ (inclus).
def count_nb_sequence(i, N):
return coef_bin(i, N)
Sujet
n = 5
i = 2
nb_sequence = count_nb_sequence(i, n)
print(nb_sequence)
Exemple n=5, i=2 :
11000
10100
10010
10001
01100
01010
01001
00110
00101
00011
On a bien 10 séquences possibles
Question
- Pour chaque $i$, vous calculerez la probabilité de l'ensemble des séquences.
ie $p(X\in \{\text{sequences that contains i times 1}\}) $
# TODO
Correction
proba_seq = coef_bin(i, n) * p1**(n-i) * (1-p1)**i # binom(n-i,n,p1)
def p_binom(i, p, n=10):
proba_seq = coef_bin(i, n) * p**(n-i) * (1-p)**i
return proba_seq
p_binom(2, 0.1, 5)
Question
- Vous calculerez alors pour chaque $i$ le nombre de séquence cumulé ie. le nombre de séquence ayant un nombre de $1$ compris entre $0$ et $i$.
# TODO
Correction
nb_sequence_cumul = sum([count_nb_sequence(j, N) for j in range(i)])
print(nb_sequence_cumul)
Question
- Vous calculerez également le poids (en probabilité) de ces séquences pour chaque $i$.
- Afficher pour $N=10,20,50,100,200,500,1000$, la courbe : $2^N - \# \text{seq}$, versus la probabilité cumulée
Correction
def plot_code_compress(n,p1):
cumul_x = 0
cumul_y = 2**n
x = [0]
y = [2**n]
for i in range(0,n+1):
cout_pr = coef_bin(i,n) * p1**(n-i) * (1-p1)**i # binom(i,n,p1)
nb_seq = coef_bin(i,n)
cumul_x += cout_pr
cumul_y -= nb_seq
x.append(cumul_x)
y.append(cumul_y)
y = np.array(y)
x = np.array(x)
for i in range(0,n+1):
y[i] = np.math.log2(y[i])
return x, y/n
def Entropy(p):
return -p*np.log2(p)-(1-p)*np.log2(1-p)
for ni in [10,20,50,100,200,500,1000]:
x, y = plot_code_compress(ni, 0.1)
plt.plot(x, y, label=ni)
plt.plot([0,1], 2*[Entropy(0.1)], label='entropy')
plt.ylabel('% not possible sequence (logscale)')
plt.xlabel('cumulative proba binomial')
plt.legend()
plt.show()
Sujet
Code de Huffman¶
Regardons comment mettre en place le code de Huffman pour des chaînes de caractères.
- Ecrire la fonction Freq, qui renvoie le nombre de fois où apparaît un caractère dans la chaîne. Renvoyer le résulat sous la forme d'un dictionnaire [caractère]->freq
Remarques
Sujet
Question
def compute_occurences(text):
# TODO
return {}
Correction
Version 0 : quand on ne connait pas bien la lib standard de python.
def table_frequences(texte):
table = {}
for caractere in texte:
if caractere in table:
table[caractere] = table[caractere] + 1
else:
table[caractere] = 1
return table
# s = 'abcddccddde'
s = 'Ils agitent des urnes en carton où les salariés glissent régulièrement quelques pièces et même des billets. « A défaut de faire grève, soutenez les grévistes ! », lancent les délégués syndicaux à leurs collègues aux portes de l’usine.'
freq = table_frequences(s)
print(freq)
Version 1 : en utilisant Counter
from collections import Counter
def compute_occurences(texte):
count = Counter()
count.update(texte)
return count
s = 'Ils agitent des urnes en carton où les salariés glissent régulièrement quelques pièces et même des billets. « A défaut de faire grève, soutenez les grévistes ! », lancent les délégués syndicaux à leurs collègues aux portes de l’usine.'
occ = compute_occurences(s)
print(occ)
Sujet
Ecrire la fonction make_tree
qui, à partir d'un dictionnaire de fréquences créer un arbre¶
- transformer votre dictionnaire sous la forme d'une liste de tuple (freq,caractere)
On cherche à isoler les éléments les moins fréquents pour leur donner un code plus long. On va donc répéter l'opération suivante (jusqu'à n'avoir plus qu'un élément dans le tas):
- trouver les deux éléments du tas les moins fréquents et les "poper" de la liste.
- rajouter la "jointure" des deux éléments de la façon suivant : (fq1+fq2, {0:c1, 1:c2}) où fq1,fq2 sont les fréquences et c1,c2 les caractères
Question
def make_tree(occurences):
# TODO
return {}
Correction
Version 0 : moche avec un faux tas qui recalcule le min à chaque fois
def make_tree(occurrences):
# Construction d'un tas avec les lettres sous forme de feuilles
tas = [(occ, lettre) for (lettre, occ) in occurrences.items()]
# print("tas=",tas)
# Creation de l'arbre
while len(tas) >= 2:
# find the min
occ1, n1 = tas.pop(np.argmin([it[0] for it in tas]))
occ2, n2 = tas.pop(np.argmin([it[0] for it in tas]))
tas.append((occ1+occ2, {0:n1, 1:n2}))
# ajoute au tas le noeud de poids occ1+occ2 et avec les fils noeud1 et noeud2
return tas[0][1]
Version 1 : avec un vrai tas.
# Play with Tuple comparison in python
t1 = (2, 2, 'a')
t2 = (1, 3, {0: 'a', 1:'b'})
print("t1 == t2 :", t1 == t2)
print("t1 > t2 :", t1 > t2)
print("t1 < t2 :", t1 < t2)
import heapq
def make_tree(occurrences):
"""Prepare tree out of occurences of symbol for Huffman compressing"""
# To avoid comparing letters to dict we add a "tie-breaker" as an unique integer i
heap = [(occ, i, lettre) for i, (lettre, occ) in enumerate(occurrences.items())]
heapq.heapify(heap)
i = len(heap)
while len(heap) >= 2:
occ1, _, n1 = heapq.heappop(heap)
occ2, _, n2 = heapq.heappop(heap)
heapq.heappush(heap, (occ1+occ2, i, {0:n1, 1:n2}))
i += 1
return heap[0][2]
Sujet
tree = make_tree(freq)
import pprint
pprint.pprint(tree)
def printTree(tree, prefix=""):
if not prefix:
print('.')
if len(tree) <= 1:
print(prefix+"└──", tree)
else:
sub_tree = tree.items()
for i, (key, val) in enumerate(sub_tree):
if i < len(sub_tree)-1:
print(prefix+"├── "+str(key))
new_prefix = prefix+"│ "
else:
print(prefix+"└── "+str(key))
new_prefix = prefix+" "
printTree(val, prefix=new_prefix)
printTree(tree)
Sujet
Ecriture du code d'Huffman à partir de l'arbre¶
- à partir du dictionnaire créé par la fonction
make_tree
, construire un dictionnaire qui à un caractère lui associe son code
Question
def code_huffman(tree, prefix, code):
# TODO
return {}
Correction
Version 0
def is_leaf(subtree):
return len(subtree) == 1
def code_huffman(tree, prefix, code):
for node in tree:
if is_leaf(tree[node]):
code[prefix+str(node)] = tree[node]
else:
code_huffman(tree[node], prefix+str(node), code)
Sujet
Make the ascii code¶
code = {}
code_huffman(tree,'',code)
print(code)
inv_map = {v: k for k, v in code.items()}
inv_map
res = ''
for c in s:
res = res+inv_map[c]
print(res)
print()
print(len(res))
print(len(s)*8)
Calculer l'entropie de la chaîne de caractères¶
Question
def Entropy(fq):
# TODO
return 0.0
Correction
def Entropy(fq):
totfq = np.sum([j for i,j in freq.items()])
S = 0
for i,j in freq.items():
S += j/totfq * np.log(1/(j/totfq))
return S
totfq = np.sum([j for i,j in freq.items()])
print(totfq)
Entropy(freq)
1896*(1/2.9)
Sujet
res = ''.join([str(bin(ord(c)))[2:] for c in s])
print(res)