Volltextindizierung

Braucht man das überhaupt?

Stimmt! Die sequentielle Suche, bei der jeder Datensatz gelesen und nach den betreffenden Informationen durchforstet wird, ersetzt im Prinzip jede Form der indizierten (oder einer sonstigen trickreichen) Suche. Und wenn das Lesen der Daten und die Verarbeitung der Informationen keine Zeit benötigen würde, könnte man sich in der Tat die Entwicklung anderer Suchfunktionen ersparen. Aber dem ist leider nicht so...

Es ist sogar noch viel schlimmer. Denn selbst wenn die Rechnergeschwindigkeit um irgendeinen beliebigen Faktor gesteigert wird, bleibt die sequentielle Suche immer nur auf kleine Informationsbestände beschränkt, wenn das Suchergebnis in einer vorgegebenen Zeit vorliegen muß.

Klar doch!

Ich möchte sogar noch einen Schritt weitergehen und behaupten, daß Sie, nachdem Sie die Volltextindizierung zum ersten Mal eingesetzt haben, nicht mehr wissen, wie Sie vorher ohne diese Funktion überhaupt auskommen konnten.

Volltextindex mit der tdbengine

Die Voraussetzung für die Volltextindizierung einer Tabelle besteht im Vorliegern zweier Tabellen:

Stichworttabelle, die im ersten Feld eine Zeichenkette enthält und automatisch numeriert wird
Relationstabelle zwischen der Ausgangstabelle und der Stichworttabelle.

Weil diese Tabellen recht häufig benötigt werden, bietet die tdbengine zu deren Erzeugen zwei Sonderfunktion der allgemeinen Funktion MakeTable:

GenList erzeugt eine neue Stichworttabelle
GenRel erzeugt eine neue Relationtabelle

GenList(Dateinname,Zeichenzahl,Modus)

Damit wird eine neue, leere Tabelle unter dem Dateinamen angelegt. Die Struktur dieser Tabelle ist, wenn kein Modus oder Modus=0 angegeben wurde:

[STRUCTURE]
field_1=Wort,STRING,Zeichenzahl
field_2=Laufende_Nummer,AUTO,1
[INDEX]
id=Wort,Laufende_Nummer

Für den Modus=1 ergibt sich ein kleiner Unterschied:

[STRUCTURE]
field_1=Wort,STRING.Zeichenzahl
field_2=WieOft,NUMBER,2
field_3=Laufende_Nummer,AUTO,1
[INDEX]
id=Wort,Laufende_Nummer,WieOft

GenRel(Tabelle1,Tabelle2,Dateiname)

legt eine leere Relationstabelle mit folgender Struktur an

[STRUCTURE]
field_1=R-Tabelle1,LINK,Tabelle1
field_2=R-Tabelle2,LINK,Tabelle2

Hinweis für Experten: Die Ausgangstabelle muß weder automatisch numeriert werden, noch ein Relationsfeld zur Stichworttabelle enthalten!

Beide Tabellen werden normalerweise über die üblichen Tabellenfunktionen weder gelesen noch geschrieben. Denn dafür sind die speziellen Volltextfunktionen der tdbengine zuständig:

Volltextindext neu erstellen

Nicht erschrecken über dieses Funktionsmonster: Alle Parameter mit Ausnahme der ersten vier sind optional!

D Tabellennummer der Ausgangstabelle
I Tabellennummer der Stichworttabelle
R Tabellennummer der Relationstabelle

Fields ist ist eine Spezialfunktion, über die die Information, welche Felder in den Volltextindex aufgenommen werden, an die Funktion übergeben werden. Die Feldkombination kann sowohl statisch als auch dynamisch erfolgen. Im Falle der CGI-Programmierung ist nur die dynamische Version möglich, weil hier ja zur Übersetzzeit keine Tabellen geöffnet sind.

Statische Version: Fields(Feld1,Feld2,Feld3...)
Dynamische Version: Fields("Feld1,Feld2,Feld3...")

Es sind alle Felder der Tabelle (mit Ausnahme von Blobs) zugelassen. Datums-, Zeit- und Zahlenfelder werden in Zeichenketten umgewandelt. Bei Auswahlfeldern wird die entsprechende Textkonstante in den Volltext übernommen.

Bei String-Feldern (Zeichenketten) gibt es eine wichtige Ausnahme: Beginnt ein String-Feld mit dem "#"-Zeichen, so wird der Rest der Zeichenkette als Pfad zu einem externen Textdokument interpretiert und dieses in den Volltextindex aufgenommen. Diese Version der tdbengine unterstützt externe ASCII, ANSI und HTML-Dokumente.

