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

[Philipp Hasenfratz]

Halihallo Michael

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.

Jep.

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.

Jep.

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.

Jep. Nur dass bei gängigen Retrieval Systemen die Daten präkoordiniert sind und die
Indizies somit bereits während dem Indexieren gebildet werden und dies natürlich so, dass
sie beim Retrieval bereits sortiert (eg. in B-tree) vorliegen. Es wäre - wie du selbst
sagst - verherend, wenn bei jeder Suche neu sortiert werden müsste.

Beides ist aber jeweils schon schlechter als der lineare Aufwand für den trivialen full table scan!

Natürlich. Nur, dass n*log(n) für das Sortieren bereits beim Indexieren erledigt
und sich die Suche auf log(n) beschränkt wird; das ist ja der Zweck an der Geschichte
ansonsten bringt es einem wirklich nix.

Also: Hashes bringen im vorliegenden Falle nichts, weil es viel zu teuer ist, sie überhaupt erst mal aufzubauen.

Das geschieht während dem Indexing, nicht während der Suche. s. oben.

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.

Jep.

---

All Deine Einwände und Hinweise aus den anderen Postings bekommen ein
ACK von mir :-)

Viele Grüsse

Philipp