Wortähnlichkeiten und unscharfe Suche¶
Wörter können eine ähnliche Bedeutung haben, oder einfach nur ähnlich geschrieben werden. In dieser Lektion schauen wir uns diese letzte Ähnlichkeit an. Wortähnlichkeiten sind oft wichtig, um Schreibvarianten und fehlerhafte Schreibweisen zu erkennen und zu finden.
Wir betrachten zwei Maße für die Ähnlichkeit zwischen Wörtern: das n-Gram Overlap und die Levenshtein-Distanz.
n-Gram-Overlap¶
In der Lektion zu Sprachbestimmung haben wir Wörte in Trigramme zerlegt. Die Menge der Trigramme, aus denen ein Wort besteht, ist nicht ganz eindeutig, aber es gibt nur wenige (unterschiedliche) Wörter, die aus den gleichen Trigramme bestehen. Wenn zwei Wörter aus fast den gleichen Trigrammen aufgebaut sind, sind die Wörter sich in der Schreibweise natürlcih sehr ähnlich.
Zunächst kopieren wir die Funktion zur Extraktion der n-Gramme.
def ngram(string,n):
liste = []
if n < len(string):
for p in range(len(string) - n + 1) :
tg = string[p:p+n]
liste.append(tg)
return liste
Und testen diese, mit drei ähnlichen Wörtern: die Deutsche, Englische und Französische Schreibweise von Hannover . Wir fügen wieder ein Symbol für den Wortanfang und das Wortende ein, damit Wortanfang- und Ende ausreiched berücksichtigt werden. Als Vergleich nehmen wir als unähnliches Wort noch Hamburg dazu.
han_3_de = ngram('#Hannover$',3)
han_3_en = ngram('#Hanover$',3)
han_3_fr = ngram('#Hannovre$',3)
ham_3 = ngram('#Hamburg$',3)
print(han_3_de)
print(han_3_en)
print(han_3_fr)
print(ham_3)
Nun gibt es verschiedene Möglichkeiten, die Übereinstimmung zwischen zwei Mengen mit einer Zahl zu erfassen. Wir nehmen hier den Jaccard-Koeffizienten. Der Jaccard-Koeffizient von zwei Mengen $A$ und $B$ ist definiert als: $$ jaccard(A,B) = \frac{A \cap B}{A \cup B} $$
def jaccard(A,B):
schnitt = 0
for a in A:
if a in B:
schnitt += 1
vereinigung = len(A) + len(B) - schnitt
return float(schnitt)/float(vereinigung)
Wir testen:
print(jaccard(han_3_de,han_3_de))
print(jaccard(han_3_de,han_3_en))
print(jaccard(han_3_de,han_3_fr))
print(jaccard(han_3_de,ham_3))
Levenshtein-Distanz¶
Bei längeren Wörtern funktioniert der n-Gram Overlap sehr gut. Bei kurzen Wörtern kann ein unterschiedlicher Buchstabe in der Mitte des Wortes schon dazu führen, dass der n-Gram Overlap sehr gering ist. Unter anderem deswegen, brauchen wir für manchs Anwendungen andere Ähnlichkeitsmaße. Das bekannteste Maß ist sicherlich die Editier- oder Levenshtein-Distanz.
Die Levenshtein Distanz zwischen zwei Wörter, ist die Zahl der Editieroperationen, die notwendig ist, um das eine Wort in das andere zu ändern. Wir können verschiedene Grundoperationen annehmen. Typischerweise haben wir, einfügen (insert), tilgen (delete) und ersetzen (substitute).
Nun ist es oft leider nicht so einfach zu sehen welche Operationen notwendig sind. In vielen Fällen gibt es auch mehrere Möglichkeiten. Die Levenshtein-Distanz ist nun definiert als die kleinste Zahl der notwendigen Editieroperationen.
Im Internet finden Sie unzählige gute und ausführliche Tutorials dazu, wie man die Editierdistanz effizient findet. Die Erläuterung hier ist daher möglichst knapp gehalten.
Statt die Operationen zu zählen versuchen wir die beiden Wörter abzugleichen. Wir haben zwei Zeiger, die am Anfang vor jedem Wort stehen. Das Ziel ist es nun beide Zeiger bis zum Wortende vorzurücken und dabei möglichst wenig Strafpunkte zu sammeln. Wenn wir beide Zeiger gleichzeitig einen Buchstaben vorrücken, und dabei den gleichen Buchstaben lesen, bekommen wir keine Strafpunkte. Wenn wir unterschiedliche Buchstaben lesen, haben wir eine Ersetzung und bekommen einen Strafpunkt (oder in manchen Varianten zwei Strafpunkte). Rücken wir den ersten vor, lassen den zweiten aber stehen, haben wir eine Tilgung und bekommen einen Strafpunkt. Im umgekehrten Fall haben wir eine EInfügung und ebenfalls ein Strafpunkt.
Wir können nun jede Kombination von zwei Zeigerpositionen in einem Diagramm darstellen. Wenn es mehrere Möglichkeiten gibt, die Kombination zu erreichen, nehmen wir immer die mit den wenigsten Strafpunkten.
Schauen wir uns das mal an mit zwie Wörtern: Macht und Krach.
| k | r | a | c | h | ||
|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | |
| m | 1 | 1 | 2 | 3 | 4 | 5 |
| a | 2 | 2 | 2 | 2 | 3 | 4 |
| c | 3 | 3 | 3 | 3 | 2 | 3 |
| h | 4 | 4 | 4 | 4 | 3 | 2 |
| t | 5 | 5 | 5 | 5 | 4 | 3 |
Es gibt also maximal 3 Möglichkeiten eine Zelle zu erreichen: von Links, von Oben oder diagonal von links oben. In den ersten beiden Fällen muss immer ein Strafpunkt zu den bereits gesammelten Punkten adiert werden. Beim diagonalen erreichen der Zelle werden die Strafpunkte durch den Vergeich der Buchstaben bestimmt. Der Wert, der in der Zelle eingetragen wird, ist das Minimum der drei Möglichkeiten.
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)]
print(edit_distance('Macht','Krach'))
print(edit_distance('Gesichtet','Geschichte'))
Visualisierung¶
Wir können die Tabelle auch ausgeben. Das bringt zwar nichts für die Berechnung der Wortähnlichkeit, aber es macht das anschaulich, was genau passiert.
Damit wir das richtige Alignment visualisieren können, brauchen wir eine zweite Tabelle, in der wir speichern, aus welcher Richtung das beste Ergebnis erreicht wurde.
%matplotlib inline
import matplotlib.pylab as pl
def print_lev_table(x,y,tab,backpointer):
x = ' '+x
y = ' '+y
tab.insert(0,list(x))
for i in range(len(y)):
tab[i].insert(0,y[i])
pl.figure()
tb = pl.table(cellText=tab, loc=(0,0), cellLoc='center')
tc = tb.properties()['child_artists']
for cell in tc:
cell.set_height(1/(len(y)))
cell.set_width(1/(1+len(x)))
ax = pl.gca()
ax.set_xticks([])
ax.set_yticks([])
i,j= len(y)-2,len(x)-1
while (i,j) != (0,0):
tb._cells[i+1,j+1]._text.set_color('red')
i,j = backpointer[i][j]
tb._cells[1,1]._text.set_color('red')
def edit_distance_vis(v, w):
matrix = [[0 for j in range(len(w) + 1)] for i in range(len(v) + 1)]
backpointer = [[(0,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)
if matrix[i][j] == val3:
backpointer[i][j] = (i-1,j-1)
elif matrix[i][j] == val2:
backpointer[i][j] = (i,j-1)
elif matrix[i][j] == val1:
backpointer[i][j] = (i-1,j)
elif i > 0:
matrix[i][j] = matrix[i-1][j] + 1
backpointer[i][j] = (i-1,j)
elif j > 0:
matrix[i][j] = matrix[i][j-1] + 1
backpointer[i][j] = (i,j-1)
else:
matrix[i][j] = 0 #Die erste Zelle
print_lev_table(w,v,matrix,backpointer)
return matrix[len(v)][len(w)]
edit_distance_vis('Gesichtet','Geschichte')
Unscharfe Suche¶
Wir wissen jetzt, wie wir Wortähnlichkeiten berechnen, wenn wir zwei Wörter haben. Wie finden wir aber überhaupt ein ähnliches Wort? Wenn wir eine Liste mit deutschen Ortsnamen haben, wie finde ich dann Hannover , wenn ich nach Hanover suche?
Die Lösung ist einfach: wir bauen einen Trigramindex, in Python einfach ein Dictionary mit Trigrammen und Wörtern, in denen diese Trigramme vorkommen.
def build_tgindex(wortliste):
index = {}
for word in wortliste:
wordext = "#"+word.lower()+"$"
for i in range(len(wordext)-2):
tg = wordext[i:i+3]
tg_list = index.get(tg,[])
tg_list.append(word)
index[tg] = tg_list
return index
Von der Seite https://serwiss.bib.hs-hannover.de/frontdoor/index/index/docId/1028 können Sie eine Liste mit über 36000 Deutschen Ortsnamen herunterladen. Wir lesen nur die erste Spalte ein, und bauen daraus einen Trigramindex:
import codecs
f_ortsnamen = codecs.open('Corpora/Ortsnamen.txt','r','latin2')
ortsnamen = [zeile.split('\t')[0] for zeile in f_ortsnamen]
ortsnamen = list(set(ortsnamen)) #Hiermit werden alle doppelte namen entfernt.
f_ortsnamen.close()
tgindex = build_tgindex(ortsnamen)
Wir testen, ob es funktioniert hat:
print(tgindex['nov'])
print(tgindex['ünc'])
print(tgindex['düs'])
Für die Suche zerlegen wir das Suchwort ebenfalls in Trigrammen, und suchen nach allen Trigrammen im Index.
Damit die Menge der Kandidaten nicht zu groß wird, filten wir einige unwahrscheinleche Vorschläge direkt heraus. Namen die viel länger oder kürzer als der Suchterm ist berücksichtigen wir nicht. Die guten Kandidaten sind im Index für viele der Trigramme. Wir nehmen nur die. die wenigstens halb so oft gefunden werden als der am häufigsten gefundene.
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
#print(kandidaten('Munchen',tgindex))
print(kandidaten('Munich',tgindex))
print(kandidaten('Duesseldorf',tgindex))
print(kandidaten('Hanover',tgindex))
Scließlich müssen wir die Kandidaten mit dem Suchterm vergleichen.
def fuzy_find(suchterm,index):
kand = kandidaten(suchterm,index)
best = ''
kleinste_ed = len(suchterm)
for w in kand:
ed = edit_distance(w,suchterm)
if ed < kleinste_ed:
kleinste_ed = ed
beste = w
return beste
print(fuzy_find('Munchen',tgindex))
print(fuzy_find('Munich',tgindex))
print(fuzy_find('Duesseldorf',tgindex))
print(fuzy_find('Hanover',tgindex))
Der Vorschlag Türnich ist einfach Pech. Bei Düsseldorf haben wir das Problem, dass das Ersetzen von 'ü' durch 'u' genau so viele Strafpunkte gibt als das Ersetzen von 'ü' durch 'e'. Wir können aber unterschiedliche Strafpunkte für unterschiedliche Fehler geben.
def substitutionsfehler(b1,b2):
fehler = {('u','ü'):0.5,('ü','u'):0.5,('a','ä'):0.5,('ä','a'):0.5,('o','ö'):0.5,('ö','o'):0.5,}
if b1 == b2:
return 0
else:
return fehler.get((b1,b2),1)
print(fuzy_find('Duesseldorf',tgindex))
Die Strafpunkte haben wir uns jetzt einfach aus dem Daumen gesogen. Ideaerweise hätte man einen Datensatz mit fehlerhaften Ortsnamen und die gewünschte richtige Variante. Man könnte dann die Ersetzungen die häufig gebraucht werden geringer bestrafen und die Gewichte so wählen, dass möglichts viele Fehler richtig korrigiert werden.