Inhaltverzeichnis:

1 Einleitung *
2 Einführung des Konzepts Wrapper *

8 Literatur *

1. Einleitung

Man verfügt über viele dynamische Quellen mit verschiedener Struktur. Dynamisch heißt hier, Quellen können dazukommen oder auch wegfallen.

Diese verschiedenen Dateien müssen trotzdem ausgelesen werden, um die darin liegenden Informationen herauszuholen. Damit man diese verschiedenen Informationen speichern kann, müssen verschiedene Programme geschrieben werden, die die jeweilige Formatierung verstehen. Diese Programme sind Wrapper. Es werden für ein bestimmtes Format mehrere Wrapper geschrieben, die verschiedene Suchverfahren haben.

Dieser Beitrag behandelt wrapper-basierte Ansätze zur Integration von Web-Datenquellen. Hier wird nicht jede Möglichkeit beschrieben, sondern einige ausgesuchte Verfahren, die einen guten Überblick verschaffen. Ein richtiger Vergleich zwischen den Ansätzen ist auch schwer durchzuführen, denn die vier beschriebenen Verfahren sind unterschiedlich, sie beschreiben Teilprobleme, diese haben verschiedene Ziele.

Wir wollen als erstes das Konzept Wrapper erläutern, dann wollen wir verschiedene Ansätze vergleichen, sowohl Ansätze im Mediator als auch ein praktisches Wrapper und die Durchführung eines Projekts. Letztendlich wollen wir die verschiedenen Ansätze mit dem Problem vergleichen.

2. Einführung des Konzepts Wrapper

2.1 Allgemeines

Ein Wrapper ist eine Schnittstelle, die den transparenten Zugriff auf mehrere verschiedene Datenquellen erlaubt.

Dieses Bild erläutert das Konzept:

Ein Nutzer fragt über eine Eingabemaske nach Informationen. Ein Mediator erhält diese Anfrage. Der Mediator weiß, welche Datenbank die Informationen enthält. Er weiß aber nicht, wie diese Datenbank abgefragt werden soll. Er fragt das Wrapper der Datenbank in einer vordefinierten Sprache (möglichst in derselben Sprache für alle Wrapper), und das Wrapper holt sich anschließend die Informationen. Dabei sieht der Nutzer nichts und das System verhält sich, als wäre nur eine einzige Datenbank gegeben. Um dieses zu erzielen, hat der Entwickler des Systems ein globales Schema erstellt. Dieses Schema beschreibt die Struktur der Daten in den verschiedenen Datenquellen.

Das Wrapper dient also hauptsächlich der Verbergung von Heterogenität. Zum Beispiel eine relationale Datenbank, eine Sammlung flacher Dateien, ein veraltetes hierarchisches Datenbanksystem, ein paar Webseiten etc. Da kommen die Wrapper in Frage, sie haben möglichst nach außen hin die gleiche Schnittstelle, z.B. SQL-Anfragen und SQL-konforme Tabellen als Ausgabe. Nach innen ist je Datenquelle die Schnittstelle anders. Die Aufgabe der Wrapper ist also die Übersetzung zwischen den beiden Formaten. Je nach Datenquelle ist es mehr oder weniger kompliziert.

Daraus folgt, daß jede Datenquelle ein spezifisches Wrapper braucht. Praktisch ist aber, daß, wenn man eine neue Quelle hat, man nur ein neues Wrapper einsetzen und nicht den Mediator neu programmieren muß. Im Gegensatz existieren Mediatoren ohne Wrapper, die bei jeder Änderung angepaßt werden sollen. Mit Wrapper ist die Kapselung erreicht, was vieles vereinfacht, aus diesem Grund benutzen wir Wrapper.

2.2 Genaueres zum Integrationsproblem im WWW

Im WWW findet man eine breite Auswahl von Daten, HTML-Seiten, Bildern, Videos, Programmen, Musik, Klang usw. Wir gehen ausschließlich von HTML-Seiten aus:

Eine Möglichkeit der Darstellung ist die, die Informationen, die wir suchen, als Tabelle darzustellen, Reihe für Reihe neue Informationen. Das ist praktisch, wenn es viele Informationen sind, die automatisch aktualisiert werden, meistens per Skript (Perl, PHP, etc.), z.B. Gebrauchtwagen- oder Hausverkauf oder Aktienkurse. Tabellen dienen aber auch für Informationen, die keine weitere Aktualisierung haben, um diese Informationen strukturiert darzustellen und zu präsentieren wie z.B. das CIA-factbook www.odci.gov/cia/publications/factbook mit Informationen aus allen Ländern der Welt, Bevölkerung, Fläche, Bruttosozialprodukt, vorwiegendes Klima usw.

Für so eine Art Site ist das Herausholen von Informationen einfacher als ein Fließtext. Das Wrapper muß nur regelmäßig die Seiten neu lesen, was Aufwand an Zeit und Bandbreite erfordert. Das Wrapper muß außerdem wissen, wie die Informationen gestaltet sind, in welcher Reihenfolge und um welche es sich handelt, was von Site zu Site natürlich anders ist. Die Sites sind meist von Firmen.

Wenn die Informationen als Tabelle gespeichert sind, sind sie auch besser strukturiert als ein Fließtext, denn das HTML hat eine sehr präzise Struktur für Tabellen. Z.B. Aktienkurse: diese Tabelle ist an das Wrapper übergeben:

 

