nicht angemeldet
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