Sommer Sitzung 09

Softwaretechnologie: Java (Teil II, Sommersemester), Notizen zu Sitzung 9

Thema	Stichworte	Material ___________________________
Überblick	Volltextsuche: Index und Vorverarbeitung; Wie letzte Woche Collation als praktische Variation der theoretischen Sortierthematik mit Fokus auf Strings (Wie vergleichen wir eigentlich?), so heute praktische Variation der theoretischen Suchthematik speziell für die Suche nach Dokumenten, die bestimmte Begriffe enthalten, d.h. Volltextsuche	Beispiele und Literatur: Home
Volltextsuche	—	—
Volltextsuche: Grundproblem	Wie Dokumente nach bestimmten Suchwort durchsuchen? – lineare Suche? – durch alle Dokumente durchgehen; Laufzeit? – O(n) mit n = Gesamtlänge aller Dokumente; bei mehreren Suchen: jedesmal O(n); d.h. lineare Suche für große Mengen keine Option; Alternative? – binäre Suche? – schneller, welche Laufzeit? – log n; Beispiel für Volltextsuche? – z.B. Google; wie lange braucht Google? – im Millisekundenbereich; was ist hier n? – das gesamte Web; d.h. Googles Laufzeit kann nicht relativ zu n sein;	—
Volltextsuche: Grundidee	Anderer Ansatz? – wir suchen für einen Suchbegriff die entsprechenden Dokumente; was kennen wir an Zugriffsmöglichkeiten, die nicht relativ zu n sind? – Hash-Table für Zugriff in O(n); wie können wir sowas nutzen? – wie nutzen, dass wir Dokumente für bestimmte Wörter suchen? – Idee: statt für jedes Dokument zu speichern, welche Wörter es enthält und die zu durchsuchen, speichern wir für jedes Wort, in welchen Dokumenten es vorkommt (und invertieren so den naiven Index); konkret wie? – z.B. eine Map, mit Wörtern als Keys und ihren Dokumenten oder IDs als Values
Vorverarbeitung	—	—
Vorverarbeitung: Ziel	Um das Verzeichnis aller Wörter aufzubauen brauchen wir was? – die Wörter, denn bisher haben wir nur Dokumente bzw. Texte, d.h. erster Schritt der Indexerstellung? – Tokenisieren der Eingabe (Bsp. “hallo, welt!” → “hallo”, “welt”); Tokenisieren, wie in Java? – String#split; Parameter ist eine Regex	—
Reguläre Ausdrücke	Reguläre Ausdrücke (regular expression, regex), eine DSL zur Musterbeschreibung; sequenziell Lesen; 1.) pures Muster: “by William Shakespeare” (z.B. als Werke-Delimiter für Shakespeares gesammelte Werke in einer Datei); 2.) Character classes: a, b, oder c: [abc]; 3.) Negation: [^abc]; 4.) quantifizieren: ?*+ {min,max}, 5.) lazy: z.B. .+?; 6.) Shortcuts: \d \w \s (und gross negiert); 7.) Ranges: 0-9 a-z (Bereiche); 8.) Gruppieren, z.B. Telefonnnummer Vorwahl und Nummer: (\\d+)-(\\d+), 9.) Referenzen mit $1 etc; 10.) Alternation; Regex leichter zu schreiben als zu lesen; Tools nützlich, z.B. QuickRex in Eclipse	s. Code
Tokenisierung mit Regulären Ausdrücken	d.h. wo trennen? – z.B. blanks; Probleme? – Zeichensetzung Teil der Wörter, wollen aber nach hallo suchen, nicht nach hallo, etc.; Grundidee: an Nicht-Buchstabenzeichen trennen, fürs Erste mit [^a-zA-Z0-9_] d.h. \W; Problem mit Umlauten, vgl. Collation? – auch ä ist nicht a-z; Lösung: [^\\p{L}] für Umlaute: Unicode-aware	s. Code
Sonderfälle mit Regulären Ausdrücken	Welches Problem bleibt? – Sachen sind manchmal Teil von Wörtern, manchmal Trennelemente; zb.? – Punkt für Satzende oder Zahlen; Doppelpunkt für Trennung aber auch Uhrzeit; vers. spezielle Formate (Mail, Telefonnummer, Uhrzeit, Geld, Versionen); auch mit Regex? – auch bestimmte Muster; statt wie vorher Regex für Trennelemente, hier die speziellen Muster beschreiben; Telefonnummer? – \\d+-\\d+, Uhrzeit, Geld, Version? – \\d+[-,.:]\\d+; Emails s. Code	s. Code
Enums statt Konstanten	Wie speichern wir unsere Muster? – feste Werte; z.B. Konstanten, aber Nachteil? – nicht iterierbar; List, aber Nachteil? – kein Zugriff über Mustername, z.B. EMAIL; Map: ginge auch, aber in Java mit speziellem Sprachfeature am einfachsten: Enum Type; für Aufzählungen, z.B. wenn wir statt true oder false was drittes wollen, das wir z.B. einer Methode übergeben; Definition: enum Option { YES, NO, MAYBE }, Nutzung: Option.YES; als sowas unsere Sonderfälle modellieren; assoziieren Namen mit den regulären Ausdrücken, z.B. komplexe Zahl, Email, etc.; volle Klasse, kann Funktionalität haben, sehr flexibel und elegant; hier zentraler Vorteil gegenüber Konstanten: wir können über alle verfügbaren Muster iterieren, z.B. als Default-Konfiguration unseres Präprozessors	s. Code: enum SpecialCase
Sonderfälle verarbeiten: Pattern und Matcher	Wie Sonderfälle praktisch verarbeiten? – 1. spezielle Muster extrahieren, 2. Rest mit Trennelement zerlegen; wie einbauen ins Tokenisieren? (Code: Pattern, Matcher, Ersetzen, Enums für gruppierte Konstanten); Spezielle Formate von oben (Uhrzeit etc.), mit Pattern, Matcher, entfernen	s. Code: extractSpecialCases
Fazit Vorverarbeitung	Vorverarbeitung quasi Token → Type → Term; Vorverarbeitung ein weites Feld, aber Regex ein pragmatisches Werkzeug, mit dem man weit kommt; weitere Vorverarbeitung (nicht Thema heute, s. Literatur): Normalisierung (Vereinheitlichung, z.B. ä-ae, british-american, Köln-Cologne), Stemming/Lemmatisierung, Stoppwortlisten für häufigste Wörter (Funktionswörter)	—
Indexerstellung	—	—
Datenstrukturen	Für Hauptstruktur des Index? – Map mit Strings als Keys; was als Value? – eine Collection der Dokumenten-IDs; doppelte Einträge? – nein; d.h.: Set als Interface; d.h. Typ unseres Index? – Map<String, Set<Integer>>; Implementierung der Map? – HashMap oder TreeMap (dann sortierte Keys, ein sortiertes Verzeichnis)	s. Code
Indexerstellung und Abfrage	Wie den Index erstellen? – Für jedes Dokument laufen wir über alle Terme, und fügen die aktuelle Dokumenten-ID in die Liste für den Term ein; Implementierung s. Code; Einfache Suche: get; Laufzeit? – O(1); d.h. Lösung für einfache Suchen Teil der Datenstruktur	s. Code: index
Indexabfragen: AND-Verknüpfung	Mehrwort-Suche: Begriffe mit AND verknüpft; d.h. für Ergebnis? – Ergebnislisten für jedes Wort erstmal einzeln; was damit machen? – Schnittmenge bilden: alle Dokumente, die in beiden Listen enthalten sind; erster Ansatz? – für jedes Element in der einen mit allen in der anderen vergleichen; Laufzeit? – n*m, d.h. O(n*m) mit n und m = Länge der Postings-Listen; wie optimieren? – wenn im Bsp. ID in P1 < ID in P2 dann P1 weiter, sonst P2 weiter; wenn gleich, beide weiter; Laufzeit? – O(n+m); wovon Korrektheit abhängig? – Listen sind sortiert, dadurch am Ende der Kürzeren fertig, denn in der Anderen können weiter hinten nur Elemente kommen die größer sind	s. Code: intersection
Konsequenzen für Indexerstellung	Wie sortierte IDs umsetzen? – beim Indexieren sortieren, aber nach jedem Einfügen; besser? – sortiert halten; d.h. für Datenstruktur des Index? – als Interface? – z.B. Map<String, SortedSet>; als Implementierung? – z.B. binärer Suchbaum? – TreeMap<String, TreeSet>; d.h. Map<String, SortedSet> index = new TreeMap<String, TreeSet>()	s. Code
Optimierte AND-Abfragen für mehrere Begriffe	Mehr als zwei Elemente mit UND verknüpft, was dann? – Ergebnis ist die Schnittmenge der Ergebnisse aller Suchbegriffe; d.h.? – Ergebnisse für alle Begriff einzeln holen; erstes nehmen, mit Rest mergen durch Bildung der Schnittmenge; wenn wir viele Listen mergen, wie können wir optimieren? – wann ist die Schnittmengenbildung mit unserem Algorithmus von oben schnell? – wenn die Listen kurz sind; d.h.? – als erstes die kürzeste Postings-Liste nehmen, denn je früher wir kürzere Listen betrachten, desto seltener müssen wir die Langen durchlaufen; d.h.? – Postings-Listen aufsteigend nach Länge sortieren, dann Schnittmenge bilden	s. Code: intersectionOf
Optimierte AND-Abfragen: Implementierung	Wie implementieren wir die Sortierung? – Comparator, s. Code; Alternative zu eigener Implementierung der Intersection in der Praxis generell: Collection#retainAll(Collection): Schnittmenge von zwei Collections	s. Code: sortByLength
Fazit	Grundlagen des Boolschen Retrievalmodell mit UND, ODER, NICHT; exaktes Retrieval; traditionalle Grundlage der Volltextsuche; Erweiterungen: positional Index für Phrasensuche, Ranking von Ergebnissen, Ähnlichkeit und tolerantes Retrieval, Komprimieren und Optimierung, weites, interessantes Feld (s. Literatur, spez. IR-Buch, online verfügbar)	—
Hausaufgabe	Erweiterungen Vorverarbeitung und Index-Abfragen mit OR	Sommer-Aufgabe-08