DUT Informatique 1 – 2014/2015
Programmation Python
Travaux Dirigés n o9
Listes, chaînes, dictionnaires : performances (suite)
Au menu : La Transformée de Burrows-Wheeler.
Dans ce TP nous allons mettre en œuvre les méthodes vues précédemment (histogramme, rotation) sur un algorithme fameux : la transformée de Burrows-Wheeler (BWT). Cet algo intervient, entre autres, dans plusieurs méthodes de compression
de données dont bzip2 (Linux), 7zip (Windows).
L’idée de départ est la suivante : sans rentrer dans les détails, on peut montrer qu’un excellent moyen de préparer le terrain
pour les algorithmes de compression (tels que l’algorithme de Huffman) est de travailler sur une source (un texte, par
exemple) triée.
Or, si il est très facile de trier un texte, il est malheureusement impossible d’effectuer le traitement inverse (retrouver un
texte à partir de la suite de ses lettre triées dans l’ordre alphabétique).
C’est là qu’intervient la BWT : elle permet de construire une version "presque" triée du texte tout en étant réversible (on
peut retrouver le texte initial). On optimisera ainsi les performances des algorithmes de compression, tout assurant que l’on
pourra décoder les textes compressés.
Cet algorithme utilise les matrices de rotation vues au TP précédent.
x Exercice 1. la transformée directe : BWT
Dans l’Exercice 2 du TP08, on a vu comment construire de manière très efficace la matrice des rotations d’un
texte sous la forme d’une liste de chaînes. C’est la première étape de l’algorithme BWT. La matrice ainsi
formée contient, en première ligne, le texte source initial.
La seconde étape consiste à trier cette matrice par ligne. Dans cette nouvelle matrice, le texte original (sans
rotation) n’est plus en ligne 0 mais quelque part au milieu (cf. exemple ci-dessous)
La nouvelle matrice contient, en première colonne, la version de source triée lexicographiquement. Ce n’est
pas celle là qui nous intéresse mais ses voisines immédiates : les seconde et dernière colonnes.
En observant celles-ci on remarque en général que, si elle ne sont pas réellement triées, elles présentent de
longues séries de symboles identiques. Ce phénomène provient du fait qu’un texte structuré présente de
nombreux motifs (suites de lettres identiques).
C’est le cas dans l’exemple ci-dessous : tous les ’m’ sont suivis de ’a’, eux-mêmes presque toujours suivis
de ’n’, tous les ’e’ sont suivis de ’*’, eux-mêmes presque toujours suivis de ’m’... L’algorithme a donc
tendance à regrouper les symboles en paquets sur les première et dernière colonnes. Sur des textes plus long
l’effet est beaucoup plus flagrant.
Exemple : pour txt="ma*maman*mange*une*mangue*" on obtient la
0 *ma*maman*mange*une*mangue
1 *maman*mange*une*mangue*ma
2 *mange*une*mangue*ma*maman
3 *mangue*ma*maman*mange*une
4 *une*mangue*ma*maman*mange
5 a*maman*mange*une*mangue*m
col.no 24
6 aman*mange*une*mangue*ma*m
7 an*mange*une*mangue*ma*mam
8 ange*une*mangue*ma*maman*m
9 angue*ma*maman*mange*une*m
col.no 0
10 e*ma*maman*mange*une*mangu
11 e*mangue*ma*maman*mange*un
12 e*une*mangue*ma*maman*mang
13 ge*une*mangue*ma*maman*man
col.no 1
14 gue*ma*maman*mange*une*man
15 ma*maman*mange*une*mangue* ⇐txt
16 maman*mange*une*mangue*ma*
17 man*mange*une*mangue*ma*ma
18 mange*une*mangue*ma*maman*
19 mangue*ma*maman*mange*une*
20 n*mange*une*mangue*ma*mama
21 ne*mangue*ma*maman*mange*u
22 nge*une*mangue*ma*maman*ma
23 ngue*ma*maman*mange*une*ma
24 ue*ma*maman*mange*une*mang
1
matrice de rotation triée :
: eaneemmmmmungnn**a**auaag*
: *****aaaaaeeeggmmmmmnnnnuu (triée)
: mmmmu*mnnn***euaaaaa*eggen
C’est en général la dernière colonne que l’on choisit comme code de sortie de l’algorithme. La seule autre
information nécessaire au décodage (cf. Exercice 2) est le no de ligne où se trouve le texte initial (line=15
dans l’exemple précédent).
☞ A partir de la fonction rotations5(text) de l’Exercice 2 du TP08, écrire une fonction BWT(text) qui construit
la matrice de rotation, la trie, en extrait l’indice line où se trouve le texte et le code (dernière colonne) sous
la forme d’une chaîne de caractère, et finalement renvoie ces deux informations.
x Exercice 2. la transformée inverse : iBWT
C’est l’opération permettant, à partir des informations line et code précédentes, la reconstruction de la source
initiale text.
Principe :
Il est a priori très simple. On dispose d’un texte (code) dont on sait qu’il correspond à la dernière colonne
Cn−1 d’une matrice de rotation triée (n est la longueur du code). On va donc essayer de reconstituer cette
matrice. L’information supplémentaire line nous dira à quelle ligne on pourra trouver le texte original.
En réalité on dispose de deux colonnes de notre matrice : il suffit en effet de trier la chaîne code pour obtenir
la première colonne C0 , qui est en fait la suivante de Cn−1 (il s’agit de rotations, ne l’oublions pas).
1 Version 1 : très simple, mais affreusement inefficace.
On initialise la matrice des rotations triée Pt comme une matrice à une colonne : C0
Ensuite, en concaténant les lignes de Cn−1 au début des lignes de Pt , puis en triant Pt par ligne, on
forme les deux premières colonnes de Pt . En procédant ainsi n − 1 fois, on aura reconstruit toutes les
colonnes de Pt .
Exemple : text="abraca" → code="caraab", line=1
C5 [0]
C5 [01]
C5 [012]
C5 [0123]
C5 [01234]
[012345]
c+a
a+a
r+a
a+b
a+c
b+r
c+aa
r+ac
a+ab
a+br
a+ca
b+ra
c+aab
a+abr
r+aca
a+bra
a+caa
b+rac
c+aabr
a+abra
r+acaa
a+brac
a+caab
b+raca
c+aabra
a+abrac
r+acaab
a+braca
a+caabr
b+racaa
aabrac
abraca
acaabr
bracaa
caabra
racaab
tri
tri
tri
tri
tri
0
1=line
2
3
4
5
Il ne reste plus qu’à extraire la ligne line de Pt .
☞ Ecrire une fonction iBWT_grosbourrin(code,line) qui implémente cette version de l’algorithme et
renvoie le texte décodé.
☞ Quelle est sa complexité ?
2 Version 2 : très efficace, mais moins simple.
L’idée est de remarquer que, puisqu’on concatène toujours les éléments de la colonne Cn−1 en début
de ligne, et que ces lignes sont déjà triées, le prochain tri effectuera toujours les mêmes échanges de
lignes.
Il suffit alors de déterminer quelle est cette table d’échanges pour reconstruire directement le texte en
une seule passe de complexité O(n).
Notons :
- Te la table d’échange. C’est en fait une permutation sur la liste d’entiers [0,1,2,....,n-2,n-1]
- C0 la version triée de la source code. C’est la première colonne de la matrice.
Alors la valeur de Te[i] correspond à la position du symbole C0 [i] dans code.
Dans l’exemple précédent (text="abraca" → code="caraab", line=1) on aurait :
C0 :
code :
0
1
2
3
4
5
a0
c
a1
a0
a2
r
b
a1
c
a2
r
b
=⇒ Te=[1,3,4,5,0,2]
En pratique, la construction de Te n’est pas si simple car il faut distinguer les différentes occurrences
d’un même symbole, comme les ’a’ numérotés dans l’exemple ci-dessus.
2
Pour cela nous allons utiliser un histogramme modifié qui associera aux symboles non pas un nombre
d’occurrences mais une positions.
☞ Ecrire une fonction histoPos(code) , qui crée et retourne un dictionnaire Hdp dont les clefs sont les
symboles présents dans la source code et les valeurs sont leur position de première apparition dans
la source triée.
Pour cela, on commencera par construire un histogramme trié, comme au TP précédent (dictionnaire
converti en liste triée de paires [symb,occ]), puis on remplacera les occurrences par les positions de
première apparition, et pour finir on convertira celle liste de paires [symb,pos] en dictionnaire.
Exemple : pour la source code="caraab", le dictionnaire de retour serait Hdp={{’a’ :0,’b’ :3,’c’ :4,’r’ :5}}.
☞ Ecrire une fonction tableEchange(code,Hdp) , qui à partir du dictionnaire précédent, constuit et retourne la table d’échange Te, sous la forme d’une liste d’entiers.
Pour cela, pour chaque symbole lu s=code[i], on place l’indice i dans Te à la position donnée par
le dictionnaire (Hdp[s]) et, pour marquer le fait que l’on a vu un exemplaire du symbole s, on
incrémente sa position dans le dictionnaire.
Exemple : pour la source code="caraab", cet algorithme se déroule comme suit :
init
Te=[ , , , , , ]
Hdp={{’a’:0,’b’:3,’c’:4,’r’:5}}
i=0
code[0]=’c’
→ Hdp[’c’]=4 → Te[4]=0 → Hdp[’c’]=5→
Te=[ , , , ,0, ]
Hdp={{’a’:0,’b’:3,’c’:5,’r’:5}}
i=1
code[1]=’a’
→ Hdp[’a’]=0 → Te[0]=1 → Hdp[’a’]=1→
Te=[1, , , ,0, ]
Hdp={{’a’:1,’b’:3,’c’:(,’r’:5}}
i=2
code[2]=’r’
→ Hdp[’r’]=5 → Te[5]=2 → Hdp[’r’]=6→
Te=[1, , , ,0,2]
Hdp={{’a’:1,’b’:3,’c’:5,’r’:6}}
i=3
code[3]=’a’
→ Hdp[’a’]=1 → Te[1]=3 → Hdp[’a’]=2→
Te=[1,3, , ,0,2]
Hdp={{’a’:2,’b’:3,’c’:5,’r’:6}}
i=4
code[4]=’a’
→ Hdp[’a’]=2 → Te[2]=4 → Hdp[’a’]=3→
Te=[1,3,4, ,0,2]
Hdp={{’a’:3,’b’:3,’c’:5,’r’:6}}
i=5
code[5]=’b’
→ Hdp[’b’]=3 → Te[3]=5 → Hdp[’b’]=4→
Te=[1,3,4,5,0,2]
Hdp={{’a’:3,’b’:4,’c’:5,’r’:6}}
Une fois que l’on a la table d’échange, l’algorithme de décodage se déroule comme suit :
(a)
(b)
(c)
(d)
on initialise l’indice d’échange à k=line et l’indice de sortie à i=0
le caractère de sortie text[i] est donné par code[Te[k]]
l’indice d’échange suivant est donné par k=Te[k]
on continue ainsi (i=i+1) jusqu’à remplissage complet du texte (n fois)
☞ Ecrire finalement une fonction iBWT_petitponey(code,line) qui implémente cette version de l’algorithme et renvoie le texte décodé.
3 Performances :
Tester et comparer les deux méthodes pour diverses sources de plus en plus volumineuses.
3
© Copyright 2024 ExpyDoc