Stück	Wkn	Wertpapier	Kaufdatum	Kaufkurs	Akt. Kurs	Änderung	Gesamtwert
125	575200	Bayer	14-11-2000	50.25	51.30	2.09 %	6412.50
250	686410	Osnabr.Bierbr.	15-11-2000	9.50	8.45	-11.05%	2112.50
125	850471	Boeing	14-11-2000	73.00	79.00	8.22 %	9875.00
200	851301	Hewlett-Packard	15-11-2000	43.50	41.00	-5.75 %	8200.00
125	878309	Rhone-Poulenc S.A.	14-11-2000	86.00	88.00	2.33 %	11000.00
8000	925901	DSL.net Inc.	27-11-2000	1.50	1.50	-0.00 %	12000.00

Es kann aber auch sein, daß die Informationen einzeln auf die Seiten verteilt sind, auf jeder Seite eine neue Information, z.B. irgendeine Art von Wörterbuch oder Enzyklopädie. Da enthält jede Seite eine andere Information, und die Seiten werden durch eine Art Inhaltsverzeichnis zusammengebunden. Alle Informationen sind dann als Fließtext dargestellt.

Da muß das Wrapper alle Seiten mindestens einmal durchlaufen und eine Datenbank anlegen, die die wesentlichen Informationen speichert. Ein Ansatz ist es, ein Wörterbuch anzulegen, welches die wichtigsten Wörter beinhaltet und möglichst fähig ist, neue Wörter zu lernen. Wenn in dem Text diese Begriffe oder Synonyme benutzten werden, handelt es sich um wichtige Informationen. Das ist beschränkt richtig. Heuristische Verfahren geben eine prozentuale Wahrscheinlichkeit, daß die Informationen auch tatsächlich richtig sind. Solche Sites sind meist von Personen verfaßt, die ein spezielles Thema beschrieben haben.

Bei Fließtext besteht auch die Möglichkeit, auf die Formatierung zu reagieren. D.h. das Wrapper schaut, wie die Informationen formatiert sind, ob fett, unterstrichen, kursiv, Überschrift usw. Wenn fünf Wörter nebeneinander stehen und fett gedruckt sind, kann es sich schon um einen Titel handeln, wenn diese außerdem unterstrichen sind, ist dies noch wahrscheinlicher. Dieses Verfahren ist nicht fehlerfrei, aber erzielt schon gute Ergebnisse.

Beim Entwurf wird festgelegt, wie man das Wrapper abfragen kann (SQL etc.) und in welcher Form die Ergebnisse ausgeliefert werden (Tabelle, Text etc.). Die Wrapper und Mediatoren ermöglichen dann den Zugriff auf die verschiedenen Informationen, als würden die Informationen alle auf derselben Site liegen.

Man muß zunächst auch noch festlegen, wie das Wrapper die Antwort auf die Frage suchen soll. Es sind zwei Möglichkeiten, entweder sucht es online, d.h. es sucht nach der Anfrage sofort sämtliche Seiten durch, oder offline, d.h. es bereitet eine Datenbank mit Ergebnissen vor und sucht nur in seiner Datenbank.

Der Online-Modus hat den Nachteil, daß es sehr lange dauern kann, bis die Ergebnisse da sind, und die Bandbreite wird außerdem erheblich reduziert, da das Wrapper selbst viel beansprucht. Er hat aber den Vorteil, daß die Informationen stets aktuell sind. Die später erläuterten Verfahren "Information Manifold" und "Learning Source Description" können nur als Online-Modus betrieben werden, da sie mit Skript auf der jeweiligen Site agieren.

Der Offline-Modus hat den Nachteil, daß die Informationen eventuell veraltet oder nicht mehr vorhanden sind; hat aber den Vorteil, daß keine Bandbreite benutzt wird und der Zugriff auf die lokale Datenbank deutlich schneller ist als der Zugriff auf das Web. Das spätere erläuterte Verfahren WHIRL kann in Offline-Modus betrieben werden. Dafür müssen zunächst die verschiedenen Sites lokal gespeichert werden. Ebenso kann das XWRAP auch lokal arbeiten.

Man muß vorher eine Vorstellung darüber haben, welcher Modus am besten zu welchen Problemen und Quellen paßt.

3. Ansätze im Mediator

Im Folgenden werden zwei Ansätze beschrieben:

"Information Manifold" hat sich als Ziel gesetzt, die Quellen deklarativ zu beschreiben, und zwar werden die Ein- und auch die Ausgabe deklarativ beschrieben und darauf werden die Querypläne aufgebaut.

"Learning Source Description" versucht das Beschreiben der Quellen zu automatisieren, d.h. das Programm generiert selbst diese Beschreibung.

3.1 Information Manifold [LRO96]

3.1.1 Entwicklung

Z.B. Site, die Autos verkaufen: entweder hat man ein Formular und beschreibt sein Wunschauto: Marke = Mercedes, Baujahr = 1999, Typ = A Klasse usw. oder falls kein Formular vorhanden ist, kann alles in Kategorien verwaltet sein. Z.B. Wurzel des Site: alle Autos, Unterverzeichnis Mercedes: alle Autos der Marke Mercedes usw., und mit den URL www.auto-verkauf.de/mercedes/a-klasse/1999 bekommt man alle Autos der Marke Mercedes, Typ A Klasse und Baujahr 1999 heraus. Das ist nur eine Möglichkeit.

