(PERL)Suchmaschienen-Stuktur

[Andres Freund]

Hi

Ich will eine Suchmaschiene programmieren die ich für verschieden Webseiten benutzen kann. Daher habe ich die Threads von (hauptsächlich) Michael und Andreas mit großem Interesse verfolgt. Ich hatte damals auch schon eine kleine geschrieben, die aber eher eine Interimslösung darstellen sollte, bis ich die Zeit finde eine besssere zu schreiben. Nun habe ich, zumindest zu Teil, diese Zeit.
Da ich aber bisher in diesen Themengebieten noch icht alzugroße Erfahrungen gewinnenkonnte, dieser Thread.

Technische Mittel zur Umsetztung (eigentlich irellevant, oder?):
-Perl
-Postgre oder Mysql je nach Einsatzort

Damit die Suche auch bei größeren Datenmengen performant bleibt habe ich mir ungefähr eine derartige Struktur vorgestellt:

1: In der Db werden immer nur die einzelnen Worte des zu durchsuchenden Dokumentes eingetragen. Zusätzlich wird ein Ziel angegeben, in dem sich das Dokument befindet.

2: es gibt jeweils eine Tabelle für Wortanfänge mit aa, ab, ac,...zz und eine Tabelle für Sonderzeichen (Ja, ich weiß, dass das viele Tabellen werden)

3: es werden nur Wörter mit einer Mindestlänge von drei Buchstaben in den Suchtabellen gespeichert. Zusätlich werden Wörter wie 'die', 'der', 'und' usw. rausgefiltert. Dabei wird z.B. eine 1 bei der Spalte praefix eigetragen.

4: um eine präfix-Suche zu ermöglichen, wird jedes Wort mit mehr als drei Buchstaben, von vorne gekürzt, dh. in der DB steht dann z.B. Hallo, allo und llo.

5: In der Suchmaschiene steht statt Sonderzeichen wie ä immer ae usw, um die verschiedenen Schreibweisen zu berücksichtigen.

6: Die unvollständigen "präfix"-Einträge werden in einer zusätlichen Tabelle gekenzeichnet, damit man sie später trennen kann.

7: Weitere Spalten enthalten, falls vorhanden und notwendig, zusätliche Informationen wie Datum, kategorie, autor......

8: Um ein ranking zu erhalten wird zuerst nach exakt dem Suchbegriff gesucht, später auch nach solche mit einem Anhängsel (Postfix mittels %) dann auch indem jetzt auch nach Wörtern gesucht wird bei denen eine 1 bei postfix steht, auch nach präfixen.

9: in der WHERE Klausel wird zuerst nach (falls vorhanden) Kategorie, autor, erstellungsdatum usw. gesucht, um die Geschwindigkeit zu erhöhen.

10: Um die Wortnmenge nicht ganz so hoch werden zu lassen werden begriffe wie 'und', 'die', Zahlen generell usw nicht eingetragen.

Meine Fragen:

a: Habt ihr Verbesserungsvorschläge, Kritik, Fragen zur generellen Struktur?

b: Zu 7, oder sollten diese ganzen Informationen in eine zusätzliche Tabelle? Wäre zwar sinvoll, aber machen die zusätzlichen Kosten für die Abfragen nicht den Vorteil zunichte?

c: Zu 10, oder sollten diese Wörter nur mit einem anderem Wort zusammen suchbar sein? Oder wie z.B. bei Google nur mit einem '+' davor?

d: Wie soll ich suchen wenn mehr als ein Suchbegriff eingegeben wird? Soll ich suchen welche das gleich Ziel haben, und diese nach dem zweiten Suchbegriffdurchsuchen? Oder das Ziel des ersten Suchbegriffes über Perl öffnen und mittels Regexen durchsuchen?

e: Macht es Sinn die Reihenfolge der where Klausel nach Länge der der Suchbegriffe zu sortieren? So dass lange, da sie vermutlich seltener vorhanden sind, zuerst gesucht werden?

mfg  und vielen, vielen Dank Andres Freund

PS: Ich hoffe es sind nicht alzuviele Fragen....und dass ich nicht das wichtigste vergessen habe.

