Forumsuche -> Verbesserungsvorschläge
-
Ich habe diese Woche Urlaub und kann mal den Staub vom Code abklopfen. Vielleicht kriegen wir das ja in Betrieb? Allerdings bräuchte ich dabei Unterstützung, weil ich wie gesagt mit PHP nicht so fit bin und daher gerne hätte, dass sich noch jemand anders die Änderungen ansieht, insbesondere im Hinblick auf Sicherheitslücken.
-
Ja, können wir sehr gerne machen, kann nur sein, dass meine Antwortzeit momentan nicht so toll ist, bin diese Woche viel unterwegs.
Würde die Änderungen auf alle Fälle auch im Mod-Forum posten, je mehr Leute, sich das durchlesen, desto besser.
-
Hallo liebe engagierte obere 10000 des Forums (
),ich weiß absolut nicht, ob das jetzt hierher passt - zumal der Thread ja schon eine Weile nicht mehr angefasst wurde - aber ich poste es einfach mal:
Für mich als "Durchschnittsbenutzer" dieses Forums ist es absolut unbegreiflich warum die Suche im Unterforum "VCL/C++Builder" mit dem Suchbegriff *Dateigrö* keine Ergebnisse liefert, die Suche mit dem Suchbegriff *Dateigröße* jedoch 57 Ergebnisse liefert!?!
MfG
-
Die Suchfunktion ist derzeit aus Performance Gründen ein wenig Eingeschränkt und kann nur ganze Wörter matchen. Wir arbeiten daran einen Patch einzuspielen (siehe Jesters Beitrag). Aber aus zeitlichen Gründen ist dies bisher noch nicht gelungen.
-
Ich hab mal ne Suche in C++ geschrieben, die in O(log n) Wildcardsuchen ausführen kann.
Falls Interesse besteht kann ich mich gern dahingehend engagieren, dass diese Suche hier eingesetzt werden kann.
Würde wahrscheinlich doch viel Belastung vom Server nehmen.
-
Tobias3 schrieb:
Ich hab mal ne Suche in C++ geschrieben, die in O(log n) Wildcardsuchen ausführen kann.
Das würde mich schon aus rein theoretischer Sicht interessieren. Bist Du sicher, dass Du immer und bei jeder Eingabe nur logarithmische Zeit benötigst?
-
Jester schrieb:
Tobias3 schrieb:
Ich hab mal ne Suche in C++ geschrieben, die in O(log n) Wildcardsuchen ausführen kann.
Das würde mich schon aus rein theoretischer Sicht interessieren. Bist Du sicher, dass Du immer und bei jeder Eingabe nur logarithmische Zeit benötigst?
Naja die Suchbegriffe werden sortiert in eine Datei geschrieben und darauf wird dann eine modifizierte binäre Suche ausgeführt.
Damit Suchanfragen wie *est oder tes* ebenfalls in (ungefähr) O(log n) zum Suchergebnis führen wird für z.B. test - test est st (das letzte je nach Einstellung nicht) zum Suchindex hinzugefügt.
Wenn man also nach est sucht kommt man zu est - da befindet sich dann ein Eintrag zu test.
Sucht man nach tes so landet man durch die binäre suche direkt bei test, weil es "tes" nicht gibt, oder er landet bei "tes" geht dann aber den Suchindex weiter runter bis die Suchbegriffe nicht mehr mit "tes" anfangen.
Die Suche ist also im worst-case O(n), falls alle Suchbegriffe im Index mit "tes" anfangen, aber in der Praxis wohl eher O(log n) ;).
Zu dem Suchbegriff sind dann in der Datei lauter ids, die vorher schon bei der indexerstellung nach relevanz sortiert wurden.
Beim verUNDen werden mehrere suchanfragen ausgeführt und die Schnittmenge ausgegeben. (Das ist natürlich dann auch nicht mehr in O(log n) machbar...).Wie macht das die phpBB-Suche? Was macht die, wenn nach einem Suchbegriff mit Wildcard gesucht wird?
-
Die phpBB-Suche packt ein % in den Suchstring und delegiert das Problem mittels "WHERE blablabl LIKE "tes*" an die mySQL-Datenbank weiter.
Die UND-Verknüpfung stelle ich mir in dieser Weise problematisch vor... genau das macht die phpBB-Suche derzeit auch. Leider führt das dazu, man keine Ergebnisse kriegt, wenn man ein häufiges und ein seltenes Wort sucht, da aus Performance-Gründen nur die ersten x Treffer in die Liste aufgenommen werden.
-
Wow, aber unser Index hat ja jetzt schon 30 Mio Einträge oder, der wird mit so einer Idee ja nicht wirklich kleiner.
-
Jester schrieb:
Die phpBB-Suche packt ein % in den Suchstring und delegiert das Problem mittels "WHERE blablabl LIKE "tes*" an die mySQL-Datenbank weiter.
Die UND-Verknüpfung stelle ich mir in dieser Weise problematisch vor... genau das macht die phpBB-Suche derzeit auch. Leider führt das dazu, man keine Ergebnisse kriegt, wenn man ein häufiges und ein seltenes Wort sucht, da aus Performance-Gründen nur die ersten x Treffer in die Liste aufgenommen werden.
Und dann geht er 30 Mio Einträge mit einem Full-Table-Scan durch?
Kein Wunder musstet ihr das deaktivieren...Das mit der UND-Verknüpfung ist aber in der Tat problematisch ich nehm da halt auch nur ne begrenzte Anzahl (5000) und durch die Vorsortierung werden auch nur die relevanteren genommen. Will man aber alle durchgehen, dauert das einfach zu lang (ist aber bestimmt in C++ schneller als in PHP
).Marc++us schrieb:
Wow, aber unser Index hat ja jetzt schon 30 Mio Einträge oder, der wird mit so einer Idee ja nicht wirklich kleiner.
Jepp, das ist da natürlich schon ein Problem. Habe mal so 400MB Textdaten indiziert und es ist ein 4GB großer Index herausgekommen. Natürlich steigt die Indexgröße auch immer langsamer an, weil Wörter öfters indiziert werden.
Hier wird halt Performance durch mehr Speicherplatzverbrauch erkauft - Sollte heutzutage kein Problem mehr sein...
-
Tobias3 schrieb:
Das mit der UND-Verknüpfung ist aber in der Tat problematisch ich nehm da halt auch nur ne begrenzte Anzahl (5000) und durch die Vorsortierung werden auch nur die relevanteren genommen. Will man aber alle durchgehen, dauert das einfach zu lang (ist aber bestimmt in C++ schneller als in PHP
).wie machst du die Relevanz-Sortierung?
edit: ich halte es nicht für sehr realistisch, die suche auf C++ umzustellen, das birgt imo zuviele Risiken. aber wenn du lust hast dich bezüglich der Suchfunktion zu engagieren, schreib mir mal ne mail (über das profil).
-
Wie wichtig sind eigentlich Wildchars? Eventuell könnte man mit einem metrischen Baum und der Editierdistanz etwas effizientes machen nur vertragen sich Wildchar und Editierdistanz so weit ich weiß nicht wirklich.
Ob man die Und-Verknüpfung effizient implementiert kriegt, weiß ich nicht. Ich kenne mich nicht genug mit den einzelnen Bäumen aus um das zu beurteilen.
-
ich denke wildcards sind schon interessant. allerdings würde ich nicht die UND-Verknüpfung dafür opfern wollen. editierdistanz klingt für mich nicht gerade nach höchster effizienz, obwohl's natürlich trotzdem nett wäre. Allerdings scheint mir Editierdistanz noch freier zu sein als wildcards... da sagt man wenigstens schonmal wo die unterschiede sind.
-
Jester schrieb:
wie machst du die Relevanz-Sortierung?
Bei einem Forum das nicht über so etwas geschicktes wie einen Pagerank verfügt, kommt da eigentlich nur die Häufigkeit des Stichwortes und die Position also entweder Titel und Beitragstext in Frage.
Also zuerst alle Suchbegriffe im Titel und dann erst die im Beitragstext.Wegen der Editierdistanz:
Das geht glaub ich sogar recht effizient - also man hasht quasi die Suchbegriffe, so dass Suchbegriffe mit Buchstabenverdrehern den selben Hash haben.
Aber wenn ich von meinen Suchgewohnheiten ausgehe brauche ich eher die *Suchbegriff* Wildcards. Soll ja keine Rechtschreibhilfe sein...Ich glaube google und co. optimieren die verUNDung vorallem dadurch, dass sie Suchanfragen auswerten und dann die verUNDdete Begriffe in einen eigenen Index aufnehmen - anders kann ich mir das nicht vorstellen.
So relevant ist das bei so einem vergleichsweise kleinem Datenbestand auch nun wieder nicht. Dann vergleicht man halt mal 100000 integer werte und sucht sich die raus die doppelt vorkommen.
-
Wie lange sind eigentlich die Stichwörter die es zu durchsuchen sind minimal, maximal und im Durchschnitt? Jetzt mal grob über den Daumen gepeilt würde ich auf 3, 8, 15 tippen aber eventuell liege ich da völlig daneben.
Die Idee mit dem M-Baum stirb wohl schon an fehlenden frei zugänglichen und durch optimierten Standardimplementierungen. Die Forumsuche ist meiner Meinung nach den Aufwand einer Implementierung nicht wert. Die Editierdistanz zu berechnen sehe ich nicht als Problem da 8^2 noch human ist. Ich glaub eher, dass die Standard-Editierdistanz zu grobe ist, das heißt zu wenig verschiedene Werte liefert (alle werte liegen zwischen 0 bis 15 und sind ganzzahlig). Dadurch dürften die Strings alle nahe beieinander liegen und man kann sie nicht in Kugeln packen ohne dabei große Überlappungen zu verursachen.
Tobias3s Ansatz erlaubt wenn ich das richtig sehe nur Wildcards am Anfang und am Ende. Wenn das kein Problem ist dann ist er wahrscheinlich nicht schlecht. Ich würde jedoch auf Hashtabellen zurückgreifen und nicht auf eine sortierte Liste und je eine für Prefixe und Postfixe anlegen.
Für ein Wort der Länge n sind das etwa 2*n Einträge, also etwa 16. Da ein Eintrag jedoch etwa nur aus 2 Pointer/IDs und dem String selbst besteht würde ich mal sagen, dass die Indexstruktur etwa 24Byte pro Eintrag braucht. Bei 30 Mio Einträgen komme ich auf etwa 10 GB allein für die Indexstruktur. Klingt nach viel aber für 30 Mio Einträgen und einer schnelle Suche ist das glaub ich drunter zu haben.
Man könnte natürlich versuchen bei den 30 Mio Einträgen ein paar weg zu schmeißen oder nur ein paar in den Index auf zu nehmen. Eventuell ist eine Kombi Lösung aus Index für häufig gesuchte Stichwörter und einem linearen Scan für den Rest eine Idee.
Die Verundung ist natürlich ein Problem, allerdings fällt mir auf Anhieb keine Datenstruktur ein welche die effizient behandeln kann.
-
Tobias3 schrieb:
Das geht glaub ich sogar recht effizient - also man hasht quasi die Suchbegriffe, so dass Suchbegriffe mit Buchstabenverdrehern den selben Hash haben.
das heißt hash(abc) = hash(bac) = hash(acb) und hups, das könnten ja auch wörter sein, also wieder beliebig vertauschen... = hash(cab) = hash(cba), also bildest du nur noch einen hash über das anagram. Oder wie darf ich das verstehen?
@Ben04: zwischen 3 und 8 ist denke ich realistisch, die Daten habe ich derzeit zwar nicht, kann ich aber sicher bekommen. 8^2 ist zwar nicht riesig, aber auch nicht zu vernachlässigen. Das kann den Unterschied zwischen funktioniert zügig und Suche ist zu langsam bedeuten.
Aber letztlich sind das hier alles theoretische Überlegungen. Die Randbedingungen sind im Wesentlichen wie folgt: Wir haben eine mySQL-Datenbank, in der ein Index liegt. Die müssen wir via PHP mit geeigneten Suchanfragen versorgen. Eine C++-Implementierung irgendwelcher toller Datenstrukturen ist sicher eine wunderbare Lösung, aber leider nicht für dieses Problem.
Die Hauptaufgaben sehe ich derzeit in folgenden Bereichen:
- Die SQL-Abfragen so umschreiben, dass sie für mySQL leichter verdaulich sind.
- Den Index bzw. den Indexer so überarbeiten, dass ein besserer Index herauskommt. Dabei kann kleiner gleichzeitig auch besser bedeuten: entfernen von unnötigen Wortendungen und ähnlichem verbessert auch die Qualität der Suchergebnisse
zu 1) habe ich schon einiges gemacht. allerdings läuft es immer noch nicht vernünftig. ich werde mich demnächst mal auf die Suche nach dem genauen Flaschenhals machen.
Ein großes Problem ist der Code vom phpBB, der ist so furchtbar und unaufgeräumt, dass jede Änderung eine Qual ist.
-
Tobias3 schrieb:
(ist aber bestimmt in C++ schneller als in PHP
).Glaube ich kaum, da das Bottleneck die Datenbank ist, bzw. die Geschwindigkeit der Festplatten.
-
Wie wäre es mit folgendem Ansatz:
Die volle Stichwortliste wird nach dem String geordnet damit Anfragen ohne Wildcard schnell sind. Das müsste die mySQL-DB doch hinkriegen oder?Sämtliche Stichwörter nach denen mal gesucht wurde werden in einer Liste gespeichert. Diese ist chronologisch geordnet und wird bei Bedarf einfach unten abgeschnitten. Wildcardsuche beschränkt sich auf diese Stichwörter.
Wird diese Liste klein gehalten kann man Wildcards mit einem Linearen Scan implementieren (so wie das jetzt schon der Fall ist). Ansonsten muss man eventuell auf Tobias3s Ansatz zurück greifen. Hierfür wäre ein cron-Job welcher die Pre- und/oder Postfix Tabellen neu generiert wahrscheinlich eine gute Idee. Wie man eine solche Tabelle am besten bei mySQL umsetzt weiß ich nicht.
Im Endeffekt ist es ja nur eine Abbildung String => ID. Wahrscheinlich reicht es dem String eine Obergrenze für die Länge zu geben und zum Primary-Key zu erklären. Kann man dem SQL irgendwie sagen, dass er Zeilen beliebig umordnen kann?
-
Natürlich der string ist sowieso primary-key in der stichwort-tabelle, die anfragen darin sind ziemlich sicher schnell. Eigentlich kann mySQL ja auch wildcards...
ich denke, um bei kleinen schritten zu bleiben könnten wir zunächst auch ohne wildcards arbeiten. Insbesondere im Hinblick darauf, dass wir mit einem verbesserten Index auch wildcards weniger nötig haben. Eigentlich gibt es nämlich keinen Grund, warum man mit "*main*" viel mehr finden sollte als mit "main".
Caching zur Verbesserung der Performance ist sicher eine gute Idee. Ich bin mir allerdings nicht sicher, wie gut es ist die Ergebnisse davon abhängig zu machen, was zuvor häufig gesucht wurde. Das ist dann schlecht reproduzierbar und erschwert die Fehlersuche. Sowas ist auf jeden Fall mit Vorsicht zu genießen.
Generell würde ich sagen: UND-Operation ist die wichtigste, Wildcards sind nice-to-have, aber nicht eminent wichtig. da verspreche ich mir von einem aufgeräumten Index mehr. Marc++us, wie siehst Du das?
-
Ben04 schrieb:
Tobias3s Ansatz erlaubt wenn ich das richtig sehe nur Wildcards am Anfang und am Ende. Wenn das kein Problem ist dann ist er wahrscheinlich nicht schlecht. Ich würde jedoch auf Hashtabellen zurückgreifen und nicht auf eine sortierte Liste und je eine für Prefixe und Postfixe anlegen.
Für ein Wort der Länge n sind das etwa 2*n Einträge, also etwa 16. Da ein Eintrag jedoch etwa nur aus 2 Pointer/IDs und dem String selbst besteht würde ich mal sagen, dass die Indexstruktur etwa 24Byte pro Eintrag braucht. Bei 30 Mio Einträgen komme ich auf etwa 10 GB allein für die Indexstruktur. Klingt nach viel aber für 30 Mio Einträgen und einer schnelle Suche ist das glaub ich drunter zu haben.
Jepp, erlaubt nur Wildcards am Anfang und am Ende. In der Mitte nicht. Man muss die wildcards auch nicht mit angeben, die Suchergebnisse mit Wildcards werden automatisch nach den exakten Ergebnissen ausgegeben.
Mein Anstatz braucht ja pro Key nur n Einträge, also braucht er die Hälfte der Datenmenge.
bei 15 Mio Einträgen braucht er bei der binären Suche ca. 20 Vergleiche. Nun sind nur Festplattenzugriffe relevant. D.h. die ersten 4 Stufen werden gecached -> 16 Zugriffe. Und vllt. sind die letzten 3 Zugriffe und das Scannen nach Wörtern mit selbem Präfix im selben Sektor -> 14 Zugriffe.
Mein Verfahren lohnt sich also bei so viel Einträgen noch. Bei mehr könnte sich allerdings wirklich Hashen lohnen.
Hashing benötigt immer 2*n Festplattenzugriffe.Jester schrieb:
das heißt hash(abc) = hash(bac) = hash(acb) und hups, das könnten ja auch wörter sein, also wieder beliebig vertauschen... = hash(cab) = hash(cba), also bildest du nur noch einen hash über das anagram. Oder wie darf ich das verstehen?
Meinte eher so was wie http://de.wikipedia.org/wiki/Soundex aber wahrscheinlich gibts da wirklich zu große Buckets.