Lokale Suchmaschine

[Andreas]

Hallo!

Und noch eine kleine Programmiertechnik-Frage ;-)
Wenn ich eine Suchmaschine, die "statische" .html- und.php-Seiten in PHP programmieren möchte, würde ich das im Prinzip so machen:

Dateinamen der Seite mit readdir() in einen Array laden, die Dateien nacheinander mit fopen() öffenen, dann mit einem Regulären Ausdruck nach dem Suchbegriff durchsuchen, wieder schließen...

Aber dabei sehe ich folgende Probleme:

• bei größeren Präsenzen wird das sehr(!) lange dauern
• ich finde auch html-Tags
• bei .php Seiten finde ich auch den ganzen php-Code.

Wahrscheinlich kann man die letzten beiden Punkte durch einen guten regulären Ausdruck ausklammern, aber der erste erscheint mir sehr schwerwiegend.

Wie macht man sowas vielleicht etwas performanter?

Zum regulären Ausdruck, sowas wie />(.*?)</  würde das nicht schon reichen?

Viele Grüße
Andreas

[Stefan Muenz]

Hallo Andreas

Dateinamen der Seite mit readdir() in einen Array laden, die Dateien nacheinander mit fopen() öffenen, dann mit einem Regulären Ausdruck nach dem Suchbegriff durchsuchen, wieder schließen...

Das ist die schlichteste und ineffektivste Methode. Bei vergleichsweise statischen Inhalten, also solchen, die sich nicht dauern, ist es in jedem Fall besser, mit einem Index zu arbeiten. Dazu brauchst du zwei Scripts: ein reines Arbeitsscript, das wie oben beschrieben verzeichnisweise aus allen Seiten, die durchsuchbar sein sollen, die Daten herausliest und in irgendeine, fuer das Suchscript auslesbare Datei schreibt, und zwar nach irgendeiner Konvention, die das Suchscript beim Auslesen anwenden kann. Das Arbeitsscript muss dann jedesmal angestossen werden, wenn der durchsuchbare Datenbestand aktualisiert werden soll. (An dieser Stelle zeigt sich uebrigens ein typischer Vorteil von Perl - man kann damit eben auch problemlos mal reine, kommandozeilenorientierte Arbeitsscripts schreiben ... jaja,. ich weiss, "irgendwie" geht das mit PHP auch *g*).

Die Index-Datei mit den durchsuchbaren Daten kann ruhig eine gewisse Groesse bekommen. Ein paar Megabyte sind voellig unkritisch und lassen sich auf modernen Rechnern in Bruchteilen von Sekunden sequentiell durchsuchen.

• ich finde auch html-Tags
• bei .php Seiten finde ich auch den ganzen php-Code.
  Wahrscheinlich kann man die letzten beiden Punkte durch einen guten regulären Ausdruck ausklammern, aber der erste erscheint mir sehr schwerwiegend.

Dafuer gibt es Module oder Funktionen. In PHP gibt es z.B. so eine strip-all-tags-Funktion. Die Muehe, die eingelesenen Daten noch ein bischen zu bearbeiten, um nur die wirklichen Nutzdaten herauszuziehen, solltest du dir auf jeden Fall machen!

viele Gruesse
  Stefan Muenz

[Andreas]

Hallo!

Das ist die schlichteste und ineffektivste Methode. Bei vergleichsweise statischen Inhalten, also solchen, die sich nicht dauern, ist es in jedem Fall besser, mit einem Index zu arbeiten.

Ja, das hat mir mein Gefühl auch gesagt, nur bin ich nicht sicher wie so ein index vernünftigerweise aussieht, so dass er schnell zu durchsuchen ist. Also im Falle einer indexdatei, wie bei der Forumssuche. Vom prinzip, wie würdet Ihr/habt Ihr die Index DAtei aufgebaut und wie genau durrchsucht Ihr die Datei?

Dazu brauchst du zwei Scripts: ein reines Arbeitsscript, das wie oben beschrieben verzeichnisweise aus allen Seiten, die durchsuchbar sein sollen, die Daten herausliest und in irgendeine, fuer das Suchscript auslesbare Datei schreibt, und zwar nach irgendeiner Konvention, die das Suchscript beim Auslesen anwenden kann. Das Arbeitsscript muss dann jedesmal angestossen werden, wenn der durchsuchbare Datenbestand aktualisiert werden soll. (An dieser Stelle zeigt sich uebrigens ein typischer Vorteil von Perl - man kann damit eben auch problemlos mal reine, kommandozeilenorientierte Arbeitsscripts schreiben ... jaja,. ich weiss, "irgendwie" geht das mit PHP auch *g*).

Ja, sicher geht das in PHP ;-) Ich wüßte nur nicht wie ich es automatisch bei Änderung einer Datei anstoßen würde, vom Browser oder per Cron oder SSH kein Thema. Aber hast Recht, diese Trennung ist notwendig!

