Marquez le texte en fonction de certaines règles spécifiques. Algorithme en C++

Question

J'écris un programme qui va marquer le texte d'entrée en fonction de certaines règles spécifiques. J'utilise C++ pour cela.

Règles

Letter 'a' should be converted to token 'V-A' 
Letter 'p' should be converted to token 'C-PA' 
Letter 'pp' should be converted to token 'C-PPA' 
Letter 'u' should be converted to token 'V-U' 

Ceci est juste un échantillon et en temps réel, j'ai autour de 500+ règles comme celui-ci. Si je fournis une entrée sous la forme 'appu', cela devrait ressembler à 'V-A + C-PPA + V-U'. J'ai mis en place un algorithme pour ce faire et je voulais m'assurer que je faisais la bonne chose.

algorithme

Toutes les règles seront conservés dans un fichier XML avec le mappage correspondant au jeton. Quelque chose comme

<rules> 
    <rule pattern="a" token="V-A" /> 
    <rule pattern="p" token="C-PA" /> 
    <rule pattern="pp" token="C-PPA" /> 
    <rule pattern="u" token="V-U" /> 
</rules> 

1 - Lorsque l'application démarre, lisez ce fichier xml et conserver les valeurs dans un 'std :: carte'. Ce sera disponible jusqu'à la fin de l'application (mise en œuvre de modèle singleton).

2 - Itérer les caractères de saisie. Pour chaque personnage, cherchez une correspondance. Si trouvé, devenez plus gourmand et cherchez plus de correspondances en prenant les caractères suivants du texte d'entrée. Faites-le jusqu'à ce que nous obtenions un non-match. Donc, pour le texte d'entrée 'appu', cherchez d'abord un résultat pour 'a'. Si trouvé, essayez d'obtenir plus de correspondance en prenant le caractère suivant du texte d'entrée. Donc, il va essayer de faire correspondre 'ap' et n'a trouvé aucun résultat. Donc ça revient juste.

3 - Remplacez la lettre 'a' du texte d'entrée car nous en avons reçu un jeton.

4 - Répétez les étapes 2 et 3 avec les caractères restants dans le texte d'entrée.

Voici une explication plus simple des étapes

input-text = 'appu' 
tokens-generated='' 

// First iteration 
character-to-match = 'a' 
pattern-found = true 

// since pattern found, going recursive and check for more matches 
character-to-match = 'ap' 
pattern-found = false 

tokens-generated = 'V-A' 

// since no match found for 'ap', taking the first success and replacing it from input text 
input-text = 'ppu' 

// second iteration 
character-to-match = 'p' 
pattern-found = true 

// since pattern found, going recursive and check for more matches 
character-to-match = 'pp' 
pattern-found = true 

// since pattern found, going recursive and check for more matches 
character-to-match = 'ppu' 
pattern-found = false 

tokens-generated = 'V-A + C-PPA' 

// since no match found for 'ppu', taking the first success and replacing it from input text 
input-text = 'u' 

// third iteration 
character-to-match = 'u' 
pattern-found = true 

tokens-generated = 'V-A + C-PPA + V-U' // we'r done! 

Questions

1 - Est-ce algorithme semble très bien pour ce problème ou est-il une meilleure façon de résoudre ce problème?

2 - Si c'est la bonne méthode, std :: map est un bon choix ici? Ou dois-je créer mon propre conteneur clé/valeur?

3 - Existe-t-il une bibliothèque disponible qui peut générer une chaîne de caractères comme celle ci-dessus?

Toute aide serait appréciée

:)

Answer 1

Alors vous allez à travers tous les jetons dans votre carte pour rechercher les matchs? Vous pourriez aussi bien utiliser une liste ou un tableau, là; ça va être une recherche inefficace malgré tout.

Une manière beaucoup plus efficace de trouver seulement les jetons appropriés pour commencer ou continuer une correspondance serait de les stocker comme trie. Une recherche d'une lettre vous donnerait un sous-trie qui contient seulement les jetons qui ont cette lettre comme première lettre, et ensuite vous continuez à chercher aussi loin que vous le pouvez.

---

Edit: laissez-moi vous expliquer un peu plus loin. Tout d'abord, je dois expliquer que je ne suis pas familier avec ces C++ std::map, au-delà du nom, ce qui en fait un parfait exemple de la raison pour laquelle on apprend la théorie de ces choses ainsi que des détails de bibliothèques particulières en particulier langages de programmation: à moins que cette bibliothèque ne mette à mal le nom "map" (ce qui est plutôt improbable), le nom lui-même en dit long sur les caractéristiques de la structure de données. Je sais, par exemple, qu'il y aura une fonction qui, étant donné une seule clé et la carte, cherchera et retournera très efficacement la valeur associée à cette clé, et qu'il y a aussi probablement une fonction qui vous donnera une liste/array/quelconque de toutes les clés, que vous pouvez rechercher vous-même en utilisant votre propre code. Mon interprétation de votre structure de données est que vous avez une carte où les clés sont ce que vous appelez un motif, ce sont une liste (ou un tableau, ou quelque chose comme ça) de caractères, et les valeurs sont des jetons. Ainsi, vous pouvez, avec un schéma complet, trouver rapidement le jeton associé à celui-ci. Malheureusement, bien qu'une telle carte corresponde bien à la conversion de votre format d'entrée XML en une structure de données interne, elle ne correspond pas aux recherches que vous devez effectuer. Notez que vous ne recherchez pas des motifs entiers, mais le premier caractère d'un motif, produisant un ensemble de jetons possibles, suivi d'une recherche du deuxième caractère d'un motif dans l'ensemble des motifs produits par cette première recherche , etc.

