¿Cuál es la mejor manera de analizar un cuerpo de texto contra múltiples expresiones regulares (más de 15) en cada línea?

https://stackoverflow.com/questions/303830

08-07-2019
|

Pregunta

Tengo un cuerpo de texto que tengo que escanear y cada línea contiene al menos 2 y, a veces, cuatro partes de información. El problema es que cada línea puede ser 1 de 15-20 acciones diferentes.

en ruby, el código actual se parece a esto:

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

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

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

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

Esto es obviamente 'EL PROBLEMA'. Logré hacerlo más rápido (en C ++ con un margen del 50%) combinando todos los regexen en uno, pero esa no es la velocidad que necesito, ¡necesito analizar miles de estos archivos RÁPIDAMENTE!

En este momento los combino con expresiones regulares, sin embargo, esto es intolerablemente lento. Comencé con Ruby y salté a C ++ con la esperanza de obtener un aumento de velocidad y simplemente no está sucediendo.

Leí casualmente sobre PEG y análisis basado en gramática, pero parece algo difícil de implementar. ¿Es esta la dirección a la que debo dirigirme o hay diferentes rutas?

básicamente estoy analizando el historial de manos de póker y cada línea del historial de manos generalmente contiene 2-3 bits de información que necesito recopilar: quién era el jugador, cuánto dinero o qué cartas implicaba la acción ... etc.

Texto de muestra que debe analizarse:

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

Después de recopilar esta información, cada acción se convierte en un nodo xml.

En este momento, mi implementación ruby ??de esto es mucho más rápida que mi C ++, pero eso es un problema. Solo porque no he escrito en el código C por más de 4-5 años

ACTUALIZACIÓN: No quiero publicar todo el código aquí, pero hasta ahora mis manos / segundo tienen el siguiente aspecto:

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

Actualmente estoy probando Antlr para ver si podemos ir más lejos, pero a partir de ahora estoy muy contento con los resultados de Spirit.

Pregunta relacionada: Consultando eficientemente una cadena contra múltiples expresiones regulares.

Solución

Sugeriría

Boost Spirit o
Antlr si la gramática es compleja;
Xpressive si es un poco más simple,
Tokenizer y código hecho a mano si es trivial .

Buena suerte

Otros consejos

Boost.Spirit es una biblioteca fantástica que le permite realizar un análisis de analizador detallado, y desde el analizador se genera y compila directamente en su código, debe ser mucho más rápido que una solución calculada dinámicamente. La sintaxis se realiza principalmente con plantillas de expresión (un término elegante para muchos operadores sobrecargados), lo que significa que realmente los escribe directamente en su código.

Aquí hay una forma de hacerlo, si estaba 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 línea, el bucle PARSER primero intenta hacer coincidir una serie de dígitos seguidos de un límite de palabra. Esta coincidencia debe comenzar en el lugar donde quedó la última coincidencia (o el comienzo de la cadena en la primera coincidencia). Como m / \ G (\ d + \ b) / gcx usa el indicador c , si la cadena no coincide con esa expresión regular, perl no restablece pos () y la siguiente coincidencia comienza en la misma posición para probar un patrón diferente.

Ver La coincidencia de expresiones regulares puede ser simple y rápida (pero es lento en Java, Perl, PHP, Python, Ruby, ...) . Dependiendo del volumen de sus datos y de la complejidad de su expresión regular, podría ser más rápido escribir su propia lógica de análisis.

Leí casualmente sobre PEG y análisis basado en gramática, pero parece algo difícil de implementar. ¿Es esta la dirección a la que debo dirigirme o hay diferentes rutas?

Personalmente, he llegado a amar los PEG. Tal vez tomará un poco de tiempo sentirse cómodo con ellos, sin embargo, creo que son mucho más fáciles de mantener que es una victoria clara. Creo que el código de análisis es la fuente de muchos errores inesperados a medida que encuentra nuevos casos límite en las entradas. Las gramáticas declarativas con no terminales son más fáciles de actualizar para mí cuando esto sucede en comparación con el bucle y condiciona el código regex pesado. Nombrar es poderoso.