Die Index-Datei mit den durchsuchbaren Daten kann ruhig eine gewisse Groesse bekommen. Ein paar Megabyte sind voellig unkritisch und lassen sich auf modernen Rechnern in Bruchteilen von Sekunden sequentiell durchsuchen.

Das stimmt, aber auch nur solange man weiß wie man schnell sucht, es gibt ja bestimmt schnelle und langsame reguläre Ausdrücke bzw. Strukturen für einen solchen Index, oder?
Ich denke aber, eine DB wird auch bei 100 Seiten schon schneller sein, oder?

• ich finde auch html-Tags
• bei .php Seiten finde ich auch den ganzen php-Code.
  Wahrscheinlich kann man die letzten beiden Punkte durch einen guten regulären Ausdruck ausklammern, aber der erste erscheint mir sehr schwerwiegend.

Dafuer gibt es Module oder Funktionen. In PHP gibt es z.B. so eine strip-all-tags-Funktion. Die Muehe, die eingelesenen Daten noch ein bischen zu bearbeiten, um nur die wirklichen Nutzdaten herauszuziehen, solltest du dir auf jeden Fall machen!

Wie Michael richtig angedeutet hat, wäre die Semantik nicht uninteressant, daher bräuchte ich doch ein paar reguläre Ausdrücke.

Viele Grüße
Andreas

[Michael Schröpl]

Hi Andreas,

Also im Falle einer indexdatei, wie bei der
Forumssuche. Vom prinzip, wie würdet Ihr/habt
Ihr die Index DAtei aufgebaut und wie genau
durrchsucht Ihr die Datei?

die Indexdatei besteht aus knapp 10 Feldern,
die durch ein Sonderzeichen ("|") getrennt sind.

Das Such-Skript liest diese Datei sequentiell,
trennt die Felder mit "split()" voneinander und
führt dann den Vergleich mit einzelnen Such-Termen
über regular expressions durch. (Damit werden dann
auch Dinge wie case-Sensitivität oder Wortgrenzen
gleich mit erschlagen.)
Auf diese Weise sind insbesondere auch beliebige
Phrasen auffindbar, nicht nur Worte.
Und diese Anforderung hat lange Zeit (Jahre ...)
verhindert, einen indexbasierten Ansatz ernsthaft
in Erwägung zu ziehen. (Inzwischen wird aber an
einem solchen gearbeitet, wobei Phrasen dadurch
realisiert werden sollen, daß zuerst ein AND über
alle darin enthaltenen Worte via Index und dann
für alle so bestimmten Treffer eine Volltextsuche
nach der exakten Phrase gemacht wird, um die echten
von den unechten Treffern zu trennen.)

Die Index-Datei mit den durchsuchbaren Daten
kann ruhig eine gewisse Groesse bekommen.
Ein paar Megabyte sind voellig unkritisch und
lassen sich auf modernen Rechnern in Bruchteilen
von Sekunden sequentiell durchsuchen.
Das stimmt, aber auch nur solange man weiß wie man
schnell sucht, es gibt ja bestimmt schnelle und
langsame reguläre Ausdrücke bzw. Strukturen für
einen solchen Index, oder?

Kaum. Ein Großteil der Arbeit ist wirklich das
Einlesen der kompletten Indexdateien - wie groß
die sind (und wie schnell das trotzdem geht!),
zeigen Dir die Ausgaben im Suchformular (bzw. in
der Ergebnisseite).
Vor allem: Wenn Du mehrere Suchterme verwendest
und diese mit AND verknüpfst, dann wird jeder
dieser Terme nur eine relativ kleine Teilmenge
aller Dokumente matchen. Laß es mal 10% sein.
Dann wird der erste Term für 10% aller Dokumente
matchen, der zweite aber nur noch in diesen 10%
aller Fälle überhaupt geprüft werden müssen und
dann wieder nur für 10% aller Fälle matchen, dann
sind wir bei 11%. Der dritte erhöht die Zahl der
Vergleiche wieder nur um ein Zehntel des Vorgän-
gers ... jeder weitere Term wird immer bedeutungs-
loser, weil er immer seltener geprüft wird.
Gleichzeitig machen weitere Terme aber die Treffer-
menge kleiner und reduzieren damit den Aufwand bei
der Ausgaben.
Im Ergebnis ist eine Suche nach einem AND aus vielen
Termen also sogar eher schneller als eine Suche nach
nur einem Term!

Ich denke aber, eine DB wird auch bei 100 Seiten
schon schneller sein, oder?

Nicht spürbar. Bei 10000 Dateien schon eher.

Viele Grüße
      Michael

[Andreas]

Hallo!

Auf diese Weise sind insbesondere auch beliebige
Phrasen auffindbar, nicht nur Worte.
Und diese Anforderung hat lange Zeit (Jahre ...)
verhindert, einen indexbasierten Ansatz ernsthaft
in Erwägung zu ziehen.

