Pascal Christoph
15.06.03
Hausarbeit zum Scheinerwerb zu Softwaretechnologie - Java (I WiSe 01/02 und II SoSe 02)
Vorab: Ich halte mich in dieser schriftlichen Ausarbeit an die Vorlage von Jean-Yves Lalande vom 17.02.02. So referieren nicht nur die Gliederungspunkte dieser Arbeit mit denen Lalandes. Diese gesamte Arbeit baut vielmehr darauf auf, vieles ist 1:1 übernommen worden. Nur an den Stellen, wo SearchEngine von der Vorlage abweicht, ist auch die Dokumentation abweichend; zudem gibt es eine Reihe Ergänzungen wie: der Genese, oder etwa einem Ausblick.
1. Allgemeine Bedingungen und Anforderungen
1.1 Zusammenarbeit und individuelle Leistung, Genese
Der Versuch, über ein Online-Forum mit allen Teilnehmern der Hausarbeit Kontakt aufzunehmen um dort Probleme sowie (Teil)-Lösungen zu besprechen, stieß leider auf wenig  Resonanz. Direkten Kontakt über Email unterhielt ich zu Jan Schnasse, dem ich hiermit danken möchte. Wir haben uns auch einmal getroffen, und ich fand das Treffen sehr erhellend. Dank gebührt Eva Remberger für ihr engagiertes Tutorium, Herrn Dr. Lalande für seine von Sun begeisterten Vortrag ("Schaut euch den Code von Sun an !") und dem nicht immer leicht zu vermittelnden "Ihr müßt was tun", sowie den die Hausaufgaben korrigierenden Tutoren , Jürgen Hermes für die Unterstützung sowie natürlich allen, die es ermöglich(t)en, dass die schöne Programmiersprache Java in dem Studiengang Informationsverarbeitung an der Philosophischen Fakultät der Universität zu Köln gelehrt wird.
Ich hatte einige Anfangsprobleme, da ich mit Jbuilder von Borland arbeiten muss (für Linux existiert das in der Vorlage und im Unterricht benutzte VisualCafé nicht) ; mir war anfangs nicht bekannt, wie ich in Jbuilder ein Programm laufen lassen kann, von dem ich nur (oder teilweise ) die compilierten class Dateien habe (statt des java Sources). So habe ich anfangs die Module mit Jbuilder geschrieben, compiliert, und das ganze Programmpaket mit dem java Interpreter von Sun getestet. Anfangs wollte ich mich gar nicht von den vorgegebenen Interfaces lösen; dass ging soweit, dass ich die nichtssagenden Variablen (lzh,LzH etc...) übernommen habe... . Bevor ich mit dem Programmieren anfing, machte ich ein kompletten Ausdruck aller von Lalande mitgelieferten Interfaces etc. und meditierte darüber erst einmal drei Tage lang ... . Insgesamt bleibt zu sagen, dass ich mich ziemlich mit der benötigten Zeit verschätzte (vielleicht braucht ein Profi ja wirklich bloss 2 Wochen dafür ...!?) und mir die Arbeit aber insgesamt viel Erkenntnisse gebracht und viel Spass gemacht hat. ⁱ
1.2 Abgabe
Die endgültige Abgabe ist nun auf Ende Juni 2003 gefallen. Die vorherigen Versionen waren unvollständig und sehr fehlerhaft. Es liegt ein Project im Jbuilder Format (jpr) und VisualCafé (vep) vor. Natürlich auch die java Sourcen und die compilierten class Bytecodes.


2. Programmiertechnische Anforderungen und Hinweise


2.1 Dokumentation


Diese schriftliche Ausarbeit gilt als globale Programmdokumentation. Zur internen Dokumentation gehören die Anmerkungen im Quelltext sowie die von javadoc erzeugte separaten Textdatei index.html .



2.2 Fehlerbehandlung
Soweit ich weiss sind alle Fehlerabbrüche kontrolliert, dass heißt es erfolgt eine informative Fehlermeldung wenn einer auftritt.


2.3 Benutzung der Quelltexte
Die Implemetierung der Baumstruktur geht auf den Unterricht zurück, wie auch manche Idee zu Methoden und Tipps, z.B. dem flushen() von Streams.


2.4 Programmierkonventionen


Klassennamen sind groß geschrieben, es sind Substantive. Methodennamen beginnen mit einem Kleinbuchstaben, es sind Verben oder Verb-Phrasen (z.b. findWordInDox() ). Manchmal sind die Bezeichner mehr, mal weniger sprechend gewählt.
Es wurde ans Einrücken gedacht, der Übersichtlichkeit halber. Jede Klasse steht auf einer Quelltextdatei gleichen Namens (Jbuilder meckert sonst auch). Alle neuprogrammierten Klassen befinden sich im Unterverzeichnis des Packages 'searchDesign', außer Main , welches sich über dem Unterverzeichnis befindet.


3. Das Programm 'SearchEngine'


3.1 Allgemeines


