Guugelhupf besteht, grob gesehen, aus zwei Teilen:
Dem Indizierer
und dem Abfrage/Query Programm.
Aus einer beliebigen Anzahl von Dateien erstellt der Indizierer einen schnell zu durchsuchenden Index.
Der Indizierer unterteilt sich selbst wieder in die folgenden Teile:
Dem Analyser, bestehend aus:
Einem Tokenizer, und
beliebig viele Filter (z.B. LowercaseFilter, StopwordFilter etc.).
Die Datenstruktur zum Aufbau und Speicherung des Index.
In der vorliegenden Version von Guugelhupf ist nur eine Art von Tokenizer implementiert, den wir CharTableTransform-Tokenizer nennen, da er aus einer Lookup-Tabelle besteht, die jedes ASCII Zeichen auf ein anderes ASCII Zeichen abbildet/transformiert, mit der Besonderheit, daß der ASCII-Wert 0 eine spezielle Bedeutung hat, und zwar ist in diesem Fall das Zeichen ein Non-Word Zeichen und kann "weggeschmissen" werden. Ein Wort ist somit definiert als alle Zeichen die von zwei ASCII 0 Zeichen umgrenzt werden. Auch wird mit dieser Art von Tokenizer eine anschließende Konvertierung zu Kleinbuchstaben gespart, indem man eine entsprechende Tabelle verwendet.
Der Code hierfür findet sich im Verzeichnis tokenizer/char-table-transform.
Drei Unterschiedliche Ausprägungen des CharTableTransform-Tokenizers sind vorhanden:
Memory Mapped (MmapTokenizer)
Stream (StreamTokenizer)
String (StringTokenizer)
Zur Erzeugung von Character-Tables kann das Ruby-Script createCharTable.rb im tools Verzeichnis verwendet werden. Es erzeugt dann entweder SML-Sourcecode, der in ein Programm einkompiliert werden kann, oder eine Binär-Datei, die erst zur Laufzeit geladen wird. Das Eingabe-File für eine Englische Character-Table könnte z.B. wie folgt aussehen:
add LOWERCASE
add UPPERCASE, LOWERCASE
add DIGITS
Dies gibt an, daß alle kleinen Buchstaben (LOWERCASE) auf sich selbst abgebildet werden sollen, ebenso wie
alle Ziffern (DIGITS). Großbuchstaben (UPPERCASE) jedoch werden auf die entsprechenden Kleinbuchstaben abgebildet.
Alle anderen Zeichen besitzen den Wert 0 und werden somit nicht zur Bildung eines Wortes verwendet.
Alle Tokenizer haben ein Subset von Funktionen mit gleichem Typ (z.B. nextToken), verdeutlicht wird das durch die Signatur TOKEN_STREAM (definiert in Datei gh-defs.sml). Dies trifft auch für alle Filter zu.
Filter haben als Eingabe einen TokenStream und liefern einen veränderten TokenStream als Ausgabe. Die vorliegende Version implementiert nur einen Stopword-Filter, der haufige Wörter einer Sprache eleminiert. Die zu eleminierenden Wörter können z.B. aus einer Datei gelesen werden, die in jeder Zeile ein Wort enthält. Diese Wörter werden dann einmalig in eine Hashtabelle eingefügt, um später eine schnelle Abfrage zu gewähleisten, ob das Token ein Stopwort ist oder nicht.
Der Sourcecode des Stopword-Filters befindet sich im Verzeichnis filter in der Datei stopword-filter.sml.
Die gebräuchlichste Datenstruktur für einen Wort-Index ist wohl eine Invertierte Wort Liste. Diesen Weg haben auch wir gewählt.
Zwei Ausprägungen sind denkbar:
FrequencyInvertedList
PositionInvertedList
Unsere Invertierte Liste verwendet eine Hashtabelle (Datei ds/hash-table.sml), und bildet damit die Wörter auf eine Splay-Tree Map ab. Letztere Datenstruktur bildet die Dokument-ID auf die Häufigkeit des Auftretens ab. Es findet also folgende Abbildung statt:
token -> docid -> frequencyBzw. für die PositionInvertedList:
token -> docid -> position list
Der Sourcecode für die Invertierte Liste ist in Datei ds/inv-list.sml.
Im Folgenden ist die Struktur eines abgespeicherten Index beschrieben.
Der Header ist eine 28-Byte große Struktur, die wie folgt aufgebaut ist:
| Byte-Position | Daten-Typ | Beschreibung |
|---|---|---|
| 0 - 15 | string | Kennung (z.B. "FREQ_INV_LIST ") |
| 16 - 19 | dword | Version (z.B. 0x00010000 für 1.0) |
| 20 - 23 | dword | Flags (z.Z. unbenutzt) |
| 24 - 27 | dword | Größe des Index (Hashtabelle) |
Daraufhin folgt die Hashtabelle (4*Größe des Index Bytes). Jedes Bucket der Hashtabelle enthält entweder den Offset (relativ zum Ende der Hashtabelle) auf die Token mit demselben Hashwert, oder bei einem leeren Bucket den Wert -1 (0xFFFFFFFF).
Die Daten (d.h. Token und Häufigkeiten) folgen direkt der Hashtabelle. Jedes nicht-leere Bucket wird in der Daten-Sektion wie folgt abgebildet:
Daraufhin folgt für jedes Token folgende Struktur:| Byte-Position | Daten-Typ | Beschreibung |
|---|---|---|
| y - (y+3) | dword | Anzahl der Dokumente (in denen das Token vorkommt) |
| y+4 | byte | Länge des Token-Textes |
| (y+5) - (y+5+n) | string | Token-Text |
Das Programm gh_index ist die Schnittstelle für den Benutzer zum Anlegen eines Indexes. Der Sourcecode befindet sich in Datei test/index.sml. Man ruft es wie folgt von der Kommandozeile auf:
% gh_index hashSize charTableFile stopwordFile indexFile docDB
Die verschiedenen Parameter sind in der folgenden Tabelle erklärt:| Parameter | Beschreibung |
|---|---|
| hashSize | Hiermit kann man die Größe der Hashtabelle angeben. |
| charTableFile | Die zu verwendente Char-Table Datei. |
| stopwordFile | Datei, die zu verwendende Stopwörter enthält. |
| indexFile | Index-Datei, die erzeugt werden soll. |
| docDB | Name der Dokument-Datenbank (ohne Endung .db). |
Die Dokument-Datenbank ist eine DBM Hash-Datenbank, in der zu jeder Dokument-ID der zugehörige Dateiname steht. Eine DocDB kann auch für mehrere Indexe verwendet werden. Der Sourcecode des DBM-Interface für SML ist im Verzeichnis dbm zu finden (Dateien dbm.c und dbm.sml).
Da gh_index eine Liste von Dateinamen von StdIn ließt, muß man diese irgenwie generieren. Unter UNIX bietet sich hierfür das Programm find an:
% find . -type f -print
liefert rekusiv eine Liste aller Dateien beginnend vom aktuellen Verzeichnis. Mit Hilfe von Pipes kann man dies nun gh_index auf StdIn umleiten:% find . -type f -print | gh_index ...
Das Ruby-Skript gh_conv kann dies ebenso, dient aber vorwiegend zur Konvertierung sowie Filterung verschiedener Dateitypen. So ermittelt gh_conv den Dateityp durch das UNIX-Hilfsprogramm file und reagiert entsprechend dem Dateityp. Es kann:Dateien ignorieren (:REJECT); sinnvoll bei Videos, Bildern oder Audio-Files
Dateien as is passieren lassen (:ASIS)
ein externes Datei-Konvertierung Programm aufrufen (z.B. lynx, ps2ascii oder catdoc)
Aufrufen kann man es auf zwei Arten:
% find . -print | gh_conv | gh_index ....
% gh_conv /start/dir | gh_index ....
Das Query-Programm besteht aus einem RankingParser (Files query/ranking-parser.sml und query/ranking.lex), der Struktur RankedQuery (File query/ranked-query.sml) sowie dem Sourcecode für das Programm selbst (test/query.sml). Der eigentliche Zugriff auf die Index-Datei findet in der InvertedList Struktur in Datei ds/inv-list.sml statt, oder falls eine extrem schnelle und Resourcen-schonende Version benötigt wird, kann ds/query-inv-list.c verwendet werden.
Der RankingParser transformiert eine Eingabe, wie etwa folgende:
(+10)IR -diode +information retrievalin eine Liste von RankedTerm's:
[RankedTerm(IR, 10), RankedTerm(diode, -1), RankedTerm(information, 1), RankedTerm(retrieval, 1)]
RankedQuery führt eine Abfrage auf den Index durch und berechnet für jedes auftretende Dokument einen Score. Die Dokumente sortiert nach absteigendem Score werden dann schließlich vom Hauptprogramm gh_query ausgegeben.
Das Programm gh_query ist die Schnittstelle für den Benutzer zum Abfragen eines Indexes. Der Sourcecode befindet sich in Datei test/query.sml. Man ruft es wie folgt von der Kommandozeile auf:
% gh_query charTableFile stopwordFile indexFile docDB
Die verschiedenen Parameter sind in der folgenden Tabelle erklärt: gh_query erwartet auf der Standard-Eingabe eine Abfrage (siehe weiter oben). Daraufhin gibt das Programm auf der Standard-Ausgabe die passenden Dokumente geordnet nach höchstem Score aus.