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

[Andreas-Lindig]

Hallo Forum,
mein Forum ist ja fast fertig, nur eine coole Volltext-Suche fehlt noch. Jetzt muß ich mal eine spezial-Frage stellen:

Wie komme ich eigentlich auf die richtigen Begriffe für Index-Dateien? Werden da die Dateien alle Wort für Wort durchsucht? Also, ich habe mir mal die JavaScript-Suche von SelfHtml angesehen und da gibt's ja haufenweise Indexe. Scheinbar werden da Arrays gefüllt mit Seitenzahlen oder sowas. Und wodurch wird so eine Suche dann schnell? Liegt das an den assoziativen Arrays, also, daß die richtige Stelle gleich angesprungen werden kann? In der SelfHtml-Suche kommen nicht nur ganze Wörter vor, sondern auch Fragmente:

Beispiel
--------
w["spinnen"]="129-224"
w["spitze"]="151-122+630-45-12+634-77-12+654-227+827-113+840-163+1994-215"
w["spitzen"]="139-65+144-102-5+145-377+436-109+442-84"
w["spitznamen"]="1480-6-15-57"
w["akustischen"]="763-113"
w["akz"]="838-253"
w["ufern"]="129-173+729-134+895-179+1607-181"
w["ufig"]="686-86"
w["ug"]="2044-613+2045-1058"

hat das einen Sinn? (wahrscheinlich ;)
Und was ist, wenn ich in dem obigen Beispiel im Suchformular z.B. "sp" eingebe?

Tja, ist alles noch nicht so konkret, aber ich habe eben noch keine konkrete Vorstellung und hätte gern mal Tips, wie man so was angeht.

Gruß, Andreas

[Philipp Hasenfratz]

Halihallo Andreas

Wie komme ich eigentlich auf die richtigen Begriffe für Index-Dateien? Werden da die Dateien alle Wort für Wort durchsucht?

Nein, man erstellt einen sogenannten inverted index, d.h. eine Volltextsuche wird
_niemals_ alle Dokumente durchforsten. Dies würde definitiv zu lange dauern. Der Trick
einer Volltextsuche ist es einen Index über die Wörter zu erstellen. Jedes Dokument wird
zuerst indexiert, d.h. in Wörter oder Wortkombinationen aufgeschlüsselt und nur diese
werden gespeichert. Enthalten nun zwei Dokumente das selbe Wort, wird es einmal
gespeichert und referenziert beide Dokumente. Dies könnte z.B. so aussehen:

Datenbank => 192;168

also: Das Wort "Datenbank" ist in den Dokumenten 192 und 168 enthalten. Sucht nun jemand
über die Volltextsuche nach "Datenbank", muss nur noch der Index abgefragt werden (und
dies kann bekanntlich sehr, sehr viel schneller geschehen, als wenn man die ganze Datei
durchsuchen müsste).

Also, ich habe mir mal die JavaScript-Suche von SelfHtml angesehen und da gibt's ja haufenweise Indexe. Scheinbar werden da Arrays gefüllt mit Seitenzahlen oder sowas. Und wodurch wird so eine Suche dann schnell?

Der Vorteil liegt darin, dass nicht _jedes_ Dokument _ganz_ durchforstet werden muss,
sondern nur noch eine Datei (der Index). Findet man in dieser den entsprechenden Eintrag
hat man gleich alle Dokumente, die den Suchbegriff enthalten. Zudem kann ein guter
Index sehr viel schneller durchsucht werden, da er vorsortiert sein kann (wie z.B. die
Indizies bei Datenbanken).

w["ug"]="2044-613+2045-1058"
hat das einen Sinn? (wahrscheinlich ;)

Ist anzunehmen, ja. 2044 referenziert wahrscheinlich irgendein Dokument von SelfHTML.

Tja, ist alles noch nicht so konkret, aber ich habe eben noch keine konkrete Vorstellung und hätte gern mal Tips, wie man so was angeht.

Benutzt du eine MySQL Datenbank? - Dann wäre ggf.
http://www.mysql.com/doc/en/Fulltext_Search.html lesenswert. Sonst müsstest du
etwas mehr dazu sagen, wie du die Volltextsuche haben möchtest und welche Techniken dir
zu Verfügung stehen.

