elegante Weise, zwei wildcarded Zeichenketten zu entsprechen

Question

Ich OCRing etwas Text von zwei verschiedenen Quellen. Sie können an verschiedenen Orten Fehler machen, wo sie einen Buchstaben/eine Gruppe von Buchstaben nicht erkennen. Wenn sie etwas nicht erkennen, wird es durch ein? Ersetzt. Wenn das Wort z. B. Roflcopter lautet, gibt eine Quelle möglicherweise Ro?copter zurück, während eine andere lautet. Ich möchte eine Funktion, die zurückgibt, ob zwei Übereinstimmungen gleichwertig sein können und mehrere ? s zulassen. Beispiel:

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

Bisher kann ich mit einem perfekten einem einer OCR entsprechen, indem mithilfe von regulären Ausdrücken:

>>> 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 

Aber das funktioniert nicht, wenn sie beide haben s an verschiedenen Orten:

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

Answer 1

Danke an Hamish Grubijan für diese Idee. Jeden ? in meinen ocr'd Namen kann überall von 0 bis 3 Buchstaben sein.Was ich tue, ist jede Zeichenfolge in eine Liste von möglichen Erweiterungen erweitern:

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

dann erweitere ich beide und seine Matching-Funktion verwenden, die ich matchats genannt:

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

Arbeiten wie gewünscht:

>>> 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 

---

Die Anpassungsfunktion:

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 

und die Maximierungsfunktion, wo cartesian_product genau das tut:

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

Nun, so lange wie einer? entspricht einem Zeichen, dann kann ich eine performante und eine kompakt genug Methode vorschlagen.

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 
>>> 

Edit: Teil B), Gehirn-Furz jetzt frei.

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

die Levenshtein distance verwenden, kann nützlich sein. Es gibt einen Wert dafür, wie ähnlich die Strings zueinander sind. Dies funktioniert auch, wenn sie unterschiedliche Längen haben. Die verlinkte Seite hat einen Pseudocode, um Sie zu starten.

Sie werden mit etwas am Ende wie folgt:

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

So könnte man einen maximalen Schwellenwert haben, unter dem Sie sagen, sie entsprechen kann.

Answer 4

dies nicht die Pythonic von Optionen sein könnte, aber wenn ein ? darf eine beliebige Anzahl von Zeichen übereinstimmen, dann suchen die folgenden Rückzieher macht den Trick:

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) 

Dies kann angepasst werden, um stringenter in was zu entsprechen. Um Stapelspeicher zu sparen, kann der letzte Fall (i+1,j+1) außerdem in eine nicht rekursive Lösung umgewandelt werden.

Edit: einige weitere Klärung in Reaktion auf die Reaktionen unten. Dies ist eine Adaption eines naiven Matching-Algorithmus für eine vereinfachte Regexes/NFAs (siehe Kernighan contrib zu Schöne-Code, O'Reilly 2007 oder Jurafsky & Martin, Sprachverarbeitung, Prentice Hall 2009).

Wie es funktioniert: die matcher Funktion rekursiv durchläuft beide Strings/Muster, beginnend bei (0,0). Es gelingt, wenn es das Ende beider Strings erreicht (len(a),len(b)); Es schlägt fehl, wenn zwei ungleiche Zeichen oder das Ende einer Zeichenfolge gefunden werden, während noch Zeichen in der anderen Zeichenfolge übereinstimmen.

Wenn matcher eine Variable trifft (?) in entweder String (sagen wir a), kann es zwei Dinge tun: entweder überspringen über die Variable (passend Null-Zeichen) oder in b über das nächste Zeichen überspringen, sondern halten die Zeige Variable in a, so dass es mehr Zeichen zuordnen kann.