Kapitel 5

Implementation

Dieses Kapitel beschreibt, was ich wie und warum gemacht habe. Die Begründung meiner Entscheidungen betrifft insbesondere den Entwurf der Suchmuster, da diese ein zentrales Konzept meiner Arbeit darstellen. Die weiteren Ausführungen beschreiben die Implementation der Systemkomponenten.

Am Ende des Kapitels ist in Abschnitt 5.5 eine Übersicht der Programmabläufe zu finden. Ich habe diesen Abschnitt an's Ende gestellt, da für sein Verständnis die Kenntnis der einzelnen Komponenten notwendig ist. Um einen ersten Eindruck der Abläufe zu bekommen, kann es aber auch sinnvoll sein, diesen Abschnitt zuerst zu lesen. Die Entscheidung sei dem Leser überlassen.

5.1 Entwurf der Suchmuster

Bei der Frage, welche Möglichkeiten IP4W3 für die Formulierung der Suchmuster zulassen soll, habe ich mich an den Möglichkeiten orientiert, die Formatierungssprachen im SGML/XML-Umfeld bieten. Im folgenden begründe ich diese Entscheidung und beschreibe die resultierenden Suchmuster.

Die Aufgabe, die ein Suchmuster erfüllen muß, besteht darin, ein Element einer Dokumentinstanz in Abhängigkeit seiner strukturellen Umgebung zu identifizieren. Obwohl es darum geht, Elemente einer Instanz zu benennen, darf sich die Formulierung nur auf die DTD abstützen. Andernfalls müßten Suchmuster für jedes Dokument maßgeschneidert werden. Zwar kann es sinnvoll sein, dies zu tun¹⁸, der Regelfall ist jedoch, sich auf die DTD zu beziehen.

Es liegt hier eine Situation vor, die in gleicher Weise bei der Formatierung von Dokumenten auftritt. Formatierungssprachen müssen in der Lage sein, Elemente in Abhängigkeit ihrer Umgebung zu behandeln. Beispielsweise hängt die Darstellung eines Elements »Überschrift« davon ab, ob es sich innerhalb eines Kapitels, eines Abschnitts usw. befindet. Abstrakter kann man sowohl bei IP4W3 als auch bei Formatierungssprachen davon sprechen, daß bestimmte Elemente (»was«) in bestimmter Weise (»wie«) behandelt werden. Das »wie« weicht in den beiden Fällen voneinander ab (Formatieren versus Durchsuchen), aber das »was« ist gleich (welches Element in welcher Umgebung?). Es ist also angebracht auch zu untersuchen, welche Mittel aus dem Anwendungsfeld der Formatierungssprachen für IP4W3 geeignet sind.

5.1.1 Elementidentifikation in anderen Systemen

Für den Entwurf der Suchmuster habe ich die (zum Teil noch im Entwurfsstadium befindlichen) Standards DSSSL [ISO96B], HyTime [ISO92], XPointer [W3C98F] und XSL [W3C97E] betrachtet.

Elementidentifikation in DSSSL [ISO96B]
Elemente können in DSSSL nur über den Namen ihres Elementtyps (gi) oder zusätzlich unter Berücksichtigung ihrer Vorgängerelemente (qualified-gi) angesprochen werden. Bei den Vorgängern muß es sich jedoch stets um eine Folge von direkten Vorgängern handeln (Eltern-Kind-Bezug). Es ist nicht möglich, in einem qualified-gi eine Hierarchiestufe auszulassen, um etwa Großeltern-Enkel-Bezüge zwischen Elementen auszudrücken¹⁹. Kompliziertere Elementstrukturen und selbst die Berücksichtigung von Attributen und ihren Werten müssen in DSSSL durch Abfragen mit der sehr mächtigen, aber komplizierten Standard Document Query Language (SDQL) behandelt werden. Dies wäre jedoch für den Administrator von IP4W3 ein zu großer Aufwand.

Ein Beispiel für einen qualified-gi, der ein Element definition innerhalb eines Elements absatz anspricht, ist: absatz definition Hier ist also definition ein Kind von absatz. Sollte definition ein Enkel sein, so ließe sich dies nicht mit einem qualified-gi ausdrücken.

Elementidentifikation in XPointer [W3C98F]
XPointer sind Bestandteil der neuen Hyperlink-Entwicklung des W3C und nicht für die Formatierung entwickelt worden. Vielmehr stellen sie universelle Zugriffsmöglichkeiten auf gesuchte Dokumentstellen zur Verfügung. Es ist deshalb nicht überraschend, daß sie mehr Funktionen bieten als etwa bei der Formatierung benötigt werden.

Bisher gibt es keine (frei verfügbaren) Programme, die die Verarbeitung oder Erstellung von XPointer-Ausdrücken unterstützen. Selbst wenn es sie gäbe, müßte die Verwendung von XPointern in IP4W3 eingeschränkt werden, da ihre Mächtigkeit die Bedürfnisse in diesem Anwendungsfall übersteigt. Eine Implementation in IP4W3 wäre also nur eine Teilimplementation, was zwar kein zwingendes Gegenargument ist, was die Entscheidung für XPointer aber auch nicht begünstigt. Der Funktionsumfang der XPointer ist für IP4W3 ausreichend.

Das obige Beispiel hier noch einmal in XPointer-Notation: child(all,absatz).child(all,definition) Eine kleine Schwäche dieses Ausdrucks ist, daß das Element absatz hier als Kind aufgefaßt wird. Zwar wird es in der Praxis ein Kind irgendeines Elements sein, jedoch ist dieser Ausdruck nicht äquivalent zu vorangegangenem DSSSL-Konstrukt. Besser wäre eine Ausdrucksmöglichkeit der folgenden Form. element(absatz).child(all,definition) XPointer bieten dafür jedoch kein Schlüsselwort an 20, da ein XPointer stets von einem bestimmten Quellelement (in der Regel die Wurzel) ausgeht und von dort eine relative Navigation erlaubt.

Zusammenfassend kann man XPointer als geeignet, jedoch als nicht optimal bezeichnen.