Viele Grüsse

Philipp

[Andreas-Lindig]

Halihallo Andreas

Hollodrio Philipp,
liegt ja doch noch einer nicht schlapp im Bett oder unterm Baum ;)

Nein, man erstellt einen sogenannten inverted index, d.h. eine Volltextsuche wird
_niemals_ alle Dokumente durchforsten.

das habe ich verstanden, deshalb will ich ja das indexieren lernen.

Jedes Dokument wird zuerst indexiert, d.h. in Wörter oder Wortkombinationen aufgeschlüsselt und nur diese werden gespeichert.

So! WELCHE Wörter nimmt man denn da. Alle? Und wann nehme ich Wortkombinationen?

Zudem kann ein guter Index sehr viel schneller durchsucht werden, da er vorsortiert sein kann (wie z.B. die Indizies bei Datenbanken).

ist denn ein assoziatives Array aus Sicht einer Programmiersprache auch 'vorsortiert'?

Benutzt du eine MySQL Datenbank? - Dann wäre ggf.
http://www.mysql.com/doc/en/Fulltext_Search.html lesenswert. Sonst müsstest du etwas mehr dazu sagen, wie du die Volltextsuche haben möchtest und welche Techniken dir zu Verfügung stehen.

Ich habe MySQL/PHP. Die Kopfdaten der Postings speichere ich in der DB, aber die Inhalte der Postings speichere ich in Dateien (aus Platzgründen, und um vielleicht mal einen Download anbieten zu können).

Gruß, Andreas

[Philipp Hasenfratz]

Halihallo Andreas

liegt ja doch noch einer nicht schlapp im Bett oder unterm Baum ;)

Oh, aber fast. Nur dass schlapp und unterm Baum nicht ganz zutreffend ist. Ich stehe
auf dem heissen Sand, in der Mitte des Feldes ein Netz aufgespannt und irgendwie fliegt
da immer ein Ball möglichst immer über das Netz... Bald, bald stehe ich dort, bei meinem
geliebten Beach-Volleyball :-)

Jedes Dokument wird zuerst indexiert, d.h. in Wörter oder Wortkombinationen aufgeschlüsselt und nur diese werden gespeichert.
So! WELCHE Wörter nimmt man denn da. Alle? Und wann nehme ich Wortkombinationen?

Ähm, das hängt von dir ab :-)

- Stoppwortliste (Negativwortliste):

Wörter wie "und, oder, er, es, the, ..." müssen wohl kaum indexiert werden, da sie
   absolut irrelevant für die Suche sind. Diese kannst du gleich ins Datennirvana senden.

- Wortkombinationen kommen sehr selten vor. Ich würde dir der einfachheitshalber eine
   "Einwortindexierung" vorschlagen.

Zudem kann ein guter Index sehr viel schneller durchsucht werden, da er vorsortiert sein kann (wie z.B. die Indizies bei Datenbanken).
ist denn ein assoziatives Array aus Sicht einer Programmiersprache auch 'vorsortiert'?

Nein. Ein assoziatives Array ist eigentlich immer unsortiert, da die Keys eine Menge und
kein Array sind. Aber: in den meisten 4GL Languages (PHP/Perl/...) kommen hashing-
Algorithmen zum Einsatz, sodass ein Eintrag dennoch sehr schnell gefunden werden kann.

Benutzt du eine MySQL Datenbank? - Dann wäre ggf.
http://www.mysql.com/doc/en/Fulltext_Search.html lesenswert. Sonst müsstest du etwas mehr dazu sagen, wie du die Volltextsuche haben möchtest und welche Techniken dir zu Verfügung stehen.
Ich habe MySQL/PHP. Die Kopfdaten der Postings speichere ich in der DB, aber die Inhalte der Postings speichere ich in Dateien (aus Platzgründen, und um vielleicht mal einen Download anbieten zu können).

Spricht etwas dagegen den Volltextindex von MySQL (Achtung: Version beachten!) zu
verwenden? - Einen eigenen Index zu erstellen ist nicht so einfach, wie es sich jetzt
vielleicht anhört...

Viele Grüsse

Philipp

