दो वाइल्डकार्ड तारों से मेल खाने के लिए सुरुचिपूर्ण तरीका

Question

मैं दो अलग-अलग स्रोतों से कुछ पाठ ओसीआर कर रहा हूं। वे प्रत्येक अलग-अलग जगहों पर गलतियां कर सकते हैं, जहां वे अक्षरों के एक पत्र/समूह को पहचान नहीं पाएंगे। अगर वे कुछ पहचान नहीं पाते हैं, तो इसे एक के साथ बदल दिया गया है? उदाहरण के लिए, यदि शब्द Roflcopter है, तो एक स्रोत Ro?copter लौटा सकता है, जबकि दूसरा, Roflcop?er। मुझे एक ऐसा फ़ंक्शन चाहिए जो दो मैचों के समतुल्य हो, चाहे ? एस के लिए अनुमति दे। उदाहरण:

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

विभिन्न स्थानों में लेकिन यह वे दोनों जब काम नहीं करता है रों:

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

अब तक मैं एक ओसीआर एक आदर्श एक के साथ नियमित अभिव्यक्ति का उपयोग करके मिलान कर सकते हैं?

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

Answer 1

इस विचार के लिए हामिश ग्रुबिजान को धन्यवाद। प्रत्येक ? मेरे ocr'd नामों में 0 से 3 अक्षरों से कहीं भी हो सकता है।

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

तो मैं दोनों का विस्तार और उसकी मिलान समारोह है, जो मैं matchats कहा जाता है का उपयोग करें:: मुझे क्या संभव विस्तार की एक सूची के लिए प्रत्येक स्ट्रिंग का विस्तार है

रूप

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

वर्क्स वांछित:

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

---

मिलान समारोह:

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 

और विस्तार समारोह, जहां cartesian_product करता है सिर्फ इतना है कि:

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

ठीक है, एक समय तक? एक चरित्र के अनुरूप है, तो मैं एक कलाकार और एक कॉम्पैक्ट पर्याप्त विधि का सुझाव दे सकता हूं।

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

संपादित करें: पार्ट बी), मस्तिष्क गोज़ मुक्त अब।

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

Levenshtein distance का उपयोग करना उपयोगी हो सकता है। यह एक मूल्य देगा कि स्ट्रिंग एक दूसरे के समान कैसे हैं। यह काम करेगा अगर वे अलग-अलग लंबाई भी हैं। लिंक शुरू करने के लिए आपको कुछ psuedocode है।

आप कुछ इस तरह से खत्म करेंगे:

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

तो तुम एक अधिकतम सीमा जिसके नीचे आप कहते हैं कि वे मेल खा सकता है हो सकता था।

Answer 4

यह विकल्पों में से सबसे pythonic नहीं हो सकता है, लेकिन एक ? वर्णों की संख्या मैच के लिए अनुमति दी है, तो निम्न उलटे पांव लौटने खोज चाल है:

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) 

इसे मिलान करने के लिए और अधिक कड़े होने के लिए अनुकूलित किया जा सकता है। इसके अलावा, स्टैक स्पेस को बचाने के लिए, अंतिम मामला (i+1,j+1) को गैर-पुनरावर्ती समाधान में परिवर्तित किया जा सकता है।

संपादित करें: नीचे प्रतिक्रियाओं के जवाब में कुछ और स्पष्टीकरण।/NFAs (सुंदर कोड, ओ रेली 2007 या Jurafsky & मार्टिन, वाणी और भाषा प्रसंस्करण को Kernighan के योगदान, अप्रेंटिस हॉल 2009 देखें) इस सरलीकृत regexes के लिए एक अनुभवहीन मिलान एल्गोरिथ्म का रूपांतरण है।

यह कैसे काम करता है: matcher फ़ंक्शन (0,0) से शुरू होने वाले स्ट्रिंग/पैटर्न दोनों के माध्यम से पुनरावर्ती चलता है। यह (len(a),len(b)) दोनों स्ट्रिंग्स के अंत तक पहुंचने पर सफल होता है; यह विफल रहता है जब यह दो असमान पात्रों या एक स्ट्रिंग के अंत का सामना करता है जबकि अन्य स्ट्रिंग में मिलान करने के लिए वर्ण अभी भी होते हैं।

जब matcher या तो स्ट्रिंग में एक चर (?) का सामना करना पड़ता (माना a), यह दो बातें कर सकते हैं: या तो चर (शून्य पात्रों मिलान) छोड़, या b में अगले वर्ण छोड़ लेकिन की ओर इशारा करते रखने a में चर, इसे और अधिक वर्णों से मेल करने की अनुमति देता है।