Aufbau Integrierter Informationssysteme Suchmaschinen Michael Schmidt, Marco Schopp Martin-Luther-Universität Halle-Wittenberg Hauptseminar - Halle - 11.12.2015

Aufbau Integrierter Informationssysteme

Suchmaschinen

Michael Schmidt, Marco Schopp

Martin-Luther-Universität Halle-Wittenberg

Hauptseminar - Halle - 26.04.23

© 2002 Mischa Schmüdd, Marggo Schobb :-) MLU-Halle-Wittenberg

Gliederung

• Warum

• Arten von

• Architektur von

• Aufgaben von

• Suchmodi und Suchoperatoren

• Zusammenfassung

Suchmaschinen


Warum Suchmaschinen?

• Existieren über 320 Mio. Seiten

• um in dieses „Chaos“ eine gewisse Ordnung zu bringen, kam es zur Entwicklung der Suchmaschinen

• Suchmaschinen sind die meist besuchten Seiten im WWW


Arten von Suchmaschinen

I. Suchmaschinen und Suchindizes

II. Kataloge

III. Metasuchmaschinen

IV. Spezialsuchmaschinen


Suchmaschinen und SuchindizesBestehen aus mehreren Komponenten, die automatisch Adressen im Internet einlesen

Die Suchsoftware scannt WWW-Dokumente und verfolgt die enthaltenen Links

Informationen werden in der Datenbank der Suchmaschine gespeichert

Beispiele:

Google & AltaVista


KatalogeBesteht aus hierarchisch aufgebauten Sachgebieten (Linksammlungen)

Die Navigation erfolgt durch Anklicken der Hauptkategorien und danach der Unterkategorien

Kataloge arbeiten nicht mit einem Index, sondern legen Linklisten an

Beispiel:

Yahoo


MetasuchmaschinenSind Abfragesysteme, die mit mehreren Suchmaschinen oder Katalogen arbeiten

Sie besitzen keinen eigenen Datenbestand, sondern nutzen die Daten der angeschlossenen Suchdienste

Beispiele:

Metager & Metacrawler


Charakteristik „echter“ Metasuchdienste

• Mehrere Suchdienste werden automatisch über eine Schnittstelle (Suchformular) befragt

• Verschiedene Suchdienste werden vorgegeben, können aber auch manchmal vom Benutzer ausgewählt werden

• Eliminierung von Mehrfachtreffern aus den Ergebnissen der verschiedenen Suchdienste


Spezialsuchmaschinen

• Beschränken ihre Arbeit auf ein fest umrissenes Fachgebiet

• Zu diesem Zweck wird eine eigene Datenbank gepflegt

• Solche Maschinen suchen zum Beispiel Personen, Software oder Businessinformationen

• Beispiel ist "Quoka" eine Produktsuchmaschine


Die Architektur von Suchmaschinen


Struktur des World Wide Web


-verwaltet URLs-entscheidet Reihenfolge-Problem der isolierten Seiten/ Teilgraphen

URL Server

-holt gegebene URL aus dem Internet-Wandelt URL in IP um-Verbindungsaufnahme über http-verlangt Seite und wartet auf Erhalt

Crawler

-ein Crawler bearbeitet immer mehrere URLs gleichzeitig-mehrere Crawler auf verschiedenen Systemen -Bsp.: >typischerweise 300 Verbindungen pro Crawler

>mit 4 Cawlern ca. 100 Seiten pro Sekunde

Crawler II

-Problem: ernorme Netzlast bei Crawlersystem und Zielserver-Reaktion der Betreiber:z.B. Freude über „regen“ Besuch oder verhindern von Seitenindizierung durch Robots Exclusion Protokol-temporäre Probleme

Crawler III-WWW Seite wird zur Analyse vorbereitet-Erstellung eines Ableitungsbaum-Kann sehr komplex werden – aufgrund der vielzahl der Sprachversionen und “Dialekte”-HTML Fehler werden vom Browser übergangen, nicht jedoch vom Parser

Parser

-wichtige Informationen aus Ableitungsbäumen extrahieren

-Links auf andere Seiten (mit Link-Auswahlmöglichkeit sog. Filter z.B. für lokale Suchmaschinen)

-es dürfen keine dyna. generierte Seiten angefordert werden

Store Server

WebCrawler-Komponente

Schematischer Aufbau

URL ServerCrawlerCrawlerCrawler

Parser

Store Server

Searcher