[Andreas-Lindig]

Bald, bald stehe ich dort, bei meinem
geliebten Beach-Volleyball :-)

ohje, auch noch bewegen...

Spricht etwas dagegen den Volltextindex von MySQL (Achtung: Version beachten!) zu
verwenden? - Einen eigenen Index zu erstellen ist nicht so einfach, wie es sich jetzt

naja, zum Einen eben das Platzproblem - ich habe bei meinem Hoster 10 mal soviel Festplatte, wie Datenbankplatz. Zum Anderen bin ich einfach neugierig, ob ich nicht auch sowas hinkriege...

Gruß, Andreas

[Philipp Hasenfratz]

Halihallo Andreas

Bald, bald stehe ich dort, bei meinem
geliebten Beach-Volleyball :-)
ohje, auch noch bewegen...

Och, wenn die tägliche Bewegung aus dem Bewegen von 10 Fingern und kurzzeitigem
wandern zur Kaffeemaschine besteht, ist es eine willkommene Abwechslung :-)

Spricht etwas dagegen den Volltextindex von MySQL (Achtung: Version beachten!) zu
verwenden? - Einen eigenen Index zu erstellen ist nicht so einfach, wie es sich jetzt
naja, zum Einen eben das Platzproblem - ich habe bei meinem Hoster 10 mal soviel Festplatte, wie Datenbankplatz. Zum Anderen bin ich einfach neugierig, ob ich nicht auch sowas hinkriege...

OK. Gegen Erfahrung-sammeln ist natürlich überhaupt nichts einzuwenden. Du möchtest also
eine eigenständige Lösung nicht über die Datenbank.?

Da die hiesige Suche auch auf dieser Lösung beruht und einige Leute davon Ahnung haben,
bist du hier bestimmt am richtigen Ort. Musst einfach die Fragen stellen :-)

Viele Grüsse

Philipp

[Andreas-Lindig]

Halihallo Andreas

haaalooo (boahehdaswetterehhabichdochglattvergessendaspostingabzuschickenundmussesjetztnochmalschreiben)

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. Hat Deine Mannschaft denn gewonnen?

OK. Gegen Erfahrung-sammeln ist natürlich überhaupt nichts einzuwenden. Du möchtest also eine eigenständige Lösung, nicht über die Datenbank?

jou!

Da die hiesige Suche auch auf dieser Lösung beruht und einige Leute davon Ahnung haben, bist du hier bestimmt am richtigen Ort.

na, hoffentlich schauen die Kenner dann noch vorbei

Musst einfach die Fragen stellen :-)

also gut: ist ein assoziatives Array zum sammeln der indizierten Wörter in meinem Fall denn die richtige Wahl?

Gruß, Andreas

[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

[Andreas-Lindig]

Hallo Hallo Hallo,

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.

Ich dachte das Array soll nicht so eindimensional (eigentlich ja zweidimensional) vorliegen, wie oben, sondern z.B. so:

$suchfeld['a'] = array(); (du kennst PHP?)
$suchfeld['d'] = array();
$suchfeld['h'] = array();
$suchfeld['i'] = array();

$suchfeld['a']['Andreas'] = array(904,129);
$suchfeld['d']['Datenbank'] = array(192,168);
$suchfeld['h']['Halihallo'] = array(985,374);
$suchfeld['h']['Hallihallo'] = array(859,86);
$suchfeld['h']['haaalooo'] = array(983,124);

das entspräche ja im Grunde schon der Aufteilung der Indexdateien nach Buchstaben, wie weiter unten angesprochen oder?

mal angenommen, dieses Array würde nicht zu groß (z.B. weil es eigentlich nur für einen Anfangsbuchstaben gilt - 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?

[...]

Ich fasse zusammen (so für mich): wenn die Datei zu groß ist, kann ich sie nicht mehr einlesen wg. Speichermangel. 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.

a) Du nimmst dennoch eine Datenbank.

also zum Beispiel, eine Tabelle mit den feldern a-z und da pack ich die Suchwörter rein? - Ich will einfach mal vermeiden, die ganzen Postings in die DB zu quetschen (ansonsten wäre der Volltextindex wohl echt das Bessere - und eben: lernen, popernen ;).

c) Du erstellst mehrere Dateien (z.B. für jeden Anfangsbuchstaben eine)

