Un analyseur Earley peut-il être transformé en un analyseur flou similaire au Levenshtein Automata Algo pour DFA?

10

Il existe un moyen d'effectuer une analyse floue (accepte les chaînes même avec des fautes de frappe à une certaine distance d'édition), avec un DFA et un automate Levenshtein construit au moment de l'exécution du mot d'entrée. Peut-on faire quelque chose de similaire avec un analyseur Earley? J'ai du mal à comprendre l'algorithme, sans parler de répondre à cette question.

EnjoysMath
la source
1
Eh bien, les PDA sont fermés à de nombreuses opérations avec NFA, cela devrait donc être possible en principe. Adapter Earley semble être un exercice par cœur, car nous sommes autorisés à utiliser des compteurs dans les articles. Suis-je en train de manquer quelque chose?
Raphael
@Raphael Oui C'est l'idée générale. Ma réponse est plus longue, car il est difficile d'évaluer ce que les utilisateurs savent ou ne savent pas.
babou
plz citer un refn / sketch defn pour "Levenshtein Automata". connaissez-vous celui qui pourrait se qualifier, mais de qui parlez-vous?
vzn

Réponses:

8

La réponse est oui. Cependant, je ne ferais pas cela avec un analyseur Earley car il y en a d'autres plus simples avec les mêmes capacités.

Fondamentalement, l'analyseur Earley appartient à une famille d'analyseurs généraux sans contexte, qui produit toutes les analyses possibles pour une chaîne donnée, lorsque la grammaire est ambiguë.

Il y a deux façons (au moins) de comprendre ces analyseurs:

  • comme interprétation de programmation dynamique d'un automate pushdown correspondant à la grammaire de la chaîne d'entrée;

  • comme la construction de l'intersection de la grammaire avec un automate à états finis.

Lors de l'analyse d'une chaîne unique, l'automate à états finis à considérer est un automate linéaire qui ne reconnaît que la chaîne à analyser, un symbole à la fois (le nombre d'états est ). Si vous appliquez la construction croisée d'un FA et d'un CF garmmar (Bar Hillel, Perlis, Shamir 1961), vous obtenez une nouvelle grammaire CF qui est une nouvelle grammaire qui génère . Le point intéressant généralement négligé est que conserve les arbres d'analyse utilisés par , jusqu'à un renommage non-terminal (en raison d'un produit croisé).| w | + 1 A G F L ( A ) L ( G ) F Gw|w|+1AGFL(A)L(G)FG

Ainsi, si le FA génère uniquement votre chaîne d'entrée, la grammaire ne générera que cette chaîne (si elle est dans , sinon elle génère la langue vide ). De plus, il le génère avec tous les arbres d'analyse que pourrait utiliser pour le générer.F L ( G ) GAFL(G)G

Cette grammaire est ce qu'on appelle généralement une forêt d'analyse partagée , et tous les algorithmes d'analyse CF généraux sont une version plus ou moins optimisée de la construction de produits croisés, qu'ils soient CYK, Earley, LR ou LL généralisés, ou autres. Donc, tout ce que je dis s'applique à eux aussi.F

Mais, comme vous le voyez, cela se généralise pour analyser un ensemble régulier, si quelqu'un est intéressé à le faire.

Telle est précisément votre question. Vous avez une chaîne . Vous voulez l'analyser jusqu'à certaines variations définies par un transducteur à états finis, qui dans votre cas est un transducteur qui produit toutes les chaînes à l'intérieur d'une certaine distance d'édition de Levenshtein de (mais l'origine du transducteur est immatérielle). L'ensemble de ces chaînes est un ensemble régulier qui peut être défini par un FA, avec une transition pondérée qui peut calculer la distance d'édition de chaque chaîne.www

Si vous effectuez le produit croisé avec votre grammaire , vous obtenez une grammaire de forêt d'analyse partagée qui génère toutes les chaînes de l'intersection. De plus, vous obtenez les pondérations de certaines règles afin de pouvoir calculer la distance d'édition de chacune des chaînes acceptées.FGF

Si cela est souhaitable, cela peut être utilisé pour ne garder que les cordes avec une distance minimale.

Cependant, cela peut être un peu amélioré car la composition avec des machines à états finis est associative.

Si vous utilisez toujours le même transducteur à états finis, comme c'est le cas dans votre question, la bonne façon de procéder est de composer la Grammaire et le transducteur (ici l'automate Levenshtein), indépendamment de la chaîne d'entrée. Cela vous donne une grammaire pondérée que vous pouvez utiliser pour analyser la chaîne d'entrée . Le problème est que l'analyse de la construction d'intersection brutale vous donne des chaînes à n'importe quelle distance de Levenshtein, c'est-à-dire .w Σ GwΣ

Il serait facile d'élaguer cette construction pour obtenir le même résultat qu'auparavant, mais la meilleure façon est une construction d'intersection plus contrôlée, telle que l'organisation de programmation dynamique utilisée par la plupart des analyseurs dans la littérature, y compris Earley, et l'utiliser pour éviter de générer règle inutile en calculant les distances et en abandonnant tout chemin de calcul lorsqu'il dépasse le seuil souhaité. La programmation dynamique peut également être utilisée pour calculer directement la forêt d'analyse (ou l'arbre d'analyse) pour la chaîne qui a la distance la plus courte à l'entrée.

babou
la source
pense que c'est utile mais peut-être aussi "lire trop" dans la question, donc dire quelque chose comme "c'est précisément votre question" ne peut pas vraiment être exact. vous avez pris une question assez vague non strictement formalisée, et (tenté de?) la formaliser vous-même. il y a probablement plus d'une façon de formaliser l'idée quelque peu vague originale. pense qu'il pourrait être utile de définir soigneusement ce que font les constructions Levenshtein DFA (il y en a quelques-unes connues / étudiées, mais de lesquelles parlons-nous?), puis d'expliquer comment ce concept pourrait être généralisé aux LFC.
vzn
1
Je donne en fait différentes formalisations qui se complètent. Il y a des subtilités que je n'ai pas abordées, comme l'utilisation exacte des poids dans le processus, qui dépend du résultat précis que vous souhaitez obtenir. Mon but n'est pas seulement de donner une réponse qui a peu d'intérêt à mon avis, mais de donner une compréhension plus large du problème. Le choix de la distance d'édition utilisée est sans importance, il fonctionne pour tout ce qui peut être exprimé avec un transducteur à état fini pondéré.
babou