Elementidentifikation in HyTime [ISO92]
HyTime ist ein auf SGML basierender Standard für Hypertext und Hypermedia. In HyTime lassen sich Dokumentstellen mit einem sogenannten Locator adressieren. Locator werden in SGML-Syntax ausgedrückt²¹. Für den Einsatz in IP4W3 sind HyTime-Locator nicht unmittelbar geeignet, da sie primär dazu dienen, Elemente in einer konkreten Instanz zu adressieren. Beispielsweise lassen sich Elemente nur unter Angabe einer ID (nameloc-Form) oder über ihre Position im Elementbaum (treeloc-Form) adressieren. Auch die proploc-Form hilft nicht weiter, da man mit ihr zwar Zugriff auf Eigenschaften (properties), wie zum Beispiel den Generic Identifier, eines Objekts hat, jedoch muß das Objekt schon gegeben sein. Was in IP4W3 benötigt wird, ist, Elemente auf Basis der DTD, also für beliebige Instanzen dieser DTD anzusprechen. IDs oder Positionen können in IP4W3 bei der Elementidentifikation nicht berücksichtigt werden, da sie nicht bekannt sind.

Um mit HyTime die gewünschten Ausdrucksmöglichkeiten zu erhalten, muß die HyTime Query Language (HyQ) bemüht werden. Das obige Absatz-Definition-Beispiel sieht dann so aus:

<HyQ> Select(DOMTREE and(Eq(Proploc(CAND GI) "absatz") Select(Relloc(Treeloc(DOMROOT 1) DOMROOT CHILDREN ) Eq(Proploc(CAND GI) "definition")) ) ) </HyQ>

Bei Verwendung von HyQ bleibt nicht mehr viel von der SGML-Syntax übrig, so daß dieser Vorteil nicht mehr besteht. Des weiteren gilt auch hier, noch mehr als bei XPointer, daß HyQ so mächtig ist, daß für den Einsatz in IP4W3 nur eine Teilmenge sinnvoll wäre. Der Standard müßte also eingeschränkt werden; ich halte es jedoch für erstrebenswerter, eine »schlankere« Syntax vollständig zu implementieren als eine mächtige Sprache nur zum Teil.

Elementidentifikation in XSL Note [W3C97E]
An dieser Stelle unterscheide ich zwischen dem aktuellen Zustand von XSL und dem ursprünglichen Entwurf [W3C97E], der nur den Status einer »Note« bekommen hat. Gemein ist beiden, daß als zugrundeliegende Syntax XML zum Einsatz kommt. Es gibt jedoch Unterschiede, wie Elemente identifiziert werden. Da ich meine Arbeit begonnen habe als die »Note« aktuell war, beziehe ich mich im folgenden darauf.

XSL erlaubt, wie DSSSL, die Elementidentifikation über den Namen des Elementtyps (in sogenannten Patterns). Verschachtelte Elemente lassen sich ebenfalls formulieren. Vorgängerrelationen können in XSL, im Gegensatz zu DSSSL, auch Hierarchiestufen überspringen, um z.B. Großeltern-Enkel-Bezüge zwischen Elementen zu beschreiben. Darüber hinaus kann XSL ohne großen Aufwand die Existenz von Attributen und ihren Werten überprüfen. Aufgrund der Tatsache, daß die Syntax XML ist, lassen sich die Eigenschaften leicht formal in Form einer DTD fassen.

Das obige Beispiel nimmt hier folgende Gestalt an: <!-- XSL Note Pattern in XML-Syntax --> <element type="absatz"> <target-element type="definition"/> </element>

5.1.2 Elementidentifikation in IP4W3

Für die Elementidentifikation in IP4W3 habe ich mich an den XSL-Patterns orientiert. Sie stellen alle Funktionen zur Verfügung, die für die Bezeichnung von Elementstellen zur Suche in IP4W3 benötigt werden. Außerdem stellt die Syntax für den Administrator kein Hindernis dar; in Verbindung mit einer DTD ist sogar automatisch eine Benutzerschnittstelle vorhanden, die dem Administrator vertraut ist und mit einem SGML/XML-Editor für einen guten Bedienkomfort sorgt. Die XSL-Note [W3C97E] enthält auch eine DTD für die in XML formulierten Patterns. Da absehbar war, daß die XSL-Note eine ungewisse Zukunft vor sich hat, habe ich nicht direkt diese DTD übernommen, sondern eine eigene geschrieben, die sich jedoch sehr stark an die DTD der Note anlehnt. Durch diesen Schritt konnte ich diesen Teil von IP4W3 von den zu erwartenden Veränderungen im XSL-Umfeld entkoppeln. Außerdem konnte ich so auch Erweiterungen einbringen, die für IP4W3 unbedingt benötigt werden, wie zum Beispiel Informationen über das zu generierende HTML-Formular.

Ein Beispiel für ein IP4W3-Suchmuster:

<element type="absatz"> <target-element type="definition"> </target-element> </element>

Weitere Beispiele habe ich bereits in Abschnitt 3.2 gezeigt. Deshalb verzichte ich an dieser Stelle darauf.

Die Gründe für die Verwendung von XSL-basierten Suchmustern in IP4W3 lassen sich wie folgt zusammenfassen:

• Die SGML/XML-Syntax ist dem Administrator vertraut.
• Die Bereitstellung einer DTD für die Suchmuster ermöglicht die Verwendung eines SGML/XML-Editors als Benutzerschnittstelle.
• Die eigens für IP4W3 entworfene DTD ist den speziellen Bedürfnissen und Möglichkeiten des Systems angepaßt. Sollte der Funktionsumfang des Systems durch Unterstützung komplexerer Suchmuster erweitert werden, läßt sich die DTD leicht anpassen.
• Keiner der anderen genannten Ansätze bietet alle diese Vorteile.

5.2 Programme

Dieser Abschnitt beschreibt die Implementierung der Programme von IP4W3. Ihre Aufgaben umfassen die Erzeugung von HTML-Formularen, die Indexierung und Indexsuche in Dokumenten, das Feststellen von Übereinstimmungen mit Suchmustern, die Ermittlung eines Atoms, das Formatieren von Dokumentausschnitten sowie die Unterstützung des Administrators bei der Bedienung von IP4W3.

5.2.1 Formulargenerator

Die Aufgabe des Formulargenerators besteht darin, die Suchmuster einzulesen und daraus ein HTML-Abfrageformular zu erzeugen. Er akzeptiert als Eingabe die analysierte Form von Suchmustern (d.h. einen ESIS-Strom [ISON1035], der von einem SGML/XML-Parser wie SP geliefert wird), wie sie in Abschnitt 3.2.1 beschrieben sind. Die Ausgabe des Generators ist ein HTML-form-Element gemäß HTML-4-DTD²².

