20
Der Nucleus einer Suchmaschine Oder: Wie funktionieren indexbasierte Text Retrieval Systeme? BarCamp Darmstadt 2010 Stefan Antoni [email protected] @Suchkultur auf Twitter

Der Nucleus einer Suchmaschine

Embed Size (px)

DESCRIPTION

 

Citation preview

Page 1: Der Nucleus einer Suchmaschine

Der Nucleus einer Suchmaschine

Oder: Wie funktionieren indexbasierte

Text Retrieval Systeme?

BarCamp Darmstadt 2010Stefan [email protected]@Suchkultur auf Twitter

Page 2: Der Nucleus einer Suchmaschine

Um was soll es hier gehen?

● Was leisten Suchmaschinen für den Benutzer?

● Welche Daten speichert die Suchmaschine und welche speichert sie nicht?● Was sind Metadaten?● Was sind Stoppwörter?

● Wie findet eine Suchmaschine?● Was ist ein invertierter Index?

Page 3: Der Nucleus einer Suchmaschine

Wovon solltet ihr schon Ahnung haben?

Ihr solltet schon mal eine Websuche bedient haben ;-)

Page 4: Der Nucleus einer Suchmaschine

Welche Themen müssen draußen warten?

● Crawling & Feeding sowie die damit verbundenen Processing-Techniken

● Anfragesprachen und Query Processing● Webtech● Linguistik und NLP (Natural Language

Processing)● Ranking-Algorithmen● Search Federation & Enterprise Search

Page 5: Der Nucleus einer Suchmaschine

Kann ich im Verlauf Fragen stellen?

Page 6: Der Nucleus einer Suchmaschine

Ja!

Page 7: Der Nucleus einer Suchmaschine

Was mir wichtig ist

● Es wäre toll, wenn ich am Ende sagen kann: „Das war nicht mein Vortrag, sondern ein interessanter Dialog“

● Diese Folien wurden mit der heissen Nadel gestrickt

→ sie werden Ungereimtheiten enthalten● Wer welche findet darf mich gerne darauf

aufmerksam machen bzw. mich korrigieren

Page 8: Der Nucleus einer Suchmaschine

Was ist eine Suchmaschine (nicht)?

● Ein Programm zum schnellen Finden von Dingen

● z. B. Dokumente in Textform● Keine Datenbank!

● Die Suchmaschine speichert keine Kopie des gesuchten Dokuments

● Eine „Verweismaschine“ → Sie verweist auf den Aufbewahrungsort des gesuchten Dokuments

● Ein „Metadatenfresser“ → Die Maschine weiß mehr über ein Dokument, als das Dokument über sich selbst

● Ein „Sortierer“, der Dokumente nach unterschiedlichen Kriterien sortieren kann (Ranking)

Page 9: Der Nucleus einer Suchmaschine

Verweise und Metadaten

● Verweise sind allgemein bekannt (aus „dem Web“)● Ein Verweis sieht im Web z. B. so aus:

http://www.suchkultur.de/blog/suchmaschinen/was-ist-ein-invertierter-index

● Ein Verweis ist selbst schon ein Metadatum:● Er ist ein Identifikationsmerkmal für ein bestimmtes

Dokument● Er stellt einen vollständigen Pfad zum Dokument dar

– Der Pfad selbst lässt Rückschlüsse über eine gewisse Ordnungsstruktur zu

● Er sagt, welches Übertragungsprotokoll für den Zugrif verwendet werden soll und kennt den zuständigen Server

Page 10: Der Nucleus einer Suchmaschine

Noch mehr Metadaten

● Typische Metadaten, die für die Suche interessant sind:

● Alle „sinntragenden“ Wörter aus dem Text des Dokuments → Namen, Tätigkeiten, Eigenschaften, Zahlen, uvm. – Aber: Keine Stoppwörter wie → der, die, das, eine,

ein, und, doch, oder, an, von, in […]

– Typische Stoppwortliste (DE): ~1000 Wörter