[Rolf Rost]

hi,

Vorschlag: schau dir mal das PERL Modul Text::Query an. Das ist mächtig. Es wird z.b. auf

http://perlbase.xwolf.de/cgi-bin/perlbase.cgi zum Durchsuchen von Dokumenten in einer Berkley Datenbank (DB_File) eingesetzt.

Gruß, Rolf

[Andres Freund]

Hi,

Vorschlag: schau dir mal das PERL Modul Text::Query an. Das ist mächtig.

Ein sehr schönes Modul, aber ich bezweifle, dass es bei 200-500MB Daten noch sonderlich schnell ist. Es "kommen und gehen" auch täglich Daten hinzu. Daher dachte ich, dass etwas derartiges nicht schnell ist genug sein wird, da ja die umfangreichen Funktionen es wahrscheinlich verlangsamen werden.
Da es in einem unter anderem in einem Intranet verwendet werden soll, sollte es schon schnell sein.
Ich werde es mir aber trotzdem mal zu Gemüte führen ;-).

mfg Andres Freund

[Rolf Rost]

Hi,

Vorschlag: schau dir mal das PERL Modul Text::Query an. Das ist mächtig.
Ein sehr schönes Modul, aber ich bezweifle, dass es bei 200-500MB Daten noch sonderlich schnell ist.

Das hat mit dem Modul selbst überhaupt nichts zu tun. Denn es kommt darauf an _wie_ du die Suche organisierst. Wenn _ein_ CGI Prozess 500MB in den Speicher lädt haben dein Provider und der Besucher sicher keine Freude dran ;-)

--Rolf

[Andres Freund]

Hi,

Das hat mit dem Modul selbst überhaupt nichts zu tun. Denn es kommt darauf an _wie_ du die Suche organisierst. Wenn _ein_ CGI Prozess 500MB in den Speicher lädt haben dein Provider und der Besucher sicher keine Freude dran ;-)

