6
votes

Réduire une chaîne à l'aide de règles de type grammaire

J'essaie de trouver un algorithme DP approprié pour simplifier une chaîne. Par exemple, j'ai une chaîne A B A B et une liste de règles


  A B -> B  
  A B -> C  
  B a -> A  
  C C -> B  


 Le but est d'obtenir tous les caractères simples pouvant être reçus de la chaîne donnée à l'aide de ces règles. Pour cet exemple, ce sera  b, c . La longueur de la chaîne donnée peut comporter jusqu'à 200 symboles. Pourriez-vous inviter un algorithme efficace? 

 Les règles sont toujours  2 -> 1 . J'ai une idée de créer un arbre, la racine est donnée de la chaîne et chaque enfant est une chaîne après une transformation, mais je ne sais pas si c'est le meilleur moyen.


                        
                        
                            
                                                                    string
                                                                    algorithm
                                                                    language-agnostic
                                                                    dynamic-programming
                                                            
                        
                                                    
                            
                            
                                12 commentaires
                                
                                                                            La règle a-t-elle toujours 2 à 1 cartographie? Quelle est votre meilleure solution? la chaîne la plus courte? la chaîne avec la plupart des mêmes lettres?
                                        
                                                                            Vous devez nous montrer des efforts. Avez-vous envisagé comment vous aborderiez ce problème? Donnez-nous vos pensées.  Essayez quelque chose.  Lorsque vous êtes coincé, postez-nous ce que vous avez essayé et expliquez quel est le problème.

                                        
                                                                            Et que voulez-vous dire avec  DP ?
                                        
                                                                            @Bas Probablement la programmation dynamique
                                        
                                                                            @Dialecticus Je le pensais, mais je déteste deviner. Il y a même un  tag  pour ça ...
                                        
                                                                            @BAS DP est la programmation dynamique. Désolé pour une erreur, j'ai déjà ajouté la balise.
                                        
                                                                            @Cerkiewny Oui, la règle est toujours 2 à 1. Il n'y a pas de meilleure solution, objectif est d'obtenir toutes les solutions possibles.
                                        
                                                                            Pourquoi  A B -> ..  deux fois dans votre liste? De plus: chaque caractère de sortie est-il écrit directement, c'est-à-dire non traité, ou le gardez-vous comme le prochain caractère «premier» et redémarrez-le au sommet?

                                        
                                                                            @Jongware 'A b' peut être transformé en 'B' ou à 'C', il existe donc deux règles. Je ne suis pas sûr que j'ai bien compris votre deuxième question, mais ce n'est pas grave si «B 'peut être reçu de différentes manières, seule une chose qui compte est que cela puisse être reçu.
                                        
                                                                            Dans votre exemple  abab , la première transformation est la règle 1:  AB -> B  (ou la règle 2:  AB -> C  - mais comment vous savez lequel utiliser?). Cela mène-t-il à la nouvelle chaîne  bab  (et utilisez la règle 3) ou est  B  immédiatement "consommé", laissant  ab  comme entrée suivante (et utiliser la règle 1 à nouveau)?

                                        
                                                                            @Jongware à l'aide de la règle 1 sur les premières lettres de  A B A B  mène à la chaîne  B A B 

                                        
                                                                            Cyky ne fonctionnerait-il pas pour cela essentiellement non modifié?

