Vorlesung 4 - TR-Systemimplementierung Flashcards
Komponenten eines TR-Systems benennen und deren Aufgabe
- Tokenizer
→ Segmentierung der Eingangsdokumente (in Wörter) (Vorverarbeitung der Dokumente) - Indexer
→ Konvertierung von Dokumenten in Datenstrukturen, welche eine schnelle Suche ermöglichen - Scorer
→ Ordnet den Dokumenten einen Relevanzscore zu - Feedback
→ Anpassung der Eingangs Query durch Nutzer Feedback
Tokenisierung Definition
- Ist die Segmentierung (Zerlegung in Sätze und Wörter) eines Textes in kleinste, in einem bestimmten Kontext betrachtete, linguistische Einheiten
- Token-Arten:
-> Zeichen (beim Suchen nicht besonders nützlich)
-> Wort/Begriff
-> Sequenz von Zeichen (n-gram)
-> Phrasen/Absätze
-> Diskursabschnitte
Methoden (drei) der Textnormalisierung erläutern und voneinander abgrenzen
- Stemming: flektive Formen eines Wortes auf dessen Grundform ( ≠ Wortstamm) abbilden
-> z. B.
kaufst → kauf Wichtig!
kaufe → kauf
kaufen → kauf
käufer → kauf - Lemmatizing: flektive Formen eines Wortes auf dessen Lemma (Wörterbuchform) abbilden
-> z. B.
kaufst → kaufen
kaufe → kaufen
kaufen → kaufen
käufer → käufer - Compound-Splitting (Kompositazerlegung): trennen von Wortzusammensetzung (Komposita)
-> Im Hamburger Hafen findet man eine
Elektrofischscheuchanlage elektro fisch scheuch anlage → elektro fisch scheuch anlage
-> Zewa gibt die:
Durchtropfsicherheitsgarantie durch tropf sicherheit garantie → durch tropf sicherheit garantie
-> Einige Geschäfte hingegen den
Damentotalräumungsverkauf damen total räumung verkauf → damen total räumung verkauf
◦ Wenn man im Wald nicht aufpasst bekommt man eine
Eichenprozessionsspinnerraupenhaardermatitis → Eichen prozessions spinner raupen haar dermatitis
Beschreiben, wie ein inverser Index aufgebaut ist und welche Funktion er erfüllt
- Funktion: ist eine vorherrschende Datenstruktur zur schnellen und effizienten Suche, wobei von den Termen auf die Dokumente abgebildet wird, in denen die Terme auftreten
-> anders als bei Vorwärts-Indizierung, wo von Dokumenten auf Terme abgebildet wird) - Aufbau:
-> Dictionary/Wörterbuch-Tabelle (moderate Größe)
–> Benötigt schnellen wahlfreien Zugriff (Direktzugriff)
–> Bevorzugt im Hauptspeicher halten (dieser ist meist sehr begrenzt)
–> Hash table, B-Tree, trie …
-> Postings-Tabelle (riesig)
–> Überwiegend sequentieller Zugriff
–> Bevorzugt im permanenten Speicher (kostengünstig)
–> Dokument-ID (DokID), Term Frequenz (f), Term Position …
Zipfs-Gesetz
- Wenige Wörter treten sehr häufig auf (z. B. Stoppwörter wie “und”), während ein Großteil der Wörter eines Vokabulars selten auftreten, also eine kleine Termfrequenz haben
Algorithmus zur sortierbasierten Inversion
- Sort-based Inversion ist ein Sortieralgorithmus zur Erstellung eines inversen Indexes
- Problem bei Erzeugung eines riesigen Indexes:
-> begrenzter Hauptspeicher (RAM), daher
→ speicherbasierte Methoden nicht nutzbar für große Collections
→ sortierbasierte Methoden nutzen - Inversen Index mittels sort-based Inversion erzeugen:
1. Parse & Count
-> Zerlegen der Doks und Sammeln von < TermID, DokID, Frequenz > im RAM
-> Sobald RAM voll ist oder bestimmter Füllstand erreicht:
–> Lauf (run/part) sortieren nach DokID und auf HDD schreiben
2. Local Sort
-> alle Läufe nach TermID sortieren
3. Merge Sort
-> alle Läufe nach TermID sortiert zusammenführen
4. Inverser Index
-> Invertierte Datei ausgeben / speichern
Möglichkeiten (zwei) zur Indexkompression
- TF-Kompression (kleine Zahlen häufiger → Zipfs Gesetz)
-> kleine Zahlen können üblicherweise häufiger beobachtet werden als große Zahlen
-> weniger Bits für kleine (hohe Frequenz) Integer auf Kosten von mehr Bits für große Integer - DocID Kompression (d-gap)
-> d-gap (speichere die Differenz): d1, d2-d1, d3-d2
-> wird durch sequenziellen Zugriff ermöglicht
Gap-Encoding-Verfahren
- Anstelle der gesamten DocID werden nur die Abstände zwischen den IDs gespeichert. Bis auf das erste Dokument, von dem die original ID gespeichert wird (Gaps = Abstand zw. DocIDs)
- Beim Aufaddieren der Abstände erhält man ursprüngliche DocID
Erklären, wie BCD-Zählcodes, Gamma- und Delta-Codes aufgebaut sind und welche Rolle Sie für die Implementierung einer Suchmaschine spielen
BCD-Zählcode:
-> Nutzen als Präfix für minimale Binärrepräsentation
-> Codierung:
→ Anzahl Bits Zahl (inkl. Abschluss mit 0) ≙
→ x ≥ 1 wird als (x-1) 1-Bits, gefolgt von einem 0-Bit codiert
→ Unary-Code für Zahl der Länge n hat die Länge n, z. B.:
x = 3 110
x = 5 11110
…
* Dekodierung:
-> Bits zählen, z. B.: 111111110 = 9
* Sehr ineffizient bei großen Zahlen
* Belohnt kleine Zahlen zu wenig
Elias γ-Code (Gamma-Code):
* Nicht-retrivaler Integer-Code entdeckt durch Peter Elias 1975
* γ-Code löst das Problem, dass die Länge einzelner Codes nicht mehr unterschieden werden konnte, durch Hinzufügen der nichtambigen Repräsentation (Unary-Code) der Länge zur minimalen Binärrepräsentation. Das „most significant bit“ der minimalen Binärrepräsentation ist immer 1 und muss nicht gespeichert werden
* Repräsentiert eine Zahl n > 0 als Paar aus Selector und Offset
-> Selector: BCD Code Länge des Offsets →
-> Offset: min. Binärrepräsentation, ohne führende 1
4 = 100
γ = 110100 = 11000
Elias δ-Code (Delta-Code):
* Wie Gamma-Code, zusätzlich wird Unary-Präfix (Selector) durch γ-Code (Gamma) ersetzt
* γ-Code funktioniert gut, wenn die Zahlen klein sind (< 32)
* δ-Code braucht nur: |δ(n)| = ⌊log^2 (n)⌋ + 2⌊ log^2 (⌊log^2 (n)⌋) + 1⌋ + 1Bit
◦ Optimal, wenn die zu codierenden Zahlen einer Wahrscheinlichkeitsverteilung der Form P(n)= 1 / (2 n(log(n))^2 folgt.
TF-Sum-Algorithmus und dessen Rolle bei der Implementierung einer Suchmaschine erläutern
- Abarbeiten eines Postings des Index (nur Postings von Wörtern, die in der Query vorkommen), Häufigkeit im Dokument eintragen aufsummieren für jedes Dokument einfaches ⇒ ⇒ Ranking (ohne Normalisierungen) entsteht
- Kann in der Implementation genutzt werden als Vorverarbeitungsschritt, oder, falls keine weitere Normalisierung gewünscht ist, das Gesamte Ranking darstellen
- Bei dem TF-Sum-Algorithmus werden die Wörter einer Query in einer Menge von Dokumenten gesucht. Bei Auffinden eines Wortes wird das Dokument, in dem es steht, notiert und die Häufigkeit des Wortes in diesem Dokument dazu geschrieben. Anschließend werden die Wörter pro Dokument addiert. Das Dokument mit den meisten Übereinstimmungen hat am Ende den höchsten Wert und somit auch den Rang 1.
- f (d ,q )=g(t 1, d , q)+…+g(t k, d, q), wobei g(ti,d ,q)=c (d, q)
- Query: „Information Sicherheit“
- Postings:
-> Information: (d1,3),(d2, 4),(d3,1),(d 4 ,5)
-> Sicherheit: (d2,3),(d 4, 1),(d5,3)
