python - separar - Encuentra la mejor coincidencia de subcadenas

separar palabra en letras python

Question

Estoy buscando una biblioteca o un método utilizando bibliotecas existentes ( difflib , fuzzywuzzy , python-levenshtein ) para encontrar la coincidencia más cercana de una cadena ( query ) en un texto ( corpus )

He desarrollado un método basado en difflib , donde divido mi corpus en ngrams de tamaño n (longitud de query ).

import difflib
from nltk.util import ngrams

def get_best_match(query, corpus):
    ngs = ngrams( list(corpus), len(query) )
    ngrams_text = [''''.join(x) for x in ngs]
    return difflib.get_close_matches(query, ngrams_text, n=1, cutoff=0)

funciona como quiero cuando la diferencia entre la consulta y la cadena coincidente son solo reemplazos de caracteres.

query = "ipsum dolor"
corpus = "lorem 1psum d0l0r sit amet"

match = get_best_match(query, corpus)
# match = "1psum d0l0r"

Pero cuando la diferencia es la eliminación de caracteres, no lo es.

query = "ipsum dolor"
corpus = "lorem 1psum dlr sit amet"

match = get_best_match(query, corpus)
# match = "psum dlr si"
# expected_match = "1psum dlr"

¿Hay una manera de obtener un tamaño de resultado más flexible (como para expected_match )?

EDITAR 1:

• El uso real de este script es para hacer coincidir las consultas (cadenas) con un resultado ocr desordenado.
• Como dije en la pregunta, el ocr puede confundir a los personajes e incluso extrañarlos.
• Si es posible, considere también el caso cuando falta un espacio entre las palabras.
• Una mejor coincidencia es la que no incluye caracteres de otras palabras que no sean las de la consulta.

EDIT 2:

La solución que uso ahora es extender los ngrams con (nk)-grams for k = {1,2,3} para evitar 3 eliminaciones. Es mucho mejor que la primera versión, pero no es eficiente en términos de velocidad, ya que tenemos más de 3 veces el número de ngrams para verificar. También es una solución no generalizable.

Answer 1

Esta función encuentra la mejor subcadena coincidente de longitud variable .

La implementación considera el corpus como una cadena larga, por lo tanto, evita tus preocupaciones con espacios y palabras sin separar.

Resumen del código: 1. Escanee el corpus en busca de valores de coincidencia en pasos de tamaño step para encontrar la ubicación aproximada del valor de coincidencia más alto, pos . 2. Encuentre la subcadena en la vecindad de pos con el valor de coincidencia más alto, ajustando las posiciones izquierda / derecha de la subcadena.

from difflib import SequenceMatcher

def get_best_match(query, corpus, step=4, flex=3, case_sensitive=False, verbose=False):
    """Return best matching substring of corpus.

    Parameters
    ----------
    query : str
    corpus : str
    step : int
        Step size of first match-value scan through corpus. Can be thought of
        as a sort of "scan resolution". Should not exceed length of query.
    flex : int
        Max. left/right substring position adjustment value. Should not
        exceed length of query / 2.

    Outputs
    -------
    output0 : str
        Best matching substring.
    output1 : float
        Match ratio of best matching substring. 1 is perfect match.
    """

    def _match(a, b):
        """Compact alias for SequenceMatcher."""
        return SequenceMatcher(None, a, b).ratio()

    def scan_corpus(step):
        """Return list of match values from corpus-wide scan."""
        match_values = []

        m = 0
        while m + qlen - step <= len(corpus):
            match_values.append(_match(query, corpus[m : m-1+qlen]))
            if verbose:
                print query, "-", corpus[m: m + qlen], _match(query, corpus[m: m + qlen])
            m += step

        return match_values

    def index_max(v):
        """Return index of max value."""
        return max(xrange(len(v)), key=v.__getitem__)

    def adjust_left_right_positions():
        """Return left/right positions for best string match."""
        # bp_* is synonym for ''Best Position Left/Right'' and are adjusted 
        # to optimize bmv_*
        p_l, bp_l = [pos] * 2
        p_r, bp_r = [pos + qlen] * 2

        # bmv_* are declared here in case they are untouched in optimization
        bmv_l = match_values[p_l / step]
        bmv_r = match_values[p_l / step]

        for f in range(flex):
            ll = _match(query, corpus[p_l - f: p_r])
            if ll > bmv_l:
                bmv_l = ll
                bp_l = p_l - f

            lr = _match(query, corpus[p_l + f: p_r])
            if lr > bmv_l:
                bmv_l = lr
                bp_l = p_l + f

            rl = _match(query, corpus[p_l: p_r - f])
            if rl > bmv_r:
                bmv_r = rl
                bp_r = p_r - f

            rr = _match(query, corpus[p_l: p_r + f])
            if rr > bmv_r:
                bmv_r = rr
                bp_r = p_r + f

            if verbose:
                print "/n" + str(f)
                print "ll: -- value: %f -- snippet: %s" % (ll, corpus[p_l - f: p_r])
                print "lr: -- value: %f -- snippet: %s" % (lr, corpus[p_l + f: p_r])
                print "rl: -- value: %f -- snippet: %s" % (rl, corpus[p_l: p_r - f])
                print "rr: -- value: %f -- snippet: %s" % (rl, corpus[p_l: p_r + f])

        return bp_l, bp_r, _match(query, corpus[bp_l : bp_r])

    if not case_sensitive:
        query = query.lower()
        corpus = corpus.lower()

    qlen = len(query)

    if flex >= qlen/2:
        print "Warning: flex exceeds length of query / 2. Setting to default."
        flex = 3

    match_values = scan_corpus(step)
    pos = index_max(match_values) * step

    pos_left, pos_right, match_value = adjust_left_right_positions()

    return corpus[pos_left: pos_right].strip(), match_value

Ejemplo:

query = "ipsum dolor"
corpus = "lorem i psum d0l0r sit amet"
match = get_best_match(query, corpus, step=2, flex=4)
print match
(''i psum d0l0r'', 0.782608695652174)

Un buen consejo heurístico es mantener siempre el step < len(query) * 3/4 , y flex < len(query) / 3 . También agregué sensibilidad al caso, en caso de que sea importante. Funciona bastante bien cuando empiezas a jugar con los valores de paso y flexión. Los valores de pasos pequeños dan mejores resultados pero demoran más en computarse. flex gobierna qué tan flexible se permite que sea la longitud de la subcadena resultante.

Importante tener en cuenta: Esto solo encontrará la primera mejor coincidencia, por lo que si hay varias coincidencias igualmente buenas, solo se devolverá la primera. Para permitir múltiples coincidencias, cambie index_max() para devolver una lista de índices para los n valores más altos de la lista de entrada, y adjust_left_right_positions() bucle sobre adjust_left_right_positions() para valores en esa lista.

Answer 2

Intentaría construir una plantilla de expresión regular a partir de la cadena de consulta. La plantilla podría utilizarse para buscar subcadenas que probablemente coincidan con la consulta. Luego use difflib o fuzzywuzzy para verificar si la subcadena coincide con la consulta.

Por ejemplo, una posible plantilla sería hacer coincidir al menos una de las dos primeras letras de la consulta, al menos una de las dos últimas letras de la consulta, y tener aproximadamente el número correcto de letras entre:

import re

query = "ipsum dolor"
corpus = ["lorem 1psum d0l0r sit amet",
          "lorem 1psum dlr sit amet",
          "lorem ixxxxxxxr sit amet"]

first_letter, second_letter = query[:2]
minimum_gap, maximum_gap = len(query) - 6, len(query) - 3
penultimate_letter, ultimate_letter = query[-2:]

fmt = ''(?:{}.|.{}).{{{},{}}}(?:{}.|.{})''.format
pattern = fmt(first_letter, second_letter,
              minimum_gap, maximum_gap,
              penultimate_letter, ultimate_letter)

#print(pattern) # for debugging pattern

m = difflib.SequenceMatcher(None, "", query, False)

for c in corpus:
    for match in re.finditer(pattern1, c, re.IGNORECASE):
        substring = match.group()
        m.set_seq1(substring)
        ops = m.get_opcodes()

        # EDIT fixed calculation of the number of edits
        #num_edits = sum(1 for t,_,_,_,_ in ops if t != ''equal'')
        num_edits = sum(max(i2-i1, j2-j1) for op,i1,i2,j1,j2 in ops if op != ''equal'' )
        print(num_edits, substring)

Salida:

3 1psum d0l0r
3 1psum dlr
9 ixxxxxxxr

Otra idea es utilizar las características de la ocr al construir la expresión regular. Por ejemplo, si el ocr siempre obtiene ciertas letras correctas, entonces, cuando alguna de esas letras esté en la consulta, use algunas de ellas en la expresión regular. O si el ocr confunde ''1'', ''!'', ''L'' e ''i'', pero nunca sustituye otra cosa, entonces si una de esas letras está en la consulta, use [1!il] en la expresión regular.

Answer 3

La ruta principal a una solución utiliza autómatas de estado finito (FSA) de algún tipo. Si desea un resumen detallado del tema, consulte esta dissertation (enlace PDF). Los modelos basados ​​en errores (incluidos los autómatas Levenshtein y los transductores, el primero de los cuales mencionó Sergei) son enfoques válidos para esto. Sin embargo, los modelos estocásticos, que incluyen varios tipos de enfoques de aprendizaje automático integrados con FSA, son muy populares en este momento.

Ya que estamos viendo distancias de edición (palabras mal escritas), el enfoque de Levenshtein es bueno y relativamente simple. Este documento (así como la disertación; también PDF) ofrece una descripción decente de la idea básica y también menciona explícitamente la aplicación a las tareas de OCR. Sin embargo, revisaré algunos de los puntos clave a continuación.

La idea básica es que desea crear un FSA que calcule tanto la cadena válida como todas las cadenas hasta una cierta distancia de error ( k ). En el caso general, este k podría ser infinito o el tamaño del texto, pero esto es mayormente irrelevante para OCR (si su OCR podría incluso devolver bl*h donde * es el resto del texto completo, le aconsejaría encontrar un mejor sistema de OCR). Por lo tanto, podemos restringir las expresiones regulares como bl*h del conjunto de respuestas válidas para la cadena de búsqueda, blah . Un k general, simple e intuitivo para su contexto es probablemente la longitud de la cadena ( w ) menos 2. Esto permite que b--h sea ​​una cadena válida para blah . También permite bla--h , pero eso está bien. Además, tenga en cuenta que los errores pueden ser cualquier carácter que especifique, incluidos los espacios (por lo tanto, la entrada de ''palabras múltiples'' es solucionable).

La siguiente tarea básica es configurar un transductor ponderado simple. Cualquiera de los puertos de OpenFST Python puede hacer esto ( aquí hay uno ). La lógica es simple: las inserciones y eliminaciones incrementan el peso, mientras que la igualdad incrementa el índice en la cadena de entrada. También puedes simplemente codificarlo como lo hizo el chico en el enlace de comentario de Sergei.

Una vez que tenga los pesos e índices asociados de los pesos, simplemente ordene y regrese. La complejidad computacional debe ser O (n (w + k)), ya que veremos w + k caracteres en el peor de los casos para cada carácter ( n ) en el texto.

Desde aquí, puedes hacer todo tipo de cosas. Usted podría convertir el transductor a un DFA. Puede paralelizar el sistema dividiendo el texto en w + k-grams, que se envían a diferentes procesos. Podría desarrollar un modelo de lenguaje o una matriz de confusión que defina qué errores comunes existen para cada letra en el conjunto de entrada (y de ese modo restringir el espacio de transiciones válidas y la complejidad de la FSA asociada). La literatura es vasta y sigue creciendo, por lo que probablemente haya tantas modificaciones como soluciones (si no más).

Esperemos que responda algunas de sus preguntas sin dar ningún código.