элегантный способ сопоставить две строки с подстановочными знаками

Question

Я распознаю текст из двух разных источников. Каждый из них может ошибаться в разных местах, где они не узнают букву / группу букв. Если они что-то не узнают, это заменяется на? Например, если слово Roflcopter, один источник может вернуть Ro?copter, а другой - Roflcop?er. Я хотел бы функцию, которая возвращает, могут ли два совпадения быть эквивалентными, учитывая несколько ? с. Пример:

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

Пока что я могу сопоставить одно OCR с идеальным, используя регулярные выражения:

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

Редактировать: Часть B), теперь свободен от мозгов.

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

Это может быть не самый 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) может быть преобразован в нерекурсивное решение.

Редактировать : еще несколько уточнений в ответ на приведенные ниже реакции. Это адаптация наивного алгоритма сопоставления для упрощенных регулярных выражений / NFA (см. Вклад Кернигана в Beautiful Code , O'Reilly 2007 или Jurafsky & Martin, Обработка речи и языка , Prentice Hall 2009).

Как это работает: функция matcher рекурсивно проходит по обоим строкам / шаблонам, начиная с (0,0). Успешно, когда он достигает конца обеих строк (len(a),len(b)); происходит сбой, когда встречаются два неравных символа или конец одной строки, в то время как в другой строке все еще есть символы для сопоставления.

Когда matcher встречает переменную (?) в любой строке (скажем, a), он может делать две вещи: либо пропустить переменную (совпадающую с нулевыми символами), либо пропустить следующий символ в b, но продолжайте указывать на переменную в a, позволяя ей соответствовать больше символов.

Answer 4

Использование расстояния Левенштейна может быть полезным. Это даст значение того, насколько строки похожи друг на друга. Это будет работать, если они тоже разной длины. На связанной странице есть некоторый psuedocode, с которого можно начать.

Вы получите что-то вроде этого:

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

Таким образом, вы можете иметь максимальный порог, ниже которого вы говорите, что они могут совпадать.