Sites werden ausgewählt nach Ein- und Ausgabemöglichkeiten. Die Sites werden sehr genau und gründlich analysiert, um zu definieren, was sie als Eingabe unbedingt und optional benötigen und was sie als Ausgabe liefern. Dieses Beschreiben der Seite erfolgt manuell, man muß durch Versuchen finden, was das Site als Ein- und Ausgabe braucht beziehungsweise liefert.

Der Inhalt und die Fähigkeiten des Site werden als Query beschrieben. Der gesamte Inhalt aller Quellen ist zuerst als hierarchische Klassen dargestellt.

Beispiel:
 

Klasse	Unterklasse von	Attribute	Disjunkt mit
Produkt Fahrzeug Motorrad Wagen Neuwagen Gebrauchtwagen WagenZumVerkauf	Produkt Fahrzeug Fahrzeug Wagen Wagen Wagen	Modell Modell, Jahr, Kategorie Modell, Jahr Modell, Jahr, Kategorie Modell, Jahr, Kategorie Modell, Jahr, Kategorie Modell, Jahr, Kategorie, Preis, Verkäufer	Personen Stereoanlage Wagen Motorrad Gebrauchtwagen Neuwagen

Wenn alle Klassen beschrieben sind, können die Quellen nach deren formaler Beschreibung als Query beschrieben werden. Das geschieht unter zwei verschiedenen Gesichtpunkten. Man muß zuerst wissen, was die Quelle liefern kann, also welche Klassen von unserer Weltansicht in der Quelle gespeichert sind und wie diese Informationen ausgelesen werden können.

In dieser Tabelle sind zwei Quellen mit informeller Beschreibung.
 

Quelle 1	Gebrauchtwagen zum Verkauf	Akzeptiert als Eingabe Wagenkategorie oder -modell, und optional eine Preis- und Jahrskala Als Ausgabe: Modell, Jahr, Preis und Verkäufer
Quelle 2	Luxuriöse Gebrauchtwagen ab $20,000	Akzeptiert als Eingabe Wagenkategorie und optional eine Preisskala Als Ausgabe: Modell, Jahr, Preis und Verkäufer

Der Inhalt wird ermittelt mit einem "" Zeichen (Mengeninklusion). Diese Quelle kann etliche Daten aus verschiedenen Klassen liefern, kann aber auf keinen Fall alle Daten aus diesen Klassen liefern Grund dafür ist, daß keine Quelle ein vollständiges Wissen besitzt.

Die Fähigkeiten einer Quelle sind die Art und Weise, die Quelle anzufragen. Es ist ein Tupel der Form (S_in, S_out, S_sel, min, max). Die Anfrage findet statt, wenn mindestens min Parameter von S_in an die Quelle übergeben sind. S_out sind die zurückgelieferten Informationen und S_sel sind Parameter, die auch als Anfrage benutzt werden können und außerdem mit einem Operator versehen sein können, z.B. der Form {=, !=, <, <=}. Dies ist sehr praktisch bei Zahlen wie Preise, Jahre usw.

Auf unseren Beispiel ergibt sich dieses:
 

Quelle 1	Gebrauchtwagen zum Verkauf	Inhalt: V1(w)  WagenZumVerkauf(w), Gebrauchtwagen(w) Fähigkeiten: ({Modell(w), Kategorie(w)}, {Model(w), Kategorie(w), Jahr(w), Preis(w), Verkäufer(w)}, {Jahr(w), Preis(w)}, 1, 4)
Quelle 2	Luxuriöse Gebrauchtwagen ab $20,000	Inhalt V2(w)  WagenZumVerkauf(w), Preis(w, p), p >= 20000 Fähigkeiten: ({Kategorie(w)}, {Modell(w), Kategorie(w), Jahr(w), Preis(w), Verkäufer(w)}, {Preis(w)}, 1, 3)

Dies alles ist so beschrieben, weil die Entwickler wollten, daß das Einfügen, das Ändern oder das Ausfallen einer Quelle keinen Einfluß auf die Weltansicht hat. Solche Ereignisse treten öfter im WWW auf und sollten nicht das gesamte Programm in Gefahr bringen. Das Programm liest also einfach jedes Mal die Beschreibungen durch und erstellt Queryplans.

Zuerst wird die Anfrage mit einem Übersetzer in eine Regel-Notation gebracht;

z.B. aus "Ich möchte den Preis und die Beschreibung für ein Sportauto, höchstens 8 Jahre alt" wird:

Die Anfrage wird zerteilt und ein sogenanntes Bucket (deutsch: Eimer) sammelt eine Liste von relevanten Quellen für die Teilanfragen.

Um die Anfrage zu beantworten und um möglichst viele Quellen zu nutzen, wird wie folgt vorgegangen:

1. Anfrage in Teilanfragen zerlegen
2. Jede Teilanfrage in Queryplan umwandeln
3. Pro Teilanfrage ein Bucket zuweisen
4. Alle Quellen durchsuchen und überprüfen, ob sie mit dem Queryplan ausführbar sind
5. Falls dies der Fall ist, Quelle in Bucket speichern
6. Mit allen Quellen, die in des Bucket gespeichert sind, wird ein gesamter Queryplan erstellt.

Eine Teilanfrage ist ein Unterziel. In unserem Beispiel ist es WagenZumVerkauf(w), Kategorie(w,Sportauto), Jahr(w,y), y <= 1992 oder Produktbeschreibung(m,y,b) usw. Wenn also eine Quelle eine Teilanfrage beantworten kann, so ist sie aufgehoben, um später in den allgemeinen Queryplan eingeführt zu werden. Mit Ausführbarkeit ist gemeint, daß die Quelle relevant ist für den Queryplan. Ob die Quelle ein Ergebnis zurückliefert oder nicht ist unerheblich, hier ist nur wichtig, daß die Quelle relevant ist.

