Wie erstellt man index-Dateien für eine Volltext-Suche?

[Michael Schröpl]

Hi Philipp,

mal angenommen, dieses Array würde nicht zu groß (z.B. weil es eigentlich nur für einen Anfangsbuchstaben gilt
Es ist auch dann noch gross.

vor allem ist seine Größe zu sehr vom Buchstaben abhängig. Die Datei mit allen Worten, die mit "Q" beginnen, ist signifikant kleiner als diejenige mit allen "N"-Worten.
An dieser Stelle kann man mit einer guten Hash-Funktion viel erreichen: Erstens gleich große Teil-Indexe, und zweitens so viele (und so kleine) Indexe, wie man will.

Das Hauptproblem ist, daß selbst eine kleine "Indexdatei" zunächst mal nur eine lineare Liste ist.
Will man daraus einen sortierten Baum erstellen, dann muß man diese Liste sortieren - wobei es nichts nützt, daß sie ggf. bereits in sortierter Form vorliegt: Der Aufwand, einen binären Baum daraus zu erstellen, ist mindestens linear zur Anzahl der Knoten. Danach kommt noch ein logarithmischer Aufwand für das Durchsuchen hinzu. Bei der Konstruktion eines Hashes sind die Kosten ähnlich.
Beides ist aber jeweils schon schlechter als der lineare Aufwand für den trivialen full table scan!

Also: Hashes bringen im vorliegenden Falle nichts, weil es viel zu teuer ist, sie überhaupt erst mal aufzubauen.
Zugriffe auf komplexe Datenstrukturen beschleunigen die Sache nur dann, wenn der teure Aufbau dieser Datenstruktur nur ein einziges Mal bezahlt werden muß - und nicht bei jedem Suchvorgang immer wieder.

Viele Grüße
      Michael