regex - Expresiones regulares borrosas

perl fuzzy-comparison

Question

Estoy buscando una forma de hacer una coincidencia difusa usando expresiones regulares. Me gustaría usar Perl, pero si alguien puede recomendar cualquier forma de hacerlo, sería útil.

Como ejemplo, quiero hacer coincidir una cadena con las palabras "Nueva York" precedidas por un número de 2 dígitos. La dificultad viene porque el texto es de OCR de un PDF, así que quiero hacer una coincidencia difusa. Me gustaría hacer coincidir:

12 New York
24 Hew York
33 New Yobk

y otras coincidencias "cercanas" (en el sentido de la distancia Levenshtein), pero no:

aa New York
11 Detroit

Obviamente, necesitaré especificar la distancia permisible ("borrosidad") para la coincidencia.

Según lo entiendo, no puedo usar el módulo String::Approx Perl para hacer esto, porque necesito incluir una expresión regular en mi coincidencia (para que coincida con los dígitos anteriores).

Además, debo señalar que este es un ejemplo muy simplificado de lo que realmente estoy tratando de hacer, así que no estoy buscando un enfoque de fuerza bruta.

Editado para agregar:

De acuerdo, mi primer ejemplo fue muy simple. No quise que la gente se colgara de los dígitos anteriores, disculpe el mal ejemplo. Aquí hay un mejor ejemplo. Considera esta cadena:

ASSIGNOR, BY MESHS ASSIGN1IBNTS, TO ALUSCHALME&S MANOTAC/rURINGCOMPANY, A COBPOBATlOH OF DELAY/ABE.

Lo que esto realmente dice es:

ASSIGNOR, BY MESNE ASSIGNMENTS, TO ALLIS-CHALMERS MANUFACTURING COMPANY, A CORPORATION OF DELAWARE

Lo que necesito hacer es extraer la frase "ALUSCHALME & S MANOTAC / RURINGCOMPANY" y "DELAY / ABE". (Me doy cuenta de que esto puede parecer una locura. Pero soy optimista.) En general, el patrón se verá más o menos así:

/Assignor(, by mesne assignments,)? to (company name), a corporation of (state)/i

donde la coincidencia es borrosa.

Answer 1

¿ Intentó utilizar el módulo String :: Approx de Jarkko en CPAN? Tiene el algoritmo de agrep , pero es mucho más lento que el de Udi.

Answer 2

¿Ha considerado una prueba de dos etapas, utilizando expresiones regulares para aplicar el requisito de [0-9]{2,2} (.*) , Luego captura el texto restante y hace una coincidencia difusa en él? Intente pensar en el problema como una intersección de una expresión regular y una cadena difusa.

Answer 3

Aunque especificó perl, hay un algoritmo útil integrado en R que implementa las distancias de edición de Levenshtein.

agrep()

Este comando también permite el uso de cualquier expresión regular o patrón para que coincida. Yo recomendaría que lo mires. http://stat.ethz.ch/R-manual/R-devel/library/base/html/agrep.html

Answer 4

Bueno, puedes restringir tus candidatos con Text::Levenshtein para obtener la distancia de edición y la reducción por comparación hasta el límite.

Pero otra idea es que puede tomar la forma correcta y crear un hash de casi fallos apuntando a la forma adecuada para que esos también se conviertan en candidatos.

Para las expresiones regulares, posiblemente tendría que usar las secciones de código experimental, tal vez algo como esto:

m/ (?i: [new] | /p{Alpha} (?{ $misses++ }) ){2,4}
   /s+
  (?i: [york] | /p{Alpha} (?{ $misses++ }) ){3,5}
 /x

Aunque en este caso, probablemente tendrías que tener una expresión regular por valor adecuado. Probablemente quieras una bandera que indique cuándo fallaste tu objetivo.

Answer 5

Los regexes tienen reglas específicas, no están diseñados para hacer lo que quieres. Va a ser mucho más fácil hacer dos pases. Usa una expresión regular para quitar los números y luego usa un módulo para cerrar tu partida.

Algo como esto (suponiendo que su entrada sea líneas de un archivo)

while( my $line = <$fh> ) {
    chomp $line;

    # do we have digits?
    if( $line =~ /^/d+/ ) {
         # removes spaces and digits from the beginning of the line
         $line =~ s/^[/d/s]*//g;

         # use your module to determine if you have a match in the remaining text.
         if( module_match ) {
             # do something
         }
         else {
             #no match
         }
    }
    else {
        # no match
    }
}

Answer 6

Podría intentar usar algo como Web 1T 5-gram Version 1 y un enfoque de maximización de verosimilitud condicional.

