Rematch: A novel regex engine for finding all matches
Loading...
Date
2024
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
En esta tesis presentamos el sistema REmatch para la extraccion de información. REmatch esta basado en un algoritmo de enumeración recientemente propuesto para evaluar expresiones regulares con variables de captura que soportan la semantica de encontrar todos los resultados. Se expone lo necesario para hacer que un algoritmo teóricamente óptimo funcione en la práctica. Como mostraremos, una implementación ingenua del algoritmo original tendría dificultades para lidiar con cargas de trabajo realistas. Dado lo anterior, desarrollamos un nuevo algoritmo y una serie de optimizaciones que hacen que REmatch sea tan o mas rápido que muchos motores RegEx populares, al mismo tiempo que puede devolver todos los resultados, una tarea con la que la mayoría de los otros motores suele tener problemas.
Description
Tesis (Master of Science in Engineering)--Pontificia Universidad Católica de Chile, 2024.
Keywords
Expresiones regulares, Document spanners, Extracción de información, Algoritmos de enumeración, Semántica de coincidencia completa