Hit List Repository- Suche nach neuen Wörtern in LEXICON-Je Wort pro Seite Vermerk in HIT LIST-Teil der Seite Abspeicherung in REPOSITORY

Store Server

LEXICON

HIT LIST

REPOSITORY

-Speicherung aller Wörter des Webs-Jedes Wort enthält Zeiger auf die entsprechende Hitlist-Designziel: effiziente Datenstruktur-schneller Zugriff – Hashtabelle -Bsp. Google: ca 14 Millionen Wörter auf 256MB

Lexicon

-je Wort in Lexicon - Menge von Zeigern auf Seiten im Repository

-dadurch schnell Berechnung der gesuchten URLs mgl.

-zusätzliche Speichermöglichkeit

Hit List

-Abspeicherung aller Infos für indizierten Seiten

-z.B nur Titel, erste 20 Zeilen oder Volltext

-bei Volltext: Notwendigkeit der Komprimierung

Repository

-Webserver, welcher Frontend für DB ist-bietet Anfragemaske-Anfragen über CGI übermittelt

- Ergebnissmenge über Ranking-Algorithmus sortiert und ausgegeben

Searcher

Lexicon


Maße für Retrieval-Systeme Recall

- c sei Anzahl der zurückgegeben Seiten, von denen d relevant sind

-von a indizierten Seiten seien b Seiten für Suchanfrage relevant

-Recall Rate ist definiert als d/b-Misst Leistung, wieviele relevante Seiten erkannt und zurückgegeben werden

-Recall Rate = 1.0 alle rel. Seiten gefunden-Recall Rate = 0.0 keine gefunden

- Problem des Rauschens

Precision-Precision Rate ist definiert als d/c-Maß für Rauschen im Ergebnis -Precision Rate = 1.0 alle zurückgegbenen Seiten relevant.-Precision Rate = 0.0 nur irrelevante Seiten zurückgegeben-Ideal RR und PR möglichst hoch-In Praxis: oft gegenläufige Veränderung-Vergleich verschiedener Architekturen mit diesen Maßen unmöglich-Jedoch: Ansätze, zur Erhöhung


Techniken zum Durchlaufen des Webs

- alle Links der ersten Seite verfolgt

-erschöpfende Indizierung in Nachbarschaft der Startseite

-Realisierung mit FIFO-Queue

-Auswirkungen auf Recall und Precicion hängt von Struktur ab

Breitensuche

- gesamter Graph des ersten links

-direkte Nachbarschaft wird schnell verlassen

-Implementierung mit Stack

-Auswirkungen auf Recall und Precicion hängt von Struktur ab

Tiefensuche

- wenigstens die „wichtigsten“ Seiten erfassen

-Entspricht dem citation index von wissenschaftliche Veröffentlichungen

-URL Server merkt sich Anzahl der Links auf eine Seite

-Je häufiger desto höhere Priorität

Backlink Count

-Ranking-Maß von Lawrence Page

-Erweiterung des Backlink Count

-Werte beim Indizieren berechenbar

-häufige Verwendung in Praxis

Page Ranking


1.Indexgröße 3. Art des Indexes2. Natural LanguageProcessing

Techniken zur Steigerung der Recall Rate

-trivialste Methode: Vergrößerung des Indexes-Problem bei älteren Suchmaschinen: Grenze des Möglichen erreicht

AdreßraumAnzahl der Filehandles des Betriebssystems

2. Natural LanguageProcessing

2.1 Stemming | 2.2 Thesaurus