Sorry, ich habe das ganze ein wenig durcheinandergebracht :-(. Ich habe sicherlich nicht vor den ganzen Text auf einmal in den Speicher zu laden *g*, oder etwa doch, das wäre dann doch sicher schnell *fg*.
Ich hatte das text::query Modul etwas mit einem anderen Modul verwechselt, tut mir leid.

mfg Andres Freund <- der wiedereinmal bemerkt, wie nützlich es ist Beschreibungen (besonders den Titel *grrr*)im CPAN genau anzuschauen bevor man postet.

[Michael Schröpl]

Hi Andres,

Technische Mittel zur Umsetztung (eigentlich irellevant, oder?):
-Postgre oder Mysql je nach Einsatzort

wenn Du Deine Tabellen selbst bauen willst (also kein mySQL-FULLTEXT etc.), sollte das egal sein.

2: es gibt jeweils eine Tabelle für Wortanfänge mit aa, ab, ac,...zz und eine Tabelle für Sonderzeichen (Ja, ich weiß, dass das viele Tabellen werden)

Ich verstehe, daß Du die jeweilige Datenmenge klein halten willst; aber wenn Du über die Worte einen Indexbaum legst, dann macht die Datenbank das von ganz alleine. Ich vermute, Du wirst einen sehr kleinen Performance-Gewinn erzielen, aber die Wartung Deiner Datenstrukturen nicht gerade vereinfachen.
Wo eine solche Idee gut funktionieren könnte, das wäre ein Ansatz, der die Suchmaschine auf mehrere Rechner verteilen würde (bei seeeehr großen Datenmengen - Deine 500 MB reichen dafür noch nicht).

4: um eine präfix-Suche zu ermöglichen, wird jedes Wort mit mehr als drei Buchstaben, von vorne gekürzt, dh. in der DB steht dann z.B. Hallo, allo und llo.

Du meinst "Substring" statt "Präfix", ja? (Präfix-Suche auf Postfixe ist Substring auf Worte.)

5: In der Suchmaschiene steht statt Sonderzeichen wie ä immer ae usw, um die verschiedenen Schreibweisen zu berücksichtigen.

Hm. Warum nicht das Wort mit Umlaut zweimal indexen? So oft kommt das ja nicht vor.

7: Weitere Spalten enthalten, falls vorhanden und notwendig, zusätliche Informationen wie Datum, kategorie, autor......

Hm. Deine nachfolgende Frage zeigt Dir das Problem ja selber: Konsistenz durch redundanzfreie Datenhaltung.

8: Um ein ranking zu erhalten wird zuerst nach exakt dem Suchbegriff gesucht, später auch nach solche mit einem Anhängsel (Postfix mittels %) dann auch indem jetzt auch nach Wörtern gesucht wird bei denen eine 1 bei postfix steht, auch nach präfixen.

Dazu kann ich nur "spannend" sagen. Ranking ist Magie - und sehr datenabhängig, fürchte ich.

9: in der WHERE Klausel wird zuerst nach (falls vorhanden) Kategorie, autor, erstellungsdatum usw. gesucht, um die Geschwindigkeit zu erhöhen.

Das kannst Du vergessen. Die Geschwindigkeit hängt nicht von der Reihenfolge der WHERE-Terme ab, sondern vor allem von der Verwendung verfügbarer Indexe. (Und täte sie es, dann würde jeder ordentliche Query Optimizer die Terme besser sortieren können als Du selbst.)

10: Um die Wortnmenge nicht ganz so hoch werden zu lassen werden begriffe wie 'und', 'die', Zahlen generell usw nicht eingetragen.

Die erzielbare Einsparung durch solche Maßnahmen solltest Du auch nicht überschätzen. Laß es 10-15% sein, das wäre schon recht ordentlich. Und da Du dann noch den Logarithmus auf die Änderung anwenden mußt, ist der erzielbare Geschwindigkeitsgewinn kaum noch meßbar. (Beim Platzbedarf schlagen diese Prozente hingegen voll durch.)

a: Habt ihr Verbesserungsvorschläge, Kritik, Fragen zur generellen Struktur?

Ich glaube nicht an das Prinzip mit den vielen Tabellen - es sei denn, bei Verteilung auf viele Maschinen. Aber auch dann würde man eine besser streuende Hash-Funktion nehmen und nicht die extrem ungleich verteilten Anfangs-Buchstabenpaare.
Ich habe allerdings selbst ein vergleichbares Prinzip implementiert - allerdings nicht mit lexikographischer Unterteilung, sondern mit inhaltlicher. Also beispielsweise eine Tabelle aller Nachrichten von heute, eine für gestern, eine für diese Woche, eine für diesen Monat etc. - weil es Erfahrungswerte für die Verteilung der Abfragen in dieser Dimension gibt. (Und vor allem, weil ich über diese Teilmengen _auch_ full table scans brauche.)

b: Zu 7, oder sollten diese ganzen Informationen in eine zusätzliche Tabelle? Wäre zwar sinvoll, aber machen die zusätzlichen Kosten für die Abfragen nicht den Vorteil zunichte?

Tja, das ist ein trade-off zwischen Performance und Wartbarkeit. Wenn Dein Tabellensystem nicht der Primärdatenträger ist, sondern aus diesem lediglich wie ein Cache geladen wird, dann kann das Sinn machen.

c: Zu 10, oder sollten diese Wörter nur mit einem anderem Wort zusammen suchbar sein? Oder wie z.B. bei Google nur mit einem '+' davor?

Auch das ist "Magie". Solche Entscheidungen kannst Du in einer sehr späten Designphase treffen, ggf. sogar erst nach einer ersten Implementierung. Wie Dein GUI _aussieht_, ist erst später wichtig - aber welche Semantik es umsetzen soll, das mußt Du schon beim Tabellenentwurf wissen.

d: Wie soll ich suchen wenn mehr als ein Suchbegriff eingegeben wird? Soll ich suchen welche das gleich Ziel haben, und diese nach dem zweiten Suchbegriffdurchsuchen? Oder das Ziel des ersten Suchbegriffes über Perl öffnen und mittels Regexen durchsuchen?

Genau darüber haben Andreas und ich lange diskutiert. ;-)
Das Problem ist: Wenn beide Terme viele Ergebnisse liefern, dann wird das JOIN zwischen beiden mörderisch und macht die schöne Indexstruktur wertlos.
Mein Vorschlag dazu war es, eine Meßfunktion für die Projektivität der Terme zu haben (die selbst dann möglichst wenig kosten darf) und damit Performance-Katastrophen wenigstens erkennen kann.

