Qual è il modo migliore per analizzare un corpo di testo contro più (15+) regex su ogni riga?

https://stackoverflow.com/questions/303830

08-07-2019
|

Domanda

Ho un corpo di testo che devo scansionare e ogni riga contiene almeno 2 e talvolta quattro parti di informazioni. Il problema è che ogni riga può essere 1 su 15-20 azioni diverse.

in ruby ??il codice attuale è un po 'così:

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

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

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

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

Questo è ovviamente "IL PROBLEMA". Sono riuscito a renderlo più veloce (in C ++ con un margine del 50%) combinando tutti i regexen in uno, ma questa non è ancora la velocità di cui ho bisogno - devo analizzare migliaia di questi file VELOCEMENTE!

In questo momento li abbino ai regex - tuttavia questo è intollerabilmente lento. Ho iniziato con Ruby e sono passato al C ++ nella speranza di ottenere un aumento di velocità e non sta succedendo.

Ho letto casualmente su PEG e analisi grammaticale ma sembra piuttosto difficile da implementare. È questa la direzione in cui dovrei andare o ci sono percorsi diversi?

fondamentalmente sto analizzando la cronologia delle mani di poker e ogni riga della cronologia delle mani di solito contiene 2-3 bit di informazioni che devo raccogliere: chi era il giocatore, quanti soldi o quali carte comportava l'azione ... ecc.

Testo di esempio che deve essere analizzato:

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

Dopo aver raccolto queste informazioni ogni azione viene trasformata in un nodo XML.

In questo momento la mia implementazione ruby ??di questo è molto più veloce della mia C ++ ma è probabile. Solo perché non scrivo nel codice c da oltre 4-5 anni

UPDATE: Non voglio pubblicare qui tutto il codice, ma finora le mie mani / i secondi sono i seguenti:

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

Attualmente sto testando antlr per vedere se possiamo andare oltre ma al momento sono molto molto contento dei risultati di spirit.

Domanda correlata: Interrogazione efficiente di una stringa su più regex.

Soluzione

Vorrei suggerire

Boost Spirit o
Antlr se la grammatica è complessa;
Xpressive se è un po 'più semplice,
Tokenizer e codice fatto a mano se è banale .

Buona fortuna

Altri suggerimenti

Boost.Spirit è una fantastica libreria che ti permette di effettuare analisi dettagliate del parser, e dal momento che il parser viene generato e compilato direttamente nel tuo codice, dovrebbe essere molto più veloce di una soluzione calcolata dinamicamente. La sintassi viene principalmente eseguita con modelli di espressioni (un termine elaborato per molti operatori sovraccarichi), il che significa che li scrivi effettivamente nel tuo codice.

Ecco un modo per farlo, se stavi usando Perl.
copiato da 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; };
    }
}

Per ogni riga, il ciclo PARSER tenta innanzitutto di far corrispondere una serie di cifre seguite da un limite di parole. Questa partita deve iniziare nel punto in cui l'ultima partita è stata interrotta (o l'inizio della stringa della prima partita). Poiché m / \ G (\ d + \ b) / gcx utilizza il flag c , se la stringa non corrisponde a quell'espressione regolare, perl non reimposta pos () e la partita successiva inizia nella stessa posizione per provare un modello diverso.

Vedi La corrispondenza delle espressioni regolari può essere semplice e veloce (ma è lento in Java, Perl, PHP, Python, Ruby, ...) . A seconda del volume dei tuoi dati e della complessità della tua regex, potrebbe essere più veloce scrivere la tua logica di analisi.

Ho letto casualmente su PEG e analisi grammaticale ma sembra piuttosto difficile da implementare. È questa la direzione in cui dovrei andare o ci sono percorsi diversi?

Personalmente ho imparato ad amare i PEG. Forse ci vorrà un po 'per sentirsi a proprio agio con loro, tuttavia penso che siano molto più mantenibili che è una chiara vittoria. Trovo che il codice di analisi sia la fonte di molti bug imprevisti mentre trovi nuovi casi limite negli input. Le grammatiche dichiarative con non terminali sono più facili da aggiornare per me quando ciò accade rispetto al loop e condizionano il pesante codice regex. La denominazione è potente.