● Und beliebig viel mehr:– Geodaten, Zeitstempel & Zeitreihen, Autoren,

Schlagworte (tags), Dokumentlänge, Teasertext, Zusammenfassung, Verweise auf andere Dokumente, Anzahl der Wörter,

Page 11: Der Nucleus einer Suchmaschine

Wie speichert man den Kram ab?

● In einem invertierten Index → dem Nucleus einer Suchmaschine

● Ähnlich wie das Schlagwortverzeichnis in einem Buch

● Sortierte Liste (z. B. alphabetisch)● Nur sinntragende Wörter● Keine Stoppwörter

Page 12: Der Nucleus einer Suchmaschine

Ein Beispiel zu Veranschaulichung

Wir haben drei Textdateien mit Zitaten:

Text: "Wir wissen, wo du bist. Wir wissen wo du warst. Wir wissen mehr oder weniger worüber du nachdenkst."

Autor: Eric E. SchmidtText: "[…] Man kann ohne Angst vor Übertreibung von einer „Generation Google“ sprechen, deren Umgang mit Wissen und Information nachhaltig von der Suchmaschine beeinflusst wird. [...]“

Autor: Malte Herwig

Titel: Eliten in einer egalitären Welt

Seiten: 188

Datum: 2005

Text: „[...] Die Erfindung der Buchdruckerkunst macht dem menschlichen Verstande zwar Ehre, doch verliert sie sehr, wenn man sie mit der Erfindung der Buchstaben vergleicht. [...]“

Autor: Thomas Hobbes

Titel: Leviathan

Titel (lang): Leviathan (or the Matter, Forme and Power of a Commonwealth Ecclesiastical and Civil)

Page 13: Der Nucleus einer Suchmaschine

Der passende Index

● Wir haben 3 heterogene Dokumente und 6 verschiedene Metadaten

● Metadaten sind: Text, Zitation, Titel, Titel (lang), Autor, Seiten und Datum

● Wir benötigen einen Index mit mindestens 6 spezialisierten Feldern, die zu diesen Datentypen passen

– Ein sogenanntes Index-Schema

– Ziel: Die Suchmaschine kann passend zu Anfragen wie „Gib mir alles von Malte Herwig (Autor) über die Generation Google (Text) aus dem Jahr 2005 (Datum)“ Dokumente liefern.

● Die Suchmaschine weiß dann in welchen Feldern des Indexes sie suchen muss

● Durch diese Vorstrukturierung kann die Suchmaschine schnell & gezielt die gesuchten Informationen „zusammenkehren“

● Sie weiß sozusagen „wo sie hingreifen muss“

Page 14: Der Nucleus einer Suchmaschine

Warum keine Datenbank?

●Eine Suchmaschine macht bei der Abfrage keine „teuren“ JOINs

●Die Abfragesprache ist auf die Suche optimiert (kein „LIKE <suchterm>“)

●Die zu speichernden Daten sind oft unstrukturiert und/oder lückenhaft (bedingt viele „NULL“-Werte)

●Die Schreibgeschwindigkeit ist nicht so wichtig, dafür aber die Lesegeschwindigkeit

●ACID (Atomicity, Consistency, Isolation & Durability) ist nicht wichtig, denn:→ Atomare Operationen sind unnötig, da nur Lesezugrife stattfinden→ Dokumente sind naturgemäß eher inkonsistente Datenstrukturen→ Isolation (=locking) killt die Performance !! und ist nicht gewünscht→ Aktualität ist wichtiger als Dauerhaftigkeit, denn: Alte Verweise verschwinden (dead links z. B.), und neue Verweise kommen hinzu. Dokumente ändern sich außerdem inhaltlich und werden neu prozessiert

●Zweiteilung der Indexerstellung und der Indexabfrage→ Während ein Index erstellt wird, ist er nicht abfragbar

●Während ein Index abfragbar ist, wird separat sein Nachfolger erstellt→ Häufig passiert das auf einem separaten Indexer-System

Page 15: Der Nucleus einer Suchmaschine

Und jetzt ein Beispiel