-Reduzierung der Wörter auf ihren Wortstamm (Bsp: „rennen“ zu „renn“-Gefahr der Mehrdeutigkeit (Bsp: engl. „informal“ „information“) Folge: Reduzierung der Precision Rate

-Zufügen von Synonymen zur Suchanfrage („Virus“„Krankheitserreger“)-Finden thematisch relevanter Seiten-Problem von Mehrdeutigkeiten keine besserer Recall aber schlechterer Precision

-lange Zeit: Vector Space Model-bei Suchmaschinen: Repräsentation durch x häufigsten vorkommenden Wörter-x zw. 40 und 100 -keine „und“, „oder“, Artikel usw.- Nachteil: keine Zusatzinformationen für den Searcher Volltextrepräsentation


Techniken zur Steigerung der Precision Rate

1.Anfragesprache

2.Ranking-Algorithmen

3.Nachbearbeitung

4.Clustering

-da oft große Menge an Ergebnissseiten

-Begriff der Practical Precision = Fähigkeit der Suchmaschine, Precision Rate der ersten Suchergebnisse hoch zu halten

-wichtige Technik für Benutzer-Setzen einer logischen Beziehung zw. SuchwörternBoolesche Ausdrücke PhrasensucheTrunkierung AbstandsoperationenGroß-/Kleinschreibung

-wichtiger Ansatzpunkt zur Verbesserung der Practical Precision

- einfachste Variante – höchstes Ranking für Seite mit größter Worthäufigkeit+Wörter vom Anfang der Seite, Titel, Überschriften, Fettschrift

-Manipulation durch Seitenbetreiber („Wettrüsten“)

-Backlink Count und Page Rank

Weitere Ranking Methoden:

- Listung gegen Geld ???

- Nutzerverhalten„Relevant ist, was alle suchen“

-Ranking nach Klickhäufigkeit(Nachteil für junge Seiten)

-Grundidee: Vergleich des Suchergebnisses mit Seiten die relevant sind-Bsp: Themenbaum eines Suchkataloges („science:biology“ von YAHOO)

-Methode für hohen Practical Precision-Nachteil: großer Zeitaufwand

-Teilung des Ergebnisses in Kategorien - Seiten des selben Servers -Seiten der selben Sprache

-Suchemaschine NORTHENLIGHT:

- Methoden der KI teilt semantisch in Klassen und Unterklassen


Techniken zur Wartung des Indexes

Aktualisierung

-Seite wird 1 bis 2 mal im Jahr neu indiziert

-Häufigkeit bestimmt Aktualisierungsfrequenz

Tote Links

-Ca. 10%-15% im Index-Lösung: höhere Aktualisierungsfrequenz-Bei Google: Anwender kann Volltextseite aus

Index bekommen


Aufgaben von Suchmaschinen

I. Dokumentenbeschaffung (Akquisition)

II. Indexierung

III. Aktualisierung

IV. Anfragebearbeitung


Dokumentenbeschaffung (1)

Unterscheidung in 2 URL-Quellen:

1. Angabe der URL eines bekannten Dokumentes, von dem die Roboter ihre automatische Suche beginnen

2. Manuelle Eintragung von URL-Vorschlägen in eine dafür eingerichtete Web-Seite


Dokumentenbeschaffung (2)

Probleme bei der Dokumentenbeschaffung:

1. Link-Bilder

2. Nicht-verlinkte Dokumente

3. Zugriffsgeschützte Dokumente

4. Geschützte Seiten nach dem Roboter-Exclusion-Standard


Indexierung• Das Angebot von Suchmethoden ist in erster Linie

von der Indizierung und der daraus resultierenden Datenbank abhängig

• Indizierungsstrategien:

1. Volltext

• Inhaltsbedeutende Begriffe oder Elemente werden aus der gesamten HTML-Seite indiziert (Mehrsprachige Stoppwortlisten)

2. Teilindex

• Indizieren von URL, Titel und Überschriften oder auch der ersten paar Zeilen der HTML-Seite

3. Spezielle inhaltsbeschreibende Bereiche

• Meta-Tags


Aktualisierung

• Aktualisiert wird meist mit einer zeitabhängigen Frequentierung

• Probleme bei der Aktualisierung:

a) Dead-Links (Dangled-Links)

b) Neue Inhalte an der angegebenen URL


Anfragebearbeitung

• Verschiedene Suchmodi (Einfache/ Erweiterte Suche)

• Formularbasierte Suchmasken mit diversen Einstellmöglichkeiten

• Voreinstellungen werden teilweise über Buttons, Menüs und Listen ausgewählt


Suchoperatoren & Suchmodi

1. Suchmodi

a) Einfache Suche

b) Erweiterte Suche

2. Groß- und Kleinschreibung

• Wird bei den meisten Diensten nicht beachtet

3. Trunkierung

• Ist die Suche nach verschieden Wortvariationen

• Benutzung des *-Operators

• Bsp. “hand*“

4. Boolesche Operatoren

• AND, OR, NOT

• Müssen bei vielen Suchdiensten über ein Pull-Down Menü ausgewählt werden

5. Phrasensuche und Abstandsoperatoren

• Suche nach der exakten Reihenfolge der angegebenen Suchbegriffe

• Suchbegriffe müssen in Hochkomma eingeschlossen sein

• Als Abstandsoperator existiert der NEAR-Operator


Zusammenfassung


ENDE

Documents

Aufbau Integrierter Informationssysteme Suchmaschinen Michael Schmidt, Marco Schopp Martin-Luther-Universität Halle-Wittenberg Hauptseminar - Halle - 11.12.2015