Existe-t-il de «petites» machines capables de faire correspondre efficacement les expressions régulières?

Il est bien connu qu'une expression régulière peut être reconnue par un automate fini non déterministe de taille proportionnelle à l'expression régulière, ou par une FA déterministe qui est potentiellement exponentiellement plus grande. De plus, étant donné une chaîne et une expression régulière , la NFA peut tester l'appartenance en temps proportionnel àet le DFA peuvent tester l'adhésion en temps proportionnel à. Le ralentissement de la NFA découle du fait que nous devons essentiellement suivre les ensembles d'états possibles dans lesquels l'automate pourrait se trouver, et l'explosion exponentielle de la DFA découle du fait que ses états sont des éléments du jeu de pouvoirs des États de la NFA.$s$$r$$|s| \cdot |r|$$|s|$

Est-il possible de reconnaître efficacement (c'est-à-dire en temps meilleur que , et en espace mieux que ), si nous permettons d'utiliser des machines plus puissantes que les automates finis? (Par exemple, y a-t-il des gains de concision à reconnaître des langages réguliers avec des automates à refoulement ou des machines de comptage?)$O(|r| \cdot |s|)$$O(2^{|r|})$

Il est assez facile d'échanger du temps contre de l'espace, comme suit.

Convertissez l'expression régulière en NFA - pour plus de concret dans la comparaison des algorithmes, nous supposerons que est le nombre d'états NFA, de sorte que votre temps lié à la simulation directe du NFA soit valide et votre espace lié à l'exécution du DFA converti est également valide chaque fois que vous travaillez dans une RAM qui peut traiter autant de mémoire.$r$$O(rs)$$O(2^r)$

Maintenant, partitionnez (arbitrairement) les états du NFA en sous-ensembles d'au plus états chacun. Dans chaque sous-ensemble , nous pouvons indexer les sous-ensembles de par des nombres de à .$k$$S_i$$\lceil r/k\rceil$$S_i$$A_i$$S_i$$0$$2^{\lceil r/k\rceil}-1$

Construisez une table où et sont compris entre 0 et , est un symbole d'entrée et est (l'indice numérique de) un sous-ensemble de . La valeur stockée dans le tableau est (l'index numérique de) un sous-ensemble de : un état est dans si et seulement si appartient à et il y a un état dans qui transite à sur le symbole d'entrée .$T[i,j,c,A_i]$$i$$j$$k-1$$c$$A_i$$S_i$$S_j$$y$$T[i,j,c,A_i]$$y$$S_j$$A_i$$y$$c$

Pour simuler le NFA, maintenez indices, un pour chaque , en spécifiant le sous-ensemble des états dans qui peuvent être atteints par un préfixe de l'entrée. Pour chaque symbole d'entrée , utilisez les tableaux pour rechercher, pour chaque paire , l'ensemble des états dans qui peuvent être atteints à partir d'un état dans par une transition sur , puis utilisez un binaire au niveau du bit ou une opération sur les indices numériques de ces ensembles d'états pour les combiner en un seul sous-ensemble d'états de . Ainsi, chaque étape de la simulation prend le temps , et le temps total pour la simulation est$k$$S_i$$A_i$$S_i$$c$$i,j$$S_j$$A_i$$c$$S_j$$O(k^2)$$O(sk^2)$ .

L'espace requis est l'espace pour toutes les tables, qui est . L'analyse de temps et d'espace est valide sur toute RAM qui peut traiter autant de mémoire et qui peut effectuer des opérations binaires sur des mots suffisamment grands pour traiter cette quantité de mémoire.$O(k^2 2^{r/k})$

Le compromis temps-espace que vous obtenez ne correspond pas parfaitement à la simulation NFA, en raison de la dépendance quadratique de . Mais alors, je suis sceptique sur le fait que soit le bon moment pour la simulation NFA: comment simuler une seule étape de la NFA plus rapidement que de regarder toutes les transitions (éventuellement quadratiques) autorisées à partir d'un système actuellement actif état à un autre état? Cela ne devrait-il pas être ?$k$$O(rs)$$O(r^2 s)$

Dans tous les cas, en laissant varier, vous pouvez obtenir des limites de temps sur un continuum entre les limites DFA et NFA, avec moins d'espace que le DFA.$k$

Ce n'est pas une réponse, mais trop long pour un commentaire. J'essaie d'expliquer pourquoi la question, telle qu'elle est posée, peut être difficile à comprendre.

Il existe deux façons de définir la complexité de calcul pour un dispositif X .

La première et la plus naturelle des voies est intrinsèque . Il faut dire comment le périphérique X utilise l'entrée, afin que nous puissions voir plus tard comment la taille n de l'entrée affecte le temps d'exécution du périphérique. Il faut aussi dire ce qui compte comme une opération (ou étape ). Ensuite, nous laissons simplement l'appareil fonctionner sur les opérations d'entrée et de comptage.

Le second est extrinsèque . Nous définissons la complexité de calcul pour un autre appareil Y et nous programmons Y agir comme simulateur pour X . Puisqu'il peut y avoir plusieurs façons pour Y de simuler X , nous devons ajouter que nous sommes censés utiliser la meilleure. Permettez-moi de dire la même chose avec d'autres mots: Nous disons que X prend du temps sur une entrée de taille n s'il existe un simulateur de X implémenté sur la machine Y qui prend du temps .$O(f(n))$$f(n)$

Par exemple, une définition intrinsèque de NFA indique qu'il faut n étapes pour traiter une chaîne de longueur n ; une définition extrinsèque qui utilise une machine RAM comme périphérique Y indique que la borne supérieure la plus connue est probablement la réponse de David Eppstein. (Sinon, il serait étrange que (1) la meilleure mise en œuvre pratique indiquée dans l'autre réponse n'utilise pas la meilleure alternative et (2) personne n'a indiqué ici une meilleure alternative.) Notez également qu'à proprement parler, votre appareil X est l'expression régulière , mais comme le NFA a la même taille, il est sûr de le considérer comme étant le périphérique X que vous regardez.