Donc ce dont vous avez vraiment besoin n'est pas une seule carte, mais des cartes de cartes de cartes, chacune codée par un seul caractère. Une recherche de "p" au niveau supérieur devrait vous donner une nouvelle carte, avec deux clés: p, produisant le jeton C-PPA, et "n'importe quoi d'autre", produisant le jeton C-PA. C'est effectivement une structure de données.

Est-ce que cela a du sens? Cela peut être utile si vous commencez par écrire le code d'analyse d'abord, de cette manière: imaginez que quelqu'un d'autre écrira les fonctions pour effectuer les recherches dont vous avez besoin, et il est un très bon programmeur et peut faire à peu près n'importe quelle magie tu veux. En écrivant le code d'analyse, concentrez-vous à rendre ceci aussi simple et propre que possible, en créant n'importe quelle interface en utilisant ces fonctions arbitraires dont vous avez besoin (tout en ne devenant pas insignifiant et en remplaçant le tout par une fonction!). Maintenant, vous pouvez regarder les fonctions de recherche que vous avez terminées, et cela vous indique comment vous devez accéder à votre structure de données, ce qui vous conduira au type de structure de données dont vous avez besoin. Une fois que vous avez compris cela, vous pouvez alors déterminer comment le charger.

Answer 2

1. Cette méthode va fonctionner - Je ne suis pas sûr que ce soit efficace, mais cela devrait fonctionner. J'utiliserais le standard std :: map plutôt que votre propre système. Il existe des outils comme lex (ou flex) qui peuvent être utilisés pour cela.Le problème serait de savoir si vous pouvez régénérer l'analyseur lexical qu'il construirait lorsque la spécification XML change. Si la spécification XML ne change pas souvent, vous pouvez utiliser des outils tels que lex pour effectuer l'analyse et le mappage plus facilement. Si la spécification XML peut changer au gré de ceux qui utilisent le programme, alors lex est probablement moins approprié.

Il y a quelques mises en garde - notamment que les deux lex et flex générer du code C plutôt que C++.

Je considérerais aussi la technologie de correspondance de motifs - le genre de choses que egrep utilise en particulier. Cela a le mérite d'être quelque chose qui peut être manipulé à l'exécution (parce que egrep le fait tout le temps). Ou vous pourriez opter pour un langage de script - Perl, Python, ... Ou vous pourriez envisager quelque chose comme la bibliothèque PCRE (Perl Compatible Regular Expressions).

Answer 3

Vous pouvez utiliser une regex (peut-être la bibliothèque boost :: regex). Si tous les motifs ne sont que des chaînes de lettres, une regex comme "(a | p | pp | u)" trouverait une correspondance gloutonne. Alors:

1. Exécuter un regex_search en utilisant le modèle ci-dessus pour localiser le prochain match
2. Branchez le match texte dans votre std :: carte pour obtenir le texte remplacer.
3. Imprimez l'entrée consommée non appariée et remplacez le texte par votre sortie, puis répétez 1 sur l'entrée restante.

Et fait.

Answer 4

Mieux encore, si vous allez utiliser la bibliothèque boost, il y a toujours le Boost tokenizer bibliothèque ->http://www.boost.org/doc/libs/1_39_0/libs/tokenizer/index.html

Answer 5

Il peut sembler un peu compliqué, mais la façon la plus efficace de le faire est d'utiliser un graphique pour représenter un graphique d'état. Au début, je pensais que boost.statechart aiderait, mais j'ai pensé que ce n'était pas vraiment approprié. Cette méthode peut être plus efficace qu'en utilisant un simple std :: map SI il y a beaucoup de règles, le nombre de caractères possibles est limité et la longueur du texte à lire est assez élevée.

De toute façon, à l'aide d'un graphique simple:

0) créer le graphique avec "start" sommet

1) lire le fichier de configuration XML et créer des sommets en cas de besoin (passage d'un "ensemble de caractères" (par exemple "pp") à un autre (par exemple "ppa")). À l'intérieur de chaque sommet, stockez une table de transition aux sommets suivants. Si le "texte clé" est terminé, marquez le sommet comme final et stockez le texte résultant

2) lisez maintenant le texte et interprétez-le en utilisant le graphique. Commencez au sommet "start". (*) Utilisez la table pour interpréter un caractère et sauter au nouveau sommet. Si aucun nouveau sommet n'a été sélectionné, une erreur peut être émise. Sinon, si le nouveau sommet est définitif, imprimez le texte qui en résulte et revenez en arrière pour lancer le sommet. Retournez à (*) jusqu'à ce qu'il n'y ait plus de texte à interpréter.

Vous pouvez utiliser boost.graph pour représenter le graphique, mais je pense qu'il est trop complexe pour ce dont vous avez besoin. Faites votre propre représentation personnalisée.