Aber wieso? Hab jetzt nicht mehr genau Dein Break-Even Beispel im Kopf, aber selbst wenn jemand bei einer großen Menge Datenmenge 3 oder 4 Wörter eingibt, könnte man doch halt 3-4 mal via Index suchen, sollte immer noch einige schneller sein, als normal!
Vor allem wenn man noch ein paar WHERE Beschränkungen einbaut, wenn _alle_ Begriffe gefunden werden sollen geht es nochmal schneller, oder?

(Inzwischen wird aber an
einem solchen gearbeitet, wobei Phrasen dadurch
realisiert werden sollen, daß zuerst ein AND über
alle darin enthaltenen Worte via Index und dann
für alle so bestimmten Treffer eine Volltextsuche
nach der exakten Phrase gemacht wird, um die echten
von den unechten Treffern zu trennen.)

So a lá Google & Co.? Nicht schlecht!

Grüße
Andreas

[Michael Schröpl]

Hallo!

Auf diese Weise sind insbesondere auch beliebige
Phrasen auffindbar, nicht nur W.
Und diese Anforderung hat lange Zeit (Jahre ...)
verhindert, einen indexbasierten Ansatz ernsthaft
in Erwägung zu ziehen.
Aber wieso? Hab jetzt nicht mehr genau Dein Break-
Even Beispel im Kopf, aber selbst wenn jemand bei
einer großen Menge Datenmenge 3 oder 4 Wörter
eingibt, könnte man doch halt 3-4 mal via Index
suchen, sollte immer noch einige schneller sein, als
normal!

Was im Index nicht gespeichert ist, das findest Du
einfach nicht. UNd wenn der Index auf Worten basiert,
kannst Du damit alleine keine Phrasen finden.

Viele Grüße
      Michael

[Michael Schröpl]

Hi Andreas,

zuerst mal mein Credo zu dieser Frage:

Wie macht man sowas vielleicht etwas performanter?

Alles, was sie einmal erledigen läßt, sollte man nicht immer wieder tun
(vor allem nicht, während der Besucher darauf warten muß).

Aber dabei sehe ich folgende Probleme:

• bei größeren Präsenzen wird das sehr(!) lange dauern

Definiere "groß".

Und bedenke, daß ein einfacher Algorithmus (sequentielles Suchen) Lauf-
zeiten direkt proportional zur durchsuchten Datenmenge haben wird,
während ein Algorithmus unter Verwendung einer Baumstruktur (Daten-
bank-Index etc.) auf logarithmische Suchzeiten (mal Overhead zur Ver-
waltung dieser Datenstruktur) kommen wird. Was von beidem für Dein
Szenario wie gut ist, hängt von Deiner Datenmenge ab.

Kleines Beispiel:
Der zusätzliche Aufwand für die Verwaltung des Indexbaums sei Faktor 7.
(Das ist eine "religiöse" Zahl, aus dem Oracle-Performance-Handbuch,
aber eine gute Hausnummer für Anschätzungen.)
Das Durchsuchen von <n> Datensätzen kostet

• bei sequentieller Suche <n> Vergleiche (da Du alle Datensätze lesen
    mußt)