En Ruby hay Treetop , que es un generador de analizadores que utiliza PEG. Recientemente, me pareció bastante agradable reemplazar un analizador regex pesado escrito a mano con una gramática corta.

¿Se superponen las coincidencias de expresiones regulares? Es decir, cuando dos o más expresiones regulares coinciden con la misma línea, ¿siempre coinciden con diferentes partes de la línea (sin superposición)?

Si las coincidencias nunca se superponen, ejecute su búsqueda usando una expresión regular que combine las 15 expresiones regulares que tiene ahora:

regex1|regex2|regex3|...|regex15

Use grupos de captura si necesita poder determinar cuál de las 15 expresiones regulares coincidió.

Buscar sus datos una vez para una expresión regular larga será más rápido que buscarlos 15 veces. Cuánto más rápido depende del motor de expresiones regulares que esté utilizando y la complejidad de sus expresiones regulares.

Pruebe una prueba simple en Perl. Lea sobre el "estudio" función. Lo que podría intentar es:

Lea todo el archivo o una gran cantidad de líneas si estos archivos son muy grandes en una sola cadena
Agregue un número de línea al comienzo de cada línea a medida que avanza.
" estudio " la cuerda. Esto crea una tabla de búsqueda por carácter, puede ser grande.
Ejecute coincidencias de expresiones regulares en la cadena, delimitadas por líneas nuevas (use los modificadores de expresiones regulares mys). La expresión debe extraer el número de línea junto con los datos.
Establezca un elemento de matriz indexado por número de línea a los datos encontrados en esa línea, o haga algo aún más inteligente.
Finalmente puede procesar los datos almacenados en la matriz.

No lo he probado, pero puede ser interesante.

Otra idea si tiene un servidor quad o oct core para usar para esto.

Cree una canalización de procesamiento que divida el trabajo. La Etapa Uno podría cortar archivos en un juego o en cada mano, luego escribir cada uno en uno de los ocho tubos de la Etapa Dos que leen los datos, los procesan y producen resultados de alguna manera, probablemente a una base de datos en otra máquina.

En mi experiencia, estos diseños multiproceso basados ??en tuberías son casi tan rápidos y mucho más fáciles de depurar que los diseños multiproceso. También sería fácil configurar un clúster de máquinas utilizando sockets de red en lugar de tuberías.

Bien, esto aclara las cosas (historial de manos de póker). Supongo que está haciendo una herramienta de estadísticas (factor de agresión, fue a un enfrentamiento, puso voluntariamente $ en el bote, etc.). No estoy seguro de por qué necesitas velocidades excesivas para eso; incluso si está haciendo multitables con 16 mesas, las manos solo deben hacer cosquillas a un ritmo moderado.

No conozco a Ruby, pero en Perl haría una pequeña declaración de cambio, al mismo tiempo que obtenía las partes significativas en $ 1, $ 2, etc. En mi experiencia, esto no es más lento que hacer comparaciones de cadenas y luego dividiendo la línea con otros medios.

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

No creo que realmente puedas hacerlo más rápido. Ponga los cheques para las líneas que ocurren más en una primera posición (probablemente las declaraciones de pliegue) y aquellas que solo ocurren escasamente al final (comenzando con una nueva mano, " *** FASE SIGUIENTE *** " ).



 Si descubre que la lectura real del archivo es un cuello de botella, tal vez pueda echar un vistazo a los módulos que puede usar para direccionar archivos grandes; para Perl, me viene a la mente  Tie :: File . 

 Asegúrese de leer cada mano solo una vez. No lea todos los datos nuevamente después de cada mano, en su lugar, mantenga una tabla hash de las ID de manos ya analizadas.



	
		
	
	
			 Para un problema como este, simplemente cerraría los ojos y usaría un generador Lexer + Parser. Probablemente pueda superar eso con la optimización manual, pero es mucho más fácil usar un generador. Además, es mucho más flexible cuando la entrada cambia repentinamente.



	
		
			Licenciado bajo: CC-BY-SA con atribución
			No afiliado a StackOverflow