Wörterbuch mit C++ selbst erstellen



  • Hallo zusammen, ich hoffe ich bin in diesem Unterforum mit meiner Frage richtig...

    Ich möchte zu Übungszwecken ein eigenes Wörterbuch mit C++ aufbauen.

    Ich habe mir ein Textfile erstellt in dem gültige deutsche Wörter gespeichert sind.

    nun möchte ich diese in ein Wörterbuch "umwandeln".
    Ich habe mir das etwa so vorgestellt:
    1. Alle Wörter in einen Vector speichern
    2. Vector sortieren
    3. die Wörter in einen Binary-Search-Tree speichern, um später mit möglichst wenig Überprüfungen sagen zu können, ob eine Buchstabenkombination ein Wort ist oder nicht.

    Ich möchte aber nicht bei jedem Programmstart das ganze Wörterbuch einlesen und sortieren, sondern direkt verfügbar haben. Jetzt stehe ich ein bisschen auf dem Schlauch, wie ich das ganze am besten anpacken soll.

    Wie mache ich es am besten, dass ich dieses Wörterbuch jeweils sofort zur Verfügung habe und nicht jedes mal einen Binary-Search-Tree aufbauen muss?

    Für Anregungen wäre ich dankbar 🙂


  • Mod

    Wenn du die Wörter in deinem sortierten vector hast, bist du doch schon fertig. Suchen in sortierten random access Containern ist auch log(N), genau wie in einem Suchbaum.

    Du hättest natürlich gar nicht erst den vector einlesen oder gar sortieren brauchen, sondern gleich in deinen Baum einlesen können. (map und set sind dir bekannt, oder?)



  • Du könntest die Wörter einmal sortieren und dann sortiert abspeichern. Dann musst du bei Programmstart nur noch Einlesen und kannst dir das Sortieren sparen.

    Aber bevor du dir jetzt so viel Gedanken über die Performance machst, solltest du mal messen, wie lange es *wirklich* dauert. Häufig täuscht man sich da gewaltig und Sachen, von denen man denkt, dass die sehr lange brauchen, gehen in der Praxis dann doch recht fix.



  • Vor allem wenn man sie nur einmal (z.B. beim Programmstart) machen muss...



  • Also, map und set waren mir nicht bekannt, habe ich aber kurz mal angeschaut.

    Vielleicht hole ich ein bisschen aus, damit klar ist, was ich eigentlich genau bezwecken will:
    Ich habe folgendes Ziel:
    Ich will für die Smartphone-App "4 Bilder 1 Wort" eine "Hilfe" erstellen (die auf dem PC ausgeführt wird) als einfaches Konsolenprogramm.
    Für die, die das Spiel nicht kennen: Man kriegt 4 Bilder, die einen Begriff darstellen. Dann kriegt man 12 Buchstaben, von denen man z.B. 5 kombinieren muss um den gesuchten Begriff zu erhalten.
    Ich habe jetzt bereits den Code erstellt, der alle möglichen Kombinationen der gegebenen Buchstaben in der gesuchten Länge erstellt. Da diese Liste natürlich haufenweise Wörter enthält, die nicht existieren, wollte ich diese mit einem Wörterbuch filtern.

    Dieses möchte ich so erstellen:
    Ich speise mehrere Bücher (von Gutenberg) im .txt-Format in ein Konsolenprogramm ein. Dieses formatiert die Wörter (alles Grosbuchstaben, Satzzeichen entfernen) und speist sie, falls sie noch nicht vorhanden sind, in einen Vector ein.

    Diesen Vector möchte ich dann einigermassen sinnvoll sortieren / Baum erstellen oder was auch immer und die ganze Struktur in das andere Programm übernehmen.
    Soweit ich mich da informiert habe, wäre das z.B. mit einer Datenbank möglich. Das wäre aber meiner Meinung nach mit Kanonen auf Spatzen geschossen und ich will mich wenn möglich, da nicht auch noch einarbeiten (ich will ja mein C++ verbessern).

    Für diese erste Art des Wörterbuches wäre es ev. noch möglich, immer am Anfang des Programmes ein Textfile einzulesen.
    In einem zweiten Schritt möchte ich aber das Wörterbuch effizienter machen:
    Ich möchte einen Baum erstellen, wo ein Knoten bis zu 26 Kinder haben kann, also für jeden Buchstaben des Alphabets ein Kind.
    So könnte ich dann einfach einem Character-Pfad folgen. Ist ein Character-Pfad ein existierendes Wort, wäre eine bool-Variable in diesem Knoten auf "true" gesetzt, existiert der Pfad nicht, ist es auch kein gültiges Wort.
    Diese Struktur dann als Textdatei zu exportieren und bei jedem Programmstart des Nutzerprogramms einzulesen, scheint mir ein bisschen kompliziert.

    Deshalb suche ich eine Möglichkeit, eine ganze Datenstruktur zu exportieren, und in einem anderen Programm benutzen zu können, ohne den Umweg über die Textdatei oder eine Datenbank...

    Edit: Es geht natürlich nur darum, ein bisschen zu üben, über Sinn oder Unsinn lässt sich hier natürlich streiten 😉



  • Mach es so:

    1. Lies mit einem std::ifstream und operator>> wörter ein, entferne mit std::remove_if und std::string::erase Satzzeichen aus den Wörtern, konvertiere den String per std::transform mit tolower in Kleinbuchstaben um.
    2. Füge das Wort dann in ein std::unordered_set ein. Ist bei deinem Einsatzzweck massiv schneller als ein Suchbaum, nur eben nicht sortiert. Das set kümmert sich darum dass kein Wort 2x drin steht.
    3. Du kannst das unordered_set ganz leicht fragen ob ein Wort existiert oder nicht, zb. mit count().
    4. Wenn du die Liste speichern möchtest dann schreib doch einfach alle werte aus dem unordered_set (mit den begin()/end() Iteratoren darüber iterieren) zeilenweise in eine Textdatei, dann kannst du sie auch trivial wieder zeilenweise einlesen.


  • Mod

    Das klingt alles übermäßig kompliziert. Ein 26-Äste Baum verändert die Suchkomplexität auch nicht großartig. Von log_2 auf log_26. Dafür müsstest du ihn selber programmieren und dir vermutlich sogar selber Algorithmen ausdenken, da (ich kenne mich nicht 100% aus) einige der Tricks, um Binärbäume schneller zu machen, davon ausgehen, dass jeder Knoten zwei Äste hat.

    Wenn dir Performance beim Lookup wirklich wichtig ist (wie groß kann der Aufwand schon sein? Es gibt vielleicht ein paar tausend bis 10000 Wörter. Das sind nur ~13 Schritte bei einer binären Suche), dann solltest du eher mal einen Hashtable (unordered_set) ausprobieren.

    Es sollte auch ziemlich egal sein, wenn deine Datenstruktur am Programmstart erstellt werden muss. Das sind wie viele Daten? 100kB? Das ist ein Scherz, das ist gar nichts. Auch für ein Mobilgerät. Egal ob du sie sortiert in einen vector einliest oder einen Hashtable neu aufbaust, das braucht bloß Sekundenbruchteile.



  • Danke für deine Antwort.

    Das Ganze, wie du es beschreibst, hat im Prinzip schon funktioniert, ich habe es einfach z.T. ein bisschen anders gelöst.

    Es wird aber eben für den 2. Schritt wichtig, dass ich diesen Baum erstellen und exportieren kann.

    Denn: Habe ich 12 Buchstaben zur verfügung und soll ein Wort mit 8 Zeichen daraus bilden --> gibt das (12!)/(4!) = ca. 20 Mio. Kombinationsmöglichkeiten.
    Diese alle zu speichern und danach jedes Wort zu überprüfen dauert ne Zeit.

    Die Wortkombinationen werden übrigens mit Backtracking gebildet.
    So kann ich dann mit diesem Baum-Wörterbuch (aus dem 2. Schritt) direkt erkennen, dass es keine Wörter gibt, die z.B. mit "XP...." beginnen gibt und somit viele Möglichkeiten ausschliessen.

    Wie gesagt, wie sinnvoll das ganze ist, da lässt sich streiten darüber, es geht nur darum, eine Übung zu machen....

    Das einzige, was ich wirklich wissen möchte ist:
    Wie kann ich ein gebildetes Array, einen gefüllten Baum, oder eine sonstige komplexe Datenstruktur exportieren, um sie in einem anderen Programm verfügbar zu haben, ohne sie jedes mal neu bilden zu müssen?

    Edit: Das war jetzt die Antwort auf deinen Vorposter, da war ich schon am schreiben.
    Die Datenstruktur erstell ich mir zur Not selbst, sollte kein allzu grosses Problem sein.
    Ich möchte wirklich nur wissen, ob es möglich ist, so eine fertige Struktur zu exportieren und falls ja, wie.



  • Wohl garnicht. Außer du legst deine komplette Datenstruktur darauf aus indem sie nur Speicher aus einem eigenen Pool bezieht, keine Zeiger sondern Offsets in diesen Pool verwendet und nur primitive Datentypen speichert. Kurz: Es ist das nicht wert.

    So wäre es mit std::unordered_set wohl am Besten gelöst:

    std::unordered_set<std::string> wordlist;
    fuellen(worldlist);
    
    std::ofstream out("woerterliste.txt");
    for(std::string& s : wordlist)
        out << s << '\n';
    
    ....
    
    std::unordered_set<std::string> wordlist2;
    std::ifstream in("woerterliste.txt");
    std::string cur;
    while(in >> cur)
        wordlist2.insert(cur);
    


  • Hab mal nen kleinen Test geschrieben:

    #include <iostream>
    #include <string>
    #include <vector>
    #include <unordered_set>
    #include <chrono>
    #include <random>
    using namespace std;
    
    unsigned const N_WORDS = 20000000;
    unsigned const WORD_LEN = 8;
    
    vector<string> makeRandomWords()
    {
    	mt19937 gen(time(nullptr));
    	uniform_int_distribution<char> dis('a', 'z');
    
    	vector<string> result;
    	for(unsigned i = 0; i < N_WORDS; ++i)
    	{
    		string curWord;
    		for(unsigned j = 0; j < WORD_LEN; ++j)
    			curWord.push_back(dis(gen));
    		result.push_back(move(curWord));
    	}
    
    	return result;
    }
    
    int main()
    {
    	auto words = makeRandomWords();
    
    	unordered_set<string> wordlist;
    	wordlist.reserve(words.size());
    
    	{
    		unordered_set<string> wordlistNoReserve;
    
    		auto start = chrono::high_resolution_clock::now();
    		for(auto const& word : words)
    			wordlistNoReserve.emplace(word);
    		auto end = chrono::high_resolution_clock::now();
    
    		auto ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    
    		cout << "Inserting " << words.size() << " words took " << ms << "ms (Avarage " <<
    			(ms * 1000 * 1000 / words.size()) << "ns per word) (without reserve)\n";
    	}
    
    	{
    		auto start = chrono::high_resolution_clock::now();
    		for(auto const& word : words)
    			wordlist.emplace(word);
    		auto end = chrono::high_resolution_clock::now();
    
    		auto ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    
    		cout << "Inserting " << words.size() << " words took " << ms << "ms (Avarage " <<
    			(ms * 1000 * 1000 / words.size()) << "ns per word) (with reserve)\n";
    	}
    
    	{
    		size_t antiOptimize = 0;
    		auto start = chrono::high_resolution_clock::now();
    		for(auto const& word : words)
    			antiOptimize += wordlist.count(word);
    		auto end = chrono::high_resolution_clock::now();
    
    		auto ms = chrono::duration_cast<chrono::milliseconds>(end - start).count();
    
    		cout << "Looking up " << words.size() << " words took " << ms << "ms (Avarage " <<
    			(ms * 1000 * 1000 / words.size()) << "ns per word)" << antiOptimize << "\n";
    	}
    }
    

    Das Ergebnis ist bei mir:

    Inserting 20000000 words took 8092ms (Avarage 404ns per word) (without reserve)
    Inserting 20000000 words took 4769ms (Avarage 238ns per word) (with reserve)
    Looking up 20000000 words took 3351ms (Avarage 167ns per word)

    Bist du dir sicher dass 167 Nanosekunden Prüfzeit ovb ein Wort gültig ist zu langsam sind?



  • Woohoa Computer sind shcon geil schnell 😃 🕶



  • gut, dann habe ich das ganze wohl überschätzt. 🙄

    aber liege ich mit meiner Annahme richtig, dass die zweite Variante (mit dem Buchstabenbaum) schneller wäre, zumal sogar bereits beim bilden der Kombinationen grosse Mengen ausgeschlossen werden könnten?

    Danke für eure Hilfe und Anregungen.



  • Schneller als was? Schneller als eine Hashtable (std::unordered_set) ? Vermutlich nicht, die Hashtable macht wortweise etwas Arithmetik/Bitschubserei auf den String und weiß dann im Regelfall direkt ob der String im Set ist.

    Schneller als ein Binärbaum? Möglicherweise. Du hast sehr wenige Schritte beim Lookup dafür hat dein Buchstabenbaum den Nachteil viel Speicher zu verschwenden wenn viele Zweige ungenutzt sind (zb. "test" allein verbraucht etwa 4 * 26 * sizeof(void*) Bytes = 832 Byte bei 64bit), das ist Gift für den Cache. Wenn da viele Cachemisses auftreten kann das schnell langsamer werden. Wenn der Baum hingegen prall gefüllt ist dann ist das wohl schneller als ein Binärbaum.



  • stimmt, das hatte ich nicht bedacht 🙄
    auch wenn die Zeiger nirgends hinzeigen brauchen sie ja Platz...
    Danke für die Mühe.



  • Habe es mal probiert, mir ist beim erstellen erstmal halb der Rechner eingefroren (wohl weil ordentlich geswappt werden musste, 8GB, SSD) und dann war es etwa 3x langsamer als die std::unordered_map.

    Aber immer noch besser als die std::map (Binärbaum, genauer gesagt R/B-Tree), da war der Lookup 13x langsamer.


  • Mod

    Wie viele Datensätze? Selbst mit allen Beugungen wirst du im Deutschen nicht auf > 100,000 Wörter kommen, außer du zählst die hundertausenden von Fachwörtern hinzu, die hier wohl nicht gefragt sind.



  • Naja, bei diesem Spiel können auch glaube ich Eigennamen dazukommen. Aber laut Wikipedia zählt die Standardsprache ~70000 Worte, während sich diese zahl auf bis zu 500000 erhöhen kann, je nach Fachrichtung und Tiefe.

    Quelle


Log in to reply