Wenn alle Quellen durchsucht worden sind, erstellt das Programm einen gesamten Queryplan mit allen Quellen, um ein sehr breites Ergebnis zu liefern.

Z.B. liefert die Quelle A nur die Beschreibung des Autos und die Quelle B nur den Preis für irgendein Auto. Das System fragt zuerst die Quelle A nach Beschreibung, speichert die Resultate und fragt die Quelle B anhand der Resultate aus der Quelle A. So hat man genau die recherchierten Informationen. Die Entwickler dieses Verfahrens haben nicht versucht, die Performance zu optimieren, sie sind nur von der Ausführbarkeit ausgegangen. Also werden die Teilanfragen einfach nach und nach bearbeitet.

Dieses Wrapper erzielt äußerst genaue Antworten bei komplizierten Anfragen. Die Anfragen müssen aber sehr genau überlegt werden und detailliert sein. Ganz einfache Fragen wie z.B. "ich möchte ein weißes Auto, egal welches" sind viel zu ungenau, und der Nutzer wird mit zu vielen Informationen überflutet. Das Einsetzen des IM ist in diesem Fall sinnlos, denn der IM ist dazu da, eine komplexe Anfrage durch Verketten verschiedener Quellen genau zu beantworten.

3.1.2 Konkret im WWW

Zeitlich ist das Verfahren ziemlich schnell, je nach Komplexität der Anfrage braucht es durchschnittlich zwei Sekunden um die Anfrage zu beantworten bei einer Anzahl zwischen 20 und 100 Quellen. Pro Erzeugung der Querypläne wird weniger als eine Sekunde benötigt, durchschnittlich 0,5 Sekunden. Die Antwortzeit ist natürlich vom jeweiligen Server abhängig.

Das größte Problem dieses Verfahrens bleibt also die Beschreibung der Quellen, da dies manuell erledigt wird. Der Wartungsaufwand zur Überprüfung der weiteren Beschreibungsrichtigkeit ist immens. Es sollte also möglichst automatisiert werden. Deswegen wurde später das LSD entwickelt.

3.2 Learning Source Descriptions [DDL00]

Das Ziel hier ist die automatische Erstellung von Quellenbeschreibungen (vgl. Information Manifold)

3.2.1 Entwicklung

Alle Sites sind zwar inhaltlich ähnlich, aber die Informationen werden nicht in derselben Reihenfolge dargestellt und die Sites geben unterschiedliche Informationen, z.B. in Sachen Häuser sind viele unterschiedliche Informationen vorhanden: Anzahl der Bäder, Anzahl der Zimmer, Anzahl der Küchen, m², Grundstück, Stellplatz, Garage, Bemerkungen, Lage, Preis usw. Aber nicht jede Information muß publiziert werden.

Man läßt LSD die Site durchlesen. Die Learner lesen die Informationen durch und versuchen, durch verschiedene Prozesse, den Inhalt von allein zu erkennen. Doan, Domingos und Levy benutzen ein Nachbarform von "WHIRL Learner", ein "Naive Bayesian Learner", ein "name matcher" und ein "county-name recognizer" ein. Diesen Learner kommen aus der Forschung des maschinellen Lernens, sie lösen das Klassifikationsproblem. Es wird an jeden Learner eine Menge von Informationen und Typen geliefert (Trainingsdatensätze), diese sind schon geordnet und dadurch lernen die Learner ein paar Gesetze. Dann versuchen sie unbekannte Informationen einem Typ zuzuordnen.

"WHIRL Learner" ist ein Verfahren, das auf TF*IDF basiert ähnlich wie im Information Retrieval. Es ist vorteilhaft bei Elementen die wortreich sind, und textinhaltlichen Elementen oder beschränkten Elementen (z.B. Farben). TF*IDF nimmt an, daß die Bedeutsamkeit eines Wortes proportional zur Häufigkeit seines Auftretens im Dokument ist, aber umgekehrt proportional zur Gesamtanzahl der Dokumente, in denen es vorkommt.

"Naive Bayesian Learner" ist ein Verfahren, welches auf Wortwiederholungen basiert. Es funktioniert gut bei Elementen die mehrmals dasselbe Wort benutzen, wenn diese Wörter nicht woanders auftreten. Es funktioniert aber schlecht bei kleinen Elementen oder numerischen Elementen. Es berechnet die Wahrscheinlichkeit, mit der ein Element einer Klasse angehört, durch Betrachtung einzelner Instanzen dieses Elements. Diese werden als stochastisch unabhängig angenommen und ihre Einzelwahrscheinlichkeiten werden kombiniert.

"Name matcher" ist ein Verfahren, welches auf Ähnlichkeit der Namen, Synonyme inbegriffen, basiert. Es benutzt auch die TF*IDF Ähnlichkeitsmessung. Es funktioniert gut bei eindeutigen Elementen (z.B. Preis oder Standort) und schlecht bei zweideutigen Elementen (z.B. Geschäft für geschäftliche Telefonnummer) oder zu allgemeinen Elementen (z.B. im Englischen: item).

"County-name recognizer" ist ein Verfahren, welches mit Hilfe eine Webdatenbank Gebietsnamen überprüft.

Wir werden das sehen anhand eines Beispiels: es sei die Tabelle gegeben:
 

