Comment fonctionnent les expressions régulières?

Disons que vous avez un document avec un essai écrit. Vous souhaitez analyser cet essai pour sélectionner uniquement certains mots. Cool.

L'utilisation d'une expression régulière est-elle plus rapide que l'analyse du fichier ligne par ligne et mot par mot à la recherche d'une correspondance? Si oui, comment ça marche? Comment pouvez-vous aller plus vite que de regarder chaque mot?

Comment ça marche?

Jetez un œil à la théorie des automates

En bref, chaque expression régulière a un automate fini équivalent et peut être compilée et optimisée en un automate fini. Les algorithmes impliqués peuvent être trouvés dans de nombreux livres de compilation. Ces algorithmes sont utilisés par des programmes Unix comme awk et grep.

Cependant, la plupart des langages de programmation modernes (Perl, Python, Ruby, Java (et langages basés sur JVM), C #) n'utilisent pas cette approche. Ils utilisent une approche de retour en arrière récursif, qui compile une expression régulière dans un arbre ou une séquence de constructions représentant divers sous-morceaux de l'expression régulière. La plupart des syntaxes "d'expression régulière" modernes offrent des références arrières qui sont en dehors du groupe des langages réguliers (elles n'ont aucune représentation dans les automates finis), qui sont trivialement implémentables dans une approche de retour arrière récursif.

L'optimisation donne généralement une machine d'état plus efficace. Par exemple: considérez aaaab | aaaac | aaaad, un programmeur normal peut obtenir une implémentation de recherche simple mais moins efficace (en comparant trois chaînes séparément) directement en dix minutes; mais en réalisant que cela équivaut à aaaa [bcd], une meilleure recherche peut être effectuée en recherchant les quatre premiers «a» puis en testant le 5ème caractère par rapport à [b, c, d]. Le processus d'optimisation était l'un de mes travaux à domicile pour le compilateur il y a de nombreuses années, donc je suppose qu'il se trouve également dans la plupart des moteurs d'expression régulière modernes.

D'un autre côté, les machines à états ont un certain avantage lorsqu'elles acceptent des chaînes car elles utilisent plus d'espace par rapport à une "implémentation triviale". Considérons un programme pour annuler l'échappement des citations sur les chaînes SQL, c'est-à-dire: 1) commence et se termine par des guillemets simples; 2) les guillemets simples sont échappés par deux guillemets simples consécutifs. Donc: l'entrée ['a' ''] devrait donner la sortie [a ']. Avec une machine à états, les guillemets simples consécutifs sont gérés par deux états. Ces deux états servent à se souvenir de l'historique d'entrée de telle sorte que chaque caractère d'entrée soit traité exactement une seule fois, comme illustré ci-dessous:

...
S1->'->S2
S1->*->S1, output *, * can be any other character 
S2->'->S1, output '
S2->*->END, end the current string

Donc, à mon avis, l'expression régulière peut être plus lente dans certains cas triviaux, mais généralement plus rapide qu'un algorithme de recherche conçu manuellement, étant donné que l'optimisation ne peut pas être effectuée de manière fiable par l'homme.

(Même dans des cas triviaux comme la recherche d'une chaîne, un moteur intelligent peut reconnaître le chemin unique dans la carte d'état et réduire cette partie à une simple comparaison de chaînes et éviter de gérer les états.)

Un moteur particulier d'un framework / bibliothèque peut être lent car le moteur fait un tas d'autres choses dont un programmeur n'a généralement pas besoin. Exemple: la classe Regex dans .NET crée un tas d'objets dont Match, Groupes et Captures.

Les expressions régulières sont rapides car vous avez des ordinateurs rapides.

Dans les années 1980, lorsque 1 MIPS était un ordinateur rapide, les expressions régulières étaient un sujet de préoccupation, de préoccupation et de recherche assez important car elles étaient lentes et laides et nécessitaient beaucoup de calculs. Un développement intelligent d'algorithmes a suivi et a aidé - mais à toutes fins pratiques ces jours-ci, vous voyez le miracle de machines rapides tapissant les fissures.

Pourquoi pensez-vous qu'ils sont plus rapides que de rechercher le document?

Il y a quelques astuces que vous pouvez faire, par exemple. si vous recherchez un mot de 10 lettres commençant par A et se terminant par B, alors si vous trouvez un A et que le caractère 9 se trouvant plus loin n'est pas B, vous pouvez en ignorer. voir algorithme Knuth – Morris – Pratt

Qu'est-ce qui rend une expression régulière rapide?

En fait, ils ne le sont pas. Pas autant. C'est juste qu'ils ne sont pas assez lents pour que la plupart d'entre nous le remarquent. Retour dans les «vieux jours lents, c'était beaucoup plus visible.

Ils ne sont pas non plus le bon outil pour chaque travail - le marteau .

Les RegEx sont comparativement plus rapides à coder que vous pourriez écrire, car la plupart des bibliothèques sont le résultat de nombreux développeurs qui ont passé de nombreuses années à les optimiser pour obtenir les dernières performances possibles. Il est difficile pour une seule personne de reproduire cela dans son propre code de recherche.

Votre prémisse de base est fausse.

Les expressions régulières ne sont pas toujours plus rapides qu'une simple recherche. Tout dépend du contexte. Cela dépend de la complexité de l'expression, de la longueur du document recherché et de toute une série de facteurs.

Ce qui se passe, c'est que l'expression régulière sera compilée dans un simple analyseur (ce qui prend du temps). Ainsi, si le document est petit, ce temps supplémentaire l'emportera sur tout avantage. De plus, si l'expression est simple, l'expression régulière ne vous donnera aucun avantage.

Si l'expression est complexe et que le document est suffisamment volumineux, vous pouvez en retirer des avantages. Le fait que cela soit suffisamment important pour considérer les expressions régulières comme plus rapides dépendra beaucoup de l'effort que vous souhaitez consacrer à la recherche (les expressions régulières peuvent également avoir certaines optimisations qu'une bibliothèque pourrait fournir et auxquelles vous n'auriez pas pensé).

Ce que j'essaie de dire, c'est qu'il n'y a pas de réponse généralisée et globale. Si vous aviez une expression spécifique (et une taille de document connue), alors vous pourriez dire dériver une réponse oui / non pour savoir si l'expression sera plus rapide qu'une simple recherche (et pourquoi).

Le véritable avantage des expressions régulières est qu'une fois que vous comprenez comment les écrire, la possibilité d'exprimer une recherche complexe de manière concise. Puisqu'il s'agit d'un formulaire généralisé, vous pouvez ensuite créer des outils qui permettent des recherches d'une manière utile dans le cas général; elle est généralement au moins aussi rapide qu'une simple recherche (sur des documents de taille minimale; sur des documents plus petits, cela n'aurait pas d'importance car même si elle est plus lente, elle est quand même assez rapide).

Il est plausible que dans certaines langues de haut niveau (peut-être javascript), l'utilisation d'une bibliothèque regex implémentée dans un langage de bas niveau (peut-être C) soit plus rapide que l'écriture d'une logique d'analyseur dans le langage de haut niveau.

Plausible - je n'ai aucune idée si c'est vraiment le cas.