ja, so ist es auch in der JS-Suche von SelfHtml gemacht, der hat sogar für einen Buchstaben mehrere Dateien - hab' ich noch nicht ganz verstanden. Aber der liest die Dateien auch in ein Array ein - wohl nur die, die er braucht. Jedenfalls ist die Suche sauschnell.

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?

e) [weitere]

auch 'ne gute Möglichkeit ;)

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.

Gruß, Andreas

--
http://extra.andeas-lindig.de/was_das/

[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

[Andreas-Lindig]

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.

Du hast mir die Augen geöffnet: klar, der macht das in JS so, weil man da keine dateien lesen kann.

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...

naja, ich meinte, wenn man schreibt: durchsuche das Array in $suchfeld['h']
foreach($suchfeld as $suchwort)
   if($suchwort == 'Hallihallo')

oder:

if($suchfeld['h']['Hallihallo'])
   echo 'gefunden';

...Ich mache mal einen Vorschlag, dass es einfacher zu verstehen ist:
...

das Beispiel war wirklich gut. Danke schön, jetzt ist klar und das scheint mir auch sehr praktikabel und schnell.

http://forum.de.selfhtml.org/archiv/2003/2/37129/#m203533 hatte ich da für einen anderen Thread gefunden.

jetzt verstehe sogar Ich so einen Index -  das Prinzip ist ja einfach. Kann ich bestimmt irgendwann mal einbauen.

--- zum Schluss noch ein Tipp: ---
...
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).

vielen Dank für Deine Sorge ;) - hast aber Recht. Ich hab gar nicht so viel Zeit. Ich übernehme mich öfters mal (zum Beispiel mit meinem Forum ;), aber so ist es überhaupt entstanden - wenn ich gewußt hätte, auf was ich mich da einlasse...

Gruß, Andreas

[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

[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

[Michael Schröpl]

Hi Philipp,

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.

doch, natürlich. Es ist nur keine gute Idee, das bei jeder Such-Anfrage immer wieder zu tun.
Ein Datenbank-Index lebt geradezu davon, daß das RDBMS wesentliche Teile des Indexbaums permanent im RAM hält.

e) [weitere]

Du hältst den Index im Hauptspeicher eines daemon-Prozesses und läßt das eigentliche Such-Frontend mit diesem über IPC kommunizieren - so, wie dieses Forum das tut. Dies kommt der Idee einer Datenbank m. E. am nächsten.

Viele Grüße
      Michael

[Michael Schröpl]

Hi Philipp,

So! WELCHE Wörter nimmt man denn da. Alle? Und wann nehme ich Wortkombinationen?
Ähm, das hängt von dir ab :-)

• Wortkombinationen kommen sehr selten vor. Ich würde dir der einfachheitshalber eine
     "Einwortindexierung" vorschlagen.

Man nimmt Wortkombinationen, wenn die Aufgabenstellung es verlangt. ;-)

Eine Volltextsuche wie im Self-Portal ist mit einer reinen Indexsuche nur sehr schwierig performant umzusetzen.

ist denn ein assoziatives Array aus Sicht einer Programmiersprache auch 'vorsortiert'?
Nein. Ein assoziatives Array ist eigentlich immer unsortiert, da die Keys eine Menge und
kein Array sind. Aber: in den meisten 4GL Languages (PHP/Perl/...) kommen hashing-
Algorithmen zum Einsatz, sodass ein Eintrag dennoch sehr schnell gefunden werden kann.

nicht "dennoch", sondern vielmehr "dadurch".
(Hashing ist üblicherweise _schneller_ als der rekursive Abstieg in einem sortierten Baum.)

Spricht etwas dagegen den Volltextindex von MySQL (Achtung: Version beachten!) zu
verwenden?

Ja. ;-) Es erzwingt eine Mindestlänge des Suchbegriffs und verwendet eine fest eingebrannte Stopwortliste. Ich mußte beides im C-Quelltext von mySQL ändern, um diese Funktion so verwenden zu können, daß sie meine Anforderungen erfüllte.

Viele Grüße
      Michael