Der Formulargenerator ist in der Tool Command Language (Tcl) implementiert, basiert auf dem SGML-Verarbeitungsprogramm CoST und ist in der Datei suchmuster2formular.cost zu finden. Ich habe CoST als Grundlage gewählt, weil dieses Programm eine programmierbare Schnittstelle (über Tcl) für den Zugriff auf SGML-Instanzen (in diesem Fall die Suchmuster) bietet.

Funktionsweise des Programms
Die Informationen zur Formularerzeugung sind in Suchmustern in den Elementen vom Typ target-element und darin im Elementtyp form enthalten. Es sind zwei mögliche Formularkomponenten zugelassen:

• Textfelder (Elementtyp textinput), denen mit dem Attribut wertebereich einer der folgenden Wertebereiche zugewiesen werden kann: beliebig, buchstaben, posinteger.
• Auswahlfelder (Elementtyp select), die dazu dienen, eine 1-aus-n-Auswahl zu ermöglichen. Dazu enthält ein select-Element mindestens ein Element vom Typ option.

Die Überprüfung des Wertebereichs findet client-seitig statt. Die in Abschnitt 5.4 beschriebene JavaScript-Funktion pruefe_wert() realisiert die Validierung. Für den Formulargenerator bleibt hierbei nur die Aufgabe, die JavaScript-Bibliothek in die HTML-Seite zu integrieren und die Formularelemente über HTML-Ereignisattribute mit den entsprechenden Funktionen zur Ereignisbehandlung zu verbinden.

Die beiden beschriebenen Formularkomponenten orientieren sich wegen ihres Verwendungszwecks an HTML-Formularen. Aus diesen Grund kann der Formulargenerator eine relativ einfache Abbildung durchführen, die der folgende Pseudo-Code zeigt:

Ausgabe des Formularkopfes;
Ausgabe des Script-Element zum Laden der JavaScript-Bibliothek;
// Schleife für jedes target-element:
Für jedes Element T vom Typ target-element
begin
  // Behandlung von textinput:
  Für das Kindelement F von T vom Typ form
  begin
    Für das Kindelement I von F vom Typ textinput
    begin
      Ausgabe des HTML-Elements zur Texteingabe
    end;
  end;

  // Behandlung von select:
  Für das Kindelement F von T vom Typ form
  begin
    Für das Kindelement S von F vom Typ select
    begin
      Ausgabe des HTML-Elements SELECT
      // alle Optionen ausgeben
      Für jedes Kindelement O von S vom Typ option
      begin
        Ausgabe des HTML-Elements OPTION
      end;
    end;
  end;
end;

5.2.2 Indexierung von und Indexsuche in SGML/XML-Dokumenten

Die Erzeugung eines Stichwortverzeichnisses passiert in zwei Schritten. Zunächst muß das Dokument so verändert werden, daß ein Element eindeutig bezeichnet werden kann. Im zweiten Schritt wird dann ein Verzeichnis erstellt, das es erlaubt, jedes Wort auf den Elementbezeichner des Elements abzubilden, in dem es vorkommt.

Um die Elementbezeichner in eine Instanz einzubringen, habe ich ein DSSSL-Programm geschrieben (ergaenze-ids.dsssl), das jedes Element einer Instanz mit einem Attribut namens internal-id ausstattet. Als Wert des Attributs wird eine fortlaufende Nummer, beginnend beim Wurzelelement vergeben. Die Ausgabe dieses Prozesses ist eine wohlgeformte, aber nicht gültige XML-Instanz, d.h. die Instanz besitzt keine Doctype-Deklaration mehr. Auf die Gültigkeit der Instanz kann beziehungsweise sollte aus folgenden Gründen verzichtet werden:

• Die ursprüngliche Instanz wird bereits beim Ergänzen der Elementbezeichner von einem Parser auf Korrektheit überprüft. Bei der weiteren Benutzung der veränderten Instanz ist deshalb gewährleistet, daß sie syntaktisch korrekt ist. Dies gilt natürlich nur, wenn (a) beim ersten Parsing kein Fehler entdeckt wird und wenn (b) die programmgesteuerte Veränderung keine neuen Fehler einbaut. Ersteres wird dem Administrator beim Parsing gemeldet, letzteres ist durch mein Programm gewährleistet.
• Durch die nicht mehr stattfindende Validierung der Instanz gegen die DTD sind nachfolgende Verarbeitungsschritte (z.B. die Formatierung) schneller als sie es mit Validierung wären.
• Würde man die Gültigkeit der ausgegebenen Instanz verlangen, so wäre eine Manipulation der DTD notwendig. Es müßte zumindest die Attributlistendeklaration jedes Elementtyps verändert werden, um das Attribut internal-id zu deklarieren. Soweit es XML betrifft, ist dies noch relativ leicht zu bewerkstelligen, da es für jeden Elementtyp mehrere Attributlistendeklarationen geben darf, die vom Parser zusammengefaßt werden. Im allgemeinen SGML-Fall ist dies jedoch nicht so, da diese Möglichkeit erst durch den »Annex K, Web SGML Adaptations« [ISO97] am 4. Dezember 1997 als optionale Möglichkeit in SGML eingeführt wurde²³. Diese Operation ist deshalb nicht ganz einfach zu implementieren. Dank der angeführten Gründe war es auch nicht notwendig oder gar sinnvoll.

Ich habe DSSSL für diese Aufgabe gewählt, weil die Sprache zusammen mit den Erweiterungen der DSSSL-Maschine Jade ein bequemes Werkzeug zur Transformation von SGML-Instanzen (Eingabe SGML, Ausgabe SGML) darstellt.

Für den Aufbau des Wortindex habe ich ein CoST-Programm geschrieben (makeindex.cost), das eine Liste von Worten mit dazugehörigen Elementbezeichnern (also den Werten des Attributs internal-id) erzeugt. CoST besitzt einen Verarbeitungsmodus, der die ereignisgesteuerte Verarbeitung von SGML-Instanzen erlaubt. Das Programm durchläuft die baumartige Darstellung des Dokuments im Tiefendurchlauf und erzeugt bei Erreichen oder Verlassen von Knoten ein Ereignis. Eines dieser Ereignisse ist das Erreichen eines CDATA-Knotens (Character Data), also eines Knotens, der Text (im Gegensatz zu beispielsweise Start- oder End-Tags) enthält. Der Event-Handler meines Programms kann nun auf den Inhalt eines CDATA-Knotens zugreifen. Dieser Inhalt steht als Tcl-Zeichenkette zur Verfügung. Um die einzelnen Worte zu erhalten, breche ich die Zeichenkette an vorgegeben Trennzeichen (Punkt, Komma, Bindestrich usw.) auf und gebe die so erhaltenen Worte zusammen mit dem zuvor ermittelten Elementbezeichner aus. Der Elementbezeichner bezieht sich dabei auf den nächsten Vorfahren, der ein Attribut namens internal-id besitzt. In Pseudo-Code nimmt der Event-Handler folgende Gestalt an:

