manera elegante de hacer coincidir dos cadenas comodín

Question

Estoy OCRing algo de texto de dos fuentes diferentes. Pueden cometer errores en diferentes lugares, donde no reconocerán una letra/grupo de letras. Si no reconocen algo, se reemplaza con un? Por ejemplo, si la palabra es Roflcopter, una fuente puede devolver Ro?copter, mientras que otra, Roflcop?er. Me gustaría una función que devuelva si dos coincidencias pueden ser equivalentes, permitiendo múltiples ? s. Ejemplo:

match("Ro?copter", "Roflcop?er") --> True 
match("Ro?copter", "Roflcopter") --> True 
match("Roflcopter", "Roflcop?er") --> True 
match("Ro?co?er", "Roflcop?er") --> True 

Hasta ahora no puede coincidir con uno de OCR con un perfecto mediante el uso de expresiones regulares:

>>> def match(tn1, tn2): 
    tn1re = tn1.replace("?", ".{0,4}") 
    tn2re = tn2.replace("?", ".{0,4}") 

    return bool(re.match(tn1re, tn2) or re.match(tn2re, tn1)) 

>>> match("Roflcopter", "Roflcop?er") 
True 
>>> match("R??lcopter", "Roflcopter") 
True 

Pero esto no funciona cuando los dos tienen s en diferentes lugares:?

>>> match("R??lcopter", "Roflcop?er") 
False 

Answer 1

Gracias a Hamish Grubijan por esta idea. Cada ? en mis nombres ocultos puede estar entre 0 y 3 letras.Lo que hago es ampliar cada cuerda a una lista de posibles expansiones:

>>> list(expQuestions("?flcopt?")) 
['flcopt', 'flcopt@', 'flcopt@@', 'flcopt@@@', '@flcopt', '@flcopt@', '@flcopt@@', '@flcopt@@@', '@@flcopt', '@@flcopt@', '@@flcopt@@', '@@flcopt@@@', '@@@flcopt', '@@@flcopt@', '@@@flcopt@@', '@@@flcopt@@@'] 

luego se expanden tanto y utilizar su función de emparejamiento, que llamé matchats:

def matchOCR(l, r): 
    for expl in expQuestions(l): 
     for expr in expQuestions(r): 
      if matchats(expl, expr): 
       return True 
    return False 

Obras como se desee:

>>> matchOCR("Ro?co?er", "?flcopt?") 
True 
>>> matchOCR("Ro?co?er", "?flcopt?z") 
False 
>>> matchOCR("Ro?co?er", "?flc?pt?") 
True 
>>> matchOCR("Ro?co?e?", "?flc?pt?") 
True 

---

La función de emparejamiento:

def matchats(l, r): 
    """Match two strings with @ representing exactly 1 char""" 
    if len(l) != len(r): return False 
    for i, c1 in enumerate(l): 
     c2 = r[i] 
     if c1 == "@" or c2 == "@": continue 
     if c1 != c2: return False 
    return True 

y la función de expansión, donde cartesian_product hace precisamente eso:

def expQuestions(s): 
    """For OCR w/ a questionmark in them, expand questions with 
    @s for all possibilities""" 
    numqs = s.count("?") 

    blah = list(s) 
    for expqs in cartesian_product([(0,1,2,3)]*numqs): 
     newblah = blah[:] 
     qi = 0 
     for i,c in enumerate(newblah): 
      if newblah[i] == '?': 
       newblah[i] = '@'*expqs[qi] 
       qi += 1 
     yield "".join(newblah) 

Answer 2

Bueno, siempre y cuando uno? corresponde a un personaje, entonces puedo sugerir un rendimiento y un método lo suficientemente compacto.

def match(str1, str2): 
    if len(str1) != len(str2): return False 
    for index, ch1 in enumerate(str1): 
     ch2 = str2[index] 
     if ch1 == '?' or ch2 == '?': continue 
     if ch1 != ch2: return False 
    return True 

---

>>> ================================ RESTART ================================ 
>>> 
>>> match("Roflcopter", "Roflcop?er") 
True 
>>> match("R??lcopter", "Roflcopter") 
True 
>>> 
>>> match("R??lcopter", "Roflcop?er") 
True 
>>> 

Editar: Parte B), sin cerebro-pedo ahora.

def sets_match(set1, set2): 
    return any(match(str1, str2) for str1 in set1 for str2 in set2) 

---

>>> ================================ RESTART ================================ 
>>> 
>>> s1 = set(['a?', 'fg']) 
>>> s2 = set(['?x']) 
>>> sets_match(s1, s2) # a? = x? 
True 
>>> 

Answer 3

Uso de la Levenshtein distance pueden ser útiles. Dará un valor de cuán similares son las cadenas entre sí. Esto funcionará si son longitudes diferentes, también. La página enlazada tiene algún código psuedo para comenzar.

que va a terminar con algo como esto:

>>> match("Roflcopter", "Roflcop?er") 
1 
>>> match("R??lcopter", "Roflcopter") 
2 
>>> match("R?lcopter", "Roflcop?er") 
3 

lo que podría tener un umbral máximo por debajo del cual se dice que pueden igualar.

Answer 4

esto podría no ser el más Pythonic de opciones, pero si se le permite al ? para que coincida con cualquier número de caracteres, entonces la búsqueda después de dar marcha atrás funciona el truco:

def match(a,b): 
    def matcher(i,j): 
     if i == len(a) and j == len(b): 
      return True 
     elif i < len(a) and a[i] == '?' \ 
      or j < len(b) and b[j] == '?': 
      return i < len(a) and matcher(i+1,j) \ 
       or j < len(b) and matcher(i,j+1) 
     elif i == len(a) or j == len(b): 
      return False 
     else: 
      return a[i] == b[j] and matcher(i+1,j+1) 

    return matcher(0,0) 

Esto se puede adaptar para ser más estricto en lo que se combina. Además, para ahorrar espacio en la pila, el caso final (i+1,j+1) se puede transformar en una solución no recursiva.

Editar: más aclaraciones en respuesta a las siguientes reacciones. Esta es una adaptación de un algoritmo de coincidencia ingenuo para expresiones regulares/NFA simplificados (ver contrib de Kernighan a Beautiful Code, O'Reilly 2007 o Jurafsky & Martin, Speech and Language Processing, Prentice Hall 2009).

Cómo funciona: la función matcher recorre recursivamente ambas cuerdas/patrones, comenzando en (0,0). Tiene éxito cuando alcanza el final de ambas cadenas (len(a),len(b)); falla cuando encuentra dos caracteres desiguales o el final de una cadena, mientras que todavía hay caracteres para unir en la otra cuerda.

Cuando matcher encuentra una variable (?) en alguna de las cadenas (por ejemplo a), puede hacer dos cosas: o bien pasar por alto la variable (juego cero caracteres), o saltar sobre el siguiente carácter de b pero mantenga apuntando a la variable en a, lo que le permite hacer coincidir más caracteres.