Clone egrep — Moteur d'Expressions Régulières Étendues

Clone partiel de la commande egrep pour la recherche de motifs dans des fichiers textuels avec support des expressions régulières étendues (ERE). Le projet compare deux approches algorithmiques : la méthode Aho-Ullman (chaîne de transformation regex → automate) et l'algorithme Knuth-Morris-Pratt (KMP) pour les motifs exacts. Les résultats sont validés par correspondance avec la commande egrep native sur le corpus Project Gutenberg.

Méthode Aho-Ullman — chaîne de transformation

La méthode Aho-Ullman transforme une expression régulière en automate déterministe minimisé en quatre étapes successives :

1. Arbre de syntaxe abstraite

L'expression régulière est parsée en un arbre où les nœuds internes représentent les opérateurs (. concaténation, | alternation, * étoile de Kleene, +) et les feuilles les caractères. Des méthodes auxiliaires (getLeftTree, getRightTree, getLeaf) permettent de parcourir l'arbre récursivement.

2. NDFA avec transitions epsilon

Chaque nœud de l'arbre est transformé en un sous-automate selon des règles structurelles :

• Symbole simple — un état initial, un état final, une transition unique (ou une transition par caractère de l'alphabet pour .).
• Concaténation — l'état final du sous-automate gauche est relié par une transition epsilon à l'état initial du sous-automate droit.
• Alternation — un nouvel état initial avec deux transitions epsilon vers les deux branches, et un nouvel état final recevant les transitions epsilon des deux états finaux.
• Étoile de Kleene — boucle epsilon permettant zéro ou plusieurs répétitions, avec transition directe vers l'état final.
• Opérateur + — identique à * mais impose au moins un parcours avant d'entrer dans la boucle.

3. Déterminisation — construction par sous-ensembles

La conversion NDFA → DFA utilise l'algorithme de construction par sous-ensembles (powerset construction). Chaque état du DFA représente un ensemble d'états du NDFA. La fermeture epsilon d'un ensemble d'états est d'abord calculée, puis pour chaque symbole de l'alphabet les transitions sont agrégées. Un état DFA est acceptant si l'un des états NDFA qu'il contient est acceptant.

4. Minimisation par raffinement de partition

Le DFA est minimisé en fusionnant les états équivalents. Les étapes sont :

1. Suppression des états inaccessibles depuis l'état initial.
2. Partition initiale en deux groupes : états acceptants et non-acceptants. Raffinement itératif jusqu'à stabilisation — deux états sont équivalents s'ils se comportent identiquement pour tous les symboles.
3. Construction du DFA minimisé : chaque partition devient un état unique, les transitions sont ajustées vers les représentants de partition.

Recherche dans le texte

Pour chaque ligne du corpus, toutes les sous-chaînes possibles sont testées contre le DFA minimisé. Une sous-chaîne est acceptée si le parcours du DFA caractère par caractère aboutit à un état acceptant. Les correspondances sont affichées avec mise en surbrillance ANSI (vert/rouge).

La complexité de la construction du DFA peut atteindre O(2^|r|) pour des expressions régulières complexes avec opérateurs imbriqués, mais la recherche dans le texte est ensuite linéaire en la taille du corpus.

Algorithme Knuth-Morris-Pratt (KMP)

KMP cible la recherche de motifs exacts (les opérateurs *, +, | sont traités comme des caractères littéraux). L'algorithme se décompose en deux phases :

• Prétraitement — construction de la table LPS (Longest Prefix Suffix) en O(m) où m est la longueur du motif. La table permet d'éviter de réexaminer les caractères déjà vérifiés lors d'un échec de correspondance.
• Recherche — parcours du texte en O(n) où n est la longueur du texte, en sautant les parties inutiles grâce à la table LPS.

Complexité totale : O(n + m).

Comparaison des approches

Les deux méthodes ont été benchmarkées sur le fichier 56667-0.txt du Project Gutenberg avec des motifs de complexité croissante :

• KMP est optimal pour les motifs exacts (linéaire, table LPS légère), mais ne supporte pas les expressions régulières avec opérateurs.
• Aho-Ullman prend en charge toute la grammaire ERE et la recherche post-construction est rapide, mais le coût de construction du DFA croît exponentiellement avec la complexité de la regex.

Une approche hybride — DFA pour les parties complexes de la regex et KMP pour les sous-parties exactes — constituerait une optimisation naturelle.