Bool'sche Suche
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.
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.
-
- Gold Member
- Beiträge: 236
- Registriert: 29 Dez 2004, 10:52
- Wohnort: Vichten/Luxemburg
- Kontaktdaten:
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)
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)
-
- Gold Member
- Beiträge: 236
- Registriert: 29 Dez 2004, 10:52
- Wohnort: Vichten/Luxemburg
- Kontaktdaten:
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.... )
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.... )
-
- Gold Member
- Beiträge: 236
- Registriert: 29 Dez 2004, 10:52
- Wohnort: Vichten/Luxemburg
- Kontaktdaten:
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....
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....
Ich dachte nur, dass du wegen der Weißraumproblematik sowieso Regex nutzen willst...
Also meine Wunschliste wäre:
Wenn du lieber ne andere Schnittstelle willst, dann können wir die natürlich auch ändern...
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?
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;
}
-
- Gold Member
- Beiträge: 236
- Registriert: 29 Dez 2004, 10:52
- Wohnort: Vichten/Luxemburg
- Kontaktdaten:
OKay...
- 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..
Wieso geht der BBCode jetzt nicht mehr ? Ich hab doch "BBCode in diesem Beitrag deaktivieren" ausgeschaltet und "BBCode ist an" steht auch da....
- 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?
- 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..
Kein Problem, werd ich hinbekommen. Wird aber 3-4 Tage dauern, habe Stress mit meinem Rechner und meinem Plugin.Til hat geschrieben: Wenn du die Suche nach folgender Schnittstelle baust
Wieso geht der BBCode jetzt nicht mehr ? Ich hab doch "BBCode in diesem Beitrag deaktivieren" ausgeschaltet und "BBCode ist an" steht auch da....
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?
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?
-
- Gold Member
- Beiträge: 236
- Registriert: 29 Dez 2004, 10:52
- Wohnort: Vichten/Luxemburg
- Kontaktdaten:
Irgendwann lern ichs. Danke.Til hat geschrieben: Dein BBCode ging nicht, weil du "[/quote=Til]" anstatt "[ / quote ]" geschrieben hattest. (Schließende Tags haben keine Parameter). Ich habs repariert.
Das ist kein Problem.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?
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 " .... ?
-
- Gold Member
- Beiträge: 236
- Registriert: 29 Dez 2004, 10:52
- Wohnort: Vichten/Luxemburg
- Kontaktdaten:
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.
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.