Upload
stefan-antoni
View
948
Download
1
Embed Size (px)
DESCRIPTION
Citation preview
Der Nucleus einer Suchmaschine
Oder: Wie funktionieren indexbasierte
Text Retrieval Systeme?
BarCamp Darmstadt 2010Stefan [email protected]@Suchkultur auf Twitter
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?
Wovon solltet ihr schon Ahnung haben?
Ihr solltet schon mal eine Websuche bedient haben ;-)
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
Kann ich im Verlauf Fragen stellen?
Ja!
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
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)
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
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,
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
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)
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“
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
Und jetzt ein Beispiel
… zum mitdenken und Fragen stellen.
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)
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)
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
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
Danke!