Quelle est la complexité temporelle des algorithmes Regex moyens ?

Question

Ce n'est pas la première fois que j'utilise des expressions régulières, et je comprends le concept de base théorie sur laquelle ils sont basés les machines à états finis.

Je ne suis pas très doué pour l'analyse algorithmique et je ne comprends pas comment une regex se compare à une recherche linéaire de base. Je pose la question parce qu'à première vue, cela semble être une recherche linéaire dans un tableau. (Si la regex est simple.)

Où pourrais-je aller pour en savoir plus sur l'implémentation d'un moteur regex ?

Answer 1

Il s'agit de l'un des schémas les plus populaires : La correspondance par expression régulière peut être simple et rapide . L'exécution d'une expression régulière compilée par DFA contre une chaîne est en effet O(n), mais peut nécessiter jusqu'à O(2^m) de temps/espace de construction (où m = taille de l'expression régulière).

Answer 2

Connaissez-vous le terme Automates finis déterministes/non-déterministes ?

Real les expressions régulières (quand je dis real Je me réfère à ces regex qui reconnaissent Langues régulières et non pas les regex que presque tous les langages de programmation incluent avec des rétro-références, etc.) peut être converti en un DFA/NFA et les deux peuvent être implémentés de manière mécanique dans un langage de programmation (un NFA peut être converti en un DFA).

Ce que tu dois faire, c'est :

1. Trouver un moyen de convertir une regex en un automate
2. Implémentez la reconnaissance de l'automate dans le langage de programmation de votre choix.

Ainsi, à partir d'une expression rationnelle, vous pouvez la convertir en un DFA et l'exécuter pour voir si elle correspond ou non à un texte donné.

Cela peut être mis en œuvre dans O(n) parce que les DFA ne reviennent pas en arrière (comme le ferait une carte de crédit). Machine de Turing ), pour qu'il corresponde ou non à la chaîne de caractères. Cela suppose que vous ne prenez pas en compte les correspondances qui se chevauchent, sinon vous devrez revenir en arrière et recommencer la correspondance...

Answer 3

L'expression régulière classique peut être implémentée d'une manière qui est rapide en pratique, mais qui a un très mauvais comportement dans le pire des cas (le DFA standard) ou d'une manière qui garantit un comportement raisonnable dans le pire des cas (en la conservant comme un NFA). La DFA standard peut être étendue pour supporter de nombreux caractères et drapeaux de correspondance supplémentaires, qui utilisent le fait qu'il s'agit fondamentalement d'une recherche par retour en arrière.

Les exemples de l'approche standard sont partout (par exemple, intégrés à Perl). Il y a un exemple qui revendique un bon comportement dans le pire des cas à http://code.google.com/p/re2/ - En fait, il est même meilleur que ce à quoi je m'attendais dans le pire des cas, donc ils ont peut-être trouvé une ou deux astuces supplémentaires.

Si vous êtes un tant soit peu intéressé par ce sujet, ou si vous vous souciez d'écrire des programmes qui peuvent être amenés à se verrouiller de manière solide en cas d'entrées pathologiques, lisez la rubrique http://swtch.com/~rsc/regexp/regexp1.html .