Quelle est la complexité temporelle des algorithmes Regex moyens?
Je ne suis pas nouveau à utiliser des expressions régulières, et je comprends le base théorie ils sont basés sur -- machines d'état finis.
Je ne suis pas très bon en analyse algorithmique et je ne comprends pas comment un regex se compare, par exemple, à une recherche linéaire de base. Je demande parce qu'à la surface, ça ressemble à une recherche linéaire. (Si le regex est simple.)
Où puis-je aller pour en savoir plus sur la mise en œuvre d'un moteur regex?
3 réponses
C'est l'un des plus populaires décrit: L'Appariement Régulier Des Expressions Peut Être Simple Et Rapide . Lancer 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) Temps/espace de construction (où m = Taille de l'expression régulière).
connaissez-vous le terme Automates Finis Déterministes/Non Déterministes?
Réel expressions régulières (quand je dis réel je fais référence à ces regex qui reconnaissent Langues Régulières, et non le regex que presque tous les langages de programmation incluent avec des références arrières, etc) peut être converti en DFA / NFA et les deux peuvent être mis en œuvre de manière mécanique dans un langage de programmation (un NFA peut être converti dans un DFA)
Ce que vous avez à faire c'est:
- Trouver un moyen de convertir une expression régulière en un automate
- implémenter la reconnaissance de l'automate dans le langage de programmation de votre préférence
de cette façon, avec un regex, vous pouvez le convertir en DFA et l'Exécuter pour voir s'il correspond ou non à un texte spécifié.
ceci peut être implémenté dans O(n), parce que DFA ne va pas en arrière (comme un Machine De Turing), donc ça correspond à la ficelle ou pas. Cela suppose que vous ne prendrez pas en compte les matchs qui se chevauchent, sinon vous devrez revenir en arrière et recommencer l'appariement...
l'expression régulière classique peut être mise en œuvre d'une manière qui est rapide dans la pratique mais qui a vraiment un mauvais comportement dans le pire des cas (la norme DFA) ou d'une manière qui a garanti un comportement raisonnable dans le pire des cas (le garder comme NFA). Le Dfa standard peut être étendu pour prendre en charge beaucoup de caractères et de drapeaux supplémentaires, qui utilisent le fait qu'il s'agit essentiellement d'une recherche de suivi.
les exemples de l'approche standard sont omniprésents (p. ex. intégrée à Perl). Y est un exemple qui prétend avoir un bon comportement du pire des cas à http://code.google.com/p/re2/ - en fait, c'est même mieux que je m'y attendais dans le pire des cas, donc ils ont peut-être trouvé un ou deux tours de plus.
si vous êtes intéressé par ceci, ou si vous vous souciez d'écrire des programmes qui peuvent être faits pour verrouiller des entrées pathologiques données solides, lisez http://swtch.com/~rsc/regexp/regexp1.html.