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

[Philipp Hasenfratz]

Halihallo Andreas

Och, wenn die tägliche Bewegung aus dem Bewegen von 10 Fingern und kurzzeitigem
wandern zur Kaffeemaschine besteht, ist es eine willkommene Abwechslung :-)
hast schon recht, aber bei der Hitze find ich's doch etwas anstrengend.

Hm, bei uns hängt das primär vom Gegner ab, sekundär vom Biergehalt im Blut, aber erst
terziär von der Hitze :-)

Hat Deine Mannschaft denn gewonnen?

Den Status "gewonnen" hatten wir in ca. 70% der eingetretenen Spiele, wovon - durch die
Regelkonvention definiert - keines Unentschieden ausgegangen ist ;)

Musst einfach die Fragen stellen :-)
also gut: ist ein assoziatives Array zum sammeln der indizierten Wörter in meinem Fall denn die richtige Wahl?

Ja, aber nicht das assoziative Array, das du meinst (glaube ich zumindest). Es ist nie
eine gute Idee den ganzen Index in einer Datenstruktur in den Speicher einzulesen.
Nehmen wir an, du hast ein Index der wie folgt aussieht:

Datenbank;192;168
Index;485;129
Andreas;904;129
Halihallo;985;374
Hallihallo;859;86
haaalooo;983;124

das ist eine mögliche Darstellung eines assoziatives Array in einer Textdatei. Wenn nun
eine Suchanfrage zum Wort "Andreas" ansteht, solltest du _niemals_ die ganze Datei in ein
assoziatives Array der Programmiersprache einlesen. Du _sollst_ die Datei sequenziell
(in einer Textdatei ist das zeilenweise) auslesen und jede Zeile einzeln untersuchen,
ob sie mit dem Suchbegriff übereinstimmt. Stell dir vor, der Index hätte 5GB; den in
ein Array einzulesen würde den RAM-Speicher sprengen.
Soviel zu den Ressourcen und nun zur Performance:
Stell dir vor, du hast einen Index mit 500'000 Zeilen (in jeder Zeile steht ein
indexiertes Wort)... Für jede Suchanfrage müsstest du durchschnittlich 250'000 Zeilen
lesen, bis du das Ergebnis kennst. Da gibt es bessere Methoden: Eine vorsortierte Liste.
Wenn alle indexierten Wörter alphabetisch sortiert vorliegen, müsstest du für den
Suchbegriff "Zanderholz" bestimmt nicht am Anfang nachsehen, sondern würdest vorzugsweise
vom Ende her lesen (da "Z" ja wohl eher "hinten" in der Datei zu finden sein wird). Du
wirst hier nur auf ein kleines Problem stossen: In Textdateien kann man nicht
herumspringen (es gibt keinen Befehl: "lies die Datei von hinten", oder "gib mir die
Ziele 759"). Nun, auch hierfür gibt es Lösungen:

a) Du nimmst dennoch eine Datenbank.
b) Du ignorierst dies und hoffst, dass es nicht viele Indexausdrücke gibt, als dass die
   Performance in den Keller steigt.
c) Du erstellst mehrere Dateien (z.B. für jeden Anfangsbuchstaben eine)
d) Du erstellst einen Algorithmus, der in Textdateien diejenige Zeile ausgibt, in
   welcher die ersten Zeichen dem Suchwort entsprechen.
e) [weitere]

Noch etwas kleines zu d):
Wenn eine _sortierte_ Liste vorliegt, kannst du - wenn du den Aufwand schon betreibst -
es gleich noch viel besser umsetzen: Stichwort: Binäre Suchbäume (B-Tree).

Viele Grüsse

Philipp