• bei rekursiver Suche 7 * log2(<n>) Vergleiche (weil Du innerhalb
    des sortierten Baums entsprechend absteigst und die Menge der zu
    betrachtenden Datensätze bei jedem Verleich halbierst.

Jetzt setzen wir mal konkrete Werte für <n> ein:

<n>    7 * log2(<n>)
       2         7
       4        14
       8        21
      16        28
      32        35
                          break-even
      64        42
     128        49
     256        56
     512        63
                          Faktor  10 für rekursives Verfahren
    1024        70
    2048        77
    4096        84
    8192        91
                          Faktor 100 für rekursives Verfahren

Du siehst: Schon bei 10000 Datensätzen wird das rekursive Verfahren um
Faktor 100 schneller sein. Bei wenigen hundert Datensätzen lohnt sich
der (erheblich höhere) Implementierungsaufwand noch nicht, aber bei
fünf Stellen würde ich eine solche Lösung immer in Betracht ziehen.
(Das Self-Portal hat sechsstellig viele Postings in seinem Archiv, ver-
wendet aber trotzdem das lineare Verfahren, weil die Aufgabenstellung
zusätzliche Anforderungen enthält, welche die Implementierung einer
rekursiv arbeitenden Lösung erschweren - da ist der magische Faktor
7 nicht mehr so ohne weiteres verwendbar.)

• ich finde auch html-Tags

Nicht, wenn Du sie in einem Vorverarbeitungsschritt bereits entfernst.
Bei statischen Seiten ist das kein Problem; bei dynamischen (PHP) ver-
stehe ich den Sinn der Durchsuchbarkeit nicht so richtig.
Aber wenn der dynamische Anteil sich auf technische Aspekte (z. B.
"last changed" etc.) der Seite beschränkt statt auf Inhalte, ließe sich
eine PHP-Seite wie eine HTML-Seite behandeln.

• bei .php Seiten finde ich auch den ganzen php-Code.

Wenn Du HTML-Tags herausparsen kannst, dann kannst Du auch PHP-Code
herausparsen. Ein Problem hast Du nur, wenn Du das _Ergebnis_ der
Auflösung dieses PHP-Codes durchsuchbar brauchst - dann aber sollte
Deine Suchmaschine besser direkt auf die Datenquelle zugreifen, auf
die auch PHP zugreift, um diese dynamischen Inhalte zu erstellen.

Wahrscheinlich kann man die letzten beiden Punkte durch einen guten
regulären Ausdruck ausklammern,

HTML-Tags bilden rekursive Klammerstrukturen, um sie wirklich zu
verstehen, reichen reguläre Ausdrücke nicht aus - dafür bräuchtest
Du das Äquivalent eines Keller-Automaten (bekannter auch als "stack"),
um so etwas zu parsen.

Du kannst HTML-Tags natürlich einfach herauslöschen - das ist leichter.
Du würdest dabei aber darauf verzichten, die Dir in diesen Tags reich-
lich ausgedrückte Semantik Deiner Dokumente zunutze zu machen.
Für die Qualität eines Treffers ist es es doch ein Unterschied, ob der
gesuchte Begriff innerhalb eines <p>, eines <h1> oder gar eines <title>
bzw. <meta> auftritt.

aber der erste erscheint mir sehr schwerwiegend.

Eben. Deshalb: Lege Dir eine auf Suchzugriffe optimierte Datenstruktur
an und pflege diese (automatisch) bei jeder Änderung der Quelldokumente.
Redundanz ist zwar in vielen Fällen "böse", aber in diesem Fall der
Schlüssel zu Performance.

Zum regulären Ausdruck, sowas wie />(.*?)</  würde das nicht schon
reichen?

Damit würdest Du _einen_ Teil des Dokuments finden, der irgendwo zwi-
schen zwei Tags steht.
Nicht aber alle - dafür müßtest Du mindestens mit einer Schleife durch
das Dokument laufen.

Viele Grüße
      Michael

[Andreas]

Hallo!

Wie macht man sowas vielleicht etwas performanter?

Alles, was sie einmal erledigen läßt, sollte man nicht immer wieder tun
(vor allem nicht, während der Besucher darauf warten muß).

Ich denke, das es am einfachsten ist, täglich per Cronjob ein Script laugen zu lassen, welches die Arbeit erledigt.

Definiere "groß".

Wahrscheinlich nicht über 100, da bei größeren Seiten wohl mehr Inhalte aus einer DB kommen, aber mir geht es halt darum, was ist wenn das halt alles in statischen html Seiten oder statischen php-Seiten steht. Als statische PHP-Seite betrachte ich Seiten, wo nur ein Counter oder Änderungsdatum.... steht, keine dynamich erzeugten Daten - also außer counter...

Und bedenke, daß ein einfacher Algorithmus (sequentielles Suchen) Lauf-
zeiten direkt proportional zur durchsuchten Datenmenge haben wird,
während ein Algorithmus unter Verwendung einer Baumstruktur (Daten-
bank-Index etc.) auf logarithmische Suchzeiten (mal Overhead zur Ver-
waltung dieser Datenstruktur) kommen wird. Was von beidem für Dein
Szenario wie gut ist, hängt von Deiner Datenmenge ab.

Wie gesagt, nicht ganz so viel. Also wie ich das sehe habe ich entweder die Möglichkeit alle Daten in eine index-Datei zu schreiben, das ergäbe eine sequentielle Suche, oder alles in eine Datenbank zu schreiben, das ergäbe bei gut gewähltem Index eine rekursiver Suche, oder?

Kleines Beispiel:
Der zusätzliche Aufwand für die Verwaltung des Indexbaums sei Faktor 7.

Das ist ja egal wenn der User davon nichts mitbekommt, oder? Außerdem kann das mysql z.B. ja automatisch.

Faktor 100 schneller sein. Bei wenigen hundert Datensätzen lohnt sich
der (erheblich höhere) Implementierungsaufwand noch nicht

Aber wo ist da der höhere Aufwand? Finde es fast leichter die Daten in eine DB zu schreiben, als mir selber eine Struktur für eine index-Datei zu überlegene, die ich danach vergleichbar einfach durchsuchen kann!

• ich finde auch html-Tags

Nicht, wenn Du sie in einem Vorverarbeitungsschritt bereits entfernst.
Bei statischen Seiten ist das kein Problem; bei dynamischen (PHP) ver-
stehe ich den Sinn der Durchsuchbarkeit nicht so richtig.
Aber wenn der dynamische Anteil sich auf technische Aspekte (z. B.
"last changed" etc.) der Seite beschränkt statt auf Inhalte, ließe sich
eine PHP-Seite wie eine HTML-Seite behandeln.

Das meinte ich. Wie Stefan richtig sagte gibt es ja die PHP-Funktion strip-tags(), die alles zwischen allen <> entfernt, damit auch  zwischen <??>, hatte ich so gar nicht dran gedacht, sorry ;-)

