7

私は2つの異なるソースからいくつかのテキストをOCRしています。彼らはそれぞれ、文字/文字のグループを認識しないさまざまな場所で間違いを犯す可能性があります。彼らが何かを認識しない場合、それは？に置き換えられます。たとえば、単語がである場合、Roflcopterあるソースはを返しRo?copter、別のソースはを返す可能性がありRoflcop?erます。2つの一致が同等であるかどうかを返し、複数?のを許可する関数が必要です。例：

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

これまでのところ、正規表現を使用して、1つの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

ええと、1つだけ？1文字に相当するので、パフォーマーとコンパクトな方法を提案できます。

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 に答える
2

このアイデアを提供してくれたHamishGrubijanに感謝します。毎日 ？私の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)
于 2010-10-14T20:48:13.870 に答える
1

レーベンシュタイン距離を使用すると便利な場合があります。文字列が互いにどの程度類似しているかの値を示します。これは、長さが異なる場合にも機能します。リンクされたページには、開始するためのいくつかの擬似コードがあります。

最終的には次のようになります。

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

したがって、それを下回ると一致する可能性があると言う最大しきい値を持つことができます。

于 2010-10-14T19:54:56.447 に答える
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)); もう一方の文字列に一致する文字がまだあるのに、2つの等しくない文字または一方の文字列の終わりに遭遇すると、失敗します。

いずれかの文字列（たとえば）で変数（）に遭遇matcherすると、2つのことを実行できます。変数をスキップする（ゼロ文字に一致する）か、の次の文字をスキップするが、の変数をポイントし続けることで、さらに一致させることができます。文字。?aba

于 2010-10-14T20:50:02.443 に答える