Straße	PLZ	Stadt	Telefon	M²	# Zimmer	# Bad	Etage	Bem.
Friedrich 5	06871	Dresden	0341-956875	55	3	1	HG	Sehr gute Lage
Goethe 25	64822	Leipzig	0658-156833	89	4	2	1	Laut wegen Straßenbahn
Bahnhof 6	12599	Berlin	0369-148697	25	1	1	7	Mit Garage
Hornplatz	03688	Neustadt	0248-987	179	10	3	Haus	Ohne Nachbarn
Wiese 88	48833	Fulda	0741-49744	65	3	1	2	Hunde nicht erlaubt

Die Learner versuchen, aus den gelesenen Elementen einen Typ zu ermitteln, d.h. finden sie ein Feld des Format 3 Zahlen + ein Minuszeichen + mindestens 3 Zahlen, ermitteln sie, daß es sich möglicherweise um eine Telefonnummer handeln könnte. Finden sie z.B. 5 Zahlen hintereinender, gehen sie davon aus, daß es sich um eine Postleitzahl handeln könnte. Finden Sie mehrere Wörter oder gar Sätze, ist es eine Bemerkung oder eine Erläuterung. Finden sie ein oder zwei Wörter und eventuell eine Zahl, dann ist es bestimmt eine Adresse usw. Das können sie natürlich erst ermitteln, wenn sie viele Elemente miteinender verglichen haben und wenn sie eine bestimmte Struktur erkennen können.

Wichtig ist hier zu bemerken, daß diese Learner ausschließlich mit gut strukturierten Daten arbeiten. Die Entwickler wollten von vornherein nicht aus dem Fließtext Informationen lesen. Es sei denn, der Fließtext wäre auch sehr stark strukturiert, so daß die Informationen leicht herauszuholen sind.

Das Wissen wird mit Hilfe einer Baumstruktur dargestellt:

Nun muß der Learner fähig sein, die passenden Informationen zusammenzufügen. Hier beispielsweise: Hausadresse = Hausort, Kontakttelefon = Agenttelefon usw.

Die Learner liefern ein Tupel mit einer prozentualen Wahrscheinlichkeit auf Richtigkeit zurück. Die Form des Tupels ist <Information,Typ>, wo eine Information einem Typ zugewiesen wird. Kleine Prozentzahlen zeigen ein unsicheres Ergebnis an im Gegensatz zu großen Zahlen.

Diese Ergebnisse werden von einem Meta-Learner ausgewertet. Dieser überprüft, mit welcher Wahrscheinlichkeit die Ergebnisse korrekt bewertet sind, und entscheidet so, welche Verfahren am geeignetsten für die jeweiligen Elemente sind. Er kann sich aber auch dafür entscheiden, daß ein Verfahren eine unsichere Aussage von einen anderen Verfahren bestätigt oder ablehnt.

LSD wurde auf Sites mit täglichen Aktualisierungen eingesetzt. Die Ergebnisse liegen zwischen 60% und 80% richtiger Raten der Informationen. Hier ist interessant, daß die Learner noch weiter entwickelt werden, und das Meta-Learner kann ohne weitere Probleme ein weiteres Learner einsetzen. Vorteile sind, daß die richtigen Raten ziemlich hoch sind, der Programmieraufwand ziemlich gering ist, die Anzahl der verwendeten Learner klein ist. Dies funktioniert nur gut durch Learner, die auf unterschiedliche Motive reagieren und zusammen fast alle Informationstypen abdecken. Gute Vorkenntnisse sind erforderlich, aber der Arbeitsaufwand nach einem erfolgreichen Start ist sehr gering.

3.2.2 Konkret im WWW

Dieses Verfahren ist noch unreif für den WWW, aber im Laufe der Forschung wird es sich verbessern. Außerdem besitzt dieses Verfahren den großen Vorteil, daß es so gut wie überall einsetzbar ist. Man müßte dieses Wrapper nicht für jede Quelle neu programmieren, es gäbe nur eines davon und es wäre für fast jede beliebige gut strukturierte Website gleich einsetzbar. Zu beachten natürlich, daß für jede neue Domäne die Learner neu trainiert werden müssen.

4 Ein praktisches Wrapper: XWRAP [LPH00]

Abbildung 2: Screenshot von XWRAP
http://www.cc.gatech.edu/projects/disl/XWRAP/xwrap-screenshots

XWRAP ist ein XML-basiertes Verfahren. Das Verfahren hat ein Vielfalt von vordefinierten Wrappers die auf verschiedene HTML-Seitenstrukturen reagieren und mit Hilfe einer Eingabemaske durch den Benutzer konfiguriert werden. Interessant ist dieses Verfahren, weil auch ein Benutzer, der sich hier überhaupt nicht auskennt, in ein paar Schritten ein kompliziertes Wrapper konfigurieren kann.

Hier ist auch beschrieben, wie man konkret eine HTML-Seite parst und die wichtigen Informationen herausholt.

4.1 Ziele

Als erstes muß man ein Programm auf seinen Computer herunterladen und anschließend starten. Man ermittelt dem Programm die gewünschte URL, das Programm startet eine http-Anfrage und die HTML-Seite wird in einem Browser angezeigt. Es sind zwei Fenster geöffnet, in dem einen sind die HTML-Seiten und in dem anderen eine Baumstruktur der HTML-Seiten sichtbar. Der Benutzer gibt den Anfangspunkt der Informationen und das Programm erstellt Regeln um später von allein wieder auf diese Informationen zu kommen.

