pattern - regex syntax
Expresiones regulares borrosas (6)
¿Has considerado usar un lexer ?
Nunca he usado uno así que no puedo ser de mucha ayuda, ¡pero parece que encaja!
En mi trabajo, con excelentes resultados, utilicé algoritmos de coincidencia de cadenas aproximados, como la distancia Damerau-Levenshtein, para hacer que mi código sea menos vulnerable a los errores ortográficos.
Ahora tengo la necesidad de hacer coincidir cadenas con expresiones regulares simples, como el TV Schedule for /d/d (Jan|Feb|Mar|...) . Esto significa que el TV Schedule for 10 Jan cadena TV Schedule for 10 Jan debe devolver 0 mientras que el T Schedule for 10. Jan debe devolver 2.
Esto podría hacerse generando todas las cadenas en la expresión regular (en este caso, 100x12) y encontrar la mejor coincidencia, pero eso no resulta práctico.
¿Tienes alguna idea de cómo hacer esto de manera efectiva?
Empecé a implementar una herramienta Java llamada prex para la coincidencia aproximada de expresiones regulares. La herramienta determina hasta qué punto una cadena s coincide con una expresión regular r , es decir , cuántas inserciones, eliminaciones y sustituciones en s son al menos necesarias (costo mínimo) de modo que la cadena resultante s '' es aceptable para r . Si está interesado, puede consultar el código de https://github.com/julianthome/prex . Estaría muy feliz de obtener algunos comentarios. Tenga en cuenta que el enfoque sigue siendo un poco lento, pero actualmente estoy incorporando algunas heurísticas para mejorar su rendimiento.
Encontré la biblioteca TRE , que parece ser capaz de hacer exactamente una coincidencia difusa de expresiones regulares. Ejemplo: http://hackerboss.com/approximate-regex-matching-in-python/ . Sin embargo, solo admite inserción, eliminación y sustitución. Sin transposición Pero supongo que eso funciona bien.
Probé la herramienta agrep de acompañamiento con la expresión regular en el siguiente archivo:
TV Schedule for 10Jan
TVSchedule for Jan 10
T Schedule for 10 Jan 2010
TV Schedule for 10 March
Tv plan for March
y consiguió
$ agrep -s -E 100 ''^TV Schedule for /d/d (Jan|Feb|Mar)$'' filename
1:TV Schedule for 10Jan
8:TVSchedule for Jan 10
7:T Schedule for 10 Jan 2010
3:TV Schedule for 10 March
15:Tv plan for March
Muchas gracias por todas sus sugerencias.
Solo uso el módulo regex : '' Módulo alternativo de expresión regular, para reemplazar a re''. Proporciona la familiaridad de re pero incluye opciones para la coincidencia difusa, junto con varias otras mejoras en re .
Para los binarios de Windows, vea este recurso .
Ver también: la expresión regular de Python (versión más reciente, Oct ''14 ) (busque "difusa" dentro del documento).
Si no eres un chico de Python (tampoco lo soy), podrías compilar tu código en C (exe / dll). Entonces usted podría usar su dll incluso desde el viejo vb6 (y similares).
Otras bibliotecas para elegir:
- TRE / agrep (''clásico, bueno, viejo y rápido) (busca'' agrep performace ''), pero necesitas escribir POSIX compatible con expresiones regulares (búsqueda de'' expresiones regulares info posix '') Por supuesto, todas las bibliotecas / ejemplos que usan TRE tienen esta limitación (busque ''hackerboss matching correspondence regex en python''). Para datos masivos: busque ''Una implementación rápida de CUDA del algoritmo de agrep''.
- FREJ (Java): algunas (más) limitaciones (por ejemplo, sin mirar hacia adelante / mirar hacia atrás)
- fuzzy-wuzzy (basado en Python) - vale la pena mirar, no probado ...
Busque también para:
- ''Comparación_de_regular_expression_engines''
- ''regular-expressions.info herramientas''
(perdón por no poder publicar enlaces reales)
Here hay un recurso sobre la pregunta que está haciendo. Es un poco bromista para una empresa. Más útil podría ser este documento . He visto una implementación inspirada en el documento que podría hacer una búsqueda difusa, sesgada para un lenguaje especial (por ejemplo, árabe vs. inglés), en un gran conjunto de datos.
En general, no podrás hacer lo que preguntaste. Puede hacer una búsqueda regexp difusa reemplazando caracteres con clases de equivalencia, o puede buscar en una base de datos para coincidencias cercanas definidas por la distancia de Levenshtein. Intentar expandir el (n) DFA detrás de una expresión regular para incluir coincidencias cercanas por distancia se volvería rápidamente imposible.