Zusätzlich können die Inhalte ADL-verknüpfter Datensätze über die L-Feld-Notation und über die R-Feld-Notation in den Volltextindex aufgenommen werden.

Beispiel: Eine einfache Volltextindizierung für eine Adreßtabelle adr.dat

VARDEF D,I,R,fc,N : REAL
.EC 1
?fc:=GenList("i-adr.dat",40,1)<>0/HALT .. Fehler beim Anlegen der Stichworttabelle
?fc:=GenRel("adr","i-adr","r-adr.rel")<>0/HALT .. Fehler beim Anlegen der Relationstabelle
IF D:=OpenDB("adr.dat")
  IF I:=OpenDB("i-adr.dat","",0,15)
    IF R:=OpenDB("r-adr.rel","",0,15)
      PrimFile(D)
      N:=ScanRecs(D,I,R,Fields("Vorname,Name,Straße,Ort,Bemerkung"))
    ELSE
      ..Fehler beim Öffnen der Relationstabelle
    END
    CloseDB(I)
  ELSE
    .. Fehler beim Öffnen der Stichworttabelle
    CloseDB(D)
  END
ELSE
  .. Fehler beim Öffnen der Ausgangstabelle
END

Dieses Beispiel enthält alle wesentlichen Bestandteile inklusive skizzierter Fehlerbehandlung.

Darauf sollten Sie achten:

• Reihenfolge beim Öffnen der Tabellen, die Relationstabelle immer als Letzte.
• Vor ScanRecs Primärtabelle wechseln, damit die Feldbezeichner der Ausgangstabelle erkannt werden.

Zunächst werden sowohl Stichwort- als auch Relationstabelle geleert. Dann werden sämtliche Datensätze der Ausgangstabelle gelesen. Bei jedem Datensatz werden die unter Fields angegebenen Felder gescannt, d.h. in einzelne Zeichenketten zerlegt, die nur aus Buchstaben bestehen. Jeder dieser Wörter wird nun in die Stichworttabelle eingetragen, wenn es dort nicht bereits vorhanden ist. Schließlich erfolgt ein Eintrag in die Relationstabelle mit je einem Verweis auf den Datensatz der Ausgangstabelle und dem zugrhörigen Satz in der Stichworttabelle.

Die optionalen Parameter:

ist eine Zeichenkette, die zusätzlich zu den Buchstaben als Wortbestandteile gelten sollen. Wenn beispielsweise auch die Postleitzahl in den Volltextindex aufgenommen werden sollen, so muß hier "0123456789" stehen.

Tip: Der Bindestrich sollte nicht als Bestandteil eines Wortes aufgenommen werden (außer in Spezialfällen), denn damit werden die einzelnen Bestandteile eines (mit Bindestrichen) zusammengestzten Wortes nicht mehr (so einfach und schnell) über die Volltextsuche auffindbar.

Bei den nächsten beiden Parametern geht es um die Einschränkung der Volltextindex. In vielen Fällen will man nämlich informationsarme Wörter wie "und" "der" u.a. nicht in den Volltextindex aufnehmen.

Cut

wird hier ein Wert größer 0 angegeben, so werden Wörter, die öfter als Cut vorkommen, nicht in den Volltextindex aufgenommen.

Kontraindex

ist der Name eine externen Textdatei, in der jene Wörter enthalten sind, die nicht in den Volltextindex aufgenommen werden. Dabei steht jedes Wort in einer eigenen Zeile, eine Sortierung ist nicht notwendig.

Der nächste Parameter definiert das grundsätzliche Verhalten der tdbengine bei Aufbauu des Volltextindex. Die einzelnen Modi werden einfach addiert:

Modus

0        Die Stichworttabelle wird neu erstellt
1        Eine bestehende Stichworttabelle wird verwendet und nur neue Wörter eingetragen
2        Eine bestehende Stichworttabelle wird verwendet, aber keine neunen Wörter aufgenommen
4 *)     Es werden nur die unbedingt benötigten Dateien angelegt
8        HTML-Tags werden überlesen und HTML-Sonderzeichen nach ASCII übersetzt
16      reserviert
32      externe Texte liegen im ASCII-Format vor (andernfalls ANSI)

*) Dieser Modus ist nur bedingt kompatibel zum relationalen System der tdbengine. Er ist aber immer dann mit großem Vorteil einzusetzen, wenn der Zugriff auf die Stichworttabelle und die Relationstabelle ausschließlich über die Volltextfunktionen erfolgt. Zudem wird der benötigte Speicherplatz auf weit weniger als 50% reduziert und die Suchgeschwindigkeit signifikant erhöht.