e: Macht es Sinn die Reihenfolge der where Klausel nach Länge der der Suchbegriffe zu sortieren? So dass lange, da sie vermutlich seltener vorhanden sind, zuerst gesucht werden?

Das hängt vom verwendeten RDBMS ab - ich würde aber pauschal "nein" sagen.

Bedenke auch, daß Du dann ggf. den längeren Term sehr oft prüfen lassen mußt, was ja schließlich auch etwas kostet ... wenn Du mit dem ersten Term über den Index einsteigst und von dort aus eine Schleife ansteuerst, den zweiten Term auszuwerten, _kann_ das eventuell prima sein - nur nutzt Du dann für den zweiten Term Deine Indextzstruktur überhaupt nicht mehr.

Viele Grüße
      Michael

[Andres Freund]

Hi Michael

Ich verstehe, daß Du die jeweilige Datenmenge klein halten willst; aber wenn Du über die Worte einen Indexbaum legst, dann macht die Datenbank das von ganz alleine. Ich vermute, Du wirst einen sehr kleinen Performance-Gewinn erzielen, aber die Wartung Deiner Datenstrukturen nicht gerade vereinfachen.

Ich hab das ganze mit einem zufallsgenerierten Inhalt mal getestet, waren so 10-15 Prozent Geschwindigkeitszuwachs, je nach der durchschnittlichen Wortlänge. Allerdings ist bei zufallgeneriertem Content die Verteilung der Anfangsbuchstaben natürlich vergleichsmäßig gleichmäßig. Ausserdem waren das schon 1GB Daten, weil ich mich igrgendwo verschrieben/verrechnet hatte. Ich weiß es bis jetzt noch nicht genau was ich falsch gemacht habe ;-).
Ein zusätzlicher Grund für mich war, dass das ganze eventuell bei einem hoster läuft der zwar mehrere DB's pro Paket gibt, aber alle mit einer maximalgröße von 100MB. Dafür wäre eine derartige Datenstruktur prinziell ja gut geignet.

Du meinst "Substring" statt "Präfix", ja? (Präfix-Suche auf Postfixe ist Substring auf Worte.)

(geschmacks)(sache)
Mit Präfix meinte ich z.B. den ersten Teil der jetzt in der Klammer steht. Ob das jetzt eigentlich substring heißt, weiß ich ehrlichgesagt nicht.

Hm. Warum nicht das Wort mit Umlaut zweimal indexen? So oft kommt das ja nicht vor.

Weil ich 1. so keine Probleme mit dem Zeichesatz in der Tabelle habe, zweitens weil ich dadurch das Problem vermeide, dass jemand nach fröhlich sucht, aber in dem Text stand froelich, und er dadurch nichts findet.

Ich glaube nicht an das Prinzip mit den vielen Tabellen - es sei denn, bei Verteilung auf viele Maschinen. Aber auch dann würde man eine besser streuende Hash-Funktion nehmen und nicht die extrem ungleich verteilten Anfangs-Buchstabenpaare.

Wegen der Verteilunng, siehe oben.

Eine bessere Verteilung könnte man allerdings recht gut einbauen, z.B. indem man einige Zeit die Verteilung der Anfangsbuchstäben der Einträge verfolgt und dann, diese später wieder neu sortiert/verteilt. Das hat allerdings den Nachteil dass der Server dazu einge Zeit in Anspruch genommen wird. Besonders nachteilig müsste sich das dann auswirken, wenn man z.B. bei Puretec ist, mit einer maximalen Laufzeit von 6s. Ein Problem ist auch das generieren der Indices bei den großen Tabellen. Daher hätte, besonders bei mysql, eine auf viele Tabellen verteilte Struktur performance-Vorteile beim erstellen erneuern der Indices, da rel. Häufig Daten verschwinden und hinzukommen werden.

