7

我正在对来自两个不同来源的一些文本进行 OCR。他们每个人都可能在不同的地方犯错，他们无法识别一个字母/一组字母。如果他们无法识别某些内容，则将其替换为 ?。例如，如果单词是Roflcopter，则一个来源可能会返回Ro?copter，而另一个来源可能会返回Roflcop?er。我想要一个函数来返回两个匹配项是否相等，允许多个?s. 例子：

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

到目前为止，我可以使用正则表达式将一个 OCR 与一个完美的 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

但是当他们都在不同的地方都有 ?s 时，这不起作用：

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

4 回答 4

2

感谢 Hamish Grubijan 提出这个想法。每一个 ？在我的 ocr 中，名称可以是 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)
于 2010-10-14T20:48:13.870 回答
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
>>>
于 2010-10-14T19:06:06.597 回答
1

这可能不是最 Pythonic 的选项，但如果?允许 a 匹配任意数量的字符，那么下面的回溯搜索就可以了：

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 的朴素匹配算法的改编（参见 Kernighan 对Beautiful Code的贡献，O'Reilly 2007 或 Jurafsky & Martin，Speech and Language Processing，Prentice Hall 2009）。

工作原理：该matcher函数递归遍历两个字符串/模式，从(0,0). 当它到达两个字符串的末尾时它会成功(len(a),len(b))；当遇到两个不相等的字符或一个字符串的结尾而另一个字符串中仍有字符要匹配时，它会失败。

当在任一字符串（比如）中matcher遇到变量（ ）时，它可以做两件事：跳过变量（匹配零个字符），或者跳过下一个字符但继续指向变量人物。?aba

于 2010-10-14T20:50:02.443 回答
1

使用Levenshtein 距离可能很有用。它将给出字符串彼此相似程度的值。如果它们的长度也不同，这也将起作用。链接页面有一些伪代码可以帮助您入门。

你最终会得到这样的东西：

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

因此，您可能有一个最大阈值，低于该阈值您说它们可能匹配。

于 2010-10-14T19:54:56.447 回答