Step

Dieser Parameter ist nur dann auf einen Wert ungleich 0 zu setzen, wenn wirklich sehr große Datenmengen bearbeitet werden. Es handelt sich dabei um den Speicherplatz, den die tdbengine währen des Indizierens vom Betriebssystem anfordert. Viel Speicherplatz bringt in diesem Fall eine erhöhte Bearbeitungsgeschwindigkeit. Allerdings kann eine zu hohe Speicheranforderung dazu führen, daß ein Teil davon vom Betriebssystem ausgelagert wird, was dann zu einem massiven Performance-Einbruch führt! Aber angenommen, sie haben ein 256 Mbyte-System, auf dem nur wenige speicherintensive Prozesse laufen so können Sie beispielsweise hier den Wert 100000000 (=100 Millionen) eingeben.

Tip: Verändern Sie diesen Wert erst dann, wenn die Indizierungszeiten wirklich aus dem Rahmen fallen.

Maskenfeld

Hierbei handelt es sich um die Nummer eines Feldes der Ausgangsdatei, das eine 16-Bit-Integerzahl speichert (NUMBER,2). Der Inhalt dieses Feldes wird in den Volltextindex, genauer in die Relationstabelle (noch genauer: in den IN2 der Relationstabelle) aufgenommen und kann bei der Volltextsuche berücksichtigt werden. Ein Sonderfall besteht, wenn hier –1 angegeben wird, denn dann können die Maskenwerte direkt (durch Doppelpunkt abgetrennt) in der Feldkombination bei Fields angegeben werden. Die Auswertung bei der Volltextsuche geschieht dann dermaßen, daß hier eine Zahl angegeben wird und diese mit einem binären AND mit der im Volltextindex gespeicherten Maske verknüpft wird. Es werden dann nur solche Verknüpfungen gefunden, bei denen das binäre AND einen Wert ungleich 0 ergibt.

Das klingt kompliziert und ist auch kompliziert, eröffnet aber sehr schöne Möglichkeiten. Dazu ein Beispiel. Angenommen Sie haben eine Adreßdatenbank, in der unterschiedliche Arten von Adressen gespeichert sind: Privatadressen, Firmenadressen, Behördern etc. Die Art der Adressen speichern Sie als Kennung in einem Integer-Feld ab:

1    Privat
2    Firma
4     Behörde
8     wissenschaftliche Institution
...

Bei Adressen, die in mehrere Kathegiorien fallen, addieren Sie einfach diese Werte. Wenn Sie nun die Feldnummer dieses Feldes bei der Volltextindizierung mit angeben, so können Sie bereits bei der Suche jede beliebige Einschränkung bezüglich der Kathegorien machen, ohne daß hierzu ein einziger Datensatz gelesen werden muß!

Alternativ zur Auswertung eines Maskenfeldes können Sie auch direkt bei Fields Maskenzahlen vergeben. In diesem Fall hat die Maskenfeldnummer den Wert –1, und die Maskenzahlen werden direkt nach den Feldnamen angegeben. Dazu wieder ein Beispiel:

ScanRecs(D,I,R,Fields("Vorname:1, Name:2, Strasse:4, Land:8, PLZ:8, Ort:8, Bemerkung:16"),"",0,"",0,0,-1)

Auch hier wird ein Volltextindex aufgebaut. In die Relationstabelle wird jedoch, wenn es sich bei dem gerade untersuchten Feld um Vorname handelt, zu jedem Eintrag die Maskenzahl 1 aufgenommen, für das Feld Name die Zahl 2 usw. Bei der Volltextsuche können Sie dann gezielt in einzelnen Feldern oder Feldkombinationen suchen (oder natürlich auch in allen Feldern gleichzeitig)!

DynKontraIndex

Hierbei handelt es sich um einen dynamischen, feldbezogenen Kontraindex, der wiederum über die Funktion Fields tranportiert wird. Das bedeutet, daß bei jedem Datensatz zunächst die hier stehenen Felder gelesen werden und daraus ein Kontraindex gebildet wird. Dieser Kontraindex gilt allerdings nur für diesen Datensatz, beim nächsten beginnt das Spiel von vorne.

Fehlerbehandlung

Die häufigsten Fehler:

50: (Unbekannter Bezeichner) In Fields steht mindestens ein falsches Datenfeld
58: (Keine Tabelle) Mindestens eine der drei benötigten Tabellen ist nicht geöffnet
64: (Keine ADL-Tabelle) Die Stichworttabelle wird nicht automatisch numeriert
77: (Keine Relationstabelle) Bei dem dritten Parameter handelt es sich nicht um eine gültige Relationstabelle

