7.2
 Volltextsuche

Volltextsuche 

Hinweis zu den Einheiten des Retrievals

Anstelle von ganzen Dokumenten als Suchresultat kann man auch kleinere Textstellen (engl. passage retrieval ) als Wiedergewinnungseinheit definieren.

7.2.1
 Indexieren

Indexieren 

Meta-Information zu Dokumenten

IR-System erlauben oft, Einschränkung bezüglich Alter, Sprache, Herkunft etc. von Dokumenten in die Anfrage einzubauen. Solche Informationen müssen für jedes Dokument gespeichert werden.

Beispiel: Vorkommensmatrix in Shakespeare-Stücken 

Term-document incidence matrix nach [Manning et al. 2009]

Lesebeispiele

Der Term „Calpurnia“ kommt im Stück Julius Caesar vor.

Der Term „Calpurnia“ kommt im Stück The Tempest nicht vor.

Effizienter Index 

Speicherplatzprobleme der Vorkommensmatrix

• 1 Million Dokumente mit je 1000 Tokens zu 6 Bytes pro Token braucht 6 GB Speicherplatz.
• Es finden sich darin typischerweise 1/2 Million Indexterme.
• Eine naive Repräsentation der Vorkommensmatrix benötigt also 500’000 × 1’000’000 Bits, d.h. ca. 58GB.

Fast alle Tabellenzellen sind 0

Aus Effizienzgründen sollte nur gespeichert werden, in welchen Dokumenten ein Term tatsächlich vorkommt.

Dictionary

Die Menge aller Indexterme (dictionary) sollte im Hauptspeicher Platz finden. Durch Termnormalisierung und Stoppwörter lassen sich ca. 1/3 der Indexterme entfernen. [Manning et al. 2009, 89]

Invertierter Index (inverted index) 

• Jedes Dokument erhält eine ID (DocID).
• Für jeden Term t speichern man die sortierte Liste der DocIDs (posting list), welche t enthalten.

Brutus	−→	1	2	4	11	31	45	173	174
Caesar	−→	1	2	4	5	6	16	57	132	…
Calpurnia	−→	2	31	54	101
dictionary		postings

Auswahl der Indexterme 
Nach der Tokenisierung werden aus Gründen der Effizienz und/oder Relevanz oft bestimmte Wörter (noise words) ausgefiltert.

• Allgemeine Funktionswörter einer Sprache, welche meist häufig vorkommen (Stoppwortliste): der, die, das …ich, du, er …auf, unter, in …und, oder …bin, bist, ist, hast …
• Bei inhaltlich homogenen Dokumentensammlungen manchmal auch Inhaltwörter , welche fast in allen Dokumenten vorkommen und dadurch keinen informativen Wert besitzen. Z.B. in Dokumenten zur Informatik: System, Computer …

Es gibt auch Suchmaschinen, welche alles indizieren – interessant für CL-Ansätze “WWW als Korpus”.

Eine kleine Stoppwortliste für Englisch ▸▸▸ 
a about after again ago all almost also always am an and another any anybody anyhow anyone anything anyway are as at away back be became because been before being between but by came can cannot come could did do does doing done down each else even ever every everyone everything for from front get getting go goes going gone got gotten had has have having he her here him his how i if in into is isn’t it just last least left less let like make many may maybe me mine more most much my myself never no none not now of off on one onto or our ourselves out over per put putting same saw see seen shall she should so some somebody someone something stand such sure take than that the their them then there these they this those through till to too two unless until up upon us very was we went were what what’s whatever when where whether which while who whoever whom whose why will with within without won’t would wouldn’t yet you your

Indexterme normalisieren 
Die Normalisierung kann keine bis viel Sprachtechnologie enthalten:

• Reduktion auf orthographische Normalform (Ä → ä; ä → ae ; ph → f)
• Trunkierung (veraltet): Abschneiden von Wortenden bei Wörtern ab einer Mindestlänge auf einen Präfix fixer Länge
  
  analys|ieren analys
  Analys|e analys
  analyt|isch analyt
• Stemming (z.B. noch in Suche im Acrobat Reader): Einzelsprachliche Kürzungsregeln, welche ohne Lexikoneinsatz Wortformen auf ihren Stamm (stem) reduzieren.