Du kannst HTML-Tags natürlich einfach herauslöschen - das ist leichter.
Du würdest dabei aber darauf verzichten, die Dir in diesen Tags reich-
lich ausgedrückte Semantik Deiner Dokumente zunutze zu machen.
Für die Qualität eines Treffers ist es es doch ein Unterschied, ob der
gesuchte Begriff innerhalb eines <p>, eines <h1> oder gar eines <title>
bzw. <meta> auftritt.

Da hast Du Recht, auf alle Fälle die meta-Angaben, wenn ich die durchgehend mache, wäre das nicht schlecht. Ich stelle mir das so vor, ich mache eine DB-Tabelle die wie folgt aussieht:

ID
URL
title
alle <h1>
meta-keywords
meta-description
body(nach strip-tags())
timestamp

Jetzt über alle Spalten außer ID, URL und timestamp einen Fulltext-Index, und dann in allen diesen Spalten nach einem Suchbegriff suchen.

MySQL gibt dann ja sogar selbst die Relevanz des Begriffes zurück, nur wahrscheinlich nicht unter Beachtung der von Dir angesprochenen und damit beabsichtigten Semantik. Aber um das zu bekommen bräuchte ich ja ein Abfrage pro Spalte, und müßte das danach noch auswerten, vor allem habe ich dann keine Ahnung was ich wie gewichten soll, im Verhältnis jetzt zur mySQL Relevanz!

aber der erste erscheint mir sehr schwerwiegend.

Eben. Deshalb: Lege Dir eine auf Suchzugriffe optimierte Datenstruktur
an und pflege diese (automatisch) bei jeder Änderung der Quelldokumente.

Bei jeder Änderung ist nicht so einfach, das müßte ich ja immer manuell machen, oder halt täglich per Cronjob immer gucken welche Dateien sich geändet haben und diese Datensätze aktualieren, das wird das sinnvollste und vor allem einfachste sein. Zur Not(bei wichtigen Änderungen) kann man das dann immer noch von Hand anstoßen.

Redundanz ist zwar in vielen Fällen "böse", aber in diesem Fall der
Schlüssel zu Performance.

Ich hoffe Du meintest Das so ähnlich wie ich jetzt geschrieben habe ;-)

Zum regulären Ausdruck, sowas wie />(.*?)</  würde das nicht schon
reichen?

Damit würdest Du _einen_ Teil des Dokuments finden, der irgendwo zwi-
schen zwei Tags steht.
Nicht aber alle - dafür müßtest Du mindestens mit einer Schleife durch
das Dokument laufen.

Normalerweise würde in PERL glaube ich ein /g reichen, das geht leider nicht in PHP, dafür läuft obiger Ausdruck verwendet mit preg_match() z.B. automatisch komplett durch und findet so viele Treffer wie vorhanden sind. Wobei ich stattdessen wohl lieber strip_tags() verwende, aber nur am Ende für den Body-Bereich, vorher  brauche ich ja noch die Möglichkeit alles zwischen <meta...> zu extrahieren, mein Versuch:

<?
$html; //Seitenquelltext

$title_array = preg_grep("/<title>(.*?)</title>/",$html);
$meta-desc_array = preg_grep("/<meta name="description" content="(.*?)">/",$html);
$meta-keyw_array = preg_grep("/<meta name="keywords" content="(.*?)">/",$html);
$h1_array = preg_grep("/<h1>(.*?)</h1>/",$html);
$b_array = preg_grep("/<b>(.*?)</b>/",$html);

$title = $title_array[0];
$meta-description = $meta-desc_array[0];
$meta-keywords = $meta-keyw_array[0];
$h1 = implode(" ",$h1_array );
$b = implode(" ",$b_array );
$body = strip_tags($html);
?>

So würde ich jedes Seite halt "zerpflücken", dadurch das die title, meta... Angaben absichtlich im body ein 2. Mal vorkommen, erhalten diese ja automatisch etwas mehr Relevanz bei der MySQL Fulltext-Search.

Was sagst Du dazu?

Schonmal vielen Dank für diese hilfreiche Antwort und

viele Grüße
Andreas

[Michael Schröpl]

Hi Andreas,

Ich denke, das es am einfachsten ist, täglich
per Cronjob ein Script laugen zu lassen, welches
die Arbeit erledigt.

Das ist eine Möglichkeit.