Ist das Funktionsergebnis negativ, wird zwar kein Laufzeitfehler ausgelöst, aber die Funktion dennoch abgebrochen

-115   Zu wenig Rechte für die Funktion (Die Relationsdatei konnte nicht geleert werden)
-56     (, erwartet) Die Felder in Fields müssen durch Komma getrennt werden

Einzelne Datensätze indizieren

ScanRec(D,I,R,Fields(Felder),ExtABC,Cut,Kontraindex,Modus,Step,MaskenFeld,DynKontraIndex) : REAL

Die Parameter sind genau dieselben wie bei ScanRecs. Allerdings werden nur folgende Modi unterstützt:

2    Es werden keine neuen Wörter in die Stichworttabelle aufgenommen
4    Es werden nur die unbedingt benötigten Informationen gespeichert

Wichtig: Der Modus 4 kann nur verwendet werden, wenn der Volltextindex mit ScanRecs in diesem Modus erzeugt wurde.

Das Funktionsergebnis liefert die Anzahl der neu hinzugekommenen Verknüpfungen bzw. einen der folgenden Fehlercodes:

-56    In Fields(...) fehlt (mindestens) ein Komma
-6      der ID-Index der Stichworttabelle konnte nicht geöffnet werden

Den Volltextindex für einzelne Datensätze löschen

UnScanRec(D,I,R,Fields(Felder),ExtABC,Cut,Kontraindex,Modus,Step,MaskenFeld,DynKontraIndex) : REAL

Die Parameter sind exakt dieselben wie bei ScanRec. Das Funktionsergebnis liefert die Anzahl der gelöschten Verknüpfungen (falls positiv) bzw. den Fehlercode.

Die Suche im Volltextindex

MarkTable(D,I,Suchstring,ExtABC,Ops,MaskenZahl,R1,R2,...) : REAL
MarkBits(D,I,Suchstring,ExtABC,Ops,MaskenZahl,BitFeld,R1,R2,...) : REAL

D                     Nummer der Ausgangstabelle
I                      Nummer der Stichworttabelle
Ausduck          Suchstring
ExtABC           wie bei ScanRecs
Ops                  logische Operatoren
MaskenZahl     Integerzahl
BitFeld            Variable vom Typ TBits[xxx]
R1, R2...         Nummer der Relationstabelle

Das Funktionergebnis ist die Anzahl der gefundenen Datensätze (falls positiv) bzw einer der Fehlercodes:

-64      ungültige Stichworttabelle
-77      ungültige Relationstabelle
-56      illegale Klammerung im Suchstring
-45      ungültiges Zeichen im Suchstring

Die letzten beiden Fehler können mit TDB_ErrorMsg und TDB_ErrorOfs näher bestimmt werden.

Beim Suchstring handelt es sich um eine Zeichenkette mit folgendem Aufbau:

Suchstring ::= Ausdruck
Ausdruck ::=  Term { Oder-Operator Term}
Term        ::=  Faktor { Und-Operator Faktor}
Faktor     ::=   Suchwort | "(" Ausdruck ")"

Ein Suchwort ist eine Zeichenkette aus Buchstaben, den Zeichen aus ExtABC sowie den Sonderzeichen "?" und "*". Dabei steht "?" als Platzalter für genau ein beliebiges Zeichen, "*" für beliebig viele Zeichen.

Folgende Operatoren sind vordefiniert (wenn in Ops ein Leerstring übergeben wird):

Oder-Operator       +  (Vereinigungsmenge, logisches ODER)
Und-Operatoren      ,  (Schnittmenge, logisches UND)
                               -  (Schnitt mit Komplementärmenge, logisches UND  NICHT)
 

Beispiele:

Ops

Maskenzahl

Sonderfall: Die Maskenzahl 0 liefert alle Verknüpfungen.

Beispiel:

Die Volltextindizierung erfolgte mit folgender Indexbeschreibung: Fields(Name:1,Vorname:2,Straße:4)

Die Suche nach Hans liefert dann je nach Maskenzahl

0 In (wenigstens) einem der Felder ist das Wort enthalten
1 Das Wort ist im Feld Name enthalten
2 Das Wort ist im Feld Vorname enthalten
3 Das Wort ist im Feld Name oder im Feld Vorname (oder in beiden) enthalten
4 Das Wort ist im Feld Straße enthalten
5 Das Wort ist im Feld Name oder im Feld Straße (oder in beiden) enthalten
...
7 Das Wort ist (wenigstens) in einem der Felder Name, Vorname oder Straße enthalten.

