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

30

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.sr|s||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||s|)O(2|r|)

Neel Krishnaswami
la source
2
Lorsque vous dites que le "NFA peut tester l'adhésion dans le temps proportionnellement à ", vous voulez dire qu'une machine RAM (déterministe) qui simule le NFA de manière évidente prend tellement de temps? Ou existe-t-il une autre manière de définir le "temps d'exécution d'un NFA" qui ne se réfère pas à un autre modèle de calcul? (En dehors de la définition sensée mais pas très utile qui dit que le temps d'exécution de tout NFA pour la chaîne est .)|s||r|s|s|
Radu GRIGore
Oui, c'est la bonne interprétation de ma question.
Neel Krishnaswami
2
Ensuite, il me semble plus naturel de simplement demander ceci: existe-t-il un algorithme (sur une machine RAM) qui décide si une chaîne est dans le langage défini par l'expression régulière qui fonctionne dans temps et espace ? (Surtout si vous définissez le temps d'exécution d'un automate pushdown également en termes de machine RAM.)sro(|s||r|)o(2|r|)
Radu GRIGore
1
Je ne comprends pas exactement le problème. L'entrée est-elle une chaîne s et une expression régulière r, et le problème est de décider si s est dans le langage défini par l'expression régulière r?
Robin Kothari
@Robin: oui, c'est ça. J'aimerais savoir si vous pouvez faire correspondre les expressions régulières plus efficacement que les automates finis en utilisant plus de puissance de calcul, ou si des fonctionnalités supplémentaires (par exemple, pile, RAM) ne vous aident tout simplement pas.
Neel Krishnaswami

Réponses:

20

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.rO(rs)O(2r)

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 à .kSir/kSiAiSi02r/k1

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,Ai]ijk1cAiSiSjyT[i,j,c,Ai]ySjAiyc

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 estkSiAiSici,jSjAicSjO(k2)O(sk2) .

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(k22r/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 ?kO(rs)O(r2s)

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

David Eppstein
la source
Je pense que votre correction est correcte, et votre réponse répond à ma question posée. Cependant, la question que je voulais poser est de savoir quelle puissance de calcul supplémentaire aide. (Par exemple, avec un compteur, vous pouvez faire correspondre une chaîne dans l'espace O (1).) Si cela ne vous dérange pas, je vais laisser la question ouverte encore un peu pour voir si quelqu'un connaît la réponse à cette question ....ak
Neel Krishnaswami
@Neel: Si la solution de David est la meilleure qu'une machine RAM puisse faire, alors les piles, les compteurs, etc. n'aideront pas. (Mais, bien sûr, il n'a donné que des limites supérieures, pas des limites inférieures.)
Radu GRIGore
1
Pour autant que je sache, ma solution utilise une "puissance supplémentaire": elle est basée sur des recherches de table et des indices entiers, ce qui n'est pas disponible dans les modèles DFA ou NFA. Je ne comprends donc pas vraiment comment cela ne répond pas à cette partie de la question.
David Eppstein
Voici une autre façon de paramétrer cela. Supposons que nous soyons sur une machine RAM avec une largeur de mot , où . Ensuite, la simulation NFA prend le temps et l' espace . La simulation DFA n'est pas possible si (pas assez d'espace disponible). La construction de cette réponse définit et prend temps et utilise tout l'espace disponible (c'est-à-dire quelque chose au voisinage de l' espace ). Il exploite essentiellement le parallélisme des bits disponible dans une machine RAM pour effectuer la simulation NFA plus rapidement. wwlgrO(sr2)O(r/w)rwkr/wO(sr2/w2)2w
DW
4

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.Ω(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.)

Radu GRIGore
la source
4

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.

Kai
la source
Un beau papier à lire !!
Hsien-Chih Chang 張顯 之
1

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.


la source
2
Je ne suis pas convaincu que ce soit une description précise de l'article. Il semble que la création du DFA à partir du NFA se fasse selon les besoins et la mise en cache des résultats. Mais la taille du cache pourrait être exponentielle dans r.
David Eppstein