Quel est le meilleur moyen d’analyser un corps de texte en fonction de plusieurs expressions rationnelles (15+) sur chaque ligne?

Question

Je dois numériser un corps de texte et chaque ligne contient au moins 2 et parfois 4 parties d'informations. Le problème est que chaque ligne peut représenter 1 sur 15 à 20 actions différentes.

en ruby, le code actuel ressemble un peu à ceci:

text.split("\n").each do |line|  #around 20 times..

..............

      expressions['actions'].each do |pat, reg| #around 20 times

.................

C’est évidemment "LE PROBLÈME". J'ai réussi à accélérer les choses (en C ++, avec une marge de 50%) en combinant toutes les expressions rationnelles en une, mais ce n’est toujours pas la vitesse dont j’ai besoin - j’ai besoin d’analyser RAPIDEMENT des milliers de ces fichiers!

À l’heure actuelle, je les associe à des expressions rationnelles, mais c’est intolérablement lent. J'ai commencé avec ruby ??et je suis passé au C ++ dans l'espoir d'obtenir un gain de vitesse sans que cela ne se produise.

J'ai lu avec désinvolture des PEG et des analyses syntaxiques basées sur la grammaire, mais cela semble un peu difficile à mettre en œuvre. Est-ce la direction que je devrais prendre ou y a-t-il différents itinéraires?

fondamentalement, je suis en train d’analyser l’historique des mains de poker et chaque ligne de l’historique des mains contient généralement 2 à 3 informations que je dois collecter: qui le joueur était, combien d'argent ou quelles cartes l'action a impliqué .. etc.

Exemple de texte à analyser:

buriedtens posts $5
The button is in seat #4
*** HOLE CARDS ***
Dealt to Mayhem 31337 [8s Ad]
Sherwin7 folds
OneMiKeee folds
syhg99 calls $5
buriedtens raises to $10

Après avoir collecté ces informations, chaque action est transformée en un noeud XML.

Pour le moment, mon implémentation ruby ??est beaucoup plus rapide que celle en C ++, mais c’est prob. Parce que je n’ai pas écrit en code c depuis plus de 4-5 ans

MISE À JOUR: Je ne veux pas poster tout le code ici, mais jusqu'ici, mes mains / seconde ressemblent à ceci:

588 hands/second -- boost::spirit in c++
60 hands/second -- 1 very long and complicated regex in c++ (all the regexen put together)
33 hands/second -- normal regex style in ruby

Je teste actuellement pour voir si nous pouvons aller plus loin, mais à partir de maintenant, je suis très très heureux des résultats de Spirit.

Question connexe: Interroger efficacement une chaîne par rapport à plusieurs expressions rationnelles.

Answer 1

Je suggérerais

• Stimuler l'esprit ou
• Antlr si la grammaire est complexe;
• Xpressive si c'est un peu plus simple,
• Tokenizer et du code manuscrit s'il est trivial .

Bonne chance

Answer 2

Boost.Spirit est une bibliothèque fantastique qui vous permet de faire une analyse détaillée de l'analyseur syntaxique. est généré et compilé directement dans votre code, devrait être beaucoup plus rapide qu'une solution calculée dynamiquement. La syntaxe est principalement faite avec des modèles d’expression (un terme sophistiqué pour beaucoup d’opérateurs surchargés), ce qui signifie que vous les écrivez réellement dans votre code.

Answer 3

Voici une façon de procéder si vous utilisiez Perl.
copié à partir de perldoc perlfaq6

while (<>) {
    chomp;
    PARSER: {
        m/ \G( \d+\b    )/gcx   && do { print "number: $1\n";  redo; };
        m/ \G( \w+      )/gcx   && do { print "word:   $1\n";  redo; };
        m/ \G( \s+      )/gcx   && do { print "space:  $1\n";  redo; };
        m/ \G( [^\w\d]+ )/gcx   && do { print "other:  $1\n";  redo; };
    }
}

Pour chaque ligne, la boucle PARSER tente d'abord de faire correspondre une série de chiffres suivie d'une limite de mot. Ce match doit commencer à la place que le dernier match a laissé (ou le début de la chaîne sur le premier match). Puisque m / \ G (\ d + \ b) / gcx utilise l'indicateur c , si la chaîne ne correspond pas à cette expression régulière, perl ne réinitialise pas pos. () et la correspondance suivante commence à la même position pour essayer un modèle différent.

Answer 4

Voir La correspondance des expressions rationnelles peut être simple et rapide (mais est lent en Java, Perl, PHP, Python, Ruby, ...) . En fonction du volume de vos données et de la complexité de votre regex, il pourrait être plus rapide d'écrire votre propre logique d'analyse.

Answer 5

  

J'ai lu avec désinvolture des PEG et des analyses syntaxiques basées sur la grammaire, mais cela semble un peu difficile à mettre en œuvre. Est-ce la direction que je devrais prendre ou y a-t-il différents itinéraires?