Anhand eines Beispiel wird die tatsächliche Funktionsweise demonstriert. Gegeben sei eine HTML Seite mit Wettervorhersagen und diese Tabelle, eine der vielen auf dieser Seite gespeicherten Tabellen.

 

Maximale Temperaturen (C)	Minimale Temperaturen (C)
27.8	16.7	In den 6 Stunden vor dem 29 Oktober 2000 12:00
26.7	7.2	In den 24 Stunden vor dem 28 Oktober 2000 12:00

<table border=1> <tr> <td align=center> <h3> Maximale Temperaturen (C) </h3> </td> <td align=center> <h3> Minimale Temperaturen (C) </h3> </td> <td> </td> </tr> <tr> <td align=center> 27.8 </td> <td align=center> 16.7 </td> <td> In den 6 Stunden vor dem 29 Oktober 2000 12:00 </td> </tr> <tr> <td align=center> 26.7 </td> <td align=center> 7.2 </td> <td> In den 24 Stunden vor dem 28 Oktober 2000 12:00 </td> </tr> </table>

Dieser HTML-Code ist vom Programm von falschen HTML-Tags und syntaktischen Fehlern bereinigt, anschließend geparst und in diesen Baum umgewandelt:

Der Benutzer muß also die interessanten Informationen selektieren, und das Programm erkennt in der Baumstruktur, welcher Abzweig von Bedeutung ist. Dann werden diese Regeln gespeichert und das Wrapper kompiliert. Die Regeln geben an, wo und wie man auf die Informationen kommt. Wenn das Wrapper kompiliert ist, muß der Benutzer noch ein paar alternative URL angeben, um das Wrapper zu testen. Wenn der Test erfolgreich ist, hat man ein Wrapper das schon funktionstüchtig ist.

4.2 Funktionsweise

Maximale Temperaturen (C), Minimale Temperaturen (C), <TD> </TD>
27.8, 16.7, In den 6 Stunden vor dem 29 Oktober 2000 12:00
26.7, 7.2, In den 24 Stunden vor dem 28 Oktober 2000 12:00

Der Baum wird durchsucht und daraus wird dieser komma-begrenzte Text mit den wichtigen Daten erzeugt. Er dient später zum Füllen der XML-templates. Die Struktur ist auch vordefiniert, die erste Zeile gibt einen Titel für die darunterliegende Informationen an.

Dazu wird auch noch die Hierarchie des Dokumentes extrahiert. Das Dokument wird zunächst analysiert, um zu wissen, welche Art von Hierarchie besteht. Dann werden die verschiedenen Tabellen oder Sektionen hierarchisch nach Dokumentvorlage gespeichert. Die Entwickler haben nach verschiedenen Studien festgestellt, daß die Hierarchie auch von der Schriftgröße abhängt. Meistens ist ein Titel größer als der darunterliegende Text, so ist es im HTML durch die Tags <Hn> und auch in Tabellen <TR> <TD>, Paragraphen <P> und Aufzählungszeichen <DL> und <DD> ist dies der Fall. Daher kann man auch diese Hierarchie speichern.

Diese Hierarchie dient der besseren Speicherung im XML. Der Benutzer sieht in seinem Fenster die angegebene Hierarchie und kann auch überprüfen, ob seine Angaben richtig sind. Das Programm generiert ein template-XML-Dokument, das die spätere Wrapper-Generierung vereinfacht. Templates sind noch nicht vollständige Dokumente mit Platzhalter, die beim Kompilieren gefüllt werden. XML deshalb, weil auch template-XML-Dokumente richtige XML-Dokumente sind, und in diesem Fall werden die Texthalter in XML kodiert. Z.B. wird das Inserieren eines Felds aus der HTML-Quelle so bezeichnet: <?XG-InsertField-XG "Feldname"?>. Das Programm sucht dann in dem komma-begrenzten Text nach dem Feld und inseriert die Daten an den passenden Punkt. Ähnlich geht es auch mit Iterationen, um einen größeren Bereich des Dokumentes zu durchsuchen. Sie sehen wie gewöhnliche while-Schleifen aus.

4.3 Konkret im WWW

Das größte Problem bei der Generierung ist die Anzahl an Iterationen, um einen ordentlichen Überblick der ganzen Website zu haben. Dafür ist das Wrapper robust.

Der gesamte Zeitaufwand bei der Generierung eines Wrappers ist ziemlich groß. Das liegt daran, daß das Programm in Java geschrieben worden ist, und die Swing Klassen benutzt. Es sind vier Hauptaufgaben:

"Fetch" ist die Aktion, die rohen Daten vom Server herunterzuladen und zu parsen

"Expand" ist die Aktion, den geparsten Baum von Java zu expandieren und anzeigen zu lassen

"Extract" ist die Phase, die Informationen zu extrahieren

"Generate" ist das Generieren der XML-Dokumente

5 Erfahrungen bei der Durchführung eines Projektes: WHIRL [CO99]

Mehrere Wrappers werden eingesetzt, um auf die größte Auswahl an Informationen reagieren zu können. Alle Wrappers erkennen einen speziellen Typ an Informationen

5.1 Entwicklung

Ausgehend von diesem Inhalt werden Wrappers geschrieben. Jedes Wrapper hat ein bestimmtes Gebiet, auf dem es sehr gut ist. D.h. es werden verschiedene Wrappers geschrieben, die auf verschiedene Informationentypen reagieren. Ein bestimmtes Wrapper kann z.B. gut erkennen, ob es sich um Tabellen handelt, ein anderes kann einen Fließtext gut bearbeiten, ein wiederum anderes bearbeitet besser Inhaltsverzeichnisse, das nächste weiß gut mit Bildern umzugehen, ein weiteres holt die Informationen aus die Formatierung heraus usw.

