Ich bin ein Anfänger in C++. Kann jemand mir eine beste Datenstruktur in C++ sagen, um alle Wörter in einem Wörterbuch zu speichern und festzustellen, ob ein Wort im Wörterbuch vorhanden ist. Ich weiß Hash-Tabellen sind die besten, aber ich weiß nicht, welche Datenstruktur sie verwendet?Beste Datenstruktur in C++, um eine Zeichenfolge in einem Wörterbuch zu finden
Vielen Dank im Voraus.
Die Standardbibliothek Ihrer C++ - Implementierung kann unordered_set oder hash_set haben. Sie sind im Wesentlichen das Gleiche; Das erste ist Teil des bevorstehenden C++ 0x-Standards und wird von einigen der neuesten Compiler unterstützt, letzteres stammt aus dem ursprünglichen SGI-STL und ist in vielen Standard-Bibliotheksimplementierungen enthalten.
Ist hash_set oder unordered_set Teil der Standardbibliothek? – brett
@brett: 'hash_set': Offiziell? Nein. Aber viele Standard-Bibliothek-Implementierungen (einschließlich Visual C++ und libstdC++) enthalten es. 'unordered_set': Noch nicht. Es wird ein Teil der Standardbibliothek sein, wenn C++ 0x irgendwann 2011 genehmigt wird. Einige Standardbibliothek-Implementierungen (z. B. die Visual C++ 2010-Bibliothek) enthalten es. –
Kann ich es in meinem Linux-Compiler verwenden? G ++? Wenn nicht, was ist die beste Datenstruktur? – brett
hash_map, wenn Sie es in Ihrer C++ - Compiler-Bibliothek (z. B. GNU C++ oder Microsoft Visual C++) haben. Wenn Sie einen anderen, weniger verbreiteten Compiler verwenden, vermute ich, dass Sie trotzdem eine anständige Implementierung von hash_map von Drittanbietern finden können.
Der bevorstehende C++ - Standard ruft stattdessen dieselbe Datenstruktur std::unordered_map auf.
Wenn Sie keine Informationen mit Wörtern in Ihrem Wörterbuch verknüpfen möchten, notieren Sie nur, ob ein Wort darin vorhanden ist oder nicht, Sie können die _set (statt) Variationen der obigen Datenstruktur verwenden Namen eingeben.
Natürlich sind sie alle Vorlagen (wie alle Container in der C++ - Standardbibliothek), daher müssen Sie sie mit der typischen Vorlagensyntax entsprechend instanziieren.
Aber ich denke, er wird besser mit einer Reihe von Worten, nicht eine Karte, die ein assoziativer Schlüssel-Wert-Container ist. Wie James sagte, sollte jede Set-Implementierung ausreichen. –
@ Hernán, wie ich bereits erwähnte, wenn er nur die Anwesenheits-/Abwesenheitsinformationen benötigt, reicht 'hash_set' oder' ungeordnet_set' - wenn er jemals irgendwelche Hilfsinformationen aufzeichnen muss, dann werden die '..._ map' Varianten verwendet besser (und genauso effizient). –
Wenn die einzige Anforderung ist, zu entscheiden, ob ein Wort in einem sich niemals ändernden Wörterbuch enthalten ist, ohne andere Informationen über das Wort zu benötigen (z. B. eine Rechtschreibprüfung), dann ist Bloom filter ein effizienter Datenstruktur für diese Aufgabe.
Wenn zu jedem Wort, das nachgeschlagen werden muss, weitere Daten zugeordnet werden müssen, ist std::map ein guter allgemeiner Startpunkt.
Wenn eine automatische Vervollständigung erforderlich ist (wenn ein Teilwort eingegeben wurde), kann ein Prefix tree (trie) verwendet werden.
Ein Bloom-Filter ist eine probabilistische Datenstruktur; es kann Ihnen keine definitive Ja/Nein-Antwort geben. Falsche Positive sind möglich, falsche Negative hingegen nicht. Der Trie ist jedoch eine gute Idee. –
Hashes sind ziemlich gut, aber die beste Struktur ist eine trie. Sie können einen Trie von <ext/pb_ds/assoc_container.hpp> in GCC erhalten. Siehe the online reference.
#include <ext/pb_ds/assoc_container.hpp>
#include <string>
#include <iostream>
int main() {
pb_ds::trie< std::string, int > dict;
dict.insert(std::make_pair("hello", 3));
std::cerr << (dict.find("hello") != dict.end()) << std::endl;
std::cerr << (dict.find("goodbye") != dict.end()) << std::endl;
}
Nur map -ähnlichen Funktionalität, kein reines set, vorgesehen. In dem obigen Beispiel habe ich einen Dummy int als Daten hinzugefügt, um ... zuzuordnen, es sollte nicht wirklich viel weh tun.
Was tut weh ist, dass dies nicht außerhalb von GCC funktioniert.
Auf der anderen Seite, ein nicht -Standard Hash-Tabelle (nicht std:: oder ext:: etwas) erlaubt es dir, nur ungefähre Übereinstimmungen zu finden, das heißt unter Prüfsummen von Wörtern anstelle der Worte selbst zu suchen. Das wäre die schnellste und kompakteste Lösung. Wörterbücher basierend auf Bloom filters können viele tausend Wörter in wenigen Kilobyte enthalten.
Wie funktioniert es nicht außerhalb von GCC? Es gibt keine Möglichkeit, diese Bibliotheken in Visual Studio (CL-Compiler) zu importieren? –
@YechielLabunskiy Die Datei ist einfach in GCC enthalten. Es könnte in MSVC funktionieren, wenn es nicht von irgendwelchen GCC-Erweiterungen abhängt oder irgendwelche MSVC-Fehler auslöst. Es ist sicherlich einen Versuch wert. Sie müssen es jedoch als separate Drittanbieterbibliothek behandeln und es auf Aktualisierungen überwachen. – Potatoswatter
Wenn Sie bereit sind, Ihre eigene Lösung zu rollen und Ihr Wörterbuch fest ist, ist ein perfect hash ein guter Weg zu gehen. Es garantiert eine konstante Nachschlagezeit.
Ich hatte dieses genaue Problem (das Erzeugen fester Wörterbücher) vor ein oder zwei Jahren und war enttäuscht zu finden, dass perfektes Hashing praktisch eine zweistufige Datenstruktur und daher mehrere Speicherlesevorgänge pro Nachschlagen erfordert. Es endet langsamer als eine einfache alte Hash-Tabelle mit Verkettung. –
FWIW, hier ist der Code, den ich geschrieben habe, um die Tabelle zu generieren: http://hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/qsgen.py#l1488 und um es zu untersuchen: http : //hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/xpcquickstubs.cpp#l70 In der Praxis erzeugt es ein paar Ketten, die 3 Einträge lang sind (einige Nachschlagewerke müssen jedoch irgendwelche Ketten laufen) . –
Ich würde lieber eine Trie verwenden. Ein Trie wird eine gute Datenstruktur für die Erstellung eines Speicher-effizienten Wörterbuchs mit schnellen Suchvorgängen und, ja, Autovervollständigung sein.
Stellen Sie sich eine Hashtabelle vor, die eine schnelle Suche nach Schlüssel/Wert-Paaren ermöglicht (oder nur nach Schlüsseln sucht), aber im Gegensatz zu einer Hashtabelle können Sie die Schlüssel in sortierter Reihenfolge durchlaufen.
Weitere Informationen/Referenz finden Sie unter Trie - Wiki.
Es gibt C++ DS von der Standard-Bibliothek zur Verfügung gestellt wie Karten, Sets usw. Also das ist die beste DS nach einer Zeichenfolge zu suchen. Ich werde alle Saiten lesen und suchen. – brett