Sie haben jetzt Edit Distance (oder Levenshtein-Distanz), den Trigrammindex, Tokenisierung und Sprachmodelle kennengelernt. Damit kennen Sie alles, was Sie für eine gute Rechschreibkorrektur brauchen.
Voraussetzung für diese Lektion ist also:
Wenn ein Wort $w$ falsch geschrieben ist, möchten wir die wahrscheinlichste Korrektur $c$ wissen, also $argmax_c P(c|w)$. Wir wenden wieder den Satz von Bayes an und finden: $$ \begin{eqnarray} argmax_c P(c|w) & = & argmax_c \frac{P(c)P(w|c)}{P(w)}\\ & = & argmax_c P(c)P(w|c) \end{eqnarray} $$
Das heißt (und das wußten wir eigentlich schon), dass der Korrekturvorschlag abhängig ist vom falsch geschriebenem Wort und vom Kontext.
Insgesamt müssen wir also:
Die einfachste Art, Rechtschreibfehler festzustellen, ist das Nachschlagen von jedem Wort in einer Liste mit Wörtern. Für eine flektierende Sprache, wie das Deutsche, ist das leider nicht so einfach, da es insgesamt doch sehr viele Wortformen gibt.
Wir brauchen also eine Liste mit korrekt geschriebenen Wörtern. Wir nutzen in diesem Beispiel eine Liste mit den 10 000 häufigsten Wörtern aus einem Zeitungskorpus der Universität Leipzig. Die Datei können Sie von der folgenden Webseite herunterladen: http://pcai056.informatik.uni-leipzig.de/downloads/etc/legacy/Papers/top1000de.txt. Wir speichern diese Datei als Corpora/top10000de.txt und lesen alle einfache Wörter (also keine Phrasen, die aus mehreren Wörter bestehen)ein:
import codecs
wordfile = codecs.open('corpora/top10000de.txt','r','utf-8')
wordlist = []
for line in wordfile:
word = line.strip()
if ' ' not in word:
wordlist.append(word)
wordfile.close()
Leider sind sehr viele Wörter und Wortformen immer noch nicht in dieser Liste enthalten. Wir erweitern die Liste daher noch mit allen Wörtern, die minstestens 2 mal im Tiger-Korpus (siehe die Lektion zur Autovervollstädigung für die Download-URL) vorkommen:
import nltk
root = 'Corpora'
fileid = 'tiger.16012013.conll09'
columntypes = ['ignore','words','ignore','ignore','pos']
tiger_corpus = nltk.corpus.ConllCorpusReader(root,fileid,columntypes,encoding='utf8')
tigerdist = nltk.FreqDist(tiger_corpus.words())
wordlist_tiger = [w for w in tigerdist if tigerdist[w] > 1 and w not in wordlist]
#print len(wordlist_tiger)
wordlist.extend(wordlist_tiger)
Wir brauchen jetzt einen Text mit Fehlern, damit wir testen können, ob wir die Fehler finden und korrigieren können. Den Text, den wir nutzen, finden Sie im Internet hier: http://lbuchner.de/de/de_fehltxt/fehltxt1.htm . Dieser Text hat genau 10 Fehler.
text = '''Gefahr durch Computerspiele
Immer wieder hört man warnende Stimmen, die auf mögliche Gefaren durch Computerspiele hinweisen. Aber Computerspiele können nach Ansicht von Experten auch eine sinvolle Freizeitbeschäftigung für Kinder und Jugendliche sein. Nach einer neuen studie fördern viele Spiele die Denk- und Kombinationsfähigkeit sowie schneles Reaktionsvermögen. Besonders empfolen werden von Fachleuten Strategiespiele, bei denen Kinder Zusammenhänge lernen. Auch Autorennen und Aktionsspiele können positife Wirkung haben, denn sie helfen unter umständen Aggressivität abzubauen. Das logische Denkvermögen kann durch Detektivspiele gefördert werden.
Als besonders positiv wird bewertet, das Kinder durch die Spiele mit wichtigen Funktionen eines Computers vertraut werden. Spiele verstärken in der Regel Einstellungen und Verhaltensweisen. Vorsicht ist deshalb bei Spielen mit Gewaltdarstellungen aller art geboten. So können zum Beispiel brutale Spiele durchaus die Gewaltbereitschaft erhöhen. Deshalb darf man es nicht nur den Kindern überlaßen welche Spiele sie auswählen und wie viel Zeit sie vor dem Bildschirm verbringen.'''
Um festzustellen, ob ein Wort in unserer Wortliste steht, müssen wir den Text zunächst in Wörter aufteilen. Wir kommen mit der Python-Methode split() ziemlich weit, aber haben dan z.B. noch das Problem, dass Punkt und Komma am Wort geschrieben werden, aber nur bei Abkürzungen oder Ordinalzahlen dazugehören.
Das Paket nltk enthält Funktionen um einen Text in Sätze und Wörter aufzuteilen. Hiermit bekommen wir schnell sehr gut Ergebnisse.
import nltk
import re
sentences = nltk.sent_tokenize(text,language='german')
for sent in sentences:
tokens = nltk.word_tokenize(sent,language='german')
for tok in tokens:
if len(tok) > 1 and not re.match(r'^[0-9\-\.,]+$',tok) and not tok in wordlist and not tok.lower() in wordlist:
print(tok)
Wir sehen jetzt, dass schon das Erkennen von Fehlern nicht trivial ist:
Das zweite Problem können wir mit Statistik, als mit Sprachmodellen und ggf. mit Regeln lösen. Für das erste Problem müssen wir zunächst einen Algorithmus für die Kompositazerlegung schreiben!
Wir schreiben mal auf der Schnelle einen naivern Algorithmus zur Kompositazerlegung. Wir probieren alle Aufteilungen eines Wortes in zwei Teilen, bei denen beide Teile mindestens 4 Buchstaben lang sind, aus. Wenn der erste Teil im Lexikon steht, schauen wir ob der zweite auch in der Wortliste steht. Eventuell kan der zweite Teil mit einem Fugenelement anfangen, und müssen wir nur den Teil nach dem Fugenelement im Lexikon suchen.
import re
def compound(w):
if len(w) < 9:
return False
for i in range(4,len(w)-3):
if w[:i] in wordlist:
if w[i:].capitalize() in wordlist:
return True
elif re.match(r'n|s',w[i:]) and w[i+1:].capitalize() in wordlist:
return True
elif re.match(r'en',w[i:]) and w[i+2:].capitalize() in wordlist:
return True
return False
for sent in sentences:
tokens = nltk.word_tokenize(sent,language='german')
for tok in tokens:
if len(tok) > 1 and not re.match(r'^[0-9\-\.,]+$',tok) and not tok in wordlist and not tok.lower() in wordlist and not compound(tok) :
print(tok)
Es bleiben jetzt noch zwei Komposita übrig. Denkvermögen hat den Verbstamm Denk, der so nicht in der Wortliste steht, als ersten Bestandteil; Detektiv wurde nicht erkannt, da das Wort einfach nicht in der Liste steht.
Um für ein falsch geschriebenes Wort Korrekturkandidaten zu finden, brauchen wir einen Trigramm-Index.
Wir wandeln jedes Wort in Kleinbuchstaben um, bevor wir es indizieren, damit wir später möglichst viele Kandidaten finden und uns danach erst entscheiden müssen, was wir mit Groß- und Kleinschreibung machen.
def build_tg_index(words):
tgi = {}
for word in words:
wordext = "#"+word.lower()+"$"
for i in range(len(wordext)-2):
tg = wordext[i:i+3]
tg_list = tgi.get(tg,[])
tg_list.append(word)
tgi[tg] = tg_list
return tgi
tgindex = build_tg_index(wordlist)
print(tgindex['pts']) #zum testen
print(tgindex['#qu']) #zum testen
Jetzt suchen wir für ein unbekanntes Wort, alle Wörter mit gemeinsamen Trigrammen. Hierzu suchen wir für jedes Trigramm aus dem gesuchten Wort, alle Wörter, die dieses Trigramm ebenfalls haben. Die Wörter die häufig gefunden werden, sind jetzt Kandidaten für die Korrektur.
In sehr langen Wörtern kommen natürlich viele Trigramme vor. Wir beschränken uns daher auf Wörtern, die maximal doppelt so lang sind, wie das gesuchte Wort.
Wörter die viel weniger gemeinsame Trigramme haben, als der beste Kandidat sind auch uninteressant, und filtern wir ebenfalls heraus.
from collections import Counter
def kandidaten(word,index):
candidates = []
wordext = "#"+word.lower()+"$"
for i in range(len(wordext)-2):
tg = wordext[i:i+3]
words_with_tg = index.get(tg,[])
words_likely = [w for w in words_with_tg if len(word)/2 < len(w) < 2 * len(word)]
candidates.extend(words_likely)
gezaehlt = Counter(candidates)
(_,best) = gezaehlt.most_common(1)[0]
result = [v for (v,tg) in gezaehlt.most_common(10000) if tg > best/2]
return result
vorschlaege = kandidaten('Prehistory',tgindex)
print(vorschlaege)
print('\n')
vorschlaege = kandidaten('Gefaren',tgindex)
print(vorschlaege)
print('\n')
vorschlaege = kandidaten('enhalten',tgindex)
print(vorschlaege)
Jetzt können wir den Kandidaten suchen, der den geringsten Edit Distance zum unbekannten Wort hat, oder den, der nach dem vorangegangenem Wort am wahrscheinlichsten ist.
def substitutionsfehler(b1,b2):
if b1 == b2:
return 0
else:
return 1
def edit_distance(v, w):
matrix = [[0 for j in range(len(w) + 1)] for i in range(len(v) + 1)]
for i in range(len(v)+1):
for j in range(len(w)+1):
if i > 0 and j > 0:
val1 = matrix[i-1][j] + 1
val2 = matrix[i][j-1] + 1
val3 = matrix[i-1][j-1] + substitutionsfehler(v[i-1],w[j-1])
matrix[i][j] = min(val1, val2, val3)
elif i > 0:
matrix[i][j] = matrix[i-1][j] + 1
elif j > 0:
matrix[i][j] = matrix[i][j-1] + 1
else:
matrix[i][j] = 0 #Die erste Zelle
return matrix[len(v)][len(w)]
Wir können jetzt die Editierdistanz berechnen, wissen aber immer noch nicht, was $P(w|c)$ für ein richtig geschriebenes Wort $c$ und ein fehlerhaftes Wort $w$ ist.
Wenn wir davon ausgehen, dass alle Tippfehler unabhängig voneinander sind, ist $P(w|c)$ das Produkt der Wahrscheinlichkeiten aller Fehler die gemacht wurden. Genau genommen müssen wir diese Wahrscheinlichkeit auch noch multiplizieren mit allen Wahrscheinlichkeiten, dass auf den korrekten Buchstaben keinen Fehler aufgetreten ist.
Um die Wahrscheinlichkeiten für jeden Fahler zu ermitteln, müssten wir Fehler in einem großen korrigierten Korpus zählen. Da wir ein solches Korpus nich haben, machen wir eine ganz einfache und naive Abschätzung. (Hier sehen wir übrigens eine typische Situation, die es heute in vielen Bereichen gibt: die Algorithmen, die wir brauchen, sind leicht verständlich und frei zugänglich. Für gute Ergebnisse brauchen wir aber Daten, die nur einige große Konzerne, wie Microsoft oder Google besitzen.) In unserem nicht repräsentativen, kurzen Text, gab es 10 Fehler auf etwas 1000 Buchstaben. Die Wahrscheinlichkeit, dass ein Buchstabe falsch geschrieben wird, wäre demnach $\frac{1}{100}$ und die Wahrscheinlichkeit, dass ein Buchstabe korrekt geschrieben wird, $1 - \frac{1}{100}$. Es sind aber viele Fehler möglich. Wir nehmen einfach mal an, dass es für jeden Buchstaben 5 typische Fehler gibt, die eine nicht vernachlässigbare Wahrscheinlichkeit haben: Tilgung, Einfügung (eines zusätzlichen folgenden Buchstabens), und Ersetzung durch einen Buchstaben, der ähnlich klingt, oder auf der Tastatur neben dem Buchstaben liegt. Die Wahrscheinlichkeit für jeden konkreten Fehler ist jetzt also $\frac{1}{500}$.
Jetzt können wir für ein Wort $c$ und ein fehlerhaftes Wort $w$ und Editierdistanz $ed(w,c)$ berechnen:
$$ P(w|c) = \left(\frac{1}{500}\right)^{ed(w,c)} \cdot \left(1-\frac{1}{100}\right)^{|c|-ed(w,c)} $$Da es leichter ist mit Logarithmen von Wahrscheinlichkeiten rechnen, berechnen wir schließlich den Logarithmus von diesem Wert.
import math
def fehlerwahrsch(word,ed):
p_error = 1.0 / 500
p_correct = 0.99
p_w_1 = math.pow(p_error,ed) * math.pow(p_correct,len(word)-ed)
return math.log(p_w_1)
print(fehlerwahrsch('errichtet',1))
Wir stellen jetzte fest (probieren Sie das aus!), dass die Wahrscheinlichkeiten für längere Korrekturvorschläge kleiner sind! Das ist in Übereinstimmung mit unserem Modell: Die Summe $P(w|c)$ für alle möglichen falsch geschriebenen Varianten muss ja $1$ ergeben. Je länger, das Wort $w$, desto mehr falsch geschriebenen Varianten gibt es!
Wir können jetzt schon mal etwas zusammenbauen und das Wort mit der kleinsten Editierdistanz als Korrektur vorschlagen:
def korrigiere(w):
vorschlaege = kandidaten(w,tgindex)
bestes_wort = ''
beste_wahrscheinlichkeit = -10000
for c in vorschlaege:
ed = edit_distance(w,c)
p = fehlerwahrsch(c,ed)
#print c, '\t',ed , '\t', p
if p > beste_wahrscheinlichkeit:
beste_wahrscheinlichkeit = p
bestes_wort = c
return bestes_wort
print(korrigiere('Gefaren'))
print(korrigiere('enhalten'))
Wir müssen jetzt noch ein Sprachmodell aus der vorigen Übung integrieren. Wir nehmen das Mxiture-Model: Wenn wir eine Folge von Wörter $w_1w_2$ haben, berechnen wir die Wahrscheinlichkeit für $w_2$ als dem Mittelwert von $P(w_2 \mid w_1)$ und $P(w_2)$. Für die Wahrscheinlichkeit auf ein einzelnes Wort nutzen wir ein einfaches back-off-Modell: wenn ein Wort im Trainingscorpus nicht vorkommt, tun wir so alsob es ein halbes Mal vorkam, ohne andere Wahrscheinlichkeiten anzupassen.
def unigram_model(corpus):
counts = {}
nrOfWords = 0
# Zunächst zählen wir die Wörter
for s in corpus.sents():
for w in s:
w = w #.lower()
nrOfWords += 1
f = counts.get(w,0)
counts[w] = f+1
# Jetzt müssen wir die Häufigkeiten durch die Gesamtzahl der Wörter dividieren, um Wahrscheinlichkeiten zu bekommen
# Bilde Liste von Paare bestehend aus Wort und Wahrscheinlichkeit.
# Daraus kann ein Dictionary erzeugt werden.
model = dict([(wrd,float(frq)/float(nrOfWords)) for (wrd,frq) in counts.items()])
return nrOfWords, model
#---------------------------------------------------------------------------------
# Ein Bigramm-modell ist dictionary mit Wörtern und Unigramm-Modelle!
#---------------------------------------------------------------------------------
def bigram_model(corpus):
counts = {}
for s in corpus.sents():
s.insert(0,u'@s')
for i in range(len(s)-1):
w1 = s[i] #.lower()
w2 = s[i+1] #.lower()
cnt_w1 = counts.get(w1,{})
f = cnt_w1.get(w2,0)
cnt_w1[w2] = f+1
counts[w1] = cnt_w1
for w, cnts in counts.items():
nr_of_w = sum(cnts.values())
for w2,f in cnts.items():
cnts[w2] = float(f)/float(nr_of_w)
return counts
nr_of_words, model1 = unigram_model(tiger_corpus)
model2 = bigram_model(tiger_corpus)
Für die Wahrscheinlichkeit einer Wortfolge, nehmen wir das erste Wort der Folge als gegeben an. Das erste Wort hat also eine Wahrscheinlichkeit von $1$. Wir müssen jetzt die Wahrscheinlichkeiten nach unserem Mixture-Modell für die nachfolgenden Wörtern miteinande multiplizieren, um die Wahrscheinlichkeiten der Wortfolge zu bekommen.
Anstatt die Wahrscheinlichkeiten zu multiplizieren, addieren wir die Logatithmen der Wahrscheinlichkeiten.
Man merke $$ \begin{align*} \ &p_1 \cdot p_2 = p_3\\ \Leftrightarrow \ &\log(p_1) + \log(p_2) = \log(p_3) \end{align*} $$
def log_prob(ugmodel,bgmodel,sent):
LogProb = 0
ug_backoff = 0.5 / float(nr_of_words)
for i in range(len(sent)-1):
w1 = sent[i] #.lower()
w2 = sent[i+1] #.lower()
P = 0.5 * ugmodel.get(w2,ug_backoff)
if w1 in bgmodel:
P += 0.5 * bgmodel[w1].get(w2,0)
LogProb += math.log(P)
return LogProb
Wir probieren unser Modell mal aus: welches Wort ist ine iner Folge von 3 Wörtern die wahrscheinlichere Korrektur?
print(log_prob(model1,model2,[u'mögliche','Gefahren','durch']))
print(log_prob(model1,model2,[u'mögliche','Haaren','durch']))
Schließlich kombinieren wir alles:
def korrigiere(w,left,right):
vorschlaege = kandidaten(w,tgindex)
bestes_wort = ''
beste_wahrscheinlichkeit = -10000
for c in vorschlaege:
ed = edit_distance(w,c)
pf = fehlerwahrsch(c,ed)
pl = log_prob(model1,model2,[left,c,right])
p = pf + pl
#print c, '\t', ed , '\t', p , '\t', pf, '\t', pl
if p > beste_wahrscheinlichkeit:
beste_wahrscheinlichkeit = p
bestes_wort = c
return bestes_wort
print(korrigiere('Gefaren',u'mögliche','durch'))
print(korrigiere('enhalten','Liste','.')) # "Das Wort ist nicht in der Liste enhalten."
print(korrigiere('Gefaren',u'Wand','.'))
print(korrigiere('schere',u'die','zwischen'))
print(korrigiere('schere',u'eine','Krise'))
Das Ergebnis ist weniger schön als es aussieht: Das Bigramm-Modell trägt wenig bei: Edit Distance ist entscheidend und das Unigramm-Modell hilft ab und zu etwas.
Wir testen zum Schuß aber noch den ganzen Text:
for sent in sentences:
tokens = nltk.word_tokenize(sent,language='german')
for i in range(len(tokens)):
tok = tokens[i]
if len(tok) > 1 and not re.match(r'^[0-9\-\.,]+$',tok) and not tok in wordlist and not tok.lower() in wordlist and not compound(tok) :
if i > 0:
davor = tokens[i-1]
else:
davor = u'@s'
if i < len(tokens)-1:
danach = tokens[i+1]
else:
danach = '.'
correct = korrigiere(tok,davor,danach)
print("(" + davor + ") " + tok + " (" + danach + ") --> " + correct)
Ohne Weltwissen und ohne ein tiefes Verständnis des Textes, sehen wir hier als Mensch schon direkt welche Korrekturvorschläge richtig, und welche falsch sind. D.h. der Algorithmus kann noch verbessert werden.
Wir brauchen: