Ce document a été produit par HEVEA.
Votre browser peut avoir a être configuré pour afficher correctement
certains symboles.
Reportez-vous à la documentation d'HEVEA.
Licence d'informatique
Compression et décompression de listes de mots triés
Examen -- Partie Unix
Janvier 1999
Les documents de cours et TD sont autorisés.
On rendra deux copies séparées pour la partie Unix et pour la
partie langage C. La partie Unix est à rendre sur une copie de
couleur.
Ce document est disponible sous forme d'un fichier PostScript compressé.
Important
Plusieurs commandes Bourne-shell sont à développer. On veillera
particulièrement à détailler pour chacune des commandes un algorithme
avant de donner le code Bourne-shell lui-même. La notation sera
répartie entre ces deux composantes de vos réponses.
Nous allons développer une commande cmprs qui compresse une
liste de mots triée (un dictionnaire). L'option -d de la
commande permet de décompresser le résultat fourni par cmprs.
Une première version de la syntaxe est la suivante :
cmprs
[-d]
[inputfile
[outputfile]]
Par défaut, la commande lit sur son entrée standard et produit son
résultat sur la sortie standard.
La compression est réalisée par l'élimination des préfixes communs des
mots et par leur remplacement par un caractère unique qui code le
nombre de caractères communs avec le mot précédent.
Soit le dictionnaire /tmp/dico ; le résultat de la commande
cmprs est le suivant :
% cat /tmp/dico
computer
computerize
computerized
computerizes
computerizing
computers
inform
informal
informality
informally
informant
informants
information
informational
informative
informatively
informed
informer
informers
informing
informs
% cmprs /tmp/dico
0computer
8ize
Bd
Bs
Aing
8s
0inform
6al
8ity
8ly
7nt
9s
7tion
Bal
9ve
Bly
6ed
7r
8s
6ing
6s
Les caractères de codage sont les suivants :
-
0-9
- représentent les entiers de 0 à 9 ;
- A-Z
- représentent les entiers de 10 à 35 ;
- a-z
- représentent les entiers de 36 à 61.
Traitement des préfixes
Deux fonctions Bourne-shell char-to-int et
int-to-char permettent de passer des préfixes sous forme d'un
caractère à leur valeur entière et inversement. Ces fonctions
acceptent un argument et affiche leur résultat sur la sortie standard.
Elles retournent normalement la valeur 0 et la valeur 1 en cas
d'erreur.
Exemples :
% char-to-int 9
9
% char-to-int X
33
% int-to-char 37
b
% int-to-char 99
% echo $status
1
Question 1 [char-to-int]
Donner le code Bourne-shell de la commande char-to-int.
Question 2 [int-to-char]
Donner le code Bourne-shell de la commande int-to-char.
Indication
Les exercices 1 et 2
peuvent être traitées en utilisant exclusivement les structures de
contrôle du Shell et les commandes tr, expr, et
cut.
Compression
Question 3 [cmd-cmprs]
Donner le code Bourne-shell de la fonction cmd-cmprs
qui produit sur la sortie standard la compression de ce qui est
lu sur l'entrée standard.
Décompression
La fonction Bourne-shell cmd-uncmprs produit sur sa sortie
standard le résultat de la décompression de ce qui est lu sur son
entrée standard.
On ne demande pas d'écrire le code de cette fonction.
La commande cmprs
On complète la syntaxe de la commande cmprs donnée en début
de sujet. La nouvelle syntaxe est la suivante :
cmprs
[-d]
[-z]
[inputfile
[outputfile]]
Il est précisé que les options de la commande peuvent être combinées.
Ainsi -dz ou -zd sont équivalents à -d
suivi de -z.
Dans la syntaxe de la commande, une valeur - pour les
fichiers inputfile ou outputfile
indique de considérer l'entrée/la sortie standard. Ainsi les trois
commandes suivantes sont équivalentes :
% cmprs -d - /tmp/toto
% cmprs -d - > /tmp/toto
% cmprs -d > /tmp/toto
Il est précisé que le fichier d'entrée et le fichier de sortie ne
peuvent être égaux.
L'option -z indique que les fichiers d'entrée et de sortie
sont compressés par la commande gzip. Ainsi les deux
commandes suivantes sont équivalentes :
% zcat /tmp/toto.cpr.gz | cmprs -d | gzip - > /tmp/toto.gz
% cmprs -dz /tmp/toto.cpr.gz /tmp/toto.gz
Question 4 [cmprs]
Donner le code Bourne-shell de la commande cmprs.
Ce document a été traduit de LATEX par
HEVEA.