Insgesamt werden mehr als 100 Wrapper eingesetzt. Die Wrappers sind mit einem Spider verbunden. Das Spider erhält die Siteliste und liest die Sites durch. Wenn es eine Seite zu Ende gelesen hat, versucht es, den Typ der Seite mittels Statistiken zu ermitteln. Handelt es sich hauptsächlich um Bilder, um Links, um Tabellen, um Fließtexte, um aufwendig formatierte Texte usw. entscheidet es, welches Wrapper am geeignetsten für die Seite ist. Da diese Ermittlung nicht ganz sicher ist, können auch mehrere Wrappers auf derselbe Seite gestartet werden.

Das Wrapper liest die HTML-Seite vom Cache heraus und speichert die Informationen nach seinen Spezifikationen. Falls das Wrapper auf keine der Informationen reagiert, erhält der Entwickler eine Fehlermeldung. Da sich das Spider manchmal für ein falsches Wrapper entscheidet, ist es normal, daß eine Fehlermeldung erscheint. Dies kostet aber Zeit für den Entwickler, denn er muß die HTML-Seite lesen und verstehen, warum der Fehler gemeldet worden ist. Falls das Spider sich für den richtigen Wrapper entschieden hat, muß das Wrapper geändert werden, denn es hat nicht auf die Informationen reagiert, wofür es programmiert war. Dies kostet wiederum Entwicklungszeit.

Um die Geschwindigkeit zu erhöhen, werden die HTML-Seiten im Cache geladen. Wenn das Wrapper dieselbe Seite wie das Spider aus dem Internet herausholen sollte, würde viel Zeit verloren gehen und viel Bandbreite für nichts verbraucht werden.

In der Tat dauert das Spidern einer ganzen Site mehrere Stunden.

Die Entwicklungszeit für die reine Programmierung des Interface, der Wrappers und der Spiders beträgt ungefähr zwei Tage. Dann müssen während der Zeit von etwa zwei - drei Monaten wöchentlich ein bis zwei Tage Entwicklungszeit eingerechnet werden, um Verbesserungen und Fehlerkorrekturen vorzunehmen und um neue Quellen einzubeziehen. Anschließend sind nur noch ca. zwei Tage pro Monat für die Wartung notwendig, z.B. um die neue Adresse einer Site nachzutragen usw. Diese beschriebene Arbeitszeit wird benötigt, wenn sich nur eine Person mit der Arbeit befaßt.

Problem des Verfahren ist das Auffinden von redundanten Informationen. Das System kann diese nicht unterscheiden. Und hinter diesem Problem verbigt sich, daß falls redundante Informationen in die Datenbank aufgenommen worden sind, die Antwort auf die Anfrage der Nutzer nicht mehr so brauchbar ist.

5.2 Konkret im WWW

Das Anfrageformular wurde so konzipiert, daß "normale" Nutzer diese Fragen stellen könnten. "Normal" bedeutet hier, Nutzer, die keine weitere Ahnung von SQL, Datenbanken, Wrapper, Mediatoren usw. haben. Die Nutzer können sich einfach einer Internetsuchmaschine bedienen. D.h. einer Suche mit einem oder mehreren Stichwörtern. Bemerkenswert ist außerdem, daß mehr als 10% der Anfragen durch das erweiterte Anfrageformular formuliert worden sind. Die Möglichkeit, seine Anfrage zu erweitern, ist durch eine Datenbank ähnlicher Sprache gegeben, also die Benutzung von UND, ODER, NICHT usw.

6 Vergleich der Ansätze mit dem Problem

6.1 Problemspezifikation

Bei WHIRL ist zu bemerken, daß das Verfahren sehr gut mit Fließtext umgehen kann. Bei IM wurde nicht von den Entwicklern gesagt, wie sie die Daten holen, aber es ist stark anzunehmen, daß die Daten auch sehr stark strukturiert sind. LSD kann dafür nur mit sehr gut strukturierten Daten umgehen, also mit Tabellen. XWRAP ist also das einzige Wrapper, das sich für beide Formate eignet. Es hat starke Regeln um eine Tabelle zu parsen, weiß aber auch die Hierarchie einer Seite z.B. durch die Schriftgröße oder die Titel zu holen. Wenn XWRAP einen Wrapper generiert hat, ist aber dieser Wrapper stark von der Struktur abhängig, es kann die Informationen nicht mehr finden, falls die Seite geändert wird. Nur das Programm XWRAP selbst kann sehr gut verschiedene Motive von HTML-Seiten parsen, die Informationen müssen immer noch durch den Benutzer als relevant gezeichnet werden.

Einheitlich können alle vorgeführten Verfahren nur HTML-Seiten auslesen. Dafür ist das Sachgebiet unbedeutend. Solange die Informationen gut strukturiert sind, ist auch jedes Verfahren in der Lage die Informationen rauszuholen.

6.2 Entwicklungsaufwand

Bei allen Verfahren braucht der Entwickler viel Zeit, um erst mal ein globales Schema zu entwickeln.

Bei dem Information Manifold Verfahren wird viel Zeit benötigt, um die Site erst einmal zu beschreiben und um die Klassen herzustellen, die die Weltansicht beschreiben. Jede einzelne Site muß zunächst geprüft werden, was sie für Eingaben braucht, was sie als optionale Eingabe akzeptiert und was sie ausgibt, je nach vollständiger Eingabe.

