Kann ich in Python mit einer Genauigkeit von Prozent einen "String enthält X" machen?

Question

Ich muss OCR auf einen großen Textblock durchführen und überprüfen, ob er einen bestimmten String enthält. Aufgrund der Ungenauigkeit des OCR muss ich überprüfen, ob er etwas Ähnliches wie eine ~85% Übereinstimmung für den String enthält.

Zum Beispiel könnte ich einen Textblock OCR, um sicherzustellen, dass er nicht keine Informationen verfügbar enthält, aber der OCR könnte n0 inf0rmation verfügbar sehen oder eine Anzahl von Zeichen falsch interpretieren.

Gibt es einen einfachen Weg, dies in Python zu tun?

Answer 1

Wie von gauden gepostet, ist SequenceMatcher in difflib ein einfacher Weg. Verwendung von ratio(), gibt einen Wert zwischen 0 und 1 zurück, der der Ähnlichkeit zwischen den beiden Zeichenfolgen entspricht, aus den Dokumenten:

Wo T die Gesamtzahl der Elemente in beiden Sequenzen ist und M die Anzahl der Übereinstimmungen, dies ist 2.0*M / T. Beachten Sie, dass dies 1.0 ist, wenn die Sequenzen identisch sind, und 0.0, wenn sie nichts gemeinsam haben.

Beispiel:

>>> import difflib
>>> difflib.SequenceMatcher(None,'no information available','n0 inf0rmation available').ratio()
0.91666666666666663

Es gibt auch get_close_matches, das für Sie nützlich sein könnte. Sie können einen Distanzschwellenwert angeben und es gibt alle Übereinstimmungen innerhalb dieser Distanz von einer Liste zurück:

>>> difflib.get_close_matches('unicorn', ['unicycle', 'uncorn', 'corny', 
                              'house'], cutoff=0.8)
['uncorn']
>>> difflib.get_close_matches('unicorn', ['unicycle'  'uncorn', 'corny',
                              'house'], cutoff=0.5)
['uncorn', 'corny', 'unicycle']

Aktualisierung: um eine teilweise Teilfolgenübereinstimmung zu finden

Um nahe Übereinstimmungen mit einer dreiwörtigen Sequenz zu finden, würde ich den Text in Wörter aufteilen, sie dann in dreiwörtige Sequenzen gruppieren und dann difflib.get_close_matches anwenden, wie folgt:

import difflib
text = "Hier ist der Text, den wir versuchen, übereinzustimmen, um die dreiwörtige Sequenz n0 inf0rmation available zu finden. Ich frage mich, ob wir es finden werden?"    
wörter = text.split()
drei = [' '.join([i,j,k]) for i,j,k in zip(wörter, wörter[1:], wörter[2:])]
print difflib.get_close_matches('no information available', drei, cutoff=0.9)
#Ergebnis:
['n0 inf0rmation available']

Answer 2

Das SequenceMatcher-Objekt im Standardbibliotheksmodul difflib gibt Ihnen direkt ein Verhältnis:

Answer 3

Sie könnten die Levenshtein-Distanz berechnen. Hier ist eine Python-Implementierung: http://pypi.python.org/pypi/python-Levenshtein/

Answer 4

Ich kenne keine verfügbare Python-Bibliothek, die das von Haus aus machen würde, aber du könntest eine finden (oder eine C- oder C++-Bibliothek finden und einen Python-Wrapper dafür schreiben).

Du kannst auch versuchen, deine eigene Lösung zu entwickeln, basierend entweder auf einem "brute force" Zeichen-für-Zeichen-Vergleich, mit Regeln, die die "Nähe" zwischen zwei gegebenen Zeichen definieren und die "Genauigkeit" basierend auf diesen Regeln berechnen (dh "o" => "0" : 90% Genauigkeit, "o" => "w" : 1% Genauigkeit, usw), oder mit komplexerer KI (wenn du nicht mit KI vertraut bist, könnte dich das Buch "Programming Collective Intelligence" starten, trotz der etwas schlechten Implementierungsbeispiele).

Answer 5

Nur um fraxels Antwort zu erweitern, ermöglicht dies das Auffinden beliebig langer Zeichenfolgen. Entschuldigung für das schlechte Format, SO ist schwer. Die Genauigkeit ist der Abschneidewert in findWords

def joinAllInTupleList(toupe):
#joinAllInTuple( [("hello", "world"),("face","book")]) = ['hello world', 'face book']
result=[]
for i in toupe:
    #i ist das Tupel selbst
    carry = " "
    for z in i:
        #z ist ein Element von i
        carry+=" "+z

    result.append(carry.strip())
return result

def findWords(text,wordSequence):

#setup
words = text.split(" ")

#erhalte eine Liste von Untermengen basierend auf der Länge von wordSequence
#d.h. erhalte alle Teilfolgen der Länge wordSequence in text!

result=[]
numberOfWordsInSequence = len(wordSequence.strip().split(" ")) 
for i in range(numberOfWordsInSequence):
    result.append(words[i:])

# print 'result',result
c=zip(*result)

# print 'c',c
#verbinde jedes Tupel zu einem String
joined = joinAllInTupleList(c)

return difflib.get_close_matches(wordSequence, joined, cutoff=0.72389)