… zum mitdenken und Fragen stellen.

Page 16: Der Nucleus einer Suchmaschine

Indexierung – Stoppwörter entfernen

Wir haben drei Textdateien mit Zitaten

Text: "Wir wissen, wo du bist. Wir wissen wo du warst. Wir wissen mehr oder weniger worüber du nachdenkst."

Autor: Eric E. Schmidt ← Ein feststehender Name bzw. eine „Phrase“

Text: "[…] Man kann ohne Angst vor Übertreibung von einer „Generation Google“ sprechen, deren Umgang mit Wissen und Information nachhaltig von der Suchmaschine beeinflusst wird. [...]“

Autor: Malte Herwig

Titel: Eliten in einer egalitären Welt

Seiten: 188

Datum: 2005

Text: „[...] Die Erfindung der Buchdruckerkunst macht dem menschlichen Verstande zwar Ehre, doch verliert sie sehr, wenn man sie mit der Erfindung der Buchstaben vergleicht. [...]“

Autor: Thomas Hobbes

Titel: Leviathan

Titel (lang): Leviathan (or the Matter, Forme and Power of a Commonwealth Ecclesiastical and Civil)

Page 17: Der Nucleus einer Suchmaschine

Optional: Linguistische Deflexion

Rückführung der sinntragenden Wörter auf Stammformen

Text: Wissen (3), nachdenken (1),

Autor: Eric E. Schmidt ← Ein feststehender Name bzw. „Phrase“

Text: Angst (1), Übertreibung (1), „Generation Google“ (1), Umgang (1), Wissen (1), Information (1), Nachhaltigkeit (1), Suchmaschine (1), Beeinflussung (1)

Autor: Malte Herwig

Titel: Eliten in einer egalitären Welt

Seiten: 188

Datum: 2005

Text: Erfindung (2), Buchdruckerkunst (1), menschlich (1), Verstand (1), Ehre (1), Verlust (1),

Autor: Thomas Hobbes

Titel: Leviathan

Titel (lang): Leviathan (or the Matter, Forme and Power of a Commonwealth Ecclesiastical and Civil)

Page 18: Der Nucleus einer Suchmaschine

Und abspeichern!

So sieht der gefüllte Index am Ende aus:

Angst → Doc_2 (1)

Beeinflussung → Doc_2 (1)

Buchdruckerkunst → Doc_3 (1)

Ehre → Doc_3 (1)

Erfindung → Doc_3 (2),

Generation Google → Doc_2 (1)

Information → Doc_2 (1)

Menschlich → Doc_3 (1)

Nachdenken → Doc_1, (1)

Nachhaltigkeit → Doc_2 (1)

Suchmaschine → Doc_2 (1)

Übertreibung → Doc_2 (1)

Umgang → Doc_2 (1)

Verlust → Doc_3 (1)

Verstand → Doc_3 (1)

Wissen → Doc_1 (3), Doc_2 (1)

Eric E. Schmidt → Doc_1

Malte Herwig → Doc_2

Thomas Hobbes → Doc_3

2005 → Doc_2

188 → Doc_2

Eliten in einer egalitären Welt → Doc_2

Leviathan → Doc_3

Text

Autor

Titel

Seiten

Datum

Page 19: Der Nucleus einer Suchmaschine

Und abfragen!

Frage: In welchen Dokumenten finde ich das Wort wissen?

Antwort als gerankte Liste mit Hyperlink-Verweisen:

1. http://server.de/doc_1 (3x wissen im Text, deshalb höheres Ranking)

2. http://server.de/doc_2 (1x wissen im Text, deshalb niedrigeres Ranking)

Frage: Wer ist der Autor von Leviathan?

Antwort: Der Autor von doc_3 mit dem Titel „Leviathan“ heißt „Thomas Hobbes“

Frage: Wie viele Seiten hat Thomas Herwigs Buch von 2005?

Antwort: Das Buch doc_2 mit Datum von 2005 hat 188 Seiten

Page 20: Der Nucleus einer Suchmaschine

Danke!