Stemming mit dem Porter-Stemmer ▸▸▸ 

Beispiel 7.2.5 (Porter-Stemmer für Englisch).
These analyses seemed especially analytic.

these  these
analyses  analys
seemed  seem
especially  especi
analytic  analyt

Indexterme normalisieren 

• Lemmatisierung : Reduktion von syntaktischen Wortformen flektierter Sprachen auf ihre Grundform: “aufgegessen” “aufessen”
• Kompositaanalyse : Auflösung von Komposita in ihre Bestandteile: “Schwimmunterricht” “schwimm” “unterricht”
• Derivationsauflösung : Auflösung von derivierten Ausdrücken: “Überzeugung” “überzeugen” “überzeugen”
• Synonymerkennung : Auflösung von engeren Synonymen oder verwandten Bezeichnungen: “Rechenmaschine” “Computer”, “Luisa” “Louise”
• “Named Entity Recognition ”: Erkennung von Personen-Angaben (Google-Squared), Erkennung von Datumsangaben für “Timelines”

Beispiele

Beispiel: Automatisches Indexieren von OPAC-Daten 

7.2.2
 Architektur

IR-System-Architektur [Carstensen et al. 2004, 483]

Frage

Warum hat es zwischen dem Kästchen “Anfrage-Compiler” und “Termextraktion und linguistische Normalisierung” eine Verbindung?

7.2.3
 Retrieval

Dokument als Menge von Indextermen 

Probleme des Boolschen Retrievalmodells 

Zweiwertigkeit

Wegen der klassischen Zweiwertigkeit , d.h. keine partiellen Treffer, können (bei kleineren Dokumentensammlungen) Null-Treffermengen entstehen.

Bei grossen Dokumentensammlungen wiederum können übergrosse Treffermengen entstehen. Eine gute Reihenfolge der Suchresultate nach Relevanz ist notwendig (erweitertes Boolsches Modell)

Dokument als Indexterm-Menge

Die Dependenzen zwischen den Wörtern lassen sich nicht darstellen. Ein Aufsatztitel wie “A formal specification language for the automatic design of chips by computer” bedeutet dasselbe wie die Wortmenge “automatic, chip, computer, design, formal, language, specification”.

Problem der Mengen-Repräsentation für die Suche 

7.2.4
 Relevanz

Relevanzabschätzung von Indextermen 
Um die Relevanz von Indextermen gegenüber Dokumenten, welche sie enthalten, abschätzen zu können, werden unterschiedlichste Masse angewendet und kombiniert.

Überlegungen zu Stoppwörter, TF und IDF 

Fragen

1. Wie verhalten sich typische Stoppwörter bezüglich TF und IDF?
2. Wie verhält sich ein Wort bezüglich TF und IDF, das in einer Dokumentensammlung nur 1 Vorkommen hat?
3. Welche Auswirkungen hat es, wenn eine Dokumentensammlung sowohl sehr kurze wie auch extrem lange Dokumente enthält?
4. Wie könnte man die Information über TF und IDF miteinander kombinieren zu einer einzigen Bewertung?

Die TF/IDF-Formel nach [Salton 1988]

• N die Anzahl Dokumente einer Dokumentenmenge D, N = .
• d ein Dokument aus der Dokumentenmenge D
• i ein Indexterm
• df_i die Anzahl der Dokumente aus D, welche Indexterm i enthalten
• tf_d,i die Anzahl der Vorkommen von Indexterm i im Dokument d (TF)
• w_d,i das Gewicht (Relevanz), welche dem Dokument d bezüglich dem Indexterm i zukommt

Fragen

Welche Werte kann tf_d,i und maximal/minimal annehmen? Was macht log?

Vektorraummodell 

Idee: Relevanz als Vektorähnlichkeit

• Anfrageterme werden wie Dokumentvektoren repräsentiert
• Relevanz von Anfrage = Ähnlichkeit von Anfragevektor mit Dokumentvektor
• Verschiedene Ähnlichkeitsmasse, z.B. euklidische Distanz, Cosinus, etc.