Bitfeld

Beispiel:

VARDEF Treffer, Temp : TBITS[1000000]

MarkBits(...,Treffer,...)
MarkBits(...,Temp,...)
BitAnd(Treffer,Marks)   (ergibt die Schnittmenge aus beiden Suchen)
BitOr(Treffer,Marks)     (ergibt die Vereinigungsmenge aus beiden Suchen)

Hinweis: Da EASY (derzeit) keine dynamische Dimensionierung von Feldern zuläßt, muß das Bitfeld ausreichend groß dimensioniert werden. Andererseits sollten die Felder auch nicht extrem überdimensioniert werden, da eine schnelle Berabeitung nur erfolgt, wenn die Felder in den Hauptspeicher passen (und nicht vom Betriebssystem ausgelagert werden). Der Speicherbedarf in Bytes kann leicht berechnet werden, indem man die Feldgröße duch 8 teilt. Ein Bitfeld für eine Tabelle mit 1000000 (=1 Million) Datsätzen belegt etwa 120 KByte.

Expertenhinweis: Ein Bitfeld, wie wir es hier einsetzen, kann auch als charakteristische Mengenfunktion aufgefaßt werden, also eine Abbildung der Menge aller Datensätze einer Tabelle in die Menge {0,1}. Es handelt sich dabei um eine sehr effiziente Implementierung von (Teil-)Mengen, da die Mengenfunktionen dann direkt (als fundamentale Maschinenoperationen) ausgeführt werden. Auch MarkTable arbeitet intern mit einem Bitfeld und bildet erst am Ende der Funktion die gefundene Menge auf die Markierungsliste ab.

Um auf die Treffer einer Suche zuzugreifen, gibt es mehrere Möglichkeiten:

Abbildung auf die Markierungsliste

Nach PutMarks(D,Treffer) stehen die Treffer in der Markierungsliste und können wie üblich weiterverarbeitet werden.

Direkter Zugriff auf das Bitfeld

i:=0
WHILE i<FileSize(D)
  IF Treffer[i]
     ..Bearbeitung des Datensatzes mit der Satznummer i
  END
  i:=i+1
END

Die Relationstabellen

Ein Szenario für zwei Relationstabellen könnte etwa folgendermaßen aussehen: Eine Tabelle für ein Textarchiv enthält eine Reihe von Informationen in gewöhnlichen Datenfeldern und einen Verweis auf ein Textdokument, das im HTML-Format vorliegt. In diesem Fall kann es sinnvoll sein, für den Volltextindex über die externen Textreferenzen eine eigene Relationstabelle zu erstellen.

Beispiel: Dokumentenarchiv

[STRUCTURE]
field_1=Autor,STRING,60
field_2=Titel,STRING,120
field_3=Kurzinhalt,MEMO
field_4=Dokument,STRING,60

Im Feld Dokument sind Referenzen wie #/home/kern/doc/beispiel_001.html abgelegt.

Über diese Tabelle wurde ein Volltextindex erzeugt mit

ScanRecs(...,Fields(Autor:1,Titel:2,Kurzinhalt:4,Dokument:8),"",0,"",4+8)

Modus 4 (nur benötigte Dateien) + 8 (Unterstützung von externen HTML-Dateien)

Unser Suchformular hat folgenden Aufbau:

<form action=... method="post">
Suchbegriff: <input type="text" name="suchbegriff" size="40"><br>
Suche in: <input type="checkbox" name="cb_autor" value="1"> Autor &nbsp;
 <input type="checkbox" name="cb_titel" value="2"> Titel &nbsp;
 <input type="checkbox" name="cb_kurzinhalt" value="4"> Kurzinhalt &nbsp;
 <input type="checkbox" name="cb_dokument" value="8"> Dokument
</form>

Damit erlauben wir dem Anwender die Eingabe eines Suchbegriffs und geben ihm die Auswahl, in welchen Bereichen der Begriff gesucht werden soll.

PROCEDURE Dokument-Suche
VARDEF D,I,R,Modus : REAL
...
..hier sind alle drei Tabellen geöffnet
..
Modus:=VAL(CGIGetParam(cb_autor))+VAL(CGIGetParam(cb_titel))
Modus:=Modus+VAL(CGIGetParam(cb_kurzinhalt))+VAL(CGIGetParam(cb_dokument))
MarkTable(D,I,CGIGetParam("suchbegriff"),"","",Modus,R)
...
..Treffer ausgeben
..
ENDPROC