3 Réponses : 2 votes Pour un problème DP, vous devez toujours comprendre comment vous pouvez construire la réponse à un gros problème en termes de sous-problèmes plus petits. Supposons que votre fonction simplifie appelée avec une entrée de longueur n . Il existe N-1 façons de diviser l'entrée dans une première et une dernière partie. Pour chacune de ces scissions, vous devez appeler récursivement votre fonction simplifier sur la première partie et la dernière partie. La réponse finale pour l'entrée de longueur n est l'ensemble de toutes les combinaisons possibles des réponses pour la première et pour la dernière partie autorisée par les règles. en python, cela peut être implémenté comme: xxx Vérification rapide: xxx pour rendre cela assez rapide pour les grandes chaînes (éviter le comportement exponentiel ), vous devriez utiliser un Memoze Decorator . Il s'agit d'une étape critique dans la résolution des problèmes DP, sinon vous faites un calcul de force brute. Une autre vitesse de faible vitesse peut être obtenue en revenant de la fonction dès que possible_chars == SET ('ABC') , car à ce stade, vous êtes déjà sûr que vous pouvez générer tous les résultats possibles. < / p> Analyse du temps d'exécution: pour une entrée de longueur n , il existe 2 sous-chaînes de longueur n-1 , 3 sous-chaînes de longueur n -2 , ... n Substrings de longueur 1, pour un total de O (n ^ 2) sous-productions. En raison de la mémoisation, la fonction est appelée au plus une fois pour chaque sous-émérule. Le temps de fonctionnement maximal pour un seul sous-problème est O (n) en raison du pour i in gamme (len (s)) , donc l'heure de fonctionnement globale est au maximum. O (n ^ 3) . 5 commentaires Je ne suis pas bon chez Python et j'ai plusieurs questions. Est-ce que tête = s [: i]; Tail = S [I:] Split String en deux parties sur l'index i ou prenez i Char's des deux extrémités de la chaîne? Et qu'est-ce qui fait possible_Chars.UPDate (règles.get (C1 + C2, SET ())) ? 1) c'est la notation de la tranche, s [: i] == s [0: i] , ce qui correspond au premier i caractères et s [i :] == s [i: len (s)] prend tout sauf le premier i caractères. Donc, pour une entrée abcd , la boucle sur i diviserait cela en tête, queue = 'A', 'BCD' , tête, queue = 'ab', 'cd' et tête, queue = 'abc', 'd' . 2) C'est une manière compacte pour: Concaténate caractères C1 et C2 , recherchez l'ensemble possible des réponses de cette combinaison dans le dictionnaire des règles et définissez enfin possible_chars le Union d'elle-même et ensemble possible de réponses de la des règles. Le obtenez (clé, défaut) méthode sur un dictionnaire lève la touche dans un dictionnaire et s'il n'est pas trouvé, renvoie une valeur par défaut. J'utilise cela pour renvoyer un ensemble vide défini () au cas où la combinaison à 2 lettres n'est pas dans les règles, l'union avec cela ne fait rien. Un moyen plus explicite serait d'écrire si C1 + C2 dans les règles: possible_Chars = possible_Chars.Union (Règles [C1 + C2]) . Pour la complétude du code, je pense qu'il est bon d'ajouter une définition de Memoize . Ou il est pris de la bibliothèque de Python que je ne suis pas au courant? 1 votes Laisse n - longueur de la chaîne donnée et R - Nombre de règles. Développer un arbre de haute direction donne une complexité informatique O (nr ^ n) dans le pire des cas (chaîne d'entrée de type AAA ... code> et des règles aa -> a code>). p> Preuve: p> racine de l'arbre a (N-1) R Enfants , qui ont (N-1) r ^ 2 enfants, ..., qui ont (N-1) r ^ n enfants (Leafs). Donc, la complexité totale est O ((N-1) R + (N-1) R ^ 2 + ... (N-1) R ^ N) = O (N (1 + R ^ 2 + ... + R ^ n)) = (en utilisant Théorème binomial ) = O (N (R + 1 ) ^ N) = O (nr ^ n). P> Mise en œuvre Java récursive de cette approche naïve: p> xxx pré> bas Swinckels's O (RN ^ 3) Mise en œuvre Java (avec Hashmap code> comme cache de mémoisation): p> xxx pré> sortie dans les deux approches: p> [b, c] 3 commentaires Je ne parle pas très couramment Java, mais votre deuxième implémentation utilise-t-elle la notice d'utilisation (c'est-à-dire la mise en cache du résultat pour les intrants fixes)? Sinon, ce n'est pas O (n ^ 3) , mais exponentiel. Merci, les deux algorithmes fonctionnent parfaitement, mais j'ai besoin d'un peu d'aide pour l'optimisation. Le deuxième algorithme est rapide, mais j'en ai besoin pour être un peu plus rapide. Peut-être que vous pouvez me donner des conseils sur l'optimisation, par exemple, utilisez une structure de données plus rapide ou une boucle plus efficace? @ user2875945 Je n'ai pas implémenté Bas Swinckels "Speed Hack" (regardez son code), cela devrait aider à la performance. 2 votes Si vous lisez ces règles de droite à gauche, elles ressemblent exactement aux règles d'une grammaire sans contexte et ont essentiellement la même signification. Vous pouvez appliquer un algorithme d'analyse ascendant comme le Authley Algorithm à vos données, ainsi qu'un règle de départ; Quelque chose comme xxx , puis examinez simplement la forêt d'analyse pour la chaîne la plus courte de Démarrer s. Bien sûr, le pire cas reste sûr, mais Earley est assez efficace, ces jours-ci. Vous pouvez également produire des forêts d'analyse lorsque analyse de dérivés . Vous pourriez être capable de les vérifier efficacement pour les chaînes courtes de Démarrer s. 0 commentaires

Articles qui pourrait vous intéresser : Compter toutes les sous-chaînes Palindrome dans une chaîne Pangram utilisant hashset en java La conversion POJO en JSON ne fonctionne pas pour la variable String commençant par "is" Comment décaler des caractères dans une chaîne? - Défi Hackerrank