Précédent Index Suivant

1  Partie C de l'examen

  La commande ecrivain

La syntaxe de la commande ecrivain est la suivante :
ecrivain   [-p psize]   [-s size]   [inputfile   [outputfile]]

Elle génère dans le fichier outputfile (par défaut la sortie standard) un fichier d'au plus size mots (par défaut 1000), à partir du fichier inputfile (par défaut l'entrée standard). L'algorithme utilise des préfixes de psize mots (2 par défaut).

  Une structure de données pour la commande ecrivain

Pour que l'algorithme de génération de texte fonctionne correctement, le volume de l'entrée doit être relativement important, par exemple le contenu complet d'un livre [On s'apprête donc à traiter de l'ordre de 100.000 mots en entrée et de l'ordre de 1.000 mots en sortie. La commande ne peut reposer sur une structure de données simpliste (par exemple la liste des mots) sous peine de performances détestables : 1000 fois une recherche séquentielle dans une liste de 100.000 mots.].

Nous allons construire une structure de données qui associe un préfixe et l'ensemble de ses suffixes. Lors de la première phase de l'algorithme (construction de la structure de données à partir du texte d'entrée), il est nécessaire de retrouver la structure d'un préfixe donné pour y ajouter un nouveau suffixe. Lors de la seconde phase de l'algorithme (génération du texte), il est nécessaire de retrouver la structure d'un préfixe donné pour choisir aléatoirement un de ses suffixes. Dans les deux cas, l'algorithme demande de retrouver rapidement l'ensemble des suffixes d'un préfixe donné. Nous pouvons utiliser une table de hachage.

Le principe d'une table de hachage est de partitionner l'ensemble des éléments en un nombre N, fixé, de listes. Une table de hachage est ainsi vue comme un tableau de N listes d'éléments. Une fonction (la fonction de hachage) retourne pour un élément donné un entier qui est un indice dans ce tableau. Ainsi, la recherche de la position d'un élément dans la table de hachage [que ce soit pour accéder à l'élément ou l'insérer dans la table] commence par calculer cet indice ; avec cet indice, on accède dans la table de hachage à une liste d'éléments ; on recherche alors séquentiellement dans la liste correspondante l'emplacement de l'élément. L'efficacité d'une table de hachage réside dans le choix judicieux de la fonction de hachage ; son exécution doit être peu coûteuse et les indices produits par cette fonction sur l'ensemble des éléments doivent bien se répartir entre 0 et N-1.

La structure de données associée à un préfixe est la suivante :
unsigned int PLEN ;     /* longueur des préfixes (nombre de mots dans un préfixe) */

typedef struct prefix Prefix ; 
typedef struct suffix Suffix ; 

struct prefix {
  char **words ;        /* le tableau (de taille PLEN) des mots du préfixe */  
  Suffix *suffixes ;    /* la liste des suffixes */ 
} ; 

struct suffix {
  char *word ;          /* la valeur du suffixe */ 
  Suffix *nextS ;       /* le suivant dans la liste des suffixes du préfixe */
} ; 
La table de hachage est alors déclarée ainsi :
#define NHASH 4093      /* taille du tableau constituant la table de hachage */

/* Un élément d'une liste de la table de hachage */ 
typedef struct elem Elem ; 
struct elem {
  Prefix prefix ;       /* le prefixe */
  Elem *nextE ;         /* l'élément suivant dans la liste */ 
} ; 

/* La table de hachage */ 
Elem *hashtable [NHASH] ; 
La figure 1 illustre cette structure de données.


Figure 1 : Une table de hachage pour ecrivain (PLEN vaut 2)


On utilise la fonction de hashage suivante :
/* la fonction de hashage. Retourne un entier inférieur à NHASH à
   partir d'un tableau de PLEN mots constituant un préfixe. */ 
unsigned int hash (char *words[]) ; 

  Questions -- Partie C


Question 1   La table de hachage est organisée sous forme de listes de préfixes lesquels sont mémorisés sous forme de tableaux de PLEN mots. Nous avons besoin d'une fonction de test d'égalité de deux préfixes :

int prefixeql (const char *words1[], const char *words2[]) ;
retourne zéro si et seulement si les deux préfixes sont différents.

Donnez le code C de la fonction prefixeql ()
.

Question 2   La fonction addsuffix () ajoute un suffixe donné à la liste des suffixes d'un préfixe donné :

void addsuffix (Prefix *p, const char *suffix) ; 
Il est garanti que la chaîne de caractères suffix sera inchangée dans la suite du programme (elle n'a donc pas à être recopiée).

On ne se préoccupe pas de savoir si le suffixe est déja présent dans la liste des suffixes [Plus un suffixe apparaît dans le texte original, plus il doit avoir de chance d'apparaître dans le texte généré. Nous ne gérons pas un compteur associé à chacun des suffixes mais procédons par présence multiple du suffixe dans la liste des suffixes.].

Donner le code C de la fonction addsuffix ()
.

Question 3  

La fonction lookup () recherche un préfixe (tableau words de PLEN chaînes de caractères) donné dans la table de hachage. Elle retourne un pointeur sur le préfixe.

Prefix *lookup (const char *words[], unsigned int create) ; 
Le paramètre create indique le comportement de lookup () dans le cas où le préfixe n'est pas présent : Donner le code C de la fonction lookup ().

Question 4   La fonction getasuffix () retourne un suffixe choisi aléatoirement parmi les suffixes du préfixe donné par le tableau de PLEN chaînes de caractères :

char *getasuffix (char *words[]) ; 
Il est garanti qu'un tel suffixe existe dans la table de hachage [On sort du programme sur une erreur fatale (un bug de notre programme !) sinon. En effet pour tout préfixe du texte initial, il y a un suffixe dans la table de hachage. Seul le dernier préfixe du texte pourrait ne pas être présent dans la table. On a donc ajouté, en fin de création de la table, le suffixe "" associé à ce dernier préfixe.].


Précédent Index Suivant