Qual é a melhor maneira de analisar um corpo de texto contra vários (15 +) expressões regulares em cada linha?

https://stackoverflow.com/questions/303830

08-07-2019
|

Pergunta

Eu tenho um corpo de texto que eu tenho que fazer a varredura e cada linha contém pelo menos 2 e às vezes quatro partes de informação. O problema é que cada linha pode ser 1 fora de 15-20 ações diferentes.

em ruby ??os olhares de código atual mais ou menos assim:

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

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

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

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

Esta é, obviamente, 'o problema'. Eu consegui ser mais rápido (em C ++ por uma margem de 50%), combinando todos os regexen em um, mas que ainda não é a velocidade que eu preciso - eu preciso analisar milhares destes arquivos rapidamente

Agora eu combiná-los com expressões regulares - no entanto este é insuportavelmente lento. Comecei com rubi e pulou para C ++ na esperança de que eu iria obter um aumento de velocidade e ele simplesmente não está acontecendo.

Eu casualmente ler PEGs e gramática de análise baseada mas parece um pouco difícil de implementar. É este o sentido que eu deveria ir ou existem rotas diferentes?

basicamente eu sou analisar históricos de mãos de poker e cada linha do histórico de mãos geralmente contém 2-3 bits de informação que eu preciso de recolher: que foi o jogador, quanto dinheiro ou o que cartões a ação implicou .. etc ..

O texto da amostra que precisa ser analisado:

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

Depois de coletar essas informações cada ação é transformado em um nó XML.

Agora minha implementação rubi isso é muito mais rápido do que o meu C ++ um, mas que de prov. Apenas porque eu não tenho escrito em código c para bem mais de 4-5 anos

UPDATE: Eu não quero postar todo o código aqui, mas até agora o meu mãos / segundo parecer com o seguinte:

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

Atualmente estou testando antlr para ver se podemos ir mais longe, mas a partir de agora eu estou muito, muito feliz com os resultados do espírito.

questão relacionada: eficiente consultando uma corda contra múltiplas expressões regulares .

Solução

Eu sugeriria

impulsionar Espírito ou
Antlr se a gramática é complexo;
Xpressive se é um pouco mais simples,
Tokenizer e código artesanal se é trivial .

Boa sorte

Outras dicas

Boost.Spirit é uma biblioteca fantástica que permite que você faça a análise analisador detalhada, e desde que o analisador é gerado e compilado para a direita em seu código, deve ser muito mais rápido do que uma solução dinamicamente calculado. A sintaxe é feito principalmente com modelos de expressão (um termo extravagante para os lotes de operadores sobrecarregados), o que significa que você realmente escrevê-los para a direita em seu código.

Aqui está uma maneira de fazê-lo, se você estivesse usando Perl.
copiado 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; };
    }
}

Para cada linha, o loop PARSER primeiras tentativas para combinar uma série de dígitos seguidos de um limite de palavra. Este jogo tem de começar no lugar o último jogo parou (ou o início da cadeia no primeiro jogo). Desde m/ \G( \d+\b )/gcx usa a bandeira c, se a cadeia não coincide com aquela expressão regular, perl não pos() de reset e o próximo jogo começa na mesma posição para tentar um padrão diferente.

de expressões regulares pode ser simples e rápido (Mas é lento em Java, Perl, PHP, Python, Ruby, ...) . Dependendo do volume de seus dados e quão complexo o seu regex é, ele pode ser apenas mais rápido para escrever a sua própria lógica de análise.

Eu casualmente ler PEGs e gramática de análise baseada mas parece um pouco difícil de implementar. É este o sentido que eu deveria ir ou existem rotas diferentes?

Pessoalmente eu tenho aprendido a amar PEGs. É, talvez, vai demorar um pouco para se sentir confortável com eles, porém eu acho que eles são muito mais sustentável que é uma vitória clara. Acho código de análise é a fonte de muitos erros inesperados que você encontrar novos casos de ponta em entradas. gramáticas declarativas com nonterminals são mais fáceis para mim para atualizar quando isso acontece comparação com laço e condição código pesado regex. Naming é poderosa.

