C++의 최상위 데이터 구조로 사전에서 문자열 찾기

Question

저는 C++의 초보자입니다. C++에서 모든 단어를 사전에 저장하고 사전에 단어가 있는지 찾아내는 데 가장 적합한 데이터 구조를 말해 줄 수 있습니까? 나는 해쉬 테이블이 최고라는 것을 알고 있지만 어떤 데이터 구조가 그들을 사용하는지 모른다.

대단히 감사합니다.

Answer 1

C++ 구현의 표준 라이브러리에는 unordered_set 또는 hash_set이있을 수 있습니다. 그것들은 본질적으로 같은 것이다. 전자는 앞으로 출시 될 C++ 0x 표준의 일부이며 최신 컴파일러에서 지원되며 후자는 원래 SGI STL에서 제공되며 많은 표준 라이브러리 구현에 포함됩니다.

Answer 2

hash_map, C++의 컴파일러 라이브러리 (예 : GNU C++ 또는 Microsoft Visual C++)에있는 경우 컴파일러가 아닌 다른 컴파일러를 사용하고 있다면 어쨌든 hash_map의 제 3 자 구현을 찾을 수있을 것으로 생각됩니다.

앞으로 나올 C++ 표준에서는 이와 동일한 데이터 구조 std::unordered_map을 대신 호출합니다.

사전에있는 단어와 정보를 모두 연관시키지 않으려면 단어가 포함되어 있는지 여부 만 기록하면됩니다 (_map 대신) _set 변형을 사용할 수 있습니다 이름을 입력하십시오.

물론이 템플릿은 모두 (C++ 표준 라이브러리의 모든 컨테이너로) 템플릿이기 때문에 일반적인 템플릿 구문을 사용하여 적절하게 인스턴스화해야합니다.

Answer 3

단어에 대한 다른 종류의 정보 (예 : 맞춤법 검사기)가 필요없이 절대로 바뀌지 않는 사전에 단어가 포함되는지 여부를 결정하는 유일한 요구 사항은 Bloom filter이 효율적입니다 이 작업을위한 데이터 구조.

각 단어와 연결할 다른 데이터가있는 경우 std::map은 좋은 범용 시작점입니다.

자동 완성이 필요한 경우 (부분 단어를 입력 한 경우) Prefix tree (trie)을 사용할 수 있습니다.

Answer 4

해시는 꽤 좋지만 가장 좋은 구조는 trie입니다. GCC의 <ext/pb_ds/assoc_container.hpp>에서 트라이를 얻을 수 있습니다. the online reference을 참조하십시오. 없는 순수한 set 만 map -like 기능

#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; 
} 

가 제공된다. 위의 예제에서 나는 더미 데이터를 맵에 추가하기 위해 ... int을 추가했다.

GCC 밖에서 작동하지 않는다면 어떤 상처를 입을까요? 한편

하는 비 - 표준 해시 테이블 (안 std:: 또는 ext:: 무엇이든) 만 대신 단어 자체의 단어의 체크섬 중 검색 즉 대략 일치를 찾을 수있다. 그것은 가장 빠르고 가장 컴팩트 한 솔루션이 될 것입니다. Bloom filters을 기반으로하는 사전에는 수 킬로바이트에 수천 단어가 포함될 수 있습니다.

Answer 5

독자적인 솔루션을 구형하고 사전이 수정되어있는 경우 perfect hash은 좋은 방법입니다. 상수 조회 시간을 보장합니다.

Answer 6

트라이를 사용하는 것이 좋습니다. Trie는 빠른 검색 및 예, 자동 완성을 사용하여 메모리 효율적인 사전을 작성하는 데 적합한 데이터 구조입니다.

해시 테이블로 생각하면 키 - 값 쌍 (또는 키 조회)을 빠르게 검색 할 수 있지만 해시 테이블과 달리 정렬 된 순서로 키를 반복 할 수 있습니다.

자세한 내용은/Trie - Wiki을 참조하십시오.