Personnellement, j’ai appris à aimer les PEG. Il faudra peut-être un peu de temps pour être à l'aise avec eux, mais je pense qu'ils sont tellement plus faciles à gérer que c'est une victoire évidente. Je trouve que l'analyse du code est à l'origine d'un grand nombre de bogues inattendus lorsque vous trouvez de nouveaux cas d'extrémité dans les entrées. Les grammaires déclaratives à terminales sont plus faciles à mettre à jour lorsque cela se produit, par rapport à la boucle et à la conditionnalisation de code regex lourd. Nommer est puissant.

En Ruby, il existe Treetop , un générateur d'analyseur syntaxique qui utilise des PEG. J'ai récemment trouvé très agréable de remplacer un analyseur syntaxique écrit à la main avec une grammaire courte.

Answer 6

Les correspondances d'expressions régulières se chevauchent-elles jamais? En d’autres termes, lorsque deux expressions rationnelles ou plus correspondent à la même ligne, correspondent-elles toujours à des parties différentes de la ligne (sans chevauchement)?

Si les correspondances ne se chevauchent jamais, lancez votre recherche en utilisant une expression régulière qui combine les 15 regex que vous avez maintenant:

regex1|regex2|regex3|...|regex15

Utilisez des groupes de capture si vous devez être en mesure de déterminer laquelle des 15 expressions rationnelles correspondantes.

La recherche de vos données une seule fois pour une longue expression régulière sera plus rapide que la recherche 15 fois. La rapidité dépend du moteur de regex que vous utilisez et de la complexité de vos expressions régulières.

Answer 7

Essayez un test simple en Perl. En savoir plus sur l’étude " " une fonction. Ce que je pourrais essayer, c’est:

• Lit le fichier entier ou un grand nombre de lignes si ces fichiers sont très volumineux en une seule chaîne
• Ajoutez un numéro de ligne au début de chaque ligne au fur et à mesure.
• " study " la ficelle. Ceci construit une table de recherche par caractère, pouvant être volumineux.
• Exécuter des correspondances d'expressions régulières sur la chaîne, délimitées par des nouvelles lignes (utilisez les modificateurs de regex m et s). L’expression doit extraire le numéro de ligne avec les données.
• Définissez un élément de tableau indexé par numéro de ligne sur les données trouvées sur cette ligne, ou faites quelque chose d'encore plus intelligent.
• Enfin, vous pouvez traiter les données stockées dans le tableau.

Je n'ai pas essayé, mais cela pourrait être intéressant.

Answer 8

Une autre idée si vous avez un serveur à noyau octal ou octal à utiliser pour cela.

Construisez un pipeline de traitement qui divise le travail. La première étape pourrait couper les fichiers en un jeu ou une main chacun, puis écrire chacun d’entre eux sur l’un des huit canaux de la deuxième étape qui lisent les données, les traitent et génèrent une sortie, probablement dans une base de données sur une autre machine.

D'après mon expérience, ces conceptions multi-processus basées sur des tubes sont presque aussi rapides et beaucoup plus faciles à déboguer que les conceptions multi-threading. Il serait également facile de configurer un cluster de machines utilisant des sockets réseau au lieu de tubes.

Answer 9

OK, cela rend les choses plus claires (historique des mains au poker). J'imagine que vous créez un outil statistique (facteur d'agression, passage à l'abattage, mise volontaire de $ dans le pot, etc.). Je ne sais pas pourquoi vous avez besoin de vitesses excessives pour cela. même si vous utilisez 16 tables multitâches, les mains ne devraient jouer qu’à un rythme modéré.

Je ne connais pas Ruby, mais dans Perl, je ferais une petite déclaration de commutateur, tout en plaçant les parties significatives à 1 $, 2 $, etc. Selon mon expérience, cela n’est pas plus lent que des comparaisons de chaînes. puis diviser la ligne avec d’autres moyens.

HAND_LINE: for ($Line)
    { /^\*\*\* ([A-Z ]+)/ and do 
        { # parse the string that is captured in $1
          last HAND_LINE; };
      /^Dealt to (.+) \[(.. ..)\]$/ and do
        { # $1 contains the name, $2 contains the cards as string
          last HAND_LINE; };
      /(.+) folds$/ and do
        { # you get the drift
          last HAND_LINE; }; };

Je ne pense pas que vous puissiez vraiment accélérer les choses. Placez les vérifications des lignes qui apparaissent le plus souvent à la première position (probablement les instructions de pliage) et de celles qui ne se produisent finalement que de manière peu dense (nouvelle main initiale, "*** PHASE SUIVANTE ***" ).

Si vous découvrez que la lecture de fichier est un goulot d'étranglement, vous pouvez peut-être jeter un coup d'œil sur les modules que vous pouvez utiliser pour traiter des fichiers volumineux. pour Perl, Tie :: File vient à l’esprit.

Assurez-vous de lire chaque main une seule fois. Ne relisez pas toutes les données après chaque main, conservez par exemple une table de hachage des identifiants de main déjà analysés.

Answer 10

Pour un problème de ce type, je fermerais simplement les yeux et utiliserais un générateur Lexer + Parser. Vous pouvez probablement battre cela avec une optimisation manuelle, mais il est beaucoup plus facile d'utiliser un générateur. En outre, il est beaucoup plus flexible lorsque l’entrée change soudainement.