Em Ruby existe Treetop que é um gerador de analisador que usa pinos. Recentemente, achei bastante agradável em substituição de uma mão pesada regex analisador escritos com uma pequena gramática.

Siga as correspondências de expressões regulares nunca se sobrepõem? Isto é, quando dois ou mais expressões regulares coincidir com a mesma linha, eles sempre combinar diferentes partes da linha (sem sobreposição)?

Se os jogos não se sobrepõem, executar a sua pesquisa usando um expressão regular que combina as 15 expressões regulares você tem agora:

regex1|regex2|regex3|...|regex15

Use a captura de grupos, se você precisa ser capaz de determinar qual das 15 expressões regulares correspondentes.

Como pesquisar seus dados uma vez por um longo regex será mais rápido do que procurar-lo 15 vezes. Quanto mais rápido depende do motor regex você está usando e da complexidade de suas expressões regulares.

Tente um teste simples em Perl. Leia sobre a função de "estudo". O que eu poderia tentar é:

Leia o arquivo inteiro ou um grande número de linhas, se esses arquivos são muito grandes em uma seqüência única
Adicionar um número de linha para o início de cada linha que você vá.
"estudo" da cadeia. Isso cria uma tabela de pesquisa por caractere, podem ser grandes.
Executar as correspondências de expressões regulares na corda, delimitadas por novas linhas (use o m e s modificadores regex). A expressão deve extrair o número da linha, juntamente com os dados.
Definir um item do array indexada pelo número da linha com os dados encontrados nessa linha, ou fazer algo ainda mais inteligente.
Finalmente, você pode processar os dados armazenados na matriz.

Eu não tentei, mas pode ser interessante.

Outra idéia se você tiver um quad spiffy ou outubro servidor núcleo para uso para isso.

Construir um pipeline de processamento que divide o trabalho. Stage One poderia cortar arquivos em um jogo ou entregar cada, em seguida, escrever cada um para uma das oito Stage Duas tubulações que lêem os dados, processá-lo e saída de produtos de alguma forma, provavelmente para um banco de dados em outra máquina.

Na minha experiência, estes projetos multi-processos com base tubulação são quase tão rápido e muito mais fácil de depurar do que os projetos multi-threading. Também seria fácil de configurar um cluster de máquinas usando sockets de rede em vez de tubos.

OK, isso torna as coisas mais claras (hand histories de poker). Eu acho que você está fazendo uma ferramenta de estatísticas (fator de agressão, foi para o showdown, voluntariamente colocar US $ em pot etc.). Não estou certo porque você precisa de velocidades excessivas para isso; mesmo se você estiver multitabling com 16 mesas, as mãos só devem agradar a um ritmo moderado.

Eu não sei Ruby, mas em Perl eu faria um pouco de instrução switch, ao mesmo tempo, como a obtenção de partes significativas em US $ 1, $ 2, etc .. Na minha experiência, isso não mais lento é do que fazer comparações de strings e, em seguida, dividindo a linha com outros meios.

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

Eu não acho que você realmente pode torná-lo mais rápido. Coloque os cheques para as linhas que ocorrem mais em uma primeira posição (prováveis ??as declarações vezes) e aquelas que só ocorrem esparsamente na última (começando nova mão, "*** NEXT PHASE ***").

Se você descobrir que a leitura de arquivo real é um gargalo, você pode, talvez, dar uma olhada em quais módulos você pode usar para lidar com arquivos grandes; para Perl, Tie::File vem à mente.

Certifique-se de que você leia cada mão apenas uma vez. Não leia todos os dados novamente depois de cada mão, em vez manter por exemplo uma tabela hash dos IDs mão já analisado.

Para um problema como este, eu tinha acabado de fechar os olhos e usar um gerador de Lexer + Analisador. Você pode bater aquele com a mão-de otimização provavelmente, mas é muito mais fácil de usar um gerador. Além disso, é a maneira mais flexível quando a entrada muda de repente.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow