Tokenize le texte selon certaines règles spécifiques. Algorithme en C ++

Question

Je suis en train d'écrire un programme qui tokenizer 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 je autour de 500+ règles comme celui-ci. Si je suis entrée comme fournirai ' appu ', il devrait tokenizer comme ' V-A + C-PPA + V-U . Je l'ai mis en place un algorithme pour faire cela et je voulais vous assurer que je suis en train de faire 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 (de la mise en œuvre de singleton).

2 - itérer les caractères de saisie de texte. Pour chaque personnage, chercher un match. Si trouvé, devenu plus gourmand et chercher plus de matches en prenant les caractères suivants du texte d'entrée. Pour ce faire, jusqu'à ce que nous recevons aucune correspondance. Donc, pour le texte d'entrée ' appu , premier regard pour un match pour' a . Si trouvé, essayez d'obtenir match de plus en prenant le caractère suivant du texte d'entrée. Donc, il va essayer de faire correspondre « ap » et a trouvé aucune correspondance. Donc, il retourne juste.

3 -. Remplacez la lettre « a » du texte d'entrée que nous avons obtenu un jeton pour ce

4 -. Répétez l'étape 2 et 3 avec les autres caractères 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 cela est la bonne méthode, std :: carte est un bon choix ici? Ou dois-je créer mon propre conteneur clé / valeur?

3 - Y at-il une bibliothèque disponible qui peut tokenizer chaîne comme 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à; il va être une recherche inefficace indépendamment.

Une façon beaucoup plus efficace de trouver juste les jetons appropriés pour commencer ou continuer un match serait de les stocker comme Trie. Une recherche d'une lettre, il vous donnera un sous-Trie qui ne contient que les jetons qui ont cette lettre comme la première lettre, puis vous continuez simplement la recherche vers le bas aussi loin que vous pouvez aller.

---

Edit: laissez-moi vous expliquer un peu plus loin

.

D'abord, je dois préciser que je ne suis pas familier avec ces C ++ std::map, au-delà du nom, ce qui en fait un parfait exemple des raisons pour lesquelles on apprend la théorie de ce genre de choses, ainsi que de détails des bibliothèques particulières en programmation particulier langues: à moins que cette bibliothèque est mal utilise abusivement le nom « carte » (ce qui est peu probable), le nom lui-même me dit beaucoup de choses sur les caractéristiques de la structure de données. Je sais, par exemple, qu'il y va y avoir une fonction qui, étant donné une clé unique et la carte, chercherai très efficace et renvoie la valeur associée à cette clé, et qu'il ya probablement aussi une fonction qui vous donnera une liste / série / whatever de toutes les clés, que vous pourriez vous rechercher 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 modèle, ceux-ci étant une liste (ou un tableau, ou quelque chose de cette nature) de caractères, et les valeurs sont des jetons. Ainsi, vous pouvez, étant donné un modèle complet, trouver rapidement le jeton associé.

Malheureusement, alors qu'une telle carte est un bon match pour convertir le format d'entrée XML à une structure de données interne, ce n'est pas un bon match pour les recherches que vous devez faire. Notez que vous n'êtes pas à la recherche des modèles entiers, mais le premier caractère d'un motif, produisant un ensemble de jetons possibles, suivi d'une recherche du second caractère d'un motif à partir de l'ensemble des modèles produits par ce premier recherche , et ainsi de suite.

Alors, que vous avez vraiment besoin est pas une seule carte, mais les cartes de cartes de cartes, chaque calées 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 « autre chose », produisant le jeton C-PA. Ceci est effectivement une structure de données arborescente.

Est-ce sens?

Il peut être utile si vous commencez par écrire le code d'analyse syntaxique d'abord, de cette manière: imaginez que quelqu'un d'autre va écrire les fonctions pour faire les recherches dont vous avez besoin, et il est un très bon programmeur et peut faire à peu près toute la magie que vous vouloir. Écriture du code d'analyse syntaxique, se concentrer sur faire ce aussi simple et propre que possible, quelle que soit la création d'une interface utilisant ces fonctions arbitraires dont vous avez besoin (sans obtenir trivial et de remplacer le tout avec une fonction!). Maintenant, vous pouvez regarder les fonctions de recherche vous vous retrouviez avec, et qui vous indique comment vous devez accéder à votre structure de données, qui vous mènera au type de structure de données dont vous avez besoin. Une fois que vous avez compris cela, vous pouvez alors comment le charger.

Answer 2

1. Cette méthode fonctionne -. Je ne suis pas sûr qu'il est efficace, mais il devrait fonctionner

2. J'utiliser la norme std :: carte plutôt que votre propre système.

3. Il existe des outils comme lex (ou flex) qui peut être utilisé pour cela. La question est de savoir si vous pouvez régénérer l'analyseur lexical qu'il construirait lorsque les changements de spécification XML. Si la spécification XML ne change pas souvent, vous pourriez être en mesure d'utiliser des outils tels que lex pour faire l'analyse et la cartographie 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 voudrais également envisager de regarder la technologie d'appariement de formes - le genre de choses qui egrep à des usages particuliers. Cela a le mérite d'être quelque chose qui peut être manipulé à l'exécution (parce que egrep fait tout le temps). Ou vous pouvez opter pour un langage de script -. Perl, Python, ... Ou vous pourriez envisager quelque chose comme PCRE (Perl Compatible Regular Expressions) bibliothèque

Answer 3

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 4

Vous pouvez utiliser une expression régulière (peut-être le coup de pouce :: bibliothèque regex). Si tous les motifs ne sont que des chaînes de lettres, une expression régulière comme « (a | p | p | u) » trouverait un match gourmand. Donc:

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. Imprimer l'entrée consommée non appariés et le remplacement du texte à votre sortie, puis répétez 1 sur l'entrée restante.

Et fait.

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 organigramme de l'État. Au début, je pensais que boost.statechart aiderait, mais je me suis dit qu'il était pas vraiment approprié. Cette méthode peut être plus efficace que l'utilisation d'un simple std :: carte S'il y a beaucoup de règles, le nombre de caractères possibles est limité et la longueur du texte à lire est assez élevé.

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

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

1) lire le fichier de configuration XML et créer des sommets si nécessaire (passage d'un « jeu de caractères » (par exemple « pp ») à une supplémentaire (par exemple « ppa »)). A l'intérieur de chaque sommet, stocker une table de transition vers les prochains sommets. Si « texte clé » est terminée, sommet de marque comme finale et stocker le texte résultant

2) lire le texte maintenant et l'interpréter à l'aide du graphique. Commencez au sommet « start ». (*) Table utilisés pour interpréter un personnage et passer à nouveau sommet. Si aucun nouveau sommet a été sélectionné, une erreur peut être émis. Dans le cas contraire, si un nouveau sommet est définitive, imprimer le texte résultant et revenir en arrière pour commencer sommet. Retour à (*) jusqu'à ce qu'il n'y a pas 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 que vous avez besoin. Faites votre propre représentation personnalisée.