• autor.markus@mattzick.net
Internet & Computer
Wie schlau ist Google?

Wie schlau ist Google?

Wortformen (Stemming)

Sortiert man die Tabelle alphabetisch fällt auf, dass der Computer zwischen „keltisch“, „keltischen“ und „Kelten“ oder zwischen „Mensch“ und „Menschen“ unterscheidet. Grundsätzlich ist das zwar nicht falsch, trotzdem möchte man beim Suchen nicht jede Variante ausprobieren. Durch sogenanntes „Stemming“ werden Worte auf ihre Grundformen reduziert: Aus den erwähnten Begriffen wird „kelt“ bzw. „Mensch“. Diese Begriffe speichern wir in einer weiteren Tabelle und verknüpfen sie mit der Worttabelle. Was bringt uns das? Der Suchbegriff wird auf genau die gleiche Weise verarbeitet. Im ersten Schritt wird in der eigentlichen Worttabelle gesucht, im zweiten Schritt wird der Begriff auf seine Grundform reduziert und in der zweiten Tabelle gesucht (die Stemming-Tabelle verknüpfen wir mit der Worttabelle und können so z.B. die Summe der Vorkommen der Worte mit der gleichen Grundform bestimmen). Ob jetzt der wahrscheinlich häufiger vorkommende „gestemmte“ Begriff oder das identische Wort im Suchergebnis weiter oben rangiert, hängt von der Gewichtung der Suche selber ab.

Soundex (Zusammenfassen nach Klang)

Während der Mensch Namen wie Maier, Mayer, Meier und Meyer sofort auseinanderhalten kann, muss das einem Programm erst noch beigebracht werden. Dies geschieht mit der Hilfe von phonetischen Algorithmen, wobei Soundex da einer der bekanntesten ist. Der ist aber für die englische Sprache optimiert und daher nur bedingt für Deutsch anwendbar, weshalb wir uns jetzt kurz das Kölner Verfahren anschauen. Die einzelnen Buchstaben werden dabei durch Ziffern ersetzt. Welche Ziffer hängt dabei auch von der Position des Buchstabens ab: Das kann für den Wortanfang eine andere als im Wort sein oder auch von den Buchstaben davor bzw. dahinter abhängen.

Buchstabe Kontext Code
A, E, I, J, O, U, Y 0
H
B 1
P Nicht vor H
D,T Nicht vor C, S,Z 2
F,V,W 3
P Vor H
G,K,Q 4
C Im Anlaut vor A,H,K,L,O,Q,R,U,X
Vor A, H, K, O, Q, U, X außer nach S,Z
X Nicht nach C, K, Q 48
L 5
M,N 6
R 7
S,Z 8
C Nach S,Z
Im Anlaut außer vor A,H,K, L,O,Q,R,U,X
Nicht vor A,H,K,O,Q,U,X
D,T Vor C,S,Z
X Nach C,K,Q

Kölner Verfahren (http://de.wikipedia.org/wiki/K%C3%B6lner_Phonetik)

Wendet man dies auf die verschiedenen Maiers an, ergibt sich die Ziffernfolge 60007, doppelte Ziffern werden entfernt, was in diesem Fall aber nicht relevant ist, denn die 0 bleibt nur stehen, wenn sie am Anfang steht.Am Ende bleibt 67 von Maier übrig. 67 bleibt aber auch von Maurer, Mauer, nur, mir etc. übrig, solche Algorithmen sind also mit Vorsicht zu genießen.

Wie schon beim Stemming werden auch hier die Ziffernfolgen in einer Tabelle abgelegt und mit der Worttabelle verknüpft, der Suchbegriff wird ebenfalls umgewandelt und wenn einer der anderen Treffer wesentlich häufiger auftaucht als das genaue Suchwort, wird dem Suchenden „Meinten Sie …“ vorgeschlagen.

Präfix, Infix, Suffix, Wortfolgen und ganze Sätze

Während Stemming Worte mit der gleichen Grundform sucht, werden in einem Infix-Index Wortteile eingetragen. Die Absicht ist es z.B. auch innerhalb des Begriffes „Wortteil“ die Sichbegriffe „Wort“ oder „Teil“ zu finden, nebenbei würde auch noch „ort“ auffindbar sein. Da hier die Größe des Index ziemlich schnell enorm groß werden kann, wendet man auch hier Stoppwörter an oder definiert eine Mindestzeichenanzahl (oder auch beides).

Neben Worten und Wortteilen können auch Wortfolgen und ganze Sätze indiziert werden. Bei einzelnen Worten konnte der Text noch an den Leerzeichen getrennt werden, nun wir das bei jedem n-ten Leerzeichen gemacht und / oder eben an den Satzzeichen.

Und weiter?

Die verschiedenen Indizes sind gefüllt, außer der Häufigkeit wurden aber bisher keine Faktoren, die die Relevanz eines Suchergebnisses bestimmen definiert. Es wird geschätzt, dass Google derzeit etwa 200 verschiedene Faktoren zum Gewichten der Ergebnisse nutzt. Grob lässt sich zwischen On-Page- (Häufigkeit/Anteil des Begriffes auf der Seite, Seitentitel, Überschriften, Bildbeschreibungen, Meta-Angaben) und Off-Page-Faktoren (Backlinks) unterscheiden, wobei die Sortieralgorithmen ständig verändert werden. Bei der Suchmaschinenoptimierung wird versucht herauszufinden wie diese Algorithmen funktionieren und die Seiten werden dann dementsprechend optimiert … was genügend Stoff für einen eigenen Bericht ist.

Vielen Dank an Bea für den Beispielsatz.

Zum Weiterlesen: c’t-Archiv, 5/2009, Seite 186 (Suchtrupp – Programmierung einer Suchmaschine für die eigene Website)

http://de.wikipedia.org/wiki/Suchmaschine ,
http://de.wikipedia.org/wiki/Indexierung ,
http://de.wikipedia.org/wiki/Stemming ,
http://de.wikipedia.org/wiki/Soundex
http://de.wikipedia.org/wiki/Kölner_Verfahren ,
http://de.wikipedia.org/wiki/Suchmaschinenoptimierung

Dieser Beitrag erschien ursprünglich im Fragment 57, Februar 2011 (Mensa Ortsblatt für die Region Rhein-Main) und entstand aus einem Vortrag, den ich auf dem MBI-Roundtable Rhein-Main gehalten habe.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert