Perfmormante Suche in vielen Strings: komplexe Suchopt.: Wortgruppen, erzwungene/unterdrückte Wörter
Hallo zusammen!
Ich hoffe ein ähnliches Thema wurde hier nicht schon behandelt, habe auf jeden Fall die Forensuche angeschmießen. Aber vielleicht haben mir auch nur die richtigen Suchbegriffe gefehlt.
Also, es geht mir um folgendes: Ich habe sehr viele mittellange Sätze. Insgesamt etwa 32.000 Stück an der Zahl. Durchschnittlich hat jeder Satz ~23 Wörter (ca. 740.000 insgesamt). Jeder Satz hat eine eindeutige ID.
Ich möchte nun eine etwas komplexere Suche auf alle diese Sätze ausführen, und mir alle Sätze liefern lassen, die den Suchkriterien entsprechen.
Dabei sollen ähnliche Suchfunktionen möglich sein wie z.B. bei der Google-Suche. Da kann man über Anführungszeichen "bestimmte Wortgruppen" suchen, also dass genau in dieser Reihenfolge diese Wörter vorhanden sind. Oder man kann mit einem Plus- oder Minus-Zeichen Wörter +erzwingen oder -unterdrücken. Ich denke das dürfte den meisten bekannt sein.
Edit: Ganz vergessen: Es soll auch möglich sein, mit Jokern nach ähnlichen Wörtern zu suchen, beispielsweise Land* (=> Land, Landschaft, Landgebiet, usw.).
Meine konkrete Frage wäre nun: Wie gehe ich hier am besten vor? In welcher Datenstruktur soll ich die Sätze bereitstellen? Als plain strings?
Wie kann ich performant alle Sätze nach Übereinstimmung durchsuchen und mir die Ergebnisse liefern lassen? Wären RegEx eine Option? Bin mir gerade unklar darüber, wie so ein RegEx-String aussehen könnte, schließlich suche ich ja nicht nach einem bekannten Muster. String.Contains() möchte ich aber vermeiden... 😉
Edit 2: Hm, eigentlich könnte man das doch einfach über eine entsprechende SQL-Query machen? Irgendwo müssen die Daten ja ohnehin gespeichert werden. Hab ich da wohl den Wald vor lauter Bäumen nicht gesehen? 🤔
Ich würde es zwar wahrscheinlich irgendwie hinbekommen, aber da ich mit Algorithmen nicht besonders vertraut bin, wäre meine Vorgehensweise vermutlich unnötig kompliziert und wahrscheinlich nicht sonderlich performant.
Deshalb dachte ich mir, frage ich einfach die Profis. 🙂
Und vielleicht noch eine Nebenfrage: Wie kann ich den Suchstring, den der User eingibt, parsen und Fehleingaben abfangen? Aus dem Suchstring müssten ja alle Einzelbedingungen extrahiert werden und gegebenenfalls in passende Datenstrukturen überführt werden, also beispielsweise eine List<List<string>> für Wortgruppen, eine List<string> für erzwungene Wörter und eine List<string> für unterdrückte Wörter.
Letzlich soll das ganze übrigens in PHP umgesetzt werden, aber das sollte für dieses Problem denke ich ohne Belang sein, werde das ganze ohnehin erstmal in C# probeweise umsetzen.
Hoffe ihr habt ein paar Denkanstöße für mich!
Danke und Gruß,
Andreas
Zuerst: Deine Signatur ist dämlich.
Du hast hier einen klassischen Fall für paralelle Programmierung, im besten Fall logarithmisch.
Ist eine Echzeitsuche oder ein Job über einen festen Datenbestand(mit Indizes)?
Im letzeren Fall hast du die Möglichkeit die Daten binär balanciert zu sortieren.
Das sichert dir zu immer in log 10 Schritten zum Ziel zu kommen.
Selbstredend kann man hier prima mit paralleler Programmierung arbeiten.
Wie kann ich den Suchstring, den der User eingibt, parsen und Fehleingaben abfangen?
Das ist im Prinzip einfach gute handwerkliche Programmierarbeit.
Bzw. was meinst du mit abfangen? Exception schmeissen oder wohlgemeint
korrigieren? Ich vermute letzteres. Dann bleibt dir wirklich das Handwerk
also String Split auf " ". ( vorher Replace auf " " zu " " mit Trim)
Zuerst: Deine Signatur ist dämlich.
Freut mich, dass sie dich anspricht. 🙂){gray}
Ist eine Echzeitsuche oder ein Job über einen festen Datenbestand(mit Indizes)?
Hatte meinen Eingangspost nochmal erweitert (siehe Edit 2).
Also, es wird wohl mit ziemlicher Sicherheit ein RDBMS zum Einsatz kommen. Auf dem Produktivsystem wohl MySQL, zum Testen würd ich wohl für die C#-Implementierung MS SQL nehmen.
Da auch in meinem Edit die Frage: Im Grunde müsste ich ja nur eine entsprechende Query an die DB absetzen, die Datensätze haben wie gesagt eine ID. Da bräuchte ich mir ja nicht selber 'nen Wolf programmieren weil das DBMS ohnehin auf Abfragen optimiert ist.
Edit: Und, ja. Soll eine Echtzeitsuche sein.
Das ist im Prinzip einfach gute handwerkliche Programmierarbeit.
Bzw. was meinst du mit abfangen?
Ja das dachte ich mir. (Und ja, mit "Fehler abfangen" meinte ich die zweite Option.) Okay, die Handwerksarbeit krieg ich sicher hin.
Hm, im Grunde wäre dann wohl meine Frage wohl so gut wie beantwortet, lol.
Trotzdem danke für die Antwort! 🙂
Gruß und Gottes Segen,
Andreas
Hallo,
ich verstehe die Vorgensweise nicht wenn produktiv PHP + MySQL verwendet werden soll warum dann mit C# + MS SQL der "Prototyp" entwickelt wird. Alleine schon deshalb nicht da die Suche des MS SQL höchstwahrscheinlich nicht mit jener von MySQL ident ist - von den "Sonderheiten" ganz abgesehen. Mit der Portierung werden sich mehr Probleme ergeben als wenn du gleich in der Zielsprache den Protypen erstellst.
Für PHP sollte doch eine Google-Suche genügend fertige Komponenten (od. wie die in PHP heißen) vorhanden sein. Für MySQL sollte sich auch genügend finden. Ich denke dass du sicher nicht der erste bist der diese Anforderung hat und da nunmal PHP + MySQL sehr verbreitet ist gibts wohl genug.
Für die "Joker" kannst du ja ein einfaches Mapping erstellen. zB * wird in MS SQL zu %, usw.
Die SuFu selbst zu implementieren wäre sicher interessant, aber nicht zielführend da viel zu viel Aufwand wenn es gut gemacht werden soll. In einer simplen Variante wäre das was für das Programmier-Spiel.
mfG Gü
Stellt fachliche Fragen bitte im Forum, damit von den Antworten alle profitieren. Daher beantworte ich solche Fragen nicht per PM.
"Alle sagten, das geht nicht! Dann kam einer, der wusste das nicht - und hat's gemacht!"
Hallo aadler,
sicherlich könnte man das alles selber programmieren, aber ich stimme gfoidl zu, dass das bei der Menge deiner Anforderungen sehr bzw. zu aufwändig wäre. Im Prinzip hast du zu ziemlich alle Anforderungen von der Google-Suche übernommen. Entsprechen wäre es sinnvoll und folgerichtig, tatsächlich Google zu verwenden. Um eine Google-Suche bzw. eine Google-Suchkomponente in die eigene Website einzubinden gibt es verschiedene Möglichkeiten, die alle im Web beschrieben sind.
herbivore
PS: Aufgrund der Community-Regeln zu Signaturen, habe ich die erhöhte Schriftgröße deiner Signatur auf Normalgröße zurückgesetzt.
Hallo,
Ich würde auch dringend zu einer bestehenden Lösung raten, etwa eine ggf. angebotene Volltextsuche deines Datenbanksystems oder ein Suchserver wie SOLR. Ich habe selbst sehr positive Erfahrungen mit SOLR gemacht (z.b. läuft die Suche von www.top10gezien.nl vollständig damit). Es läuft als eigenständiger Server und wird über HTTP angesprochen, ist also ziemlich unabhängig von der verwendeten Umgebung. Und ja: das Ding ist schnell 😃
Grüße,
Andre
Hallo zusammen 😃
@Gü: Ja das stimmt schon, die Unterschiede zwischen PHP und C# sind nicht gerade gering. Aber da das ganze sowieso stückweise auch ein Übungsprojekt ist, weil's ein Privatprojekt ist, dachte ich mir kann ich auch zwei Implementierungen machen. Zeitdruck habe ich eh keinen. 😃
P.S.: Wenn mal im Programmierspiel eine vereinfachte Variante dieser Problemstellung als Aufgabe gestellt und gelöst wird, werd ich's mir ja mal anschauen. 😃
@herbivore: Hm, auf die Idee, die Google-Suche zu integrieren bin ich gar nicht gekommen... Aber ob man die dann auch optisch gut in den Rest der Seite integrieren kann? Werd's mir mal anschauen.
@Andre: Solr sieht auch interessant aus, danke. Allerdings glaube ich nicht, dass ich das benutzen kann. Habe nur ein bisschen Webspace gemietet und da krieg ich keinen Zugriff auf den Server...
Danke insgesamt für eure Antworten! Ich tendiere momentan doch sehr stark zu der DBMS-Lösung. Damit bin ich eh schon am meisten vertraut. Ist wohl wirklich so, dass ich gestern Abend zu kompliziert gedacht und den Wald vor lauter Bäumen nicht gesehen hab, weil das ja eigentlich die naheliegendste Möglichkeit ist. 😃
Gruß und Gottes Segen,
Andreas