Maintenant, lorsque vous utilisez le deuxième type de définition, il est peu logique de demander comment la restriction des fonctionnalités du périphérique X affecte le temps d'exécution. Il est cependant logique de se demander comment la restriction des fonctionnalités de l'appareil Y affecte la durée de fonctionnement. De toute évidence, autoriser des machines plus puissantes Y pourrait nous permettre de simuler X plus rapidement. Donc, si nous supposons l'une des machines les plus puissantes qui pourraient être implémentées (cela exclut les machines non déterministes, par exemple) et que nous trouvions une borne inférieure , alors nous savons qu'aucune machine moins puissante ne pourrait faire mieux.$\Omega(f(n))$

Donc, dans un sens, la meilleure réponse que vous pourriez espérer est une preuve dans quelque chose comme le modèle de sonde cellulaire que la simulation d'un NFA a besoin d'un certain temps. (Notez que si vous prenez en compte la conversion NFA en DFA, vous avez besoin de temps pour écrire le gros DFA, donc la mémoire n'est pas le seul problème.)

Même si vous croyez qu'il n'y a rien de nouveau ou d'ancien à apprendre sur la correspondance des expressions régulières, consultez l'un des plus beaux articles que j'ai rencontrés depuis longtemps: une pièce sur les expressions régulières de S Fischer, F Huch et T Wilke, ICFP 2010.

(Le MMT Chakravarty mérite le mérite d'avoir recommandé ce document.)

EDIT: La raison pour laquelle cet article est pertinent est qu'il décrit une nouvelle technique (basée sur celle de Glushkov des années 60) qui évite de construire le NFA complet (sans parler du DFA) correspondant au RE. Ce qui est fait à la place ressemble à l'exécution d'un algorithme de marquage similaire à celui bien connu pour décider de l'acceptation d'un mot par un NFA sur l'arbre de syntaxe du RE. Les mesures de performances suggèrent que cela est compétitif, même avec la bibliothèque re2 récemment publiée par google.

Jetez un œil à cet article de Russ Cox. Il décrit une approche basée sur NFA, d'abord employée par Ken Thompson, par laquelle une chaîne d'entrée s peut être mise en correspondance avec une expression régulière r dans le temps O (| s |. C ) et l'espace O (| r |. D ), où c et d sont des constantes de la limite supérieure. L'article détaille également une implémentation C de la technique.