In Ruby c'è Treetop che è un generatore di parser che utilizza i PEG. Di recente l'ho trovato abbastanza piacevole nel sostituire un parser scritto a mano pesante regex con una breve grammatica.

Le corrispondenze di espressioni regolari si sovrappongono mai? Cioè, quando due o più regex corrispondono alla stessa linea, corrispondono sempre a parti diverse della linea (nessuna sovrapposizione)?

Se le corrispondenze non si sovrappongono mai, esegui la ricerca utilizzando un'espressione regolare che combina le 15 regex che hai ora:

regex1|regex2|regex3|...|regex15

Utilizza i gruppi di acquisizione se devi essere in grado di determinare quale delle 15 regex ha trovato corrispondenza.

La ricerca dei tuoi dati una volta per un lungo regex sarà più veloce della ricerca di 15 volte. Quanto più velocemente dipende dal motore regex che stai usando e dalla complessità delle tue espressioni regolari.

Prova un semplice test in Perl. Leggi lo "studio" funzione. Quello che potrei provare è:

Leggi l'intero file o un numero elevato di righe se questi file sono molto grandi in una singola stringa
Aggiungi un numero di riga all'inizio di ogni riga mentre procedi.
" studio " la stringa. Questo crea una tabella di ricerca per carattere, può essere grande.
Esegui corrispondenze di espressioni regolari sulla stringa, delimitate da newline (usa i modificatori regex m e s). L'espressione dovrebbe estrarre il numero di riga insieme ai dati.
Imposta un elemento dell'array indicizzato dal numero di riga sui dati trovati su quella riga o esegui operazioni ancora più intelligenti.
Infine è possibile elaborare i dati memorizzati nell'array.

Non l'ho provato, ma potrebbe essere interessante.

Un'altra idea se hai un server quad o oct core spiffy da usare per questo.

Costruisci una pipeline di elaborazione che divide il lavoro. Lo Stage One potrebbe tagliare i file in un gioco o consegnarli ciascuno, quindi scrivere ciascuno su uno degli otto pipe dello Stage Two che leggono i dati, li elaborano e producono in qualche modo output, probabilmente su un database su un altro computer.

Nella mia esperienza, questi progetti multi-processo basati su pipe sono quasi altrettanto veloci e molto più facili da eseguire il debug dei progetti multi-thread. Sarebbe anche facile impostare un cluster di macchine utilizzando socket di rete anziché pipe.

OK, questo rende le cose più chiare (storie delle mani di poker). Immagino che tu stia creando uno strumento statistico (fattore di aggressività, è andato allo showdown, hai messo volontariamente $ in piatto ecc.). Non sono sicuro del motivo per cui hai bisogno di velocità eccessive per questo; anche se stai eseguendo il multitablaggio con 16 tavoli, le mani dovrebbero fare il solletico solo a un ritmo moderato.

Non conosco Ruby, ma in Perl farei una piccola istruzione switch, allo stesso tempo portando le parti significative in $ 1, $ 2 ecc. Nella mia esperienza, questo non è più lento del confronto delle stringhe e quindi suddividere la linea con altri mezzi.

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; }; };

Non credo che tu possa davvero renderlo più veloce. Metti i controlli per le righe che si verificano maggiormente in una prima posizione (probabilmente le istruzioni fold) e quelle che si verificano solo scarsamente alla fine (inizio nuova mano, " *** NEXT PHASE *** " ).

Se scopri che la lettura effettiva dei file è un collo di bottiglia, puoi forse dare un'occhiata a quali moduli puoi usare per indirizzare file di grandi dimensioni; per Perl, mi viene in mente Tie :: File .

Assicurati di leggere ogni mano una sola volta. Non rileggere nuovamente tutti i dati dopo ogni mano, tenere invece ad es. una tabella hash degli ID mano già analizzati.

Per un problema come questo, chiuderei semplicemente gli occhi e userei un generatore Lexer + Parser. Puoi batterlo con l'ottimizzazione della mano probabilmente, ma è molto più facile usare un generatore. Inoltre, è molto più flessibile quando l'input cambia improvvisamente.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow