3. Wildcards in std::set Suche

Wildcards in std::set Suche

  • T

    Hallo,

    ich habe eine Struktur, die erlaubte Statements enthält.
    Es handelt sich um ein std::set, da doppelte Einträge nicht vorkommen sollen und diese Liste sehr groß werden kann, weswegen ein Container mit binary tree search Voraussetzung ist.

    Dieses set kann zum Beispiel folgendes enthalten:

    Hallo
    Huhu
    Bla
    Em*
    Jaja

    wobei alle Statements erlaubt sind, die mit Em anfangen.
    Nur wie soll ich nach sowas suchen?

    Wenn ein Statement wie "Hallo" reinkommt, suche ich einfach mittels std::set::find.

    Kommt nun aber ein Statement wie "Employee" rein, werde ich mit der Standardsuche natürlich kein Ergebnis erzielen.

    Hat jemand eine Idee, wie ich sowas anstellen könnte?
    Eine schnelle Lösung wäre ja, beim Einlesen des Sets alle Einträge mit '*' in einem anderen Set zu speichern (oder std::vector) und wenn im ersten Set nichts gefunden wird, mit einer normalen For-Schleife das zweite Set zu durchsuchen:

    /*
Set2=
Em (das Sternchen würde ich abschneiden)
*/

for (int i = 0; i < set2.size(); ++i)
{
    // wenn Statement mit set2[i] anfängt, dann mache irgendwas
    break;
}

    Das sollte erst mal funktionieren, kann aber wiederum langsam sein, wenn set2 einige Millionen Einträge hat (was passieren kann).

    Außerdem würde das nur funktionieren, wenn ich ein einziges Wildcard-Zeichen zulasse und nach dem Wildcard-Zeichen Schluss ist, Konstrukte wie

    Em*ee
    Em*a*
    usw

    würden nicht funktionieren.

    Hat jemand eine bessere Idee, wie ich in diesem Fall mit Wildcards umgehen könnte?

    0
  • P

    nutz was das Regular Expressions kann und konvertiere die Wildcards ... oder nutz was das Wildcards kann.

    zB Qt QRegExp ... das kann beides. Gibts aber vielleicht auch mit weniger Abhängigkeiten in einer kleineren lib ... schau doch mal bei boost + regexp (google)

    0

  • Vielleicht ist std::set nicht der geeignete Container für dein Problem, guck dir mal folgende Datenstrukturen an, vielleicht sind sie besser geeignet:

    Trie

    Edit:
    Suffixbaum gehört wohl nicht hierhin o.O

    0
  • T

    An regular expressions habe ich auch schon mal gedacht, muss mal gucken. Ich programmiere normalerweise immer in Qt, für dieses Projekt geht das aber nicht (es soll eine Wrapper-DLL werden und die möglichst keine Abhängigkeiten haben).

    Boost ist eventuell eine Möglichkeit, muss ich mal genauer schauen. Die Suche sollte wirklich schnell sein, deswegen hatte ich erst einmal ein std::set versucht, da es ja binary tree search implementiert.

    0
  • L

    Klingt irgendwie irgendwie wie eine Aufgabe für einen Lexer. Dafür gibt es diverse Standardlösungen.

    Grundidee: Für jeden String in deinem set einen entsprechenden DFA bauen. Anschließend alle DFAs zu einen Gesamt-DFA vereinigen.

    Sobald der Gesamt-DFA steht, können ankommende Anfragen in O(n) bedient werden, wobei n die Länge der Anfrage bezeichnet. Dafür ist das Aufbauen des Gesamt-DFAs vermutlich recht teuer.

    0
  • B

    Mal ein Schnellschuss:

    template<typename Range>
struct WildcardLess
{
    bool operator()(const Range& lh, const Range& rh) const
    {
        typedef typename Range::const_iterator Iter;
        for(Iter il = lh.begin(), lhe = lh.end(), 
            ir = rh.begin(), rhe = rh.end();
            il != lhe && ir != rhe; ++il, ++ir)
        {
            if (Less(*il, *ir)) return true;
            else if (Less(*ir, *il)) return false;
        }
        return false;
    }
private:
    static bool Less(char lh, char rh)
    {
        if (lh == '*' || rh == '*') return false;
        return lh < rh;
    }
};

int main(int argc, char* argv[])
{
    using namespace std;
    typedef set<string, WildcardLess<string> > wset;
    wset s;
    s.insert("hallo");
    s.insert("huhu");
    s.insert("bla");
    s.insert("em*");
    s.insert("jaja");
    s.insert("ema");

    copy(s.begin(), s.end(), ostream_iterator<string>(cout, "\n"));
    wset::const_iterator i = s.find("emerald");
    if (i != s.end())
        cout << endl << *i;
    return 0;
}

    bla
em*
hallo
huhu
jaja

em*

    Den WildCardLess:operator() kann man sicher auch noch schöner gestalten.
    Und unterschiedlich lange Strings mit gleichem Anfang sind wohl gleich. Aber das bekommst du sicher noch hin:)
    Wenn Du die statements nur einmal einliest und dann nur noch suchst, ist wahrscheinlich ein sortierter Vector mit binärer Suche schneller. Gibt es auch fertig, z.b. AssocVector oder (ich glaube) irgendwo versteckt in boost.

    0
  • T

    Hallo brotbernd,

    danke für den Tipp, interessante Lösung. Werde ich mir gleich mal genauer anschauen!!!
    🙂

    0
  • L

    Das wird nicht funktionieren. Mal abgesehen, dass es sowieso nicht für sowas wie

    Em*ee
Em*a*
usw

    funktionieren kann, klappt es nichtmal mit ausschließlich abschließenden Wildcards. So erzeugt

    s.insert("hallo");
s.insert("huhu");
s.insert("bla");
s.insert("ema");
s.insert("jaja");
s.insert("em*");

    das Set {"bla", "ema", "hallo", "huhu", "jaja"}, in dem "emerald" nicht enthalten ist.

    Imho ist einfach die ganze Idee mit dem std::set schlecht..

    0
  • ?

    life schrieb:

    Sobald der Gesamt-DFA steht, können ankommende Anfragen in O(n) bedient werden, wobei n die Länge der Anfrage bezeichnet. Dafür ist das Aufbauen des Gesamt-DFAs vermutlich recht teuer.

    Tools wie flex und yacc können dir den Quelltext dafür generieren, falls die Worte im Voraus feststehen...

    0
  • T

    Ich benutze ANTLR in dieser ProxyDLL, um Oracle-SQL-Grammatik zu parsen.
    Die Worte im SET stehen nicht fest, sie kommen aus einer Configdatei, die für jeden Anwender unterschiedlich ist.

    Es gibt Configs mit bis zu 260.000 Einträgen, eventuell wird dies sogar noch mehr.
    Deswegen sollen Wildcards eingeführt werden, um die Configdatei ein wenig kleiner zu bekommen.

    Also eine feste Grammatik gibt es nicht, deswegen dachte ich an ein Set (oder vergleichbares mit einer schnellen Suche).

    Der Vorschlag von brotbernd scheint für simple Wildcards (em*) perfekt zu funktionieren, jedenfalls bei meinen bisherigen Tests. Eventuell reicht mir das sogar, wenn ich festlege, das nur diese Form von Configelementen erlaubt ist, dann hätte ich immer noch ein Set mit einer custom binary search, wäre erst einmal in Ordnung.

    Ich werde mir dennoch noch einmal die BOOST library anschauen, vielleicht finde ich schon was komplett fertig implementiertes für meine Zwecke.

    0
  • ?

    TheGrudge schrieb:

    Der Vorschlag von brotbernd scheint für simple Wildcards (em*) perfekt zu funktionieren, jedenfalls bei meinen bisherigen Tests. Eventuell reicht mir das sogar, wenn ich festlege, das nur diese Form von Configelementen erlaubt ist, dann hätte ich immer noch ein Set mit einer custom binary search, wäre erst einmal in Ordnung.

    Ich sehe bei diesem Vorschlag allerdings nicht, dass der erstellte Operator eine Vollordnung der Elemente herstellt. Falls das der Fall ist, führt das dazu, dass std::set früher oder später Blödsinn macht. D.h. Elemente, die eigentlich im set drin sind, werden nicht gefunden und können nicht mehr gelöscht werden.

    Ein weiteres Problem ist, dass der * genau als ein einzelenes Zeichen gematcht wird. Das kann aber vollkommen falsch sein.

    0
  • L

    Ich habe doch schon ein Beispiel aufgezeigt, bei dem brotbernds Quellcode auch bei simplen Wildcards versagt.

    Im Übrigen kann man den Gesamt-DFA natürlich auch dynamisch erzeugen. Das ist nur nicht der normale Einsatzzweck Lexer-Generatoren wie flex. Ggf. müsste man sich hier also selbst was zusammenbauen.

    Wenn du die Reg.Expr. so einschränkst, dass die Wildcards nur am Ende stehen dürfen, dürfte das Gesamt-DFA Aufbauen auch sehr effizient möglich sein (dann sind wir im Prinzip wieder bei DocShoes prefix-trees).

    0
  • T

    Ich habe nun folgenden Testcode, der scheint recht gut zu funktionieren:

    #include <boost/regex.hpp>
#include <iostream>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

bool regExpMatch(const std::string& str1, const std::string& str2)
{
    std::string tmp = str1;
    size_t lookHere = 0;
    size_t foundHere;
    string from("*");
    string to(".*");
    while ((foundHere = tmp.find(from, lookHere)) != string::npos)
    {
        tmp.replace(foundHere, from.size(), to);
        lookHere = foundHere + to.size();
    }
    boost::regex re(tmp);
    boost::match_flag_type flags = boost::match_default;
    return !(boost::regex_match(str2, re, flags));
}

bool myCompare(const string& str1, const string& str2)
{

    if (str1.find("*") != string::npos)
    {
        return regExpMatch(str1, str2);
    }
    else if (str2.find("*") != string::npos)
    {
        return regExpMatch(str2, str1);
    }
    else
    {
        int r = str1.compare(str2);
        return (r < 0);
    }
}

void addItem(set<string> &myset, const string& str)
{
    string tmp = str;
    transform(tmp.begin(), tmp.end(), tmp.begin(), ::toupper);
    myset.insert(tmp);
}

int main()
{
    set<string> allowedStatements;
    addItem(allowedStatements, "schema.");
    addItem(allowedStatements, "Ha*o");
    addItem(allowedStatements, "em*y*");
    addItem(allowedStatements, "aaaaA");
    addItem(allowedStatements, "sshdsjdsdhsdjhsd");

    set<string> searchTerms;
    addItem(searchTerms, "schema.");
    addItem(searchTerms, "bla");
    addItem(searchTerms, "hallllllllllllllllllo");
    addItem(searchTerms, "hausmeister_otto");
    addItem(searchTerms, "employee");

    bool found = false;
    for (set<string>::const_iterator it = searchTerms.begin(); it != searchTerms.end(); ++it)
    {
        cout << "Searching for '" << *it << "'... ";
        found = (binary_search(allowedStatements.begin(), allowedStatements.end(), *it, myCompare));
        cout << (found ? "FOUND!" : "NOT FOUND!") << endl;
    }
}

    Wenn ich nur das '*' Wildcard zulasse, scheine ich mit dieser Lösung eigentlich ganz gut zurecht zu kommen.
    Bis jetzt waren alle Tests positiv, werde aber noch einen CPPUnit-Test schreiben, um die Funktion zu verifizieren.

    0
  • T

    Hmm schade da geht doch noch was schief:

    Searching for 'BLA'... NOT FOUND!
    Searching for 'EMPLOYEE'... NOT FOUND!
    Searching for 'HALLLLLLLLLLLLLLLLLLO'... FOUND!
    Searching for 'HAUSMEISTER_OTTO'... FOUND!
    Searching for 'SCHEMA.'... FOUND!

    Aus irgendeinem Grund scheint das nicht richtig zu matchen.
    Das Problem ist wohl, das ich nicht genau weiß, was ich in der Compare-Funktion zurückliefern soll. Ich liefere FALSE wenn es matched, so ähnlich wie die compare() Funktion von std::string.
    Aber das scheint wohl nicht richtig zu sein?

    0
  • B

    Gleichheit in assoziativen Containern bedeutet Äquivalenz, d.h. weder kleiner noch größer. Ein Element wird also gefunden wenn gilt:

    !(e1 < e2) && !(e2 < e1)

    Schau Dir nochmal eine C++ Referenz an. Was Du da machst (z.B. binary_search in einem set) macht überhaupt keinen Sinn.

    0
  • T

    Hmm irgendwie verstehe ich nicht ganz, warum binary_search mit einem Set keinen Sinn macht. Ich dachte std::set implementiert dies intern, wenn ich std::set::find nutze?

    0
Anmelden zum Antworten