cách thanh lịch để khớp với hai chuỗi ký tự đại diện

Question

Tôi đang OCRing một số văn bản từ hai nguồn khác nhau. Mỗi người có thể phạm sai lầm ở những nơi khác nhau, nơi họ sẽ không nhận ra một lá thư/nhóm chữ cái. Nếu họ không nhận ra một cái gì đó, nó được thay thế bằng một? Ví dụ: nếu từ là Roflcopter, một nguồn có thể trả lại Ro?copter, trong khi một từ khác, Roflcop?er. Tôi muốn một hàm trả về hai kết quả trùng khớp có tương đương hay không, cho phép nhiều số ? s. Ví dụ:

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

Cho đến nay tôi có thể phù hợp với một OCR với một hoàn hảo bằng cách sử dụng biểu thức thông thường:

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

Nhưng điều này không hoạt động khi cả hai đều có s ở những nơi khác nhau:?

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

Answer 1

Nhờ Hamish Grubijan cho ý tưởng này. Mỗi ? trong tên ocr'd của tôi có thể là bất cứ nơi nào từ 0 đến 3 chữ cái.Những gì tôi làm là mở rộng mỗi chuỗi vào một danh sách các hoạt động mở càng tốt:

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

sau đó tôi mở rộng cả hai và sử dụng chức năng phù hợp với mình, mà tôi gọi là matchats:

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

trình như mong muốn:

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

---

Chức năng phù hợp:

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 

và chức năng mở rộng, nơi cartesian_product không chỉ rằng:

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

Vâng, miễn là một? tương ứng với một ký tự, sau đó tôi có thể đề xuất một phương thức thực hiện và một phương pháp đủ nhỏ gọn.

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

Chỉnh sửa: Phần B), não rắm miễn phí ngay bây giờ.

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

Sử dụng Levenshtein distance có thể hữu ích. Nó sẽ cung cấp một giá trị của các chuỗi tương tự như thế nào với nhau. Điều này sẽ hoạt động nếu chúng có độ dài khác nhau. Trang được liên kết có một số mã psuedocode để giúp bạn bắt đầu.

Bạn sẽ kết thúc với một cái gì đó như thế này:

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

Vì vậy, bạn có thể có một ngưỡng tối đa dưới đây mà bạn nói rằng họ có thể phù hợp.

Answer 4

Điều này có thể không phải là Pythonic nhất lựa chọn, nhưng nếu một ? được phép để phù hợp với bất kỳ số lượng ký tự, sau đó tìm kiếm backtracking sau thực hiện thủ thuật:

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ều này có thể thích nghi với điều kiện phù hợp hơn. Ngoài ra, để tiết kiệm không gian ngăn xếp, trường hợp cuối cùng (i+1,j+1) có thể được chuyển thành một giải pháp không đệ quy.

Chỉnh sửa: một số làm rõ thêm để phản hồi các phản ứng dưới đây. Đây là một sự thích nghi của một thuật toán phù hợp ngây thơ cho các regex/NFA đơn giản (xem phần đóng góp của Kernighan với Mã đẹp, O'Reilly 2007 hoặc Jurafsky & Martin, Xử lý lời nói và ngôn ngữ, Prentice Hall 2009).

Cách hoạt động: chức năng matcher theo cách đệ quy đi qua cả hai chuỗi/mẫu, bắt đầu từ (0,0). Nó thành công khi nó đạt đến cuối của cả hai chuỗi (len(a),len(b)); nó thất bại khi nó gặp hai ký tự không bằng nhau hoặc kết thúc của một chuỗi trong khi vẫn còn các ký tự để khớp trong chuỗi khác.

Khi matcher gặp một biến (?) trong cả hai chuỗi (nói a), nó có thể làm hai việc: hoặc bỏ qua các biến (phù hợp với zero ký tự), hoặc bỏ qua các nhân vật tiếp theo trong b nhưng giữ trỏ đến các biến trong a, cho phép nó khớp với nhiều ký tự hơn.