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

[Philipp Hasenfratz]

Halihallo Andreas

Hallo Hallo Hallo,

Re :-)

Ich dachte das Array soll nicht so eindimensional (eigentlich ja zweidimensional) vorliegen, wie oben, sondern z.B. so:
$suchfeld['a'] = array(); (du kennst PHP?)

^^^^^^^^^^^^^^^^ kennen ja, können: no comment :-)

$suchfeld['a']['Andreas'] = array(904,129);
$suchfeld['d']['Datenbank'] = array(192,168);
das entspräche ja im Grunde schon der Aufteilung der Indexdateien nach Buchstaben, wie weiter unten angesprochen oder?

Ja, theoretisch! - Aber praktisch müsstest du eben genau für diese Struktur den
_gesamten_ Datenbestand in dein PHP-Array einlesen, das ist _nicht sinnvoll_.

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. Wäre die Zeichenverteilung immer gleich, würdest du pro
Anfangsbuchstabe einfach 26x weniger Daten haben (a-z).
Du hängst zu sehr an dieser JS-Suche. Trenne dich von ihr, in PHP gibt es bessere
Lösungsmöglichkeiten, da du mit der Datei interagieren kannst.

wie unten beschrieben, also die erste Dimension gelte dann schon dem zweiten Buchstaben: $suchfeld['aa'], $suchfeld['ab'], $suchfeld['ac'] usw.), würde das Programm denn für obiges Beispiel bei der Suche nach 'Hallihallo' direkt in $suchfeld['h'] springen?

Wie meinst du das? - PHP springt nicht einfach so rum, das musst du der Sprache schon
sagen...
Aber nein, nein, nein, diese Arrayaufschlüsselung bringt dir _absolut nichts_. Wenn du
für jeden Buchstaben einen Index generierst, musst du ja nur den ersten Buchstaben aus
dem Suchwort auslesen und die entsprechende Indexdatei öffnen. Diese dann zeilenweise
(sprich: nix da Arrays!) einlesen und das Suchwort finden (bzw. die referenzierten
Dokumente einlesen).

Ich fasse zusammen (so für mich): wenn die Datei zu groß ist, kann ich sie nicht mehr einlesen wg. Speichermangel.

Naja, eingelesen kann sie fast immer werden, dafür gibts Auslagerungs- und Swapbereiche,
_aber_ die Performance sinkt drastisch! - Und das ist das Problem.

Wenn ich sie aber Zeile für Zeile durchsuchen will, sollte sie vorsortiert sein, aber gleichzeitig geteilt, weil ich nicht an beliebiger Stelle die Suche starten kann.

Ich glaube, ich wollte etwas viel Information in einem Posting verpacken, das hat dich
etwas "erschlagen". Mein Fehler.

Also, für die Volltextsuche ist es sehr hilfreich alle Wörter schon zu Indexieren, sodass
nicht mehr jede Datei ganz durchsucht werden muss. Jetzt stellt sich die Frage, wie man
diesen Index möglichst performant umsetzen kann. Oftmals (besonders in einem Forum wie
diesem z.B.) sind das eben ziemlich viele Daten, die Verarbeitet werden müssen. Diese
Daten müssen also effizient angeordnet werden, dass man schnell auf sie zugreifen kann.
Tja, jetzt hatte ich folgenden Vorschlag gebraucht, dass wenn nach "Hallihallo" gesucht
wird, gar nicht den _gesamten_ Index durchsuchen muss, sondern für jeden
Anfangsbuchstaben einen separaten Index schreibt. So könnte für das Suchwort "Hallihallo"
einfach der Index für "h" eingelesen werden (die durchsuchte Datenmenge sinkt dadurch
und wird folglich schneller).
Die andere Möglichkeit über B-trees möchte ich jetzt nicht ausführen, da diese über Text-
Dateien nur über etwas komplexere Algorithmen umgesetzt werden können (das würde ich dir
nicht empfehlen, da müsstest du dich zuerst mit dem Thema ganz allgemein auseinanderge-
setzt haben); das lässt sich von heute auf morgen nicht ohne weiteres umsetzen.

a) Du nimmst dennoch eine Datenbank.
also zum Beispiel, eine Tabelle mit den feldern a-z und da pack ich die Suchwörter rein?

Eine Tabelle mit den Feldern a bis z? - Wie stellst du dir das vor?
Nein, wie gesagt hat die Datenbank bereits einen Index, du brauchst ihn nur noch zu
setzen. Ich mache mal einen Vorschlag, dass es einfacher zu verstehen ist:

Tabelle InvertedIndex

Suchwort: PRIMARY KEY, UNIQUE (eben: dieses ist somit Indexiert)
PassendeDokumente: TEXT (z.B. 192,168,985,474,173)

Nun hast du z.B. "Hallihallo", welches in den Dokumenten 192,168 vorkommt:

INSERT INTO InvertedIndex (Suchwort,PassendeDokumente) VALUES ('Hallihallo','192;168')

nun kommt eine Suchabfrage zu "Hallihallo":

SELECT PassendeDokumente FROM InvertedIndex WHERE Suchwort="Hallihallo"

tja, logisch, oder? - Und was ist hier mit der Performance? - Ja, absolut schnell, denn
auf Suchwort liegt ein Index, d.h. die Datenbank kann den Eintrag "Hallihallo" sehr, sehr
schnell finden. Wenn kein Index auf Suchwort gesetzt wäre, müsst die Datenbank ja die
gesamte Tabelle nach "Hallihallo" durchsuchen. Mit einem Index eben nicht mehr, da
die Datenbank die Einträge bereits sortiert hat und dann so vorgehen kann, wie es Sven
in seinem Posting geschrieben hat (s. unten).

d) Du erstellst einen Algorithmus, der in Textdateien diejenige Zeile ausgibt, in
   welcher die ersten Zeichen dem Suchwort entsprechen.
nix verstehen! muß diese Datei dann auch erst Zeile für Zeile durchsucht werden? oder ist das eine Abkürzung?

Nun, diesen Punkt hätte ich nicht schreiben sollen :-)
Jain, es gibt eben Algorithmen, mit denen man dies nicht zeilenweise machen müsste, aber
diese sind wie schon gesagt nicht über Nacht umzusetzen.

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).
eieiei, was ist das denn? Michael Schröpl hat hier neulich auch von 'allfälligen Indexbäumen' gesprochen - war aber etwas abstrakt.

http://forum.de.selfhtml.org/archiv/2003/2/37129/#m203533 hatte ich da für einen
anderen Thread gefunden. Also wenn eine neue Archivsuche eingeführt wird, die auf link-
priority setzt, ist Svens Posting diesbezüglich ganz weit oben :-)

--- zum Schluss noch ein Tipp: ---

Ich glaube, ich habe dich etwas verwirrt, das tut mir leid. Ich würde dir vorschlagen,
dass du jetzt erstmal eine "ganz einfache" Suche schreibst. D.h. ein Programm, welches
die Postings einliest, die Wörter extrahiert und diese im inverted index aktualisiert.
Danach ein Programm, welches ein Suchwort entgegennimmt und den inverted index durchsucht
und dir die Dokumente/Postings-IDs zurückgibt, welche das Suchwort enthalten. Wenn du
dies hast (dauert ein Weilchen, nehme ich an), gehts weiter im Text :-)
Alles andere, a-z, mehrere Dateien, B-trees, ... ist schön zu haben, sollte aber erst
gemacht werden, wenn die "Grundlage" erarbeitet ist (ansonsten wird man schnell
überfordert).

Viele Grüsse

Philipp