Bei LSD ist das Aussuchen von passenden Learnern, die möglichst viele Informationen abdecken, und die Zusammenfassung aller Learner außerdem zeitaufwendig. Wenn der Meta-Learner einmal fehlerfrei geschrieben ist, braucht man kaum das Programm zu ändern, denn das Einfügen eines neuen Learners erfolgt ohne weitere Komplikationen.

Bei dem auf WHIRL basierende Verfahren braucht der Entwickler viel Zeit für das Aussuchen der Sites, das Programmieren, die Nachbesserungen und die Wartung.

Das XWRAP soll schnell gehen, da das Produkt eigentlich fertig steht. Man muß nur zweckmäßige Regeln ermitteln, um die Information zu finden. Die Frage aber wie kompliziert XWRAP selbst ist, bleibt offen. Die Entwickler haben nicht beschrieben, wie aufwendig das Schreiben dieses Programm war.

6.3 Ungelöste Probleme

Ein weiteres Problem für Sites mit schneller Aktualisierung ist, was man mit den alten Daten macht. Sind die alten Daten noch aktuell oder müssen sie einfach gelöscht werden? Hier muß man nach dem Grad der Wichtigkeit der Daten entscheiden, ob sie im laufe der Zeit noch relevant sind. Wenn man Häuser verkauft, muß man für die Buchhaltung die Informationen über Häuser behalten, aber die Informationen sind für den Nutzer unwichtig. Anders für Aktien, jeder Tag, sogar jede Stunde zählt. Die Kurse geben eine Tendenz auf längere Zeit. Hier ist es wichtiger, ältere Informationen für den Nutzer zu behalten, damit er bessere Vergleichsmöglichkeiten hat. Ein weiteres Problem des Wrappers ist, daß es die Aktualität der Daten nicht einschätzen kann. Wenn nicht eindeutig auf der Seite steht, wie alt die Daten sind, kann das Wrapper nicht entscheiden, was es mit diesen vermutlich neuen, aber ggf. doch schon alten Daten machen soll. Darunter leidet die Qualität der Daten.

Zur Zeit ist noch unklar, ob die Wrappers u.a. auch mit Bildern umgehen können. Wir sind ausschließlich von HTML-Seiten ausgegangen und die verschiedenen Ansätze haben nichts über andere Materialien als HTML ausgesagt. Es war sogar so, daß nicht einmal jede HTML-Seite hinsichtlich ihre Informationen ausgelesen werden konnte, sondern nur HTML Seiten mit gut strukturiertem Inhalt. In WHIRL wurde kurz über Audiodaten gesprochen, aber es ging nur um die Hierarchie: sprich in welches Verzeichnis gelegt, wie lautet der Titel des Link und der Name der Datei, mehr nicht.

Ein wichtiger Punkt des Wrappers ist die Benutzerfreundlichkeit. Die Eingabemaske für die Anfrage soll verständlich sein und die zurückgegebene Informationen leserlich erscheinen. Leider haben die verschiedenen Ansätze nicht beschrieben, wie sie diese Benutzerfreundlichkeit erreichen.

7 Zusammenfassung

Die großen Unterschiede der verschiedenen Verfahren sind folgende: LSD, IM und WHIRL sind prototypische Verfahren. IM ist im Jahre 1996 geschrieben worden und war ein Versuch mittels Beschreibung. Es wurde nur experimentell in Einsatz genommen. Ähnliches gilt für LSD; dieses Verfahren wurde im Jahre 2000 geschrieben und soll nur zeigen, daß ein solches überhaupt möglich ist. Man wollte versuchen den manuelle Schritt von IM zu automatisieren.

Das WHIRL-Verfahren funktioniert; man braucht aber sehr gute Kenntnisse, um es anzuwenden und zu programmieren. Ziel der Entwickler war es zu zeigen, wie aufwendig es ist, Wrappers in Benutzung zu halten, da ständige Verbesserung und Wartung notwendig sind.

Letztendlich ist das XWRAP ein fertiges Wrapper, es ist ein fertiges Produkt. Durch einfaches Anschließen soll es funktionieren. Ein Nachteil ist hier, daß man das Programm je nach Bedarf nicht mehr selbständig verändern kann. Man kann das Wrapper nicht selbst ändern, man kann nur die Regeln ändern, um zu versuchen, alles zu verbessern. Das Programm ist also schwer erweiterbar. Nur das vorfertige Produkt soll alle möglichen HTML-Seiten abdecken.

Noch ist das Einsetzen eines Wrappers eine sehr schwierigen Aufgabe, es steckt immer noch viel Arbeit dahinter. Die Automatisierung ist sehr gering, außer bei XWRAP, welches bei der Entwicklung und ausschließlich bei dieser hilft, man muß alles selbst schreiben. Die Wartung ist auch sehr zeitaufwendig. Fehlermeldungen des Wrappers müssen überprüft werden, oftmals auch die möglichen Änderungen der gewählte Sites und die zutreffende Änderung im globalen Schema oder in der Beschreibung.

Die Forschung geht weiter voran, um bessere Wrapper zu schreiben. Es ist stark anzunehmen, daß es in ein paar Jahren viel bessere Wrapper geben wird. Hier sei nur auf den riesigen Sprung zwischen IM und LSD in nur vier Jahren hingewiesen.

8 Literatur