Du kannst auch jeweils ein Skript über die Dokumente
laufen lassen, deren Inhalt sich gerade bzw. seit
einem definierten Zeitpunkt geändert hat.

Definiere "groß".
Wahrscheinlich nicht über 100,

Dann hast Du bei der Verwendung des "trivialen"
Ansatzes keine Performance-Probleme zu befürchten.
(Dies wird weiter unten noch von Bedeutung sein.)

Wie gesagt, nicht ganz so viel. Also wie ich das
sehe habe ich entweder die Möglichkeit alle Daten
in eine index-Datei zu schreiben, das ergäbe eine
sequentielle Suche, oder alles in eine Datenbank
zu schreiben, das ergäbe bei gut gewähltem Index
eine rekursiver Suche, oder?

Nicht die Datenbank macht die rekursive Suche aus,
sondern die Art der Abfrage.

Wenn Du ein Dokument lediglich so speicherst, daß
Du dessen gesamten Text als ein Feld der Datenbank
darstellst, hast Du gegenüber der Textdatei nichts
gewonnen.
Stellst Du das Dokument aber so dar, daß Du jedes
einzelne Wort in dieser Tabelle speicherst, dann
kannst Du Worte über den entsprechenden Index in
logarithmischer Zeit finden. Das bedeutet aller-
dings erst mal, einen Wort-Indexer schreiben zu
müssen (oder den zu verwenden, den die Datenbank
schon hat, etwa mySQL-FULLTEXT), und es bedeutet
auch, auf eine Phrasensuche (mehrere Worte im di-
rekten Kontext) verzichten zu müssen.

Der zusätzliche Aufwand für die Verwaltung des
Indexbaums sei Faktor 7.
Das ist ja egal wenn der User davon nichts
mitbekommt, oder?

Das _bekommt_ der Benutzer mit.
Es kann allerdings sein, daß dieser Faktor 7 deshalb
nicht auffällt, weil er nur bei Datenmengen stört,
die so klein sind, daß der Grundaufwand (CGI-Anbindung
etc.) höher ist als die eigentliche Suche.

Außerdem kann das mysql z.B. ja automatisch.

Das ändert nichts daran, daß es die Laufzeit erhöht.
Indexadressierung ist nicht kostenlos - es gibt einen
breakeven-Punkt, und den wollte ich Dir vorführen.

Faktor 100 schneller sein. Bei wenigen hundert
Datensätzen lohnt sich der (erheblich höhere)
Implementierungsaufwand noch nicht
Aber wo ist da der höhere Aufwand? Finde es fast
leichter die Daten in eine DB zu schreiben, als
mir selber eine Struktur für eine index-Datei zu
überlegene, die ich danach vergleichbar einfach
durchsuchen kann!

Du mußt Dir die Struktur in jedem Fall überlegen -
und Du tust es weiter unten ja auch.

Ob das Ergebnis dann eine CSV-Daten oder eine SQL-
Tabelle ist, das ist relativ egal - aber ob Du
einfach eine Datei aufmachst oder eine Datenbank-
schnittstelle per SQL ansteuern mußt, das ist für
jemand, der in SQL nicht fit ist, sehr wohl ein
Unterschied.

schlecht. Ich stelle mir das so vor, ich mache
eine DB-Tabelle die wie folgt aussieht:
ID
URL
title
alle <h1>
meta-keywords
meta-description
body(nach strip-tags())
timestamp

Genau das meinte ich. Zu diesem Zeitpunkt ist die
Realisierungsform (Tabelle oder Datei) noch völlig
offen - es geht erst einmal darum, die Semantik
Deiner Suchmaschine zu definieren: Welche Abfragen
sind überhaupt möglich, und welche Informationen
stehen für die Definition einer Bewertungsfunktion
zur Sortierung der Treffer zur Verfügung.
Hier machst Du Deine Datenmodellierung.

Jetzt über alle Spalten außer ID, URL und timestamp
einen Fulltext-Index, und dann in allen diesen
Spalten nach einem Suchbegriff suchen.

Für Wortsuche prima ... für Phrasensuche nicht.
Das ist ein wesentlicher Teil der Funktionalität,
sich für bzw. gegen Phrasensuche zu entscheiden.

MySQL gibt dann ja sogar selbst die Relevanz des
Begriffes zurück, nur wahrscheinlich nicht unter
Beachtung der von Dir angesprochenen und damit
beabsichtigten Semantik.

Die kannst Du aber als Gewicht drauf multiplizieren.

Aber um das zu bekommen
bräuchte ich ja ein Abfrage pro Spalte, und müßte
das danach noch auswerten, vor allem habe ich dann
keine Ahnung was ich wie gewichten soll, im
Verhältnis jetzt zur mySQL Relevanz!