d: Wie soll ich suchen wenn mehr als ein Suchbegriff eingegeben wird? Soll ich suchen welche das gleich Ziel haben, und diese nach dem zweiten Suchbegriff durchsuchen? Oder das Ziel des ersten Suchbegriffes über Perl öffnen und mittels Regexen durchsuchen?
Genau darüber haben Andreas und ich lange diskutiert. ;-)
Das Problem ist: Wenn beide Terme viele Ergebnisse liefern, dann wird das JOIN zwischen beiden mörderisch und macht die schöne Indexstruktur wertlos.

Ich dachte mir, dass ich das ganze aufteile, das erste Wort, oder eben das längere Wort zuerst alleine in der Db suche, mit einem Limit von z.B. tausend. Ich suche nur die Ziele heraus, die z.B. in einer einfachen Text-Datei liegt. Diese durchsuche ich dann mittel Regexes nach dem Vorkommen des zweiten Wortes, wieder nur bis ich hundert habe, die dann in irgendeiner Form ausgebe.
Die andere Idee war die, dass ich, wenn ein Suchbegriff z.B. "Hallo" ist, alle Ziele in einem einfachen Array speichere, dann ohne irgendwelche besondere Maßnahmen das zweite Wort genauso durch die Db laufen lasse (Mit einem Statemant der Art: SELECT ziel FROM xyz WHERE wort=Hallo). Danach vergleiche ich die Ergebnisse der ersten Abfrage, mit denen der zweiten. Wenn bei einem Array Element eine Übereinstimmung mit einem Ergebniss der zweiten Abfrage vorliegt, öffne ich die Datei in der das ganze steht und gebe den anfang des Inhaltes aus. Das hat leider Ja den Nachteil, dass ich sehr viele Arraylemte miteinander vergleichen müstes. Bei einem dritten Wort wären in dem Array aber nur noch die "Ziele", die schon Übereingestimmt habe, was vermutlich nicht sonderlich viele sind. Dadurch wird das Ergebniss mit zusätlichen Suchbegriffen nicht alzu sehr langsamer.
Das mit dem Join würde nat. wieder sehr viele Resourcen auf dem Db Rechner benötigen.

Mein Vorschlag dazu war es, eine Meßfunktion für die Projektivität der Terme zu haben (die selbst dann möglichst wenig kosten darf) und damit Performance-Katastrophen wenigstens erkennen kann.

Etwas derartiges ist leider, befürchte ich, für einen, der in meinem Stadium des lernens ist, ein wenig zu anspruchsvoll. Ich werde mir aber die alten Threads von euch noch mal anschauen, vielleicht werde ich ja inspiriert.

So, hier nocheinmal die allgemeine Tabellenstruktur so wie ich sie mir momentan vorstelle:

-----------------------------------------------------------
|  Wort   |  Ziel  | Präfix/Substring | Kategorie | Autor |
-----------------------------------------------------------
|Belastung| 1d4df2 |0                 | Lacke     | Andres|
-----------------------------------------------------------
|stung    | 13s44d |1                 | Lacke     | Andres|
-----------------------------------------------------------
|FCKW     | 1s2442 |0                 | Lacke     |Michael|
-----------------------------------------------------------

Was dadurch ersichtlich wird, was ich eventuell *g* früher hätte erwähnen hätte sollen, ist, dass ich den "ganzen Content" eigentlich nicht zusammenhängend in der DB speichern wollte, da mir das IMHO kaum nutzen bringt, wenn ich teilweise keinen fulltext index benutzen kann, will.

Dem jetzt langsam, aber sehr sicher der Kopf raucht, und der langsam ins Bett gehen sollte weil er morgen früh wieder in der Schule (noch 2 1/2 Jahr ;-( )sein muss. Der auch _viel_ lieber anfangen würde etwas derartiges zu studieren. Ja, ich weiß lieber jetzt richtig lernen als später nachlernen *g*.

mfg und vielen, vielen Dank:
Andres (Michael) Freund  *g* wirklich, ich heiß auch Michael