CPGE Oujda Problème sur les chaines de caractères Spé

Révisions

Définitions préliminaires

- La compression de données est le traitement informatique utilisant un algorithme particulier, qui permet de transformer une suite de bits A en une suite de bits B plus courte. Les suites A et B contiennent les mêmes informations, mais codées d’une manière différente

- La décompression est l’opération inverse de la compression

- L’algorithme RLE (Run-Length Encoding), appelé en français le codage par plages, est un algorithme de compression informatique qui consiste à repérer et à éliminer la redondance des données. Toute suite de bits ou de caractères identiques est remplacée par un couple (caractère répété suivi de son nombre d’occurrences (son nombre de répétitions)). Exemple: CCCCBBBRCC donne: C4B3R1C2

Dans ce qui suit, on se propose d’étudier l’algorithme RLE pour compresser des chaînes de caractères :

- On appelle chaîne d’origine, toute chaîne de caractères avant sa compression.

- On appelle chaîne compressée de la chaîne d’origine ch, la chaîne de caractères contenant une occurrence unique (un seul caractère) de toute suite de caractères identiques consécutifs se trouvant dans la chaîne d’origine ch .

Exemple :- si ch = AAARTTAAVVTTT , sa chaîne compressée = ARTAVT

- Soient ch une chaîne d’origine et s sa chaîne compressée. On appelle tableau d’occurrences de s dans ch, un tableau d’entiers contenant le nombre des

répétions successives de chaque caractère de s dans la chaîne d’origine ch

Exemple :- Si la chaîne d’origine ch = BBBXXXXXXBBBYYYYYB et s sa chaîne compressée, alors le tableau d’occurrences de s dans ch est {:3, 6, 3, 5,1}

Mise en œuvre de l’algorithme RLE en langage Python

Dans ce problème, il s’agit d’écrire des fonctions en langage python utilisant l’algorithme RLE pour la compression et la décompression de chaînes de caractères

Rappels :

- Une chaîne de caractères en langage python est un tableau de caractères non modifiable , sa longeur est donnée par la fonction len

-Le premier élément d’une liste en langage python a pour indice zéro ( 0) Remarques

- On suppose que toutes le chaînes de caractères manipulées dans ce problème, ont des longueurs strictement inférieurs à 255.

Dans cette partie, on se propose d’écrire des fonctions en langage pyhon avec paramètres pour la compression et la décompression de chaîne de caractères

- On suppose avoir déclaré comme paramètres ch pour la chaîne d’origine et ch_compress pour sa chaîne compressée)

Soit une variable tableau de nom occur destinée à contenir le tableau d’occurrences de ch_compress dans ch,

Question 1 ) Ecrire le code d’une fonction d’entête : def compresser(ch)

qui met dans la chaîne ch_compress , la chaîne compressée de ch

Exemple : - Si la chaîne ch = AAAXRRZZZAAAA

- l’appel de la fonction compresser(ch) retourne AXRZA

Question 2) Ecrire le code d’une fonction d’entête: def occurrence(ch)

qui retourne le tableau occur (occurrences de ch_compress dans ch) Exemple

- Si la chaîne d’origine ch = DDDRRRRDTTYYYY,

- l’appel de la fonction occurrence (ch) retourne le tableau occur tel que : occur[0]=3, occur[1]=4, occur[2]=1, occur[3]=2, occur[4]=4

Question 3) Ecrire le code d’une fonction d’entête :

def decompresser(ch_compress,ch,occur) qui permet de décompresser la chaîne ch_compress en chaîne d’origine ch

Exemple :

- Si la chaîne ch_compress = BACB et occur={3,5,4,1}

- l’appel de la fonction decompresser(ch_compress,occur) retourne BBBAAAAACCCCB

Dans cette question on se propose de compresser une chaîne de caractères sans utiliser le tableau d’occurrences

- On appelle chaîne codée d’une chaîne d’origine, la chaîne de caractères contenant une occurrence unique de toute suite de caractères identiques consécutifs

se trouvant dans la chaîne d’origine, suivie du nombre d’occurrence du caractère dans la chaîne d’origine

Question 4) Ecrire le code d’une fonction d’entête :

def coder(s) qui permet de mettre dans la chaîne s_codee , la chaîne codée de s,

Exemple : - Si la chaîne s = EEEEEAAACCCCAAX

- Après l’appel de la fonction coder(s) , s_codee=E5A3C4A2X1

Solutions Q 1)

def compresser(ch):

ch_compress=""

i=0

while i<len(ch):

while ((i<(len(ch)-1)) and ( ch[i]==ch[i+1])):

i+=1

if(i<len(ch)):

ch_compress=ch_compress+ch[i]

i+=1

return ch_compress

print(compresser("AAARTTAAVVTTT"))

Q2)

def occurrence(ch_compress,ch):

i,j=0,0

occur=[]

while(i<len(ch_compress)):

nb=0;

while (j<len(ch))and (ch[j]==ch_compress[i]) :

j+=1

nb+=1

occur.append(nb)

i+=1

return occur

ch="AAARTTAAVVTTT"

ch_c=compresser(ch)

print(ch_c)

occ=occurrence(ch_c,ch)

print(occ)

Q3)

def decompresser(ch_compress,occur):

i,j=0,0

ch=""

while(i<len(ch_compress)):

for k in range(occur[i]):

ch=ch+ch_compress[i];

i+=1

return ch

Q4)

def coder(s):

i=0

s_codee=""

while (i<len(s)):

occ=1;

while((i<len(s)-1) and (s[i]==s[i+1]) ):

i+=1

occ+=1

if(i<len(s)):

s_codee=s_codee+s[i]

s_codee=s_codee+str(occ)

i+=1

return s_codee