// Event-Handler für CDATA-Knoten

// Inhalt des Knotens ermitteln
var inhalt    := ermittle Inhalt des Knotens;

// Inhalt in Worte auftrennen
var wortliste := trenne inhalt an den zeichen { ,.\t-()"!;/:};

// Element-ID des nächsten Vorfahren ermitteln
var elemID    := Ermittle den Attributwert des Attributs "internal-id"
                 des nächsten Vorfahren;

// alle Worte mit Element-ID ausgeben
Für jedes Wort W in wortliste 
begin
  Ausgabe von W und elemID;
end;

Anschließend liegt der Index als zweispaltige Tabelle vor. Die linke Spalte enthält ein Wort und in der rechten Spalte steht der zugehörige Elementbezeichner.

CoST war hier das Programm der Wahl, weil mit der zugrundeliegenden Sprache Tcl auch die leichte Verarbeitung von Komponenten möglich ist, die außerhalb der Reichweite von SGML liegen. In diesem Fall meine ich damit die einzelnen Worte. Die Modellierung von SGML/XML endet bei Parsed Character Data (PCDATA). Ob es sich bei PCDATA um einen Buchstaben, ein Wort, einen Satz oder ganze Absätze handelt, ist in SGML/XML nicht darstellbar und mit einigen Werkzeugen zur Verarbeitung nicht oder nur mit großem Aufwand zu handhaben. Zum Aufbau eines Wortindex sind die Möglichkeiten von CoST/Tcl hingegen sehr gut geeignet.

Bei der Stichwortsuche wird der so aufgebaute Index vom CGI-Skript (search.pl) sequentiell durchlaufen und das gesuchte Wort wird mit den Worten auf der linken Seite verglichen. Jeder Treffer liefert den Elementbezeichner auf der rechten Seite zurück. Bei diesen Treffern handelt es sich zunächst nur um potentielle Treffer, da in einem weiteren Schritt geprüft werden muß, ob sich der Treffer im gewünschten Elementkontext (festgelegt durch ein Suchmuster) befindet. Dieser Vorgang wird im folgenden Abschnitt 5.2.3 beschrieben.

Diskussion des Suchvorgangs
Die Stichwortsuche ist relativ einfach implementiert. Eine sequentielle Suche scheint mit Blick auf die Laufzeit eine schlechte Wahl zu sein. Eine naheliegende Verbesserung wäre der Einsatz eines Hashing-Verfahrens zur Effizienzsteigerung. Aus mehreren Gründen habe ich dies nicht implementiert.

• Da sich IP4W3 noch in der Testphase befindet, ist nicht absehbar, welche Möglichkeiten bei der Suche benötigt werden. Beispielsweise ist die Suche nach regulären Ausdrücken mit dem herkömmlichen Hashing nicht möglich. Die vorliegende Implementierung der sequentiellen Suche mit Perl läßt sich direkt auf reguläre Ausdrücke ausweiten.
• Die Effizienzsteigerung bei der Suche mit einem Hashverfahren ist zwar unbestritten, jedoch kostet der Aufbau der Hashtabelle genau so viel Zeit, wie die sequentielle Suche. Den Vorteil des Hashing kann man nur dann ausnutzen, wenn die Tabelle nur einmal aufgebaut wird und wenn anschließend mehrere Suchen damit ausgeführt werden. Dies ist hier nicht möglich, da das CGI-Skript bei jeder Suche vom Web-Server neu aufgerufen wird. Würde es dann zunächst die Indexdaten sequentiell einlesen und daraus die Hashtabelle aufbauen, so könnte man in der gleichen Zeit die sequentielle Suche durchführen.
  Eine Alternative wäre es, eine binäre Suche in der sortierten Wortliste auf der Festplatte durchzuführen. Dazu müßte jedoch die Größe eines Feldes (und damit die maximale Wortlänge eines Stichworts) beschränkt werden. Sollte sich die Suche als zu langsam herausstellen, wäre das die beste Alternative. Nachteile wären auch hier der Verzicht auf die Suche nach regulären Ausdrücken sowie der erhöhte Platzbedarf, der aus der festen Feldgröße resultiert.
  Bei den Testläufen war die Laufzeit der Suche verschwindend gering, so daß die tatsächliche Antwortzeit stärker von Einflüssen abhängt, die außerhalb von IP4W3 liegen²⁴.

5.2.3 Prüfen auf Übereinstimmung mit dem Suchmuster und Ermitteln des passenden Atoms

Die bei der Indexsuche gefundenen Treffer sind zunächst nur Übereinstimmungen von Suchbegriff und Indexeintrag. Es muß noch geprüft werden, ob die Treffer auch in der richtigen Umgebung liegen. Das heißt, das gefundene Wort muß sich innerhalb des gewünschten Zielelements und dieses innerhalb der richtigen umgebenden Elemente befinden. Der Benutzer wählt dazu eine Kategorie aus, in der er die Suche durchführen möchte. Das zu einer Kategorie korrespondierende Suchmuster enthält die Informationen, die zur Umgebungsprüfung benötigt werden. Um die Prüfung möglichst schnell durchführen zu können, werden die Suchmuster einmalig in Programmcode umgewandelt, den das Programm zur Umgebungsprüfung und Atomermittlung (search-atoms.cost) zur Laufzeit einlesen und direkt ausführen kann (vgl. Abbildung 16). Die Umwandlung wird von suchmuster2umgebungspruefung.cost durchgeführt. Als Eingabe bekommt dieses CoST-Programm²⁵ eine Instanz mit Suchmustern und erzeugt als Ausgabe ein assoziatives Array mit den CoST-Programmanweisungen zur Umgebungsprüfung. Als Index für das Array wird die ID des Suchmusters verwendet, die laut DTD notwendig (REQUIRED) ist.

Abbildung 16: Umgebungsprüfung: Ablauf zur Initialisierung und zur Laufzeit

Bei der Umwandlung eines Suchmusters in Programmcode muß berücksichtigt werden, daß die Überprüfung in einem Blatt des Dokumentbaums stattfindet. Dies liegt daran, daß in SGML/XML-Dokumenten nur in Blättern Text enthalten sein kann, also kann auch nur dort ein Treffer auftreten. Zur Umgebungsprüfung navigiert mein Programm (search-atoms.cost) deshalb zu diesem Blatt und »schaut« in der Hierarchie nach oben. Diese Sichtweise spiegelt sich im Algorithmus wider, mit dem suchmuster2umgebungspruefung.cost ein Suchmuster verarbeitet, um die Programmanweisungen zur Umgebungsprüfung zu erzeugen. Um das Suchmuster »bottom-up« zu durchlaufen, führt das Programm eine Tiefensuche durch und gibt bei Erreichen eines End-Tags den entsprechenden CoST-Programmcode aus. Durch dieses Vorgehen ist die gewünschte Sichtweise gewährleistet. Es folgt der zuständige Event-Handler als Pseudo-Code:

// Event-Handler, der bei Erreichen eines
// *End-Tags* ausgeführt wird
if aktuelles Element E hat Start-Tag der Form <ELEMENT TYPE=x>
then
    Ausgabe: Programmcode, der zum Vaterelement vom Typ x navigiert;

    // Kindelemente namens attribute
    Für jedes Kindelement K von E vom Typ <ATTRIBUTE NAME=y VALUE=z>
    begin
       Ausgabe: Programmcode, der prüft, ob es ein Attribut
                  namens y mit Wert z gibt;
    end;
elseif aktuelles Element E hat Start-Tag der Form <ELEMENT>
then
    Ausgabe: Programmcode, der zum Vaterelement navigiert;

    // Kindelemente namens attribute
    Für jedes Kindelement K von E vom Typ <ATTRIBUTE NAME=y VALUE=z>
    begin
       Ausgabe: Programmcode, der prüft, ob es ein Attribut
                namens y mit Wert z gibt;
    end;
elseif aktuelles Element E hat Start-Tag der Form <TARGET-ELEMENT TYPE=x>
then
    Ausgabe: Programmcode, der prüft, ob das aktuelle Element
             vom Typ x ist;

    // Kindelemente namens attribute
    Für jedes Kindelement K von E vom Typ <ATTRIBUTE NAME=y VALUE=z>
    begin
       Ausgabe: Programmcode, der prüft, ob es ein Attribut
                namens y mit Wert z gibt;
    end;
elseif aktuelles Element E ist vom Typ ANY
then
    Ausgabe: Programmcode, der nacheinander zu allen Vorfahren navigiert;
fi;

Es werden nur die Elementtypen element, target-element, any und attribute betrachtet. Andere Typen, die in Suchmustern vorkommen, haben keine Bedeutung für die Umgebungsprüfung. Als Beispiel sei hier ein Suchmuster aus dem Anwendungsbeispiel »XML-Spezifikation« gezeigt, gefolgt von dem CoST-Programmcode, den der obige Event-Handler beim Tiefendurchlauf generiert.

<suchmuster id="def"> <element type="absatz"> <any> <target-element type="definition"> <beschreibung>Begriffsdefinitionen</beschreibung> <form> <textinput wertebereich="beliebig"> </form> </target-element> </any> </element> </suchmuster> Es treten nacheinander die Ereignisse für die End-Tags </target-element>, </any>, </element> ein (im Suchmuster hervorgehoben). Der Programmcode, der durch obige Ereignisroutine erzeugt wird, sieht wie folgt aus: element "definition" ancestor parent element "absatz" Gespeichert wird diese Ausgabe in einem Arrayeintrag, der den Index »def« (das ist die ID des Suchmusters) besitzt. Je nach Anzahl der Suchmuster gibt es entsprechend viele Arrayeinträge. Die Ausführung des obigen Programmcodes durch CoST läßt sich umgangssprachlich folgendermaßen interpretieren: Wenn das aktuelle Element vom Typ definition (element "definition") ist, wähle den nächsten Vorfahren (ancestor) aus (in CoST ist ein Element auch Vorfahre von sich selbst), wähle dann das Vaterelement (parent); ist es vom Typ absatz (element "absatz")? Sobald diese letzte Frage positiv beantwortet wird, wird die Abarbeitung beendet. Andernfalls würde über einen Backtracking-Mechanismus zu einer vorhergehenden Abfrage zurückgesprungen, für die es eine weitere Lösung gibt. In diesem Fall kann ancestor mehr als eine Lösung haben, da ancestor schrittweise alle Vorfahren bis zur Wurzel auswählt.

Das Programm search-atoms.cost liest die Ausgabe von suchmuster2umgebungspruefung.cost ein und greift über die ID des Suchmusters direkt auf den Programmcode zu, der zur Umgebungsprüfung ausgeführt wird. Dabei wird ein boolescher Wert als Ergebnis geliefert. Der logische Wert »wahr« bedeutet, daß der fragliche Treffer aus der Stichwortsuche tatsächlich in der richtigen Umgebung stattgefunden hat. Andernfalls trat die Wortübereinstimmung an einer anderen Stelle im Dokument auf. Auf eine detaillierte Darstellung als Pseudo-Code kann hier verzichtet werden, weil die Vorgehensweise sehr einfach ist: search-atoms.cost bekommt als Parameter die vom Benutzer ausgewählte Kategorie übergeben. Im obigen Beispiel wäre das »def«. Die Auswertung der Anweisung

query? element "definition" ancestor parent element "absatz"

liefert bereits den gesuchten booleschen Wert. Die eigentliche Arbeit besteht also darin, die Suchmuster in die CoST-Anweisungen zu überführen, die dann nur (mit dem Präfix query? versehen) ausgeführt werden.

Die möglichen Fälle bei der Suche/Umgebungsprüfung werden nun folgendermaßen behandelt:

Kein Treffer bei der Stichwortsuche

Der Benutzer erhält eine entsprechende Rückmeldung.

Treffer bei der Stichwortsuche in der richtigen Umgebung

Der Benutzer erhält eine Kurzansicht der Treffer (HTML-Trefferliste) und kann daraus auswählen.

Treffer bei der Stichwortsuche, aber nicht in der richtigen Umgebung

Der Benutzer erhält eine Meldung darüber, daß es Treffer außerhalb der von ihm gewählten Kategorie gab. Er kann dann eine Suche ohne Kategorie ausführen.

Ermittlung des Atoms
Wurde ein Treffer in der richtigen Umgebung gefunden, so ermittelt search-atoms.cost das zugehörige Atom. Wie bereits früher ausgeführt, stimmen Atome und Suchmuster in der vorliegenden Implementation von IP4W3 überein. Aus diesem Grund wird als Atom unmittelbar das Element zurückgeliefert, das bei der Umgebungsprüfung als äußerstes Element gefunden wurde.

Interessant ist noch die Frage, was passiert, wenn eine Suche ohne Kategorie, also ohne Suchmuster durchgeführt wird. In diesem Fall wird jeder Treffer als in der richtigen Umgebung befindlich angesehen. Für die Ermittlung des Atoms verwende ich in diesem Fall folgende Heuristik: Ausgehend von dem Zielelement, das den gesuchten Begriff enthält, gehe ich in der Elementhierarchie so weit nach oben, bis ich auf ein Element treffe, das keinen gemischten Inhalt (mixed content) enthält. Umgangssprachlich heißt das, ich suche einen Vorfahren, der selbst keinen Text, sondern nur Kindelemente enthält. Ein solches Element wird auch als Container-Element bezeichnet. Container-Elemente sind als Vorgabeatome geeignet, da meine Betrachtung verschiedener Dokumenttypen zeigt, daß Container meist Dokumentteile enthalten, die auch alleinstehend verständlich sind. Da die Suche ohne Kategorie eine Ausnahme darstellt, ist diese Heuristik meiner Meinung nach adäquat, was auch durch die betrachteten Anwendungsbeispiele unterstützt wird.

Generierung der HTML-Trefferliste
Zu jedem gefundenen Atom erzeugt search-atoms.cost auch die HTML-Ausgabe für die Trefferliste. Dabei handelt es sich um eine Tabelle, die in jeder Zeile einen Treffer enthält. Jede Zeile besitzt eine HTML-Checkbox, die der Benutzer anklicken kann, um den Treffer vollständig zu sehen. Daneben befindet sich eine Kurzfassung des Atoms. Diese Kurzfassung besteht aus jeweils n Zeichen des Atoms und des Zielelements. Vom Atom werden die ersten n Zeichen angezeigt und vom Zielelement die ersten n/2 Zeichen vor und nach dem gesuchten Begriff. Der Wert von n ist momentan auf 100 vorgegeben.

5.2.4 Formatierer (DSSSL-Rahmen)

Bei der Formatierung geht es in diesem Zusammenhang primär (aber nicht nur) um die Transformation von beliebigen SGML/XML-Dokumenten in HTML zur Darstellung im Web-Browser. Eine Formatierung für den Ausdruck soll dabei nicht ausgeschlossen sein.

Aufgrund dieses allgemeinen Ansatzes muß es eine Schnittstelle geben, die dem Benutzer erlaubt, Formatierungsanweisungen für einen Dokumenttyp in IP4W3 zu integrieren. Folgende Ziele wurden dabei verfolgt:

• Berücksichtigung von offenen Standards
• Eignung für Online- (HTML) und Papierausgabe

Im Umfeld von SGML/XML und dem World Wide Web stehen folgende Alternativen zur Verfügung:

• Cascading Style Sheets (CSS, [W3C96A] und [W3C97A])
• Extensible Style Language (XSL, [W3C98K])
• Document Style Semantics and Specification Language (DSSSL, [ISO96B])

Die Cascading Style Sheets sind eng an HTML gebunden und auch in ihrem Level 2 nicht mächtig genug, um den Ansprüchen in diesem Kontext zu genügen. Gegen XSL spricht, daß die Sprache noch nicht endgültig verabschiedet ist. Das W3C will die Entwicklung Mitte 1999 abschließen²⁶. Ein praktisches Argument gegen XSL ist die mangelhafte Implementation; ein frei verfügbares Programm (XT) ist sehr instabil und nicht einsetzbar. DSSSL ist unter den genannten Alternativen zum gegenwärtigen Zeitpunkt die beste und wurde aus folgenden Gründen für IP4W3 gewählt:

• DSSSL ist eine ISO-Norm, die 1996 verabschiedet wurde.
• DSSSL ist für die Formatierung auf Papier geeignet und in der Implementierung Jade auch hervorragend für die HTML-Ausgabe geeignet.
• DSSSL-Formatierungen sind unabhängig vom Dateiformat²⁷ (RTF, Postscript, PDF).

DSSSL-Rahmen
Innerhalb von IP4W3 besteht der Formatierer aus einem DSSSL-Rahmen (format.dsssl), der zur Anwendung durch ein Rumpf-Programm für die spezielle DTD ergänzt werden muß. Der Rahmen navigiert zu den auszugebenden Elementen, die über ihre eindeutigen Elementbezeichner adressiert werden, und übergibt dann die Kontrolle an den Rumpf.

Beispiel (vgl. Abbildung 17): Wenn die Elemente A und B, die sich an beliebiger Stelle im Dokument befinden, formatiert werden sollen, sieht die Verarbeitungsreihenfolge so aus: Der DSSSL-Rahmen durchläuft das Dokument (Tiefensuche) und prüft in jedem Knoten, ob es sich um das Element A oder B handelt. Sobald er das erste Element findet (hier A), formatiert der Rumpf den gesamten Teilbaum, dessen Wurzel A ist. Da DSSSL auch hierbei eine Tiefensuche ausführt, übergibt der Rumpf die Kontrolle wieder an den Rahmen, nachdem der gesamte Teilbaum abgearbeitet ist. Der Rahmen wird also nicht noch einmal in den Teilbaum A hinabsteigen, sondern seine Suche nach dem Knoten B in dem nicht abgearbeiteten Teil fortsetzen.

Abbildung 17: Aufgabe des Formatier-Rahmens: Navigation zu den gesuchten Elementen

Problem bei dieser Vorgehensweise Falls der DSSSL-Rumpf nicht speziell für den Einsatz in IP4W3 entwickelt wurde28, muß man bedenken, daß sich Anweisungen im Rumpf auf Grundeinstellungen (bei Webseiten zum Beispiel die Hintergrundfarbe, bei Papierausgabe zum Beispiel das Seitenformat) abstützen, die für die Dokumentenwurzel gemacht werden. Da der Rumpf die Kontrolle nun erst später erlangt, kann es sein, daß die Grundeinstellungen noch nicht durchgeführt wurden.

Bei der Numerierung von Abschnitten treten keine unerwünschten Nebeneffekte auf, da die Formatierung im Kontext des gesamten Dokuments durchgeführt wird.

Navigation zu den zu formatierenden Elementen
Das Aufsuchen der zu formatierenden Elemente ist für die Geschwindigkeit des Vorgangs sehr wichtig. In der Regel ist die Anzahl der auszugebenden Elemente sehr klein im Vergleich zur Anzahl aller Elemente im Dokument. Das liegt daran, daß die Anzahl der Treffer möglichst gering sein soll. Des weiteren stehen die Treffer meist weit unten in der Hierarchie der Elemente, um kleine Dokumentausschnitte als Treffer zu erhalten. Ich habe deshalb die von DSSSL durchgeführte Tiefensuche modifiziert, um das Durchsuchen ganzer Teilbäume zu vermeiden, sofern die Aussage möglich ist, daß sich in einem fraglichen Teilbaum kein Treffer befindet²⁹. Dazu habe ich ausgenutzt, daß als Elementbezeichner ausschließlich fortlaufende Zahlen benutzt werden, deren Ordnung die Reihenfolge der Elemente beim Tiefendurchlauf angibt. Die genaue Vorgehensweise des DSSSL-Rahmens zeigt das folgende Listing im Pseudo-Code, das ich anschließend noch erläutere.

var atom_ids := Liste der zu formatierenden Element-IDs

// Behandlung eines Elements
if Element-ID des aktuellen Elements E ist in atom_ids enthalten
then Formatiere aktuelles Element  // Wechsel zu DSSSL-Rumpf (1)
else 
    if aktuelles Element E hat keinen Bruder rechts im Elementbaum
    then (3)
        Verarbeite rekursiv alle Kinder K des aktuellen Elements E;
    else (4)
        Min := Element-ID des aktuellen Elements + 1;
        Max := Element-ID des Bruders - 1;
        // [Min,Max] ist also das Interval der 
        // Element-IDs aller Nachfahren

        if es gibt ein Element X in atom_ids: Min <= X <= Max
           // das heißt mindestens ein Nachfahre ist zu formatieren
        then (5)
            Verarbeite rekursiv alle Kinder K des aktuellen Elements E;
        else (6)
            Liefere leeres Flow Object als Ergebnis;
        fi
    fi
fi

Falls das aktuelle Element zu den zu formatierenden gehört, wird die Kontrolle, wie oben beschrieben, an den Rumpf übergeben (1). Im anderen Fall (2) hängt das weitere Vorgehen davon ab, ob es einen jüngeren Bruder gibt. Das ist ein Element, das den gleichen Vater wie das aktuelle Element besitzt und in der Instanz unmittelbar auf das aktuelle Element folgt. Bei SGML/XML muß man noch unterscheiden, ob Elemente Geschwister sind, wenn sie nicht vom gleichen Typ sind. In DSSSL ist dieser Unterschied von Bedeutung. In IP4W3 spielt der Elementtyp keine Rolle. Die Überprüfung wird deshalb mit der Funktion absolute-last-sibling? und nicht mit last-sibling? ausgeführt (siehe 10.2.4.4 in [ISO96B]). Falls es einen solchen Bruder gibt (4), ist es möglich, das Intervall zu bestimmen, in dem die Elementbezeichner der Nachfahren liegen. Falls es ein Element in der Liste der zu formatierenden Elementbezeichner gibt, das innerhalb des Intervalls liegt, so werden rekursiv alle Kinder abgearbeitet (5). Im anderen Fall ist klar, daß kein Nachfahre formatiert werden muß. Also kann der gesamte Teilbaum ausgelassen werden (6). Für den Fall, daß es gar keinen jüngeren Bruder gibt (3), ist es nicht möglich, das Intervall der Elementbezeichner der Nachfahren unmittelbar zu bestimmen³⁰. Aus diesem Grund werden auch dann alle Kinder abgearbeitet. Der rechte Zweig eines Teilbaums wird also stets betrachtet.

Verhindern von mehrfacher Ausgabe von Dokumentausschnitten
Das Umschalten zwischen Rahmen und Rumpf sorgt auch dafür, daß zwei zu formatierende Elemente, die ineinander verschachtelt sind, nicht mehrfach ausgegeben werden.

Abbildung 18: Formatierung von verschachtelten Elementen

Abbildung 18 illustriert diese Situation: Neben den Elementen A und B soll auch noch das Element C ausgegeben werden, das ein Nachfahre von A ist. Der Ablauf ist hier folgendermaßen: Die DSSSL-Steuerung läuft bis zum Element A, das der Rahmen als gesuchtes Element identifiziert. Dann läuft wie zuvor beschrieben die Formatierung des Teilbaums A ab. Im Anschluß daran wird der Teilbaum A nicht noch einmal behandelt. Ohne daß weitere Vorkehrungen notwendig sind, wird das Element C also nicht zweimal ausgegeben. Aus diesem Grund kann auf die aufwendige Überprüfung, welche bei der Suche gefundenen Elemente ineinander enthalten sind, verzichtet werden.

Diese positive Eigenschaft wird durch den DSSSL-Rahmen in keiner Weise berührt. Sowohl die unveränderte Tiefensuche von DSSSL als auch meine zuvor beschriebene effizientere Variante besitzen die Eigenschaft. Meine Lösung verhält sich funktional neutral, was für den Autor eines DSSSL-Rumpfes sehr wichtig ist, um keine unerwarteten Resultate zu riskieren.

5.2.5 Administrations-Werkzeug

Das Administrations-Werkzeug ip4w3-manager hat folgende Aufgabe: es erfragt vom Administrator die Informationen, die nötig sind, um ein Dokument in IP4W3 aufzunehmen. Diese Informationen werden benutzt, um die anderen Programme mit den korrekten Parametern aufzurufen. Außerdem speichert ip4w3-manager die Daten ab, damit sie bei einem erneuten Aufruf verfügbar sind³¹.

Da das Administrations-Werkzeug im wesentlichen eine nette Verpackung³² für die anderen Programme ist, kam es bei der Implementierung darauf an, den Aufruf von Programmen und die Parameterübergabe möglichst einfach zu realisieren. Die von ip4w3-manager erfüllte Funktion ist keine sehr komplexe, so daß ich in diesem prototypischen Stadium des Gesamtsystems auf eine graphische Oberfläche verzichten konnte. Aus diesen Gründen habe ich das Programm als Bourne-Shell-Skript implementiert.

5.3 CGI-Skripte

In IP4W3 kommen zwei CGI-Skripte zum Einsatz, preview.pl und search.pl. Letzteres Skript führt die Stichwortsuche durch, die, wie oben beschrieben, eine einfache sequentielle Suche ist. Für die Formatierung ist preview.pl zuständig.

Im wesentlichen haben beide Skripte die Aufgabe, die Schnittstelle zwischen Web-Server und den zuvor beschriebenen Programmen zu bilden. Sie müssen dazu Parameter gemäß Common-Gateway-Interface-Konvention akzeptieren, auswerten und beim Aufruf an die anderen Programme weiterreichen. Die Behandlung der CGI-Parameter ist in einem Perl-CGI-Modul gekapselt, das als frei verfügbares Paket im Comprehensive Perl Archive Network (CPAN) erhältlich ist. Dies war der Hauptgrund für die Verwendung von Perl. Zwar läßt sich ein CGI-Skript auch relativ leicht selbst implementieren, jedoch ist hier nicht nur aus funktionalen Gründen auf eine korrekte Implementierung zu achten, sondern aus Gründen der Systemsicherheit auch auf eine sichere. Diese Anforderung macht die CGI-Programmierung schwierig, da es (natürlich?) möglich ist, eine korrekte aber mit Sicherheitslücken behaftete Umsetzung zu schreiben. Die Ausführung eines solchen Programms jedem WWW-Benutzer zu gestatten, ist riskant. Durch Benutzung eines ausgetesteten und zuverlässigen CGI-Moduls wird das Risiko minimiert.

Neben dem Aufruf von nsgmls, Jade und CoST erzeugen beide Skripte auch den HTTP-Kopf (Hypertext Transfer Protocol), der dem Web-Browser mitteilt, daß er als Datenformat HTML zu erwarten hat. Des weiteren geben die CGI-Skripte HTML-Code aus, in den die Ausgabe der anderen Programme eingebettet wird.

5.4 JavaScript-Funktionsbibliothek

Die JavaScript-Funktionsbibliothek ip4w3.js stellt folgende Funktionen zur Verfügung, die den Endanwender beim Ausfüllen der Suchformulare unterstützen.

function pruefe_wert(formularfeld,wertebereich)
prüft, ob der Wert (value) des formularfelds nur Zeichen der durch die Zeichenkette wertebereich angegebenen Menge enthält. Diese Funktion realisiert die Einschränkung des Wertebereichs, die der Administrator bei der Definition der Suchmuster angeben kann.

function alle_checkboxen(aktion,formular)
beeinflußt den Status sämtlicher Checkboxen im formular. Als aktion stehen zur Verfügung:

"einschalten"

aktiviert alle Checkboxen.

"ausschalten"

deaktiviert alle Checkboxen.

"umschalten"

invertiert den Zustand aller Checkboxen.

Alle beschriebenen Funktionen benötigen ausschließlich den Sprachumfang der JavaScript-Version 1.0 und sind damit zu allen JavaScript-fähigen Browsern kompatibel. Die Auslagerung in eine externe Bibliothek verlangt jedoch, daß der Browser in der Lage ist, das src-Attribut des Elements script zu verstehen. Dieses wurde durch Netscape mit dem Navigator 3 in Verbindung mit JavaScript 1.1 eingeführt. Es ist seit Version 4 Bestandteil des HTML-Standards. Der Formulargenerator von IP4W3 (siehe 5.2.1) sorgt dafür, daß für Browser, die externe JavaScript-Bibliotheken nicht einladen, die notwendigen Funktionen zumindest definiert sind, damit keine Fehlermeldung erscheint.

5.5 Programmabläufe

Nachdem ich nun die Implementation der einzelnen Komponenten beschrieben habe, möchte ich in diesem Abschnitt das Zusammenspiel und die Abläufe mit Hilfe von Abbildungen beschreiben.

Den Anfang macht die Ablaufskizze für das Anmelden eines neuen Dokuments (vgl. Abbildung 19). Eine wichtige Position nimmt dabei der ip4w3-manager ein, da er dem Benutzer die Ausführung der Einzelschritte abnimmt. Aus dem ursprünglichen Dokument wird durch Hinzufügen von eindeutigen Elementbezeichnern eine veränderte Instanz erzeugt (ergaenze-ids.dsssl). Diese dient als Grundlage für den Suchindex (makeindex.cost). Aus den Suchmustern wird das HTML-Formular generiert (suchmuster2formular.cost) und der Programmcode, der bei der Suche benötigt wird (suchmuster2umgebungspruefung.cost).

Abbildung 19: Anmelden eines Dokuments: Zusammenspiel der einzelnen Programme und der von ihnen gelesenen und geschriebenen Dateien

Bei der Suche (vgl. Abbildung 20) passiert folgendes: Die vom Benutzer in das Formular eingetragenen Daten übergibt der Web-Server gemäß CGI-Konvention an das Suchskript search.pl. Dieses führt die Stichwortsuche im Suchindex aus und läßt die gefundenen potentiellen Treffer vom Programm search-atoms.cost prüfen. Dazu muß das Programm die veränderte Instanz einlesen, um zu verifizieren, daß sich die Treffer in der richtigen Umgebung befinden. Außerdem benötigt es den im vorherigen Schritt erzeugten Programmcode. Die Ausgabe ist die HTML-Trefferliste der ermittelten Atome (Kurzform der Dokumentausschnitte).

Abbildung 20: Programmablauf bei der Suche

Zur Formatierung (vgl. Abbildung 21) wird die Benutzerauswahl an das Skript preview.pl übergeben, das lediglich als CGI-Hülle für den Formatierer dient. Er bedient sich des DSSSL-Rahmens und -Rumpfes sowie (natürlich) der veränderten Instanz. Die Ausgabe wird an den Browser des Benutzers zur Darstellung übermittelt. Der Formatierungsschritt wird gegebenenfalls mehrfach durchlaufen, wenn der Benutzer die Größe der Dokumentausschnitte modifiziert und sie neu anzeigen läßt.

Abbildung 21: Programmablauf beim Formatieren