Die geschriebenen Klassen implementieren die gegebenen Interfaces. Neue Datenstrukturen habe ich auch benutzt (dazu später mehr).
Die vorliegende Lösung kommt ohne die vorgegebenen Klassen des Packages searchDesign aus.
Im folgenden werden zunächst die Architektur und die Funktionalität vonSearchEngine beschrieben (3.2). Für eine bessere Verständlichkeit werden dabei zunächst die Benutzerschnittstelle (3.2.1) und danach der Verlauf einer Suchanfrage skizziert (3.2.2). Die Funktionalität der verschiedenen Komponenten wird dann unter 3.2.3 beschrieben. Unter 3.3 wird der genaue Verlauf des Programms beschrieben. Details zur Implementation der jeweiligen Klasse finden Sie unter 3.6 sowie in den Definitionen der entsprechenden Interfaces im Code.


3.2 Grundfunktionalität und Architektur von SearchEngine
SearchEngine ist eine Suchmaschine, die über die Grundfunktionalität gängiger Suchmaschinen verfügt.
" Wie funktionieren Suchmaschinen ?
In 1. Linie tun sie genau das, was der Benutzer sieht: Zu einem angegebenen Suchbegriff werden (Internet-) Seiten mit passendem Inhalt gesucht und angezeigt."( Spallek/Kreinade : Suchmaschinen , dtv, Seite 20 oben )







"Die wesentlichen 3 Teile sind:
Der Crawler: er durchwühlt die Verzeichnisse, speichert die (Pfade der) Seiten zur späteren Verarbeitung. Allerdings kann der Sucher mit diesen Seiten nicht viel anfangen. Es würde viel zu lange dauern, wenn alle Seiten bei jeder Anfrage noch einmal durchsucht werden müssten. Daher gibt es ein weiteres Programm, das die gesammelten Dateien bearbeitet. Es filtert alle Wörter, die als Suchbegriff gewertet werden können (hier: die also nicht in stopwords.txt stehen, der Verfasser) , die Adressen der Seite und die Positionen in diesen Dokumenten an welchen die Worte stehen heraus, und schreibt sie in eine Datenbank (hier: eine serialisierte direkte Datenzugriffsstruktur, der Verfasser ).
In der Datenbank steht nicht , welche Wörter in einer Seite enthalten sind, sondern umgekehrt , welche Seiten bestimmte Stichwörter enthalten (es wird nach Stichwörtern, nicht nach Seiten (Dokumenten) geordnet)." (ebenda, Seite 20 ff)
SearchEngines Architektur, die in folgender Grafik dargestellt wird, ist angelehnt an der Suchmaschine Altavista (vgl. Sunny Lam: The overview of Web SearchEngy Engines, February 9 2001):

"Change Folder": öffnet eine FileSelectorBox. Das ausgewählte Verzeichnis wird an die Methode Engine.buildIndex übergeben. Eine Partition (oder 'root') indizieren: oberstes Verzeichnis auswählen, '/' gefolgt von Enter eingeben.

"Start indexing": ruft die Methode Engine.buildIndex(...) auf, der das ausgewählte Verzeichnis übergeben wird.

"use Hashtable in Indexer ": setzt die Komponente useTableInIndexer von Settings.user auf true bzw. false . Damit wird die Wahl der benutzten Direktzugriffsstruktur (HashMap oder Binary Tree, vgl. 3.7) bestimmt.
"use Hashtable in KeyData": setzt die Komponente useTableInKeyData von Settings.user auf true bzw. false . Damit wird die Wahl der benutzten Direktzugriffsstruktur (HashTable oder Binary Tree, vgl. 3.7) bestimmt. Dies bitte nur zum Testen benutzen - die HashMap der KeyData arbeitet fehlerhaft !

Suchmodus

"ContextWidth": setzt Settings.user.contextLength, die Länge des Kontextes, der jeweils links und rechts von dem gefundenen Wort ausgegeben werden soll, auf den gewählten Wert (1-10 oder 100).
"NumberOfPlacesInDocForEachWord": hierdurch wird es möglich, die Anzahl der Fundstellen jedes Terms zu restringieren. Der Wert 0 ist auch möglich ; es werden dadurch nur die sortierten Dokumente angezeigt , ganz ohne die Fundstellen der Terme.

"Suche starten": ruft die Methode Engine.findWords(...) auf, der der im Textfeld "Sucheingabe" eingegebene Text übergeben wird.
Momentan wird das Ergebnis einer Suchanfrage automatisch in eine 'searchResult.txt' gespeichert. ⁱⁱⁱ Dieser Name wird, als letzter Parameter, der Methode QueryEngine.initialize(...) übergeben.

3.2.2 Eine Suchanfrage
Nach der Indizierung können Suchanfragen gestartet werden. Der Screenshot auf der rechten Seite zeigt das Ergebnis einer solchen Anfrage.
Bei dieser Suchanfrage wurden Dokumente gefunden, deren

