01 - Einführung

IR befasst sich mit der Suche nach Inhalten

• Artikel (z.B. wissenschaftliche Aufsätze, Zeitungsartikel)

• Office Dokumente (z.B. Präsentation und Spreadsheets)

• Multimedia-Inhalte (z.B. Bilder oder Videos)

• Webseiten, Profile in sozialen Netzwerken, E-Mails

Daten haben meist keine oder wenig Struktur

• Einfache Textdokumente (keine Struktur)

• HTML-Dokumente (Überschriften und Absätze markiert)

• XML/JSON (semi-strukturiert)

Informationsbedürfnis des Benutzers als Ausgangspunkt

• Oft vage (z.B. Was kann ich in Berlin unternehmen?)

• Ungenau als ANfrage formuliert (z.B. berlin sights)

Dokumentensammlungen sind groß und wachsen weiterhin

Relationale Datenbanken:

• Daten sind strukturiert und haben eine klare Semantik

• Informationsbedürfnis präzise als Anfrage formulierbar

Information Retrieval System:

• Daten sind (meist) unstrukturiert ohne klare Semantik

• Informationsbedprfnis vage als Anfrage formulierbar

• Sehr ähnlich zu herkömmlichen Information Retrieval Systemen

• Hauptunterschiede: Hier noch notieren!

• Wir haben einen 0/1 Vektor für jeden Term

• Zur Beantwortung der Anfrage:

  • Nehme die Vektoren von Brutus, Ceasar und Calpurnia (komplementiert) und führe ein bitweises UND aus

• 110100 UND 110111 UND 101111 = 100100

  • Brutus AND Ceasar BUT NOT Calpurnia

• Betrachte N = 1M Dokumente, jedes mit ca. 1000 Termen

• Das ergibt bei 6 Bytes/Term einschl. Leerzeichen und Interpunktionszeichen

  • 6 GB Daten für alle Dokumente

• Sagen wir, es gibt darunter m=500K unterschiedliche Terme

  
  

• 500K x 1M Matrix hat halbe Billionen 0’en und 1’en

• Aber nicht mehr als eine Milliarden 1’en

  • -> Matrix ist extrem dünn besetzt

• Können wir eine bessere Repräsentation wählen?

  • -> Wir brauchen nur die 1-Positionen zu speichern

• Für jeden Term T müssen wir eine Liste aller Dokumente, die T enthalten, speichern

• Was machen wir, wenn das Wort Ceasar zu Dokument 14 hinzugefügt wird?

• Verkettete Listen werden Arrays vorgezogen

  • Dynamische Speicherplatzallokation

  • Einfügen von Termen in Dokumenten einfach

  • Zeiger eventuell speicheraufwändig

• Tokenization

  • Sätze in Wörter aufbrechen

    • Beispiele: “John’s”, a state-of-the-art solution

• Normalization

  • Mappring von Suchanfrage und Termen

    • Man möchte, dass U.S.A und USA gleich abbilden

• Stemming

  • Verschiedene Terme auf den selben Wortstamm abbilden

    • authorize, authorization

• Stop Wörter

  • sehr häufig vorkommende Wörter

    • the, a, to, of

• Gegeben: Sequenz von Paaren (Token, DocID)

• Sortiere Terme alphabetisch:

• Mehrfacheinträge für Terme aus einem Dokument werden verschmolzen

• Anzahlinformation wird hinzugefügt

Wo zählen wir für die Speicherung?

• Invertierter Index ist erstellt:

  • Wie bearbeiten wir Anfragen?

  • Welche Arten von Anfragen können wir bearbeiten?

• Betrachten wir folgende Anfrage: Brutus AND Ceasar

  • Brutus im Dictionary suchen;

    • Laden der Postings

  • Ceasar im Dictionary suchen

    • Laden der Postings

  • “Merge” der Posting: Schnittmenge

• Paralleles Durchlaufen der zugehörigen Listen

• Übernahme der Dokumentreferenzen, die in beiden Listen vorhanden sind in die Ergebnisliste

• Durch Sortierung der Liste hohe Effizienz

  • Zeitkomplexität linear bezüglich der Anzahl der Postings

  • Listenlängen x und y -> Merge: O(x+y)

• Das Boole’sche Modell ermöglicht Anfragen als Boole’sche Ausdrücke:

  • Operatoren: AND, OR, und NOT

  • Binäre Relevanz: Dokument trifft auf Anfrage oder nicht

• 3 Jahrzehnte das dominierende Vorgehen

• Bestimmte Berufsgruppen (z.B Anwälte) präferieren Boole’sche Anfragen

  • Vorgehen ist intuitiv: “Man weiß, was man bekommt”

• -> in Foliensatz die Übung machen!

Was ist die beste Ordnung für die Anfragebearbeitung?

• Für jeden der n Terme Posting Liste laden und mit AND mergen …

• Abarbeitung anch zunehmender df:

  • Anfragen mit der kleinsten Menge usw.

    • -> Grund, warum dok., freq. im Dictionary gespeichert wird

HIER ERGÄNZEN WEIL FOLIE WAR LEER