Bool'sche Suche

Beitrag von **Til** » 25 Jan 2005, 14:32

Wenn der Aufbau des Auswertungsbaums Zeit braucht, dann wär das nicht so schlimm. Hauptsache die eigentliche Suche geht schnell. (Der Baum wird ja nur einmal aufgebaut, jedoch n mal angewendet)

Die Frage, wie du das implementiert hattest, hat sich mehr auf die eigentliche Suche bezogen. Wenn bei der Suche nach "a OR b OR c" dreimal String.indexOf() aufgerufen wird, dann wär das nicht so toll. Die Suche wäre dann O(n * m), statt O(n). Lieber eine Regex (".*(a|b|c).*"). Wobei man dann halt bei "(a AND b) OR (NOT c)" wiederum keine Regex mehr nehmen kann.

Die schnelle Suche ist halt schon ein wichtiges Feature in TV-Browser. Da wäre es schlecht, wenn es da Einschnitte gäbe. Du musst bedenken, dass die Suche an vielen Stellen automatisch und teiweise mehrfach angewendet wird (Lieblingssendungen, Erinnerer, Filter).

Aber mach ruhig mal ne Implementierung. Optimieren kann man danach ja immer noch. Du kannst also die Regex-Geschichten erstmal rauslassen, wenn es dir zu blöd ist. Da die Suche so zentral ist, will ich dir allerdings nicht versprechen, dass wir deine Lösung rein nehmen, bevor ich den Code nicht gesehen habe.

pumpkin · Beitrag von **pumpkin** » 25 Jan 2005, 21:05

Hab mal ein Benchmark für regex vs BinSearch auf die Beine gestellt: 24898 Texte aus TvBrowser (1,6MB, alles was mein Plugin zu fassen bekommt, von Jahreszahlen und langen Beschreibungen). Durchsucht wird alles 50x nach 2 Ausdrücken ".*Star.*|.*Sternchen.*", ".*der.*" (resp.: "Star OR Sternchen", "der"). compile, (resp. new Searcher()) wird insgesamt nur 2x aufgerufen.

Regex braucht 21,4 sek, BinSearcher 7,8 sek.

Kann mir mal jemand ein paar komplexere Beispiele geben ? (ich krieg kein regex mit AND hin)

Beitrag von **Til** » 25 Jan 2005, 22:49

Cool! Sogar schneller. Dann ist ja alles OK!

pumpkin · Beitrag von **pumpkin** » 26 Jan 2005, 12:14

Ja, aber ich hab nur mit einfachen Ausdrücke getestet.

Und das Ding kann noch nicht nach Ausdrücken wie "die lange nacht" suchen (weils keine "-Zeichen gibt). Ausserdem würde bei der Suche "die lange nacht" (ein Leerzeichen mehr) durchfallen. Ich lass mir mal was für die Fälle einfallen.

(Umwandeln nach (die AND lange AND nacht) und erst bei einem Treffer das regex .*(die\slange\snacht).* zur Kontrolle hinterher.... )

Beitrag von **Til** » 26 Jan 2005, 12:50

Nimm doch schon zum Suchen eine Regex ".*die\s*lange\s*nacht.*" (ohne AND).

Ich würde erste gar keine Anführungszeichen einbauen "a AND b c" heißt: ".*a.*" AND ".*b\s*c.*"...

Und "a OR b c" heißt: ".*(a|b\s*c).*".

pumpkin · Beitrag von **pumpkin** » 27 Jan 2005, 10:25

Ich glaub nicht so wirklich dass das was wird.

regex-suchen nach dem vollen Begriff dauert etwa 3x länger als indexOf()-suchen (nach allen 3 Begriffen einzeln). Wenn ich mit indexOf()-suchen 75% der Texte ausschliessen kann bin ich (inklusive Überprüfung durch regexp) immernoch schneller als direktes regex-suchen. OK, wenn die Begriffe "dumm" gewählt sind ist Feierabend und das System erzeugt 30-40% Overhead umsonst.

Ich hab ein ganz anderes Problem: ich versteh euer Suchsystem nicht so ganz. Wenn ihr die Suche irgendwann verbauen wollt, sagt mir was BinSearch können muss und ich erweiter mein altes Packet entsprechend (also mit/ohne "", mit/ohne Suchoptimierer, mit/ohne XOR...). Aber TvDataSearcher fass ich nicht an, das ist mir zu heikel. Es ist auch sinnfrei das einzubauen solange die plugins alle intern mit regex arbeiten. Und die ganze Sache hat Zeit, so schnell kommt ja keine neue Version....

Beitrag von **Til** » 27 Jan 2005, 11:19

Ich dachte nur, dass du wegen der Weißraumproblematik sowieso Regex nutzen willst...

Also meine Wunschliste wäre:

Keine Anführungszeichen, dafür automatische Zusammenfassung: "James Bond OR 007" -> "[James Bond] OR [007]"
AND, OR, NOT. (XOR braucht glaube ich niemand).
Schachtelbare Klammern
Was würde dein Suchoptimierer machen?

Wenn du die Suche nach folgender Schnittstelle baust, dann übernehme ich den Einbau:

Code: Alles auswählen

public class BooleanSearcher {

  public BooleanSearcher(String pattern, boolean caseSensitive,
    ProgramFieldType[] fieldArr)
    throws TvBrowserException;

  public void addMatches(ChannelDayProgram dayProg,
    List programList)
    throws TvBrowserException;

}

Wenn du lieber ne andere Schnittstelle willst, dann können wir die natürlich auch ändern...

Beitrag von **Til** » 27 Jan 2005, 11:27

Die Plugins nutzen übrigens die util.ui.SearchForm mit ihren util.ui.SearchFormSettings. Da drin ist alles gekapselt. Die Plugins müssen sich um nichts mehr kümmern.

pumpkin · Beitrag von **pumpkin** » 27 Jan 2005, 12:03

OKay...

Keine Anführungszeichen, dafür automatische Zusammenfassung: "James Bond OR 007" -> "[James Bond] OR [007]"

Noch nicht drin, aber machbar. Im Moment macht er aus "James Bond OR 007" => "James AND Bond OR 007", das kann man aber bestimmt irgendwie ändern. Ich füg einfach selbst beim Bau der Logik die "-Zeichen/Objekte ein.

AND, OR, NOT. (XOR braucht glaube ich niemand).
Schachtelbare Klammern

ist beides drin.

Was würde dein Suchoptimierer machen?

- Wenn ein Wort 2x vorkommt nur eine indexOf()-Suche machen. (Also z.B. bei "(James AND Bond) OR (James AND 007)" nur einmal nach "James" suchen)

- Intern eine AND/OR-Kette nicht mehr als "wort AND (wort AND (wort AND wort))" sondern als "wort AND wort AND wort AND wort" verwalten weil:

- Die AND-Ketten (wort AND wort AND wort AND....) absteigend nach der Länge der Wörter sortieren. Wenn eines der Wörten nicht gefunden wird bricht die Suche ab. Wenn ich zuerst nach den langen Wörtern suche ist die Wahrscheinlichkeit für einen schnellen Abbruch höher.

- Die OR-Ketten andersrum sortieren. (ein Treffer reicht ja schon)

- Die Suche Begriffen mit Leerstellen zuerst durch AND und dann erst durch regex jagen (Damit ich nicht auf " " <=> " " <=> "\t" reinfalle) (Keine Angst das geht schnell,.. wenn die Suche nicht gerade auf "der die das" läuft.)

- Evtl auch die Sortierung innerhalb von Logik-bäumen umbauen, aber ich glaub nicht das die Suchbegriffe so komplex werden... oder ?

Ob das alles was bringt hängt schwer von den Suchbegriffen ab. Wenn eh nur sehr einfaches Zeug ansteht hat's keinen Sinn. Aber bei komplexeren Sachen könnte es schon was bringen. Sind allerdings alles Heuristiken, das kann alles schwer nach hinten lossgehen..

Til hat geschrieben: Wenn du die Suche nach folgender Schnittstelle baust

Kein Problem, werd ich hinbekommen. Wird aber 3-4 Tage dauern, habe Stress mit meinem Rechner und meinem Plugin.

Wieso geht der BBCode jetzt nicht mehr ? Ich hab doch "BBCode in diesem Beitrag deaktivieren" ausgeschaltet und "BBCode ist an" steht auch da....

Beitrag von **Til** » 27 Jan 2005, 12:31

Der Suchoptimierer hört sich gut an!

Die Umsortierung des Suchbaums kann man wohl weglassen. So komplex werden die Anfragen nicht werden und das wäre nur eine Quelle für undurchschaubare Bugs.

Dein BBCode ging nicht, weil du "[/quote=Til]" anstatt "[/quote]" geschrieben hattest. (Schließende Tags haben keine Parameter). Ich habs repariert.

Wegen der 3-4 Tage: Laß dir ruhig Zeit! Ich hab eh erst ab dem 10.02. Zeit und außerdem gibt es bei uns keinen Termindruck. Soll ja Spaß machen.

Was mir noch einfällt: Könntest du statt "AND", "OR" und "NOT" auch die C/Java-Syntax ("&&", "||" und "!") zulassen? Oder wäre das ein größeres Ding?

Beitrag von **Til** » 27 Jan 2005, 12:35

Oder laß lieber das "!" weg. Das könnte zu Problemen führen, wenn jemand nach "Otto! Der Film" suchen will, oder so...

pumpkin · Beitrag von **pumpkin** » 27 Jan 2005, 12:45

Til hat geschrieben: Dein BBCode ging nicht, weil du "[/quote=Til]" anstatt "[ / quote ]" geschrieben hattest. (Schließende Tags haben keine Parameter). Ich habs repariert.

Irgendwann lern ichs. Danke.

Til hat geschrieben: Was mir noch einfällt: Könntest du statt "AND", "OR" und "NOT" auch die C/Java-Syntax ("&&", "||" und "!") zulassen? Oder wäre das ein größeres Ding?

Das ist kein Problem.

Eine Bemerkung noch: Steuerzeichen (AND, OR, NOT, &&, (, ),...) sollten links und rechts ein Leerzeichen haben. Sonst geht sowas "Wort AND (Wort OR Wort)" schief. "(Wort" wäre ja auch ein Begriff nach dem man suchen könnte. Oder ich erweitere einfach alle Zeichen, also ")" => " ) ". Nur dann kann man nicht mehr nach "Wort_mit_klammer)" suchen. Oder wir bauen doch "-Zeichen ein. Das halte ich für am sinnvollsten. Die "-Zeichen innerhalb eines Suchwortes müssten allerdings escaped werden, z.B. mit " .... ?

pumpkin · Beitrag von **pumpkin** » 27 Jan 2005, 12:48

Was wäre mit:

"arnold and the chipmunks" als Suche ? das and würd ich als Steuerzeichen sehen.

Beitrag von **Til** » 27 Jan 2005, 12:55

Du kannst ruhig die Anführungszeichen zulassen. Wenn man sie jedoch nicht setzt, dann sollten sie automatisch gesetzt werden.

Wegen "arnold and the chipmunks": Du könntest verlangen, dass die Schlüsselwörter groß geschrieben werden müssen...

pumpkin · Beitrag von **pumpkin** » 15 Feb 2005, 21:05

Stand der Dinge:

AND, &&, OR, ||, NOT, (, ) sind implementiert (Grossschreibung beachten). Beliebig tiefe Verschatelungen sind möglich. Die Zeichen ".", """ und "," werden rausgefiltert. Der Optimierer holt einiges als Dummheiten wieder raus, aber nicht alles. Leerzeichen werden immer als \s interpretiert.

Beispiele (vorne der String, hinten in Langform)

Wort1 Wort2 == .*(Wort1\sWort2).*

Fehlt vor den Klammern ein op wird ein AND eingebaut:
Wort1 (Wort2 AND Wort3) == Wort1 AND (Wort2 AND Wort3)

"-gelten nicht:
Wort1 "Wort2 AND Wort3" == Wort1 Wort2 AND Wort3 == .*(Wort1\sWort2).* AND Wort3

Til setzt das ganze unter tvbrowser.core.searcher.booleansearch ins CVS ein.