(Bewertung des Ergebnisses, vgl. Anhang A.2) erste der Fundstellen der gesuchten Wörter, eingestellt durch NumberOfPlacesInDocForEachWord, in seinem Kontext (8 Wörter davor und 8 Wörter dahinter hier, gegeben durch ContextWidth, angezeigt wird.
Der genaue Verlauf des Programms wird unter 3.3 beschrieben. Vorher werden die einzelnen Komponenten und ihre Aufgaben erläutert.

3.2.3 Die einzelnen Komponenten
Der Crawler ist für das Auffinden der zu durchsuchenden Dokumente zuständig. In der reellen Welt (Praxis) holt sich ein Crawler die Dokumente von den verschiedenen Webservern und stellt sie dem Indexer zur Verfügung. Der Crawler von SearchEngy simuliert dieses Verhalten lokal, indem er über eine minimale Funktionalität verfügt (vgl. weitere Anmerkungen zu der Funktionalität von Crawlern im reellen Leben unter 3.3.2). Von einem von dem/r Benutzer/in angegebenen Verzeichnis ausgehend speichert er die Pfade zu allen ASCII- und HTML-Dateien, die sich in diesem Verzeichnis und seinen Unterverzeichnissen befinden, und stellt sie (in Form eines String []) dem Parser zur Verfügung. Etwas chaotisch, aber funktionierend, ist der Crawler der vorliegenden Version recht robust geworden. So kann das Modul zwischen echten Files/Ordnern und lediglich symbolischen Files/Ordnern unterscheiden, und entgeht damit beim crawlen einer möglichen Endlosschleife. Allerdings scheint der Crawler recht speicherintensiv zu arbeiten; mein (Sub-)Ziel, eine Suchmaschine zu entwickeln, die meine ganze Festplatte (40.000 .txt/.htm - Files, insg. 230 MB gross) einliest und indiziert, scheitert leider.
Der Indexer erstellt einen Index, in den alle mit der Suchmaschine abfragbaren Wörter der Dokumente mit ihren Fundstellen eingetragen werden. Davon ausgenommen sind die Stoppwörter, welche in der mit der Vorlage mitgelieferten Datei 'stopwords.txt' enthalten sind. Es handelt sich um die frequentesten Wörter des Deutschen wie Artikel, Pronomen, frequente Adverbien usw. Die hier benutzte Liste wurde, leicht modifiziert, dem Fachinformationszentrum Karlsruhe entliehen. Mit jedem Texteditor kann sie leicht modifiziert werden; der Benutzer passe sie sich den Bedürfnissen nach an.
Der Index ist eine Direktzugriffsstruktur, in der Objekte des Typs KeyData gespeichert werden. Als Schlüssel dient das in einem KeyData gespeicherte Wort. Über dieses Wort hinaus speichert ein KeyData wiederum eine Direktzugriffsstruktur, in der alle Dokumente, in denen das betroffene Wort enthalten ist, gespeichert werden. Diese Direktzugriffsstruktur enthält Objekte des Typs DocumentData. Ein DocumentData speichert für ein Dokument alle Positionen, an denen das betroffene Wort in diesem Dokument vorkommt. Diese Fundstellen dienen der Ausgabe eines gefundenen Keywords (bzw. mehrerer gefundener Wörter) im Kontext (s.o.). Folgende Grafik schematisiert die Struktur des Indexes:

Der Indexer bearbeitet alle vom Crawler gesammelten Dokumente sequentiell mit Hilfe des Parsers. Der Parser liefert sequentiell alle Wörter der Eingabe (des jeweiligen Dokuments) mit den zugehörigen Daten zur Fundstelle mit Hilfe seiner Methode nextWord() zurück. Der Parser ist so konzipiert, dass er sowohl ASCII- als auch HTML-Texte bearbeiten kann. Das Parsen und Bearbeiten von HTML-Texten, das natürlich eine unabdingbare Komponente einer vernünftigen Suchmaschine ist, wurde im Rahmen dieser Hausarbeit gelöst (vgl. u.a. hierzu Anhang A.1). Damit die Suchmaschine bei Bedarf um weitere Komponenten, wie rtf oder pdf Formate, erweitert werden kann, wurde der Parser so konzipiert , dass er mit einem Filter arbeitet, der momentan entweder ein HTML-Filter ist oder ein ASCII-Filter, welcher Wörter (aus ASCII-Buchstaben) filtert und weitergibt.
An Fundstelleninformation wird man in einem DocumentData gespeichert: das betroffene Dokument in Form einer DokumentID (int) und die Byteposition jeder Fundstelle in der Datei .Auf das Speichern ihres Abstand zum vorherigen Wortanfang habe ich verzichtet (vgl. 4). Nach der Bearbeitung aller Dokumente speichert der Parser die Pfade zu diesen Dokumenten und jeweils dahinter, in einer neuen Zeile, die Anzahl der in dem betroffenen Dokument geparsten Wörter (Nichtstopwörter) in dem File 'docmap.txt'. Diese Datei wird später von der QueryEngine benutzt, wenn es darum geht, die Fundstellen der Keywords wiederzufinden, um letztere in ihrem Kontext auszugeben. Die Gesamtanzahl der Keywords eines Dokuments wird bei der Berechnung des Rankings durch die QueryEngine benötigt (vgl. Anhang A.2) ; es wird daher mit gespeichert .
Nach der Indizierung wird der vom Indexer gebildete Index (die Direktzugriffsstruktur) auf einer Datei namens 'index.bin' serialisiert, d.h. binär auf dieses File geschrieben, und gezippt, um später wieder eingelesen werden zu können (vgl. 3.3.3 und 3.6.4 hierzu).
Die QueryEngine liest bei ihrer Initialisierung die Datei ' pureIndex' ein und rekonstruiert den Index, um Anfragen an die Suchmaschine bearbeiten zu können. Sie verfügt über eine Methode processQuery(String term), welche folgende Grundfunktionalität zur Verfügung stellt: Suche nach einem einzelnen Keyword, Suche nach mehreren Keywords mit AND-Verknüpfung, und Suche nach 'Wortketten', d.h. festen Aneinanderreihungen von 2 oder mehr Wörtern. Die Suchergebnisse werden sowohl in das JEditorPane der GUI (das Programm-Ausgabe-Feld, das die DOS-Konsole ersetzt) ausgegeben als auch auf die Textdatei searchResult.txt . Sie enthalten den Pfad zu den Dokumenten, einen Rankingwert (vgl. unten Anhang A.2) und jeweils die im Suchmodus angegebenen Vorkommen der in einem Dokument gefundenen Terme, jeweils in ihrem Kontext (je n Wörter links und rechts des Terms, je nach Einstellung der Kontextbreite, s. Screenshot oben).

3.3 Verlauf des Programms SearchEngine
3.3.1 Einlesen der Direktivendatei
SearchEngine liest bei ihrer Initialisierung eine Direktivendatei 'SearchEngy.ini' (im Projektverzeichnis) ein, vgl. die Methode Engine.init(). Diese Datei enthält folgende Informationen, jeweils in einer eigenen Zeile, ohne Leerzeilen dazwischen:

• den Namen der Datei, in die der Index gespeichert werden soll, 'index.bin'

• den Namen der Docmap-Datei, 'docmap.txt'

• den Namen der Stopwortlistendatei, 'stopwords.txt'

In der Stoppwortlistendatei 'stopwords.txt' stehen die vorgegebenen Stoppwörter im ASCII-Code verzeichnet, eines je Zeile, ohne führende oder folgende Leerzeichen.
Beim Einlesen der Direktivendatei werden die entsprechenden Informationen in den statischen Komponenten der Klasse Engine gespeichert, um an die verschiedenen Komponenten des Programms weitergereicht zu werden.
3.3.2 Indizierung
Im Indizierungsmodus wird der Index erstellt. Der/die Benutzer/in muss zunächst den Pfad zu dem Basisverzeichnis auswählen, welches die zu bearbeitenden Dokumente (es zählen auch alle Dokumente in allen möglichen Unterordnern dieses Basisverzeichnisses) enthält, und kann bestimmen, welche Typen von Datenstrukturen (Hashtable oder Binary Tree) im Indexer und in den in ihm enthaltenen KeyData verwendet werden sollen (defaultmäßig wird gemischt).
Wir nehmen an, dass es sich um deutsche Texte handelt und dass die Dokument im ASCII-256 Code oder in HTML vorliegen. Hier besteht Erweiterungbedarf, da SearchEngine ganz prinzipiell Unicode liest (nur eben nicht verarbeitet (->siehe Filter)).
Die Ausgabedatei, in der die Suchergebnisse enthalten sind, ist ebenfalls in ASCII-256 kodiert , Cr/Lf als Zeilenende (auch bei der letzten Zeile), keine Leerzeilen.
Anhand des angegebenen Pfades zu dem Startverzeichnis, der der Methode Engine.buildIndex(...) übergeben wird (s.o.), wird dieses vom Crawler nach Dateien mit den (case-insensitiven) Endungen .txt, .html und .htm, durchforstet. Der Crawler geht
hierbei durch alle Unterverzeichnisse des Startverzeichnisses und speichert die Pfade der gefundenen Dateien. Die Vorgehensweise ist recht einfach, allerdings nicht gerade dynamisch, geschweige denn speicherplatzsparend. In der reellen Praxis müsste der Crawler nach und nach dem Indexer die Dokumente zur Verfügung stellen. Auch könnte die 'docmap.txt' ab und zu beschrieben werden, sodass die alten Pfade nicht statisch im RAM zu verbleiben brauchen.


Der Parser wird mit den vom Crawler gefundenen Pfaden und der oben erwähnten Stopwortliste und der Summe der Länge der gefundenen Files initialisier. Er bearbeitet bei seiner Initialisierung die Stoppwortliste und speichert die Stoppwörter in eine effiziente Direktzugriffsstruktur (in einer Hashtablel). Der Parser bearbeitet sequentiell alle ihm von dem Crawler in Form eines String [] zur Verfügung gestellten Dokumente mit Hilfe seiner Methode nextWord(), welche ein KeyData zurückgibt. Er gibt erst dann null zurück, wenn alle Dokumente gelesen wurden. Der Parser filtert mit Hilfe der Stoppwortliste die Stoppwörter heraus (vgl. Details zum Parser unter 3.6.1).
Die Datenstruktur KeyData, die die Daten zu einem im Index gespeicherten Wort enthält, besteht aus einem Wort als String, und dem Value der Dokumente, die dieses Wort enthalten. Diese Values speichern Objekte des Typs DocumentData. Der key des DocumentData ist die ID des betroffenen Dokumentes. Es speichert ferner ein Array der Fundstellen des betroffenen Wortes als int, darin die Byte-Position des ersten Buchstaben des Keywords im betroffenen Dokument, als int codiert (vgl. 3.6.2 und 4. für Details).
Während des Einlesens zählt der Parser die Gesamtzahl der indizierten Wörter eines Dokumentes (also keine Stoppwörter, keine html-tags, keine nicht-Wörter). Nach dem Einlesen aller Dokumente schreibt der Parser folgende Informationen in das File 'docmap.txt':

• die Anzahl der bearbeiteten Dokumente, gefolgt von Cr/Lf ,

• zu jeder bearbeiteten Datei den Pfad zu dieser Datei,

• gefolgt in einer neuen Zeile von der Anzahl der darin enthaltenen Nichtstoppwörter.

Der Indexer trägt die vom Parser zurückgegebenen KeyData in eine Direktzugriffsstruktur ein (eine HashMap, alternativ einen selbst implementierten sortierten Binärbaum, vgl. 3.7), wobei das Wort (in ASCII, Groß- und Kleinschreibung neutralisiert) als Schlüssel dient, jedes Wort also nur einmal in Form eines KeyData gespeichert wird. In den KeyData dieser Direktzugriffsstruktur werden sukzessive die Dokumente und die Fundstellen jedes KeyWords akkumuliert.
Die Methode saveBinary() des Indexers serialisiert den gebildeten Index auf eine Datei 'indexPure.bin'. Es wird auch eine gezippte Datei 'index' erstellt, deren Zweck momentan fraglich ist.

3.3.3 Suchanfragen
Suchanfragen sind prinzipiell nur über das GUI zu bewerkstelligen. Da es sich um das weniger speicherintensive Modul handelt, und auch, da SearchEngine als Applet-Client geplant ist,sehe ich keinen Grund, dies als Feature einzubinden.


I m Suchanfragemodus wird die QueryEngine von SearchEngine initialisiert.
Bei der Initialisierung wird die Datei 'index' eingelesen und entzippt, und dann nach 'pureIndex.bin' geschrieben, diese eingelesen und daraus der Index rekonstruiert. Insgesamt werden drei Dateien der QueryEngine als Parameter ihrer Methode initialize(...) übergeben: die Datei, in der der Index serialisiert und gezipptt wurde ('index'), die vom Parser erzeugte Docmap-Datei 'docmap.txt' und die Ausgabedatei ('searchResult.txt').
Die Methode processQuery(String term) der QueryEngine bearbeitet die Anfragen.
Drei Typen von Termen werden als Anfragen von der QueryEngine unterschieden und bearbeitet:

1. ein einzelnes Schlüsselwort.
   Beispiel: König

2. AND-Verknüpfungen von Schlüsselwörtern. Enthält der übergebene Term mehrere durch Spaces (Leerzeichen) von einander getrennte Wörter, dann wird die Abfrage als AND-Verknüpfung interpretiert (entsprechend der Konvention gängiger Suchmaschinen wie Google z.B.).
   Beispiel: König Frosch Kugel

3. Wortketten.Bei Wortkombinationen in doppelten Anführungsstrichen sucht die QueryEngine nach den entsprechenden adjazenten Wörtern.
   Beispiel:"böse Hexe"

Diese drei Typen von Abfragen sind beliebig miteinander kombinierbar, so dass folgende Anfrage von der QueryEngine entsprechend bearbeitet wird:
Beispiel:Wolf "zwei Kinder" Jäger


3.3.4 Funktionalität von processQuery
Eine Suchanfrage wird mit der Funktion processQuery(String term) gestartet, wobei der übergebene String eine beliebige Kombination von Termen und Wortketten enthält. Einschränkung bislang: die Anzahl der Wörter/Wortketten darf 127 nicht überschreiten.



Zunächst muss der Term in seine einzelnen Bestandteile tokenisiert werden, wobeii zwischen einzelnen Wörtern und Wortketten unterschieden wird. Es müssen alle Dokumente ermittelt werden, die alle Wörter des Terms enthalten.Dazu wird eine neue Klasse benötigt, die TruthTable. In ihr werden zwei parallele boolean Arrays verwaltet, mit denen momentan bloss and Verknüpfungen gemacht werden können. Das Ergebnis einer solchen Verknüpfung wird im ersten Array gespeichert, die Fundstellen eines/r weiteren Wortes/Wortkette im 2. Array mit true markiert und dann wieder mit and bearbeitet etc. Bei der Behandlung der Wortketten muss verifiziert werden, dass die einzelnen Wörter einer Wortkette adjazent (d.h. aufeinander folgend) sind. Die nötigen Informationen dafür werden durch das Rückwärtseinlesen der Dokumente ab der Stelle gewonnen, die in dem letzten Wort der Wortkette in dessen DocumentData gespeichert ist (siehe die Methode QueryEngine.wortKetten() und andere). Am Ende dieser Bearbeitung des Terms hat man alle Dokumente, die alle Terme der Anfrage enthalten. Die Ausgabe dieser Dokumente ist nach dem Ranking (vgl. Anhang A.2) sortiert . Ich benutzte dafür eine (selbst implementierte, rückwärtssortierende) HashMap. Anschließend gibt contextAusgabe() die Suchergebnisse auf dem Bildschirm (in dem Programm-Ausgabe-Feld der GUI) aus, storeResultsOnDisk() gibt die in der Engine angegebene Ausgabedatei aus (' searchResult.txt'). Vgl. hierzu den Screenshot unter 3.2.2.
Die Ausgabe der Keywords im Kontext geschieht mittels eines RandomAccessFiles, der die Wörter aus den entsprechenden Dokumenten holt. Für die Ausgabe wird der Originaltext aufbereitet. Hier wird HTML generiert . Vor dem ersten Wort und nach dem letzten Wort des Kontextes werden jeweils drei Punkte ausgegeben, jeweils vom Kontext durch ein Leerzeichen getrennt (vgl. 2. Screenshot unter 3.2.2). Satzzeichen werden mit ausgegeben. Die Ausgabe ist nicht ganz sauber. So sollte sich nicht darauf verlassen werden, daß bei Angabe von ContextWidth 8 auch tatsächlich 8 Worte davor und danach ausgegeben werden. Vielmehr ist dies relativ zu sehn. Jede Textzeile wird als Folge von Zeichen ausgegeben, abgeschlossen durch "/n" . Es wird als HTML-Text aufbereitet mit Settings.user.talk.urlMessage() und duch Settings.user.talk.flushOutputHtml() auf die GUI-Oberfläche gezeichnet ^iv .
Zeilenenden der Eingabedatei (Cr/Lf) werden durch ein einfaches Blank ersetzt. Alle anderen Steuerzeichen (ASCII-Codes von 0 bis 31, z.B. Tab), ob einzelne oder aufeinander folgende, werden überlesen. Das gilt auch für Zeilenende. Ein Zeilenende ist ein Cr (Carriage Return) auf dem Mac, ein Paar Cr und Lf (Line Feed) auf dem PC und ein Lf unter Unix. Die programmierte Version sollte auf allen diesen Plattformen korrekt laufen.

3.3.5 Testbeispiele
Komplexere Phrasen wie :
"Ich wette, wenn wir um die Wette laufen, ich lauf schneller als du."
laufen ganz gut. Allerdings funktionieren längst nicht alle. Zum ersten muss darauf geachtet werden, dass das letzte Wort in der Phrase nicht in der Stoppwordliste steht, dass es also im Index ist. Desweiteren dürfen die vorangestellten Worte nicht mit einem ';' enden. Man probiere aus, welche Anfragen funktionieren. Die Engine gibt entsprechenden Kommentar aus, z.B. wenn das letze Wort einer Phrase nicht im Index steht. Dann soll man dieses löschen und nochmal suchen lassen ^v . Es funktionieren auch nicht die Genitiv-Hochkomma 's' . Solche Worte sollten nicht in der Phrase stehn. Ich habe versucht, die Phrasen-Auffindung robust zu machen. Trotzdem lässt sich an dieser Stelle noch einiges verbessern (s.o.) . Es muss beachtet werden, dass die Anfrage in einem String[byte] liegt, also auf 128 Worte/Phrasen beschränkt ist.
Meine Ausgabedatei stimmt mit der der Vorlage überein. Wird die Option 'HashTable in KeyData' (siehe 3.2.1.2 GUI ) aktiviert, kann es aber zu Problemen bei der korrekten Ausgabe kommen (Kontext-Worte werden nicht richtig ausgegeben, oder DocumentDatas nicht richtig gespeichert ) . Dies muss noch überarbeitet werden.
3.4 Vermischte allgemeine Hinweise
Es wurde extra darauf verzichtet, vernünftige Pufferlängen zu definieren . Das Hauptproblem der SearchEngine ist nicht ihre Geschwindigkeit (die ist wahnsinnig schnell; bei der Ausgabe gibt es aber Verbesserungsbedarf) , sondern die Speicherverwaltung.
Statt wie Vorgeschlagen einen Vector zu verwenden, kommt die ArrayList zum Einsatz. Bei gleicher Funktionalität ist diese nicht Thread sicher, also nicht synchronisiert, und deswegen schneller.


3.5 Meldungen
SearchEngine gibt Meldungen über den Arbeitsfortschritt aus. Dies ist sehr wichtig, da insbesondere bei langsamen Rechnern oder großen Datenmengen der Benutzer entscheiden muss, ob das Programm noch sinnvoll arbeitet oder eventuell in einer Endlosschleife meditiert. Extra zu diesem Zweck wurde ein altes AWT-Fenster in die Swing Oberfläche integriert, welches auf alle Fälle und unabhängig vom Programmstatus aktualisierte Meldungen zeichnet (siehe auch Fussnote 1).
3.6 Details zu einzelnen Komponenten
3.6.1 Parser
Der Parser liefert mit seiner Methode nextWord() sequentiell alle Nichtstoppwörter der Dokumente in Form von KeyData. Er arbeitet dabei mit einem CharFilter, der je nach Dokumenttyp ein TextFilter (für ASCII-Dateien) oder ein HTML-Filter ist. Ein solcher Filter liefert das aktuelle Wort der Eingabe durch nextWord(), bei Bedarf kann die aktuelle Position in der Eingabe durch filter.bytePos ,also einem direkten Zugriff auf das Datum, ermittelt werden. Das sind alle Informationen, die der Parser braucht, um die in KeyData zu speichernden Daten zu ermitteln (s.o. 3.3).
Zur Ermittlung eines Wortes: Der Einfachheit halber beenden alle Nichtbuchstabenzeichen inkl. Bindestrich ein Wort - auch die Apostrophe, auch Ziffern. Bei einem Bindestrich am Zeilenende kann man eigentlich nicht sicher entscheiden, ob es sich um einen Bindestrich oder einen Trennstrich handelt. Dieses Problem ignorieren wir aber hier. Eine einfache Erweiterung wäre auch Zifferngruppen als Wort zulassen, oder Ziffern als Bestandteile eines Worts. Das Programm ignoriert Ziffern komplett, egal in welcher Form.
Erweiterungen liegen nahe. Vgl. folgende Beispiele, die lediglich zur Illustration der Problematik hier angeführt werden:
"James, wo ist mein Schlüssel?"
Hier sollte wohl mindestens das Satzzeichen mit zum Fundstellenkontext zählen, am besten auch die Anführungszeichen.
"James, war's meine Frau?" (vertraulicher Ton)


Ein Apostroph zwischen zwei Wortzeichen sollte man wohl nicht trennen (oder doch?).
SearchEngine speichert bloss "james" und "frau", da die anderen Worte zu den Stoppwörtern gehören oder keine Wörter sind. ^vi
3.6.2 Verwaltung der Fundstellen
Bei der Speicherung der Fundstellen eines Keywords müssen für die Ausgabe des Keywords im Kontext durch die QueryEngine die Anfangsposition des Keywords im Dokument gespeichert werden. Diese Daten werden in einem Array des Document-Data gespeichert, einem int[] positions (vgl. Abb in 3.2.3) .

A.1 Ranking
Vernünftige Suchmaschinen (dazu zählt SearchEngine) geben Auskunft über das Ranking einer Suchabfrage, auch Termgewichtung genannt. Man findet in der Literatur zahlreiche verschiedene Definitionen von Ranking, vgl. hierzu z.B. Nohr, Holger (2000): Automatische Dokumentindexierung ? Eine Basistechnologie für das Wissensmanagement, Arbeitspapiere, Wissensmanagement Working Papers Knowledge Management, S. 17-19). Der Vollständigkeit halber wird das benutzte Verfahren im folgenden genau beschrieben. Es ist , mit zwei kleinen Erweiterungen, die exakte Übernahme aus der Vorlage. Die ersten Einträge beziehen sich auf die Anzahl der Fundstellen der Wörter "alte" und "Frau" in den Dokumenten, darauf die Einträge der berechneten Werte für jede einzelne Fundstelle (dazu gleich die Formel), als letzes die erweiterten Formeln. Die Berechnung des Rankings erfolgt durch die (unerweiterte) Formel:
tf _ik * log ( N / n _k). Dabei ist N die Anzahl aller Dokumente im Index, tf _ik die Termfrequenz eines Terms t _k in einem Dokument i und n _k die Anzahl aller Dokumente, die den Term t _k enthalten.
Beispiel:
Das Verzeichnis enthält 20 Dokumente, damit ist N=20.Von diesen Dokumente enthalten 9 den Term "alte", also ist n_alte =9. N/n _k ist in diesem Fall 2,22, log_e(N/n _k)= 0,798. Für das Wort Frau ergibt sich:N = 20, nFrau = 13. N/n _k = 1,53, log_e(N/n_k) = 0,430. Diese Werte nun werden mit der Anzahl der Fundstellen pro Dokument multipliziert, daraus ergeben sich die letzten Einträge in der Tabelle. Die Dokumente 1,9,14 und 18 können bei der weiteren Berechnung ebenfalls ignoriert werden, da dort nicht beide Terme auftreten.Bei der Suche nach >alte Frau< wäre also das "beste Dokument" in diesem Fall 17 (verschiedene_Märchen.txt). Die Bewertung des Dokumentes wäre (22,3 + 12,4) / 2 = 17,35 , also der Mittelwert der Bewertung der einzelnen Terme.
Dabei ist zu beachten, dass dieses Dokument gleichzeitig auch deutlich größer ist als alle anderen Dokumente im Beispielverzeichnis, eine höhere Anzahl von Fundstellen war zu erwarten.

