Expresiones regulares difusas

En mi trabajo he obtenido excelentes resultados con 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.Expresiones regulares difusas

Ahora tengo una necesidad de hacer coincidir cadenas con expresiones regulares simples como TV Schedule for \d\d (Jan|Feb|Mar|...). Esto significa que la cadena TV Schedule for 10 Jan debe devolver 0, mientras que T Schedule for 10. Jan debe devolver 2.

Esto se puede hacer generando todas las cadenas en la expresión regular (en este caso 100x12) y encontrar la mejor coincidencia, pero eso no es práctico.

¿Tiene alguna idea de cómo hacer esto de manera efectiva?

Fuente

2010-02-28 Thomas Ahle

Encontré el TRE library, costuras de bruja para poder hacer exactamente 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 acompaña 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 tiene

$ 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 toda tu propone.

Fuente

2010-03-04 10:54:24

¿Ha considerado usar un lexer?

Nunca he usado uno así que no puedo ser de mucha ayuda, ¡pero parece que encaja!

Fuente

2010-02-28 16:18:47

Creo que los lexers son más para tokenizar que para hacer coincidir. Si empiezo a dividir mi cadena, no podré reconocer los caracteres movidos de un token a otro. –

Puede que tenga que definir su problema como un problema de lexing/análisis, en lugar de como una expresión regular simple. Entonces podrías usar la distancia de Levenshtein en los tokens individuales. – Avi

Ya veo. Pero el enlace lexer que has enviado parece bastante determinista. ¿Qué sucede si en lugar de 'TV Schedule for 10 Jan' obtengo' TV Schedule for Jan 10'? Eso debería tener una distancia de 2, ya que se han transpuesto dos caracteres. Tal vez el lexer podría identificar subcadenas que parecen números o meses, pero entonces 'TV Schedule for Jan 10' o' TV Schedule for 10 Jan 2010' daría problemas. –

Here es un recurso sobre la pregunta que está haciendo. Es un poco bromista para una empresa. Más útil podría ser this paper. He visto una implementación inspirada en el documento que podría hacer una búsqueda difusa, parcial para un idioma especial (por ejemplo, árabe vs. inglés), en un conjunto de datos grande.

En general, no podrá hacer lo que ha preguntado. 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.

Fuente

2010-02-28 16:33:06 bmargulies

¿El primero parece estar en la coincidencia de cadena aproximada estándar? El segundo parece estar en búsquedas borrosas en un diccionario. ¿Eso probablemente podría usarse pensando en la expresión regular como un "diccionario de ficción"? –

Acabo de utilizar el regex module: 'Módulo de expresión regular alternativo, para reemplazar 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, consulte this resource.

Fuente

2013-04-12 15:46:39

Ver también: The Python regex (newer version, Oct '14) (busque "fuzzy" dentro del documento).

Si no eres un chico de Python (tampoco lo soy), tienes could compile tu código para 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) (buscar 'agrep performace'), pero que necesita para escribir POSIX expresiones regulares compatibles (búsqueda para '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) - algunos (más) limitaciones (por ejemplo, sin mirar hacia adelante/mirar hacia atrás)
difusa wuzzy (basado en Python) - vale la pena mirar, no se ha probado ...

Revise también:

'herramientas' regular-expressions.info

(lo siento por no poder publicar enlaces reales)

Fuente

2014-10-26 23:23:53

empecé a implementar una herramienta de Java llamada para Prex aproximada expresiones regulares. La herramienta determina hasta qué punto una cadena s es de búsqueda de una expresión regular r, es decir cómo se al menos requieren muchas inserciones, deleciones y sustituciones en s (costo mínimo) de tal manera que la cadena resultante s' es aceptable por 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.

Fuente

2016-09-18 12:36:36 Julian

Respuesta

Cuestiones relacionadas