Si no recuerdo mal, el Capítulo 14 de Beautiful Data está dedicado a este conjunto de datos y cómo usarlo para detectar errores ortográficos, etc.

Answer 7

Regla de oro: cuando tienes que ir al desbordamiento de la pila y preguntar "¿Cómo puedo hacer X en una sola expresión regular?" deberías considerar hacer X con algo más que una sola expresión regular.

En función de sus ediciones, haría algo como esto:

while(<>) {
  chomp;
  if(/assignor, by (/w+) (/w+), to (/w+), a (/w+) of (/w+)/i) {
    # now use String::Approx to check that $1, $2, $3, $4, and $5 match
  } else {
    warn "Errors!/n";
  }
}

No te estoy dando todo aquí. No hice que el bit ", by (/w+) (/w+)" opcional para simplificar la expresión regular para que pudieras obtener la esencia. Para hacerlo, probablemente necesite recurrir a capturas con nombre y al grupo (?:) no captura. No tenía ganas de profundizar en todo eso, solo quería ayudarte a entender cómo abordaría esto.

Recuerde: si tiene que preguntar "¿Cómo lo hago todo en una sola expresión regular?" deberías dejar de intentar hacerlo todo en una sola expresión regular.

Answer 8

Separe el problema en dos partes:

1. Haga coincidir el número de dos dígitos.
2. Fuzzily coincide el residuo contra ''Nueva York''.

En el ejemplo, usted sabe que ''Nueva York'' consiste en 2 palabras; es posible que pueda aprovechar eso para eliminar alternativas como ''Detroit'' (pero no necesariamente ''San Francisco'') con mayor facilidad.

Incluso podría usar '' String::Approx '' después de todo, aunque menciona:

... los módulos Text :: Levenshtein y Text :: LevenshteinXS en CPAN. Ver también Text :: WagnerFischer y Text :: PhraseDistance.

(Mi Perl no pudo encontrar Text :: PhraseDistance a través de CPAN; los otros están disponibles e instalan correctamente).

Answer 9

Si tiene un patrón que desea encontrar la mejor coincidencia con una colección de texto , puede probar la distancia de q-gramo . Es bastante fácil de implementar y adoptar para necesidades especiales.

Su segunda descripción en realidad fue útil aquí, porque el patrón y los textos deberían ser bastante largos. La distancia de q-gram no funciona bien con palabras como "York", pero si su patrón típico es una dirección completa, eso debería estar bien.

Pruébalo así:

• transforma tus textos y patrones en un juego de caracteres reducido, como solo mayúsculas , stripping, wordifying (un espacio entre palabras) todos los símbolos reemplazados por "#" o algo así.
• elija una longitud de q-gramo, para trabajar con. Pruebe con 3 o 2. Llamamos a esto q=3 .
• que, construya un qgram-profile de cada texto:
• dividir cada texto en q-palabras, es decir. NEW_YORK convierte en [NEW, EW_, W_Y, _YO, ORK] , almacena esto con cada texto.
• si buscas tu patrón entonces, haces lo mismo con tu patrón,
• recorre tu base de datos de qgram de texto y
  • contar para cada patrón / par de texto cuántos qgram son iguales.
  • cada golpe aumentará el puntaje en 1.
• los textos con los puntajes más altos son tus mejores éxitos .

Si lo hiciste, puedes modificar este algoritmo de la siguiente manera:

• añada todos sus textos (y también el patrón antes de la búsqueda), con caracteres especiales q-1 , de modo que incluso sus palabras cortas obtendrán un perfil decente. Por ejemplo, New York convierte en ^^NEW YORK$$ .
• Incluso puedes jugar reemplazando todas las consonantes con "x" y las vocales con "o", y así sucesivamente. Juega con un par de clases de personajes de esta manera, o incluso crea súper símbolos reemplazando grupos de personajes por otros, es decir, CK se convierte en K , o SCH se convierte en $ .
• Al aumentar la puntuación con un qgram-hit, puede ajustar el valor de 1 por otras cosas, como la diferencia de longitud de texto frente a patrón .
• almacene 2 gramos y 3 gramos ambos, y al contar, pese diferente.

Tenga en cuenta que este algoritmo en la forma básica descrita aquí no tiene un buen tiempo de ejecución durante la búsqueda, es decir, O(|T|*|P|) (con |T| y |P| las longitudes totales de su texto y patrón ). Esto se debe a que describí que recorre todos sus textos y luego su patrón . Por lo tanto, esto solo es práctico para una base de textos de tamaño medio. Si piensa un poco, puede crear una estructura de índice avanzada sobre los q-grams (tal vez usando hashtables), por lo que esto podría ser práctico también para grandes textos -bases.