Najlepsza struktura danych w C++, aby znaleźć ciąg w słowniku

Question

Jestem początkującym w C++. Czy ktoś może mi powiedzieć najlepszą strukturę danych w C++ do przechowywania wszystkich słów w słowniku i znaleźć, czy słowo jest obecne w słowniku. Wiem, że tabele mieszania są najlepsze, ale nie wiem, która struktura danych je wykorzystuje?

Dziękuję bardzo z góry.

Answer 1

Twoja standardowa biblioteka implementacji C++ może mieć unordered_set lub hash_set. Zasadniczo są to ta sama rzecz; pierwsza jest częścią nadchodzącego standardu C++ 0x i jest obsługiwana przez niektóre z najnowszych kompilatorów, druga pochodzi z oryginalnego SGI STL i jest zawarta w wielu standardowych implementacjach bibliotek.

Answer 2

hash_map, jeśli masz go w swojej bibliotece kompilatora C++ (np. GNU C++ lub Microsoft Visual C++). Jeśli używasz innego, mniej rozpowszechnionego kompilatora, podejrzewam, że mimo wszystko możesz znaleźć przyzwoitą implementację strony trzeciej w postaci hash_map.

Nadchodzący standard C++ wywołuje zamiast tego tę samą strukturę danych: std::unordered_map.

Jeśli nie chcesz kojarzyć żadnych informacji ze słowami w słowniku, po prostu zapisz, czy słowo jest w nim obecne, możesz użyć odmian _set (zamiast _map) powyższej struktury danych wpisz nazwy.

Oczywiście wszystkie one są szablonami (tak jak wszystkie pojemniki w standardowej bibliotece C++), więc trzeba je odpowiednio utworzyć za pomocą typowej składni szablonu.

Answer 3

Jeśli jedynym wymaganiem jest ustalenie, czy słowo zawiera się w stale zmieniającym się słowniku, bez potrzeby podawania jakichkolwiek innych informacji o słowie, (na przykład sprawdzanie pisowni), wówczas Bloom filter jest wydajnym struktura danych dla tego zadania.

Jeśli istnieją inne dane, które należy powiązać z każdym słowem, które należy wyszukać, std::map jest dobrym punktem początkowym ogólnego przeznaczenia.

Jeśli wymagane jest automatyczne uzupełnianie (po wprowadzeniu częściowego słowa), można użyć Prefix tree (trie).

Answer 4

Hashe są całkiem dobre, ale najlepszą strukturą jest trie. Możesz dostać trie z <ext/pb_ds/assoc_container.hpp> w GCC. Zobacz 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; 
} 

Tylko map -jak funkcjonalność, a nie czysta set, jest przewidziane. W powyższym przykładzie dodałem manekina int jako dane do odwzorowania ... nie powinno to za bardzo szkodzić.

To, co jest nie tak, nie zadziała na zewnątrz GCC.

Z drugiej strony, non -standard tabeli mieszania (nie std:: lub ext:: cokolwiek) pozwoli Ci znaleźć tylko przybliżone wyniki, to znaczy, aby szukać wśród sum kontrolnych słów zamiast samych słów. To byłoby najszybsze i najbardziej kompaktowe rozwiązanie. Słowniki oparte na Bloom filters mogą zawierać wiele tysięcy słów w kilku kilobajtach.

Answer 5

Jeśli chcesz przetestować swoje własne rozwiązanie, a Twój słownik jest poprawiony, dobrym pomysłem jest perfect hash. Gwarantuje stały czas wyszukiwania.

Answer 6

Wolałbym używać Trie. Trie będzie dobrą strukturą danych do budowy wydajnego pamięciowo słownika z szybkimi odnośnikami i tak, autouzupełnianie.

Wyobraź sobie, że jest to hashtable, zapewniające szybkie wyszukiwanie par klucz-wartość (lub po prostu wyszukiwanie kluczy), ale w przeciwieństwie do hashtable pozwala na iterację po kluczach w posortowanej kolejności.

Proszę odnieść się do Trie - Wiki w celu uzyskania dalszych informacji/odniesienia.