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
Module de C/Unix
Projet C

igrep --- Recherche indexée

Jean-Luc Levaire

Décembre 1997

Ce document est disponible sous forme d'un fichier PostScript compressé.





La commande igrep (indexed grep) proposée ici est inspirée de la commande grep existant sur la plupart des systèmes Unix. Sa principale particularité est qu'elle utilisera le fichier d'index créé par la commande stfsindex du projet Unix afin de minimiser son espace de recherche.

La commande igrep sera développée en C-ANSI, de façon modulaire.

  Reconnaissance du langage associé à une expression rationnelle

La commande grep imprime les lignes, appartenant à un ensemble de fichiers, qui contiennent un certain motif. Le motif recherché est donné dans la ligne de commande sous la forme d'un argument représentant une expression rationnelle. La commande igrep doit elle aussi reconnaître le langage associé à une expression rationnelle pour effectuer la recherche du motif.

Pour toute expression rationnelle, il est existe un unique (au nom des états près) automate fini déterministe minimal reconnaissant le langage associé. La construction d'un tel automate passe par trois phases:
  1. construction de l'arbre de syntaxe abstraite correspondant à l'expression rationnelle ;
  2. construction d'un automate fini déterministe à partir de cet arbre ;
  3. minimisation de l'automate déterministe ;

  Construction de l'arbre correspondant à l'expression

La grammaire des expressions rationnelles utilisées par la commande igrep est donnée Fig. 1. C'est une version légérement simplifiée de celle utilisée par grep. La construction de l'arbre de syntaxe abstraite à partir d'une expression se fait par une analyse récursive descendante, dont le principe est illustré Fig 2 pour une grammaire simplifiée. 
expression ::= expression-concatenation '|' expression | expression-concatenation
expression-concatenation ::= expression-repetition expression-concatenation |
                             expression-repetition
expression-repetition ::= expression-simple '*' | expression-simple
expression-simple ::= '(' expression ')' | car-non-speciaux | intervalle
car-non-speciaux ::= tout caractere sauf '|', '*', '[', ']', '.' |
                     '\|' | '\*' | '\[' | '\]' | '\.'
intervalle ::= '.' | '[' liste ']' | '[^' liste ']' | '[' liste '-]' | '[^' liste '-]'
liste ::= non-moins liste1 
liste1 ::= non-fermant liste1
non-moins ::= tout caractere sauf '-'
non-fermant ::= tout caractere sauf ']'

Figure 1 : Grammaire des expressions rationnelles de igrep


Figure 2 : Construction de l'arbre

  Construction de l'automate déterministe

Les algorithmes présentés dans la suite fonctionnent sur l'arbre de syntaxe abstraite construit précédemment, auquel on a ajouté un noeud racine (root) ayant pour fils droit un symbole de fin n'appartenant pas à l'alphabet de départ (voir Fig. 2), et pour fils gauche l'ast originel. Pour construire un automate déterministe à partir de cet arbre, il faut calculer pour chaque noeud n les trois ensembles premier(n), dernier(n), suivant(n), et la fonction nul(n) définis à la figure Fig. 3. Ces ensembles et cette fonction peuvent se calculer en réalisant un parcours de l'arbre en profondeur d'abord.
Noeud n premier(n) dernier(n) nul(n)
n est une feuille Ø Ø True
étiquettée e      
n est une feuille i i False
étiquettée i      
premier(c1) È premier(c2) dernier(c1) È dernier(c2) nul(c1) ou nul(c2)
si nul(c1) alors
premier(c1) È premier(c2)
sinon premier(c1)
si nul(c2) alors
dernier(c1) È dernier(c2)
sinon dernier(c2)
nul(c1) and nul(c2)
premier(c1) dernier(c1) True

Construction de la fonction suivant : Soit n un noeud de l'arbre,
  1. si n est un noeud de concaténation avec c1 pour fils droit et c2 pour fils gauche, et si i appartient à dernier(c1), alors tous les éléments de premier(c2) sont dans suivant(i);
  2. si n est un noeud de répétition, et si i appartient à dernier(n), alors tous les éléments de premier(n) sont dans suivant(i);

Figure 3 : Définition des fonctions premier, dernier, nul et suivant.

Pour obtenir l'automate déterministe à partir de ces ensembles, il reste à appliquer l'algorithme présenté Fig. 4. Cet algorithme construit un ensemble d'états Detat, chaque état représentant un ensemble de noeuds de l'arbre, et une table de transition Dtran, représentant les transitions de l'automate. Ainsi, si Dtran[T, a] = U, alors il y a une transition dans l'automate de l'état T à l'état U étiquettée par la lettre a. Les états de Detat sont marqués pour indiquer qu'ils n'ont pas encore été examinés. L'état initial de l'automate est premier(root), les états finaux sont tous les états contenant le noeud représentant le symbole de fin.
Initialement, Detat contient un seul état non marqué constitué des noeuds de premier(root).

Tant que il reste un état T non marqué dans Detat faire
Figure 4 : Construction de l'automate déterministe.

  Minimisation de l'automate

La minimisation d'un automate déterministe M s'effectue en partitionnant l'ensemble de ses états. Le calcul de cette partition Pfinale se fait en appliquant itérativement l'algorithme de la figure 5 sur la partition courante P. Chaque application de cet algorithme à P calcule une nouvelle partition Pnew, et, lorsque Pnew = P, on a trouvé la partition finale Pfinale = Pnew. Si Pnew ¹ P, on réitère l'algorithme de la figure 5 en prenant P = Pnew. Initialement, la partition P comporte deux groupes, le groupe des états acceptants (finaux), et les états non-acceptants.
Pour chaque groupe G de P faire
Figure 5 : Algorithme de partitionnement d'une partition P.

Chaque groupe d'états de Pfinale représente en fait un état de l'automate minimal M'. Pour calculer les transitions de l'automate minimal, on choisit pour chaque groupe de Pfinale un état représentant. Les états de l'automate minimal seront les états représentants. Soit s un état représentant, et supposons qu'il y a une transition par la lettre a dans l'automate non minimal de s vers t. Soit r le représentant du groupe de t, alors on a une transition dans l'automate minimal de s vers r par la lettre a. L'état initial de M' sera le représentant du groupe contenant l'état initial de M, ses états finaux seront les représentants des groupes qui contiennent un état final de M. Il reste à supprimer les états morts (bouclant sur eux-mêmes pour toute lettre) non finaux, et les états non-atteignables depuis l'état initial.

  Implémentation de la commande igrep

La commande igrep a la syntaxe suivante: 
igrep [-z] expression-rationnelle [-f liste-de-fichiers]
La grammaire des expressions rationnelles est celle présentée précédemment. Sans l'option -f, la commande igrep effectue la recherche des motifs dans les fichiers indexés par la commande stfsindex. La liste de ces fichiers se trouve dans le fichier $HOME/.stfs.filenames.igrep utilise alors l'index pour optimiser sa recherche dans l'ensemble des fichiers indexés. Si l'option -f est présente, igrep se comporte comme la commande grep, c'est-à-dire qu'elle parcourt les fichiers passés en paramètre en affichant les lignes qui contiennent un mot du langage de l'expression rationnelle. Si il n'y a aucun fichier dans liste-de-fichiers, igrep lit sur son entrée standard. Si l'option -z est présente, les fichiers compressés ou codés sont décompressés/décodés. Les utilitaires de décompression utilisés sont uncompress et gunzip. L'utilitaire de décodage considéré est uudecode.

Ce document a été traduit de LATEX par HEVEA.