Complexité de la substitution Regex

Question

Je n’ai trouvé la réponse à cette question nulle part.Quelle est la complexité d’exécution d’une correspondance et d’une substitution Regex ?

Modifier:Je travaille en python.Mais j'aimerais connaître en général les langages/outils les plus populaires (Java, Perl, sed).

Answer 1

D'un point de vue purement théorique :

L'implémentation que je connais serait de construire un automate fini déterministe pour reconnaître l'expression régulière.Cela se fait en O(2^m), m étant la taille de l'expression régulière, en utilisant un algorithme standard.Une fois celui-ci construit, le passage d'une chaîne à travers celui-ci est linéaire dans la longueur de la chaîne - O(n), n étant la longueur de la chaîne.Un remplacement sur une correspondance trouvée dans la chaîne doit être à temps constant.

Donc dans l’ensemble, je suppose que O(2^m + n).

Answer 2

Autres informations théoriques d'intérêt possible.

Pour plus de clarté, supposons la définition standard d'une expression régulière

http://en.wikipedia.org/wiki/Regular_langue

de la théorie du langage formel.Pratiquement, cela signifie que le seul matériau de construction est des symboles d'alphabet, des opérateurs de concaténation, de l'alternance et de la fermeture de Kleene, ainsi que de l'unité et des constantes nulles (qui apparaissent pour des raisons théoriques en groupe).Généralement, c'est une bonne idée de ne pas surcharger ce terme malgré la pratique quotidienne des langues de script, ce qui conduit à des ambiguïtés.

Il y a une construction NFA qui résout le problème d'appariement pour une expression régulière R et un texte d'entrée T dans O (| R | | T |) Temps et O (| R |) Space, où | - | est la fonction de longueur.Cet algorithme a encore été amélioré par Myers

http://doi.acm.org/10.1145/128749.128755

à la complexité temporelle et spatiale O(|r| |t| / log |t|) en utilisant des listes de nœuds d'automates et le paradigme des Quatre Russes.Ce paradigme semble être nommé d'après quatre gars russes qui ont écrit un journal révolutionnaire qui n'est pas en ligne.Cependant, le paradigme est illustré dans ces notes de conférence de biologie informatique

http://lyle.smu.edu/~saad/courses/cse8354/lectures/lecture5.pdf

Je trouve hilarant de nommer un paradigme par le numéro et la nationalité des auteurs au lieu de leur nom de famille.

Le problème de correspondance pour les expressions régulières avec des références de rétro-traitants supplémentaires est NP-Complete, qui a été prouvé par Aho

http://portal.acm.org/citation.cfm?id=114877

par une réduction du problème de couverture de sommets qui est un problème NP-complet classique.

Pour faire correspondre les expressions régulières avec des références de manière déterministe, nous pourrions utiliser un retour en arrière (un peu comme le moteur Perl Regex) pour garder une trace des sous-mots possibles du texte d'entrée T qui peuvent être attribués aux variables en r.Il n'y a que des sous-mots o (| t | ^ 2) qui peuvent être affectés à n'importe quelle variable dans r.S'il y a n variables en r, alors il y a des affectations possibles (| t | ^ 2n).Une fois qu'une affectation de sous-chaînes aux variables est fixée, le problème se réduit à la correspondance de l'expression régulière de la plaine.Par conséquent, la complexité la pire des cas pour faire correspondre les expressions régulières avec des références est O (| t | ^ 2n).

Remarque cependant, les expressions régulières avec des dossiers ne sont pas encore des exploits complets.

Prenez, par exemple, le symbole "ne vous soucie pas" de tout autre opérateur.Il existe plusieurs algorithmes polynomiaux qui décident si un ensemble de modèles correspond à un texte d'entrée.Par exemple, Kucherov et Rusinowitch

http://dx.doi.org/10.1007/3-540-60044-2_46

définir un modèle comme un mot w_1@w_2@...@w_n où chaque w_i est un mot (pas une expression régulière) et "@" est un symbole "ne s'en soucie" de longueur variable qui n'est contenu dans aucun des w_i.Ils dérivent un algorithme O ((| T | + | P |) Log | P |) pour faire correspondre un ensemble de modèles P contre un texte d'entrée t, où | t | est la longueur du texte, et | p | est la longueur de tous les mots de P.

Il serait intéressant de savoir comment ces mesures de complexité se combinent et quelle est la mesure de complexité du problème d'appariement pour les expressions régulières avec des dossiers, "ne se soucient pas" et d'autres caractéristiques intéressantes des expressions régulières pratiques.

Hélas, je n'ai pas dit un mot sur Python...:)

Answer 3

Cela dépend de ce que vous définissez par regex.Si vous autorisez les opérateurs de concaténation, alternatifs et Kleene-star, le temps peut effectivement être O(m*n+m), où m est la taille d'une regex et n est la longueur de la chaîne.Pour ce faire, vous construisez un NFA (qui est linéaire en m), puis en le simulant en conservant l'ensemble des états dans lesquels vous vous trouvez et en le mettant à jour (dans O(m)) pour chaque lettre d'entrée.

Choses qui rendent l'analyse des regex difficile :

• parenthèses et références arrière :la capture est toujours acceptable avec l'algorithme susmentionné, même si cela augmenterait la complexité, ce qui pourrait donc être irréalisable.Les backreferences augmentent le pouvoir de reconnaissance de l'expression régulière, et sa difficulté est bien
• une perspective positive :n'est qu'un autre nom pour l'intersection, ce qui élève la complexité de l'algorithme susmentionné à O(m^2+n)
• anticipation négative :un désastre pour la construction de l'automate (O(2^m), éventuellement PSPACE-complet).Mais il devrait toujours être possible d'aborder avec l'algorithme dynamique quelque chose comme O(n^2*m)

Notez qu’avec une mise en œuvre concrète, les choses pourraient s’améliorer ou empirer.En règle générale, les fonctionnalités simples doivent être suffisamment rapides et sans ambiguïté (par ex.pas comme a*a*) les expressions régulières sont meilleures.

Answer 4

Pour approfondir la réponse de l'entreprise, pour la construction de l'automate, O(2^m) est le pire des cas, même si cela dépend vraiment de la forme de l'expression régulière (pour une expression très simple qui correspond à un mot, c'est en O( m), en utilisant par exemple le Algorithme de Knuth-Morris-Pratt).

Answer 5

Cela dépend de la mise en œuvre.Quelle langue/bibliothèque/classe ?Il existe peut-être un meilleur cas, mais il serait très spécifique au nombre de fonctionnalités de l'implémentation.

Answer 6

Vous pouvez échanger de l'espace contre de la vitesse en créant un automate fini non déterministe au lieu d'un DFA.Celui-ci peut être parcouru en temps linéaire.Bien sûr, dans le pire des cas, cela pourrait nécessiter un espace de O(2^m).Je m'attendrais à ce que le compromis en vaille la peine.

Answer 7

Si vous recherchez la correspondance et la substitution, cela implique un regroupement et des références arrière.

Voici un exemple Perl où le regroupement et les références arrière peuvent être utilisés pour résoudre un problème NP complet : http://perl.plover.com/NPC/NPC-3SAT.html

Ceci (couplé à quelques autres informations théoriques) signifie que l'utilisation d'expressions régulières pour la correspondance et la substitution est NP-complète.

Notez que ceci est différent de la définition formelle d'une expression régulière - qui n'a pas la notion de regroupement - et correspond en temps polynomial comme décrit par les autres réponses.