Das ist in der Tat ein Problem. Aber Du mußt ja nicht
die Relevanzfunktion von mySQL verwenden. Du mußt auch
nicht deren FULLTEXT verwenden - ein Wort-Indexer ist
schnell geschrieben, und der könnte die Relevanz eines
Wortes für ein Dokument unter Berücksichtigung _aller_
Spalten bereits vor dem Einfügen dieses Wortes in die
Datenbank berechnen. Du hättest also eine Tabelle mit

CREATE TABLE fulltext AS
  search_word      <irgend ein char-Typ>
  search_quality   <integer>
  document_id      <primary key der anderen Tabelle>

und würdest suchen mit

SELECT document_id, search_quality
   FROM fulltext
  WHERE search_word = <suchbegriff>
  ORDER BY search_quality DESC;

oder so ähnlich.

Redundanz ist zwar in vielen Fällen "böse", aber
in diesem Fall der Schlüssel zu Performance.
Ich hoffe Du meintest Das so ähnlich wie ich jetzt
geschrieben habe ;-)

Ich denke schon. Die Such-Datenbank enthält natürlich
dieselben Inhalte wie die eigentlichen Dokumente,
aber eben auf eine andere Art des Zugriffs optimiert.

Viele Grüße
      Michael

[Andreas]

Hallo Michael!

Vorab schonmal Danke für die ausführlichen Antworten, damit hilfst Du mir sehr, bzw. hast mir in der Vergangenheit schon sehr geholfen! Vielen Dank!

Das _bekommt_ der Benutzer mit.
Es kann allerdings sein, daß dieser Faktor 7 deshalb
nicht auffällt, weil er nur bei Datenmengen stört,
die so klein sind, daß der Grundaufwand (CGI-Anbindung
etc.) höher ist als die eigentliche Suche.

Ich habe im Prinzip 2 Möglichkeiten, wenn ich Phrasensuche ermöglichen will:
1. Mache ich das mit einer eigenen Index-Tabelle
2. oder ich mache einfach so viele einzelne Abfragen nacheinander wie Worte in der Suche vorkommen über die besagten Fulltext-Index Spalten. Das hört sich zwar nicht wirklich vernünftig an, aber wie viele Leute suchen nach mehr als 3,4 Wörtern?
Dafür könnte ich mir die Index-Tabelle sparen, die ja sehr schnell eine Mio Datensätze und mehr haben würde, ob das so gut wäre? ich denke der Fulltext-Index in mysql dürfte das schneller und sparsamer machen, oder?

Ob das Ergebnis dann eine CSV-Daten oder eine SQL-
Tabelle ist, das ist relativ egal - aber ob Du
einfach eine Datei aufmachst oder eine Datenbank-
schnittstelle per SQL ansteuern mußt, das ist für
jemand, der in SQL nicht fit ist, sehr wohl ein
Unterschied.

Ich meinte halt, das mit ein MySQL Daten schneller durchsuchen kann als PHP, da dafür optimiert!

Das ist in der Tat ein Problem. Aber Du mußt ja nicht
die Relevanzfunktion von mySQL verwenden. Du mußt auch
nicht deren FULLTEXT verwenden - ein Wort-Indexer ist
schnell geschrieben, und der könnte die Relevanz eines
Wortes für ein Dokument unter Berücksichtigung _aller_
Spalten bereits vor dem Einfügen dieses Wortes in die
Datenbank berechnen. Du hättest also eine Tabelle mit

CREATE TABLE fulltext AS
  search_word      <irgend ein char-Typ>
  search_quality   <integer>
  document_id      <primary key der anderen Tabelle>

und würdest suchen mit

SELECT document_id, search_quality
   FROM fulltext
  WHERE search_word = <suchbegriff>
  ORDER BY search_quality DESC;

oder so ähnlich.

Sehr interessant - und so einfach, da wäre ich nie drauf gekommen, nur wie soll ich das erstellen? Wenn ich tatsächlich 1.000 Seiten mit je 10.000 Worten gleichzeitig indizieren will, mal abgesehen vom php-timeout, soll ich in einer schleife 10 Mio Inserts starten? Wie soll das gehn? Womit? oder mit mysql < file.sql einlesen?

Außerdem ´habe ich das problem, dqas ich wahrscheinlich 80% der Wörter gar nicht brauche, da danach eh nicht gesucht wird. Nur leider kann man das nur sehr schwer automatisiert machen, höchtens ein paar die ganz oft vorkommen in einen arra schreiben und immer prüfen ob if(in_array("Wort")) oder sowas. Wäre aber wohl eher ein Tropfen auf den heißen Stein oder?

Grüße
Andreas

[Michael Schröpl]

Hi Andreas,

Ich habe im Prinzip 2 Möglichkeiten, wenn ich
Phrasensuche ermöglichen will:

1. Mache ich das mit einer eigenen Index-Tabelle

das schaffst Du nicht. Ein Text enthält eine Anzahl
von Worten, die proportional zur Länge des Textes
ist (egal, ob Du diese Länge in Worten oder Bytes
oder ... mißt).
Aber die Anzahl der darin enthaltenen Phrasen nimmt
exponentiell mit der Länge des Textes zu.