Aus diesem Grunde habe ich (die ansonsten sehr taugliche) Funktion um einen Teiler wordNum erweitert (siehe QueryEngine, ranking() ). WordNum ist die Gesamtanzahl der indizierten Worte in dem Dokument.Es wird durch 500 geteilt; daraus folgt, daß bei einer Gesamtzahl von 500 indizierten Worten der WordNum gleich 1 ist. Sind es mehr Worte, wird WordNum größer, und da es ein Teiler für die Gesamtfunktion ist, wird das Ergebnis der Gesamtfunktion kleiner. Dann wird noch ein Extremgrenze abgesteckt: nämlich wird der Teiler kleiner 1, wird der Teiler auf 1 gesetzt. Das verhindert ein ungewünschtes Verhalten bei der Bewertung von Dokumenten, die z.B. nur eine Fundstelle aufweisen, aber auch nur insgesamt 100 indizierte Wörter groß sind, und also der Teiler WordNum 100/500=1/5 betragen würde, was einem Faktor von 5 entspricht. So würde das Dokument ein gleiches Ranking bekommen wie ein Dokument mit 5 Fundstellen bei insgesamt 500 indizierten Wörtern - dies wäre eine Verzerrung der Wichtigkeit von Dokumenten (meiner Meinung nach). Als letztes habe ich noch einen kleinen Faktor eingebaut: amount ist die Anzahl der Fundstellen und hinzu wird 1/5tel der Anzahl von sich selbst addiert. Nach dem Berechnen vom Ranking wird dieses mit dem Faktor amount multipliziert.
Die obige Tabelle ist in den letzten beiden Spalten unterschiedlich stark von grün über gelb bis fast weiß gefärbt. Die dunklere Färbung entspricht der besten Chart-Bewertung. Der geneigte Betrachter stellt fest, daß die Ergebnisse der Original-Formel zu denen der Erweiterung unterschiedlich sind. Mir gefallen die neuen Ergebnisse besser, doch auch sie sind nicht perfekt. Z.B. stört, daß es egal ist, wenn in einem Dokument ein Suchwort einmal vorkommt, das andere Wort 50 mal, und das dieses Dokument die selbe Bewertung erhält wie ein Dokument gleicher indizierter Wortanzahl (und gleichen anderen Parametern) mit 25 Vorkommen des einen Suchwortes und 26 des Anderen. So hätte Hänsel und Gretel.txt eine echte Chance auf den verdienten 3. Platz ... ^ix
Hinweis:
Bei der Suche nach Wortketten ändert sich die Dokumentfrequenz log(N/n _k), weil n_k dann gleich der Anzahl aller Dokumente ist, die die Wortkette (und nicht nur die Terme der Kette) enthalten. In obigem Beispiel enthalten beispielsweise nur die Dokumente 5, 7, 8, 13, 17 und 19 die Wortkette "alte Frau", entsprechend wäre n _k hier 6. Aus gleichem Grund ändert sich natürlich auch die Anzahl der Fundstellen im Dokument.
Das Programm der Vorlage vereinfacht hier jedoch und berechnet das Ranking von Wortketten genauso wie das Ranking einzelner Terme ^x - allerdings werden bei der Ausgabe nur die Dokumente angezeigt, die die Wortkette enthalten (AND-Verknüpfung eben).
A.2 Schwellenwertberechnung
Ist nicht implementiert. Es folgt keine Berechnung , keine Termgewichtung eines Keys, auf dessen Grundlage entschieden wird, ob er indiziert wird.
A.3 HTML-Filter
Es wurde ein HTML-Filter implementiert,der über eine Grundfunktionalität verfügt. Die notwendige Grundfunktionalität besteht darin, HTML-Tags sauber herauszufiltrieren und die Sonderzeichen des Deutschen (wie '&auml;' für 'ä', '&szlig' für ß, etc..., s.u.) richtig zu behandeln, d.h. in die entsprechenden Buchstaben umzuwandeln. Bei einer vollständigen Funktionalität müsste man die Behandlung von Sonderfällen wie verschachtelten Kommentaren, Tabellen, Javascript u.a. gesondert untersuchen und ggfs extra implementieren. Es böte sich an , mit einer Datei ('htmlcodes.txt'), in der alle in den Dokumenten auftauchenden HTML-Codes in der Form "auml ä", also ohne "&" und ";" enthalten sind, zu arbeiten. Der Inhalt der Datei könnte dann in eine Hashtable eingelesen werden und diente dem sicheren Matchen bei der "Dekodierung" von HTML.
Momentan ist es eine unsaubere Implementation (siehe HTMLFilter).
Die CharFilter werden , anders als in der Vorlage, nur beim Parsen, nicht auch bei der Ermittlung des Kontextes für die Ausgabe der Ergebnisse durch die QueryEngine benutzt. Dazu dient mir die Klasse RAFReader, mit deren Methoden afterWord(), previousWord(), previousPureWord() ... . Allerdings sind diese Funktionen sehr chaotisch und unübersichtlich und dementsprechend schlecht zu warten.
Und endlich:
"Bei der Komplexität waren wir ... alles wird dann so kompliziert, dass es beinahe unmöglich ist, ein Programm ohne Fehler zu schreiben, das ist fast unmöglich!!(...)...Null oder Eins. (...) Das ist, wie gesagt, relativ einfach, nur die Kombinationen ... nur die Möglichkeiten, die werden dann so komplex. Es LADET Fehler ein, kann man sagen, und dann muss man eben das Programm probieren, die Fehler finden und korrigieren, das war früher relativ einfach. Aber heutzutage würde ich sagen, die Programme,die die Arbeit der Welt tun, sagen wir: Flugzeuge landen, Artillerie abschießen, Versicherungs- oder Börsenrechnungen machen usw., dass diese Programme niemand mehr völlig versteht. Niemand ! Und wenn die ganze Struktur so hochkomplex ist, dann wird auch die Frage, was ein Fehler ist, auch hochkomplex ...".
(Josef Weizenbaum:Kratzen, wo es juckt! Besuch beim Vater von Eliza,von Gabriele Goettle,taz, 30. Dezember 2002)


Literaturverzeichnis:
[1] Goll,Weiß,Müller: Java als erste Programmiersprache,Teubner,2001
[2] Hannover Uni: Java2 Grundlagen und Einführung, RRZN,2001
[3] Krüger: GoTo Java2 Handbuch der Java-Programmierung, Addison Wesley, 2000
[4] Flanagan: Java in a nutshell, o'reilly, 2001
[5] Zuser,Biffl,Grechenig,Köhle: Software Engineering mit UML und dem Unified Process, Pearson Studium,2001
[6] Norman Hendrich: Java fuer Fortgeschrittene, Springer Verlag, 1997
[7] Spallek/Kreinade : Suchmaschinen , dtv
[8] Kofler: Linux, Installation,Konfiguration,Anwendung, Addison Wesley, 2001