2. oder ich mache einfach so viele einzelne Abfragen
   nacheinander wie Worte in der Suche vorkommen über
   die besagten Fulltext-Index Spalten.

Das reicht noch nicht. Damit findest Du zwar Texte,
in denen alle Worte vorkommen, die auch in der Phrase
vorkommen - aber sie müssen nicht in genau der
Anordnung vorkommen, wie sie in der Phrase stehen.

Das hört sich zwar nicht wirklich vernünftig an,
aber wie viele Leute suchen nach mehr als 3,4
Wörtern?

Es ist schlimm genug, wenn sie nach 4 Worten suchen.
Du bekommst dann nämlich vier Treffermengen, die Du
erst mal zwischenspeichern und schneiden mußt ...
und jede dieser Mengen kann tausende von Elementen
enthalten, obwohl am Ende nicht ein einziger echter
Treffer dabei heraus kommt.

Dafür könnte ich mir die Index-Tabelle sparen, die
ja sehr schnell eine Mio Datensätze und mehr haben
würde, ob das so gut wäre?

Wie möchtest Du ohne die Indextabelle die Suchvorgänge
schnell bekommen?

ich denke der Fulltext-Index in mysql dürfte das
schneller und sparsamer machen, oder?

FULLTEXT _ist_ eine Indextabelle (über bestimmte Arten
von Worten des Textes, die nur bestimmte Zeichen ent-
halten und eine bestimmte Mindestlänge aufweisen - ich
habe genau diese beiden Stellen im mySQL-Quelltext
ändern und das RDBMS neu übersetzen müssen, um den
Begriff "Wort" auf meine eigene Aufgabenstellung an-
zupassen).

Tabelle ist, das ist relativ egal - aber ob Du
einfach eine Datei aufmachst oder eine Datenbank-
schnittstelle per SQL ansteuern mußt, das ist für
jemand, der in SQL nicht fit ist, sehr wohl ein
Unterschied.
Ich meinte halt, das mit ein MySQL Daten schneller
durchsuchen kann als PHP, da dafür optimiert!

Nein. Nicht mySQL ist schnell, sondern eine Daten-
struktur in Kombination mit einem Algorithmus. Die
Realisierung kann in jeder Sprache erfolgen; für mySQL
spricht lediglich, daß _bestimmte_ Realisierungen
bereits fertig vorhanden sind. Wenn Deine Aufgaben-
stellung sich mit mySQL elegant lösen läßt, mußt Du
üblicherweise weniger eigenen Code schreiben als mit
PHP - auch weil SQL abstrakter ist als PHP und damit
üblicherweise kompakter.

Sehr interessant - und so einfach, da wäre ich nie
drauf gekommen, nur wie soll ich das erstellen?

Mit einem Programm. ;-)

Wenn ich tatsächlich 1.000 Seiten mit je 10.000
Worten gleichzeitig

Nacheinander.

indizieren will, mal abgesehen vom php-timeout,
soll ich in einer schleife 10 Mio Inserts starten?

Kommt jedes Wort denn nur genau einmal pro Dokument
vor? Andernfalls sind es viel weniger INSERTs.

Wie soll das gehn? Womit?

Wie gesagt: Mit einem Programm, das in einer Schleife
über jedes Deiner Dokumente läuft, dieses in Worte
zerhackt, deren relative Häufigkeit bestimmt und die
gesamte Qualitätsbestimmung des Wortes (Relevant) für
dieses Dokument bestimmt und dann viele einzelne
INSERTs durchführt.
In bestimmten SQL-APIs kann man INSERTs übrigens
blockweise durchführen - es ist performanter, ein
paar tausend Zeilen auf einmal einzufügen, weil dann
nicht so viele API-Zugriffe erfolgen (die kosten
reichlich Overhead).

Außerdem ´habe ich das problem, dqas ich
wahrscheinlich 80% der Wörter gar nicht brauche,
da danach eh nicht gesucht wird.

Dann mach Dir eine Stopwortliste. mySQL-FULLTEXT hat
so etwas.

Nur leider kann man das nur sehr schwer
automatisiert machen, höchtens ein paar die ganz
oft vorkommen in einen arra schreiben und immer
prüfen ob if(in_array("Wort")) oder sowas.

Gar nicht erst in den Index schreiben.
(Die Liste in mySQL ist etwa 500 Worte lang.)

Wäre aber wohl eher ein Tropfen auf den heißen
Stein oder?

Wenn diese Worte sehr oft vorkommen (und sehr wenig
aussagen, z. B. "ist" oder "hat"), kann das durchaus
ziemlich viel sparen. Und solange Du keine Phrasen
finden willst, in denen so ein Wort enthalten ist ...

Viele Grüße
      Michael