C++中用于在字典中查找字符串的最佳数据结构

Question

我是一名C++初学者。有人能告诉我在C++中用于存储字典中所有单词并查找单词是否存在的最佳数据结构吗？我知道哈希表是最好的选择，但我不知道哪种数据结构使用它们？

非常感谢您的帮助。

- brett

---

标准库提供了像maps、sets等C++数据结构。那么，哪种数据结构最适合搜索字符串呢？我将读取所有字符串s并进行搜索。 - brett

Answer 1

你的C++实现标准库可能有unordered_set或hash_set。它们本质上是相同的；前者是即将发布的C++0x标准的一部分，并受到一些最新编译器的支持，后者来自原始的SGI STL，并包含在许多标准库实现中。

- James McNellis

---

哈希表（hash_set）或无序集合（unordered_set）是标准库的一部分吗？ - brett

@brett：hash_set: 官方的？没有。但是许多标准库的实现（包括Visual C++和libstdc++）都包括它。 unordered_set：目前还没有。当C++0x在2011年获批时，它将成为标准库的一部分。一些标准库的实现（例如Visual C++ 2010库）包括它。 - James McNellis

我可以在我的Linux编译器中使用它吗？G++？如果不能，那么最好的数据结构是什么？ - brett

通常情况下，libstdc++与g++一起使用，所以很可能可以。我不经常使用g ++，所以无法确定。您可以试试看。 - James McNellis

@brett，正如我的答案所指出的，GNU C++和Microsoft Visual C++都提供了hash_map(有关详细信息请参见我指向的维基百科条目)--当然，如果从我的答案中不清楚的话，还提供了hash_set。如果你需要在任何符合标准的C++上运行而没有添加组件/库，则std::map(或者如果你仅仅想要存在/不存在信息，而没有每个单词的辅助数据，则使用std::set)是唯一的选择，但这不是一个哈希映射[或集合;-)]。旧的（仍然当前）C++标准中没有哈希数据结构。 - Alex Martelli

Answer 2

哈希表很不错，但最好的数据结构是trie（字典树）。你可以从GCC的<ext/pb_ds/assoc_container.hpp>获取trie。详见在线参考资料。

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

仅提供类似于map的功能，而不是纯粹的set。在上面的示例中，我添加了一个虚拟的int作为要映射到的数据……这不会对其造成太大的影响。

真正有问题的是，在GCC之外这样做行不通。

另一方面，一种非标准哈希表（不是std::或ext::等）将允许您仅查找近似匹配，即在单词的校验和之间搜索而不是单词本身。这将是最快，最紧凑的解决方案。基于Bloom过滤器的字典可以在几千字节内包含许多单词。

- Potatoswatter

---

为什么它在GCC之外不能工作？没有办法将这些库导入到Visual Studio（CL编译器）中吗？ - Yechiel Labunskiy

@YechielLabunskiy 这个文件可以直接使用GCC进行包含。如果它不依赖于任何GCC扩展或触发任何MSVC错误，那么它可能也可以在MSVC中工作。这值得一试。但你需要将其视为一个独立的第三方库，并监控其更新。 - Potatoswatter

Answer 3

哈希表，如果你的C++编译器库中有它（例如GNU C++或Microsoft Visual C++）。 如果你使用其他不太常见的编译器，我猜你仍然可以找到一个不错的第三方实现hash_map。

即将发布的C++标准将把这个数据结构称为std::unordered_map。

如果你不想在字典中与任何单词关联信息，只需记录单词是否存在，你可以使用上述数据结构类型的_set（而不是_map）变体。

当然，它们都是模板（就像C++标准库中的所有容器一样），所以您需要使用典型的模板语法来实例化它们。

- Alex Martelli

---

但我认为他最好使用一组单词，而不是一个关联键值容器的映射。正如詹姆斯所说，任何集合实现都应该足够。 - Hernán

@Hernán，正如我所提到的，如果他只需要存在/不存在信息，则hash_set或unordered_set就足够了——如果他需要记录任何辅助信息，那么..._map变体将更好（并且同样有效）。 - Alex Martelli

Answer 4

我建议使用Trie数据结构。Trie是一种良好的数据结构，可用于构建内存高效的字典，并提供快速查询和自动完成功能。

可以将其视为哈希表，提供快速查找键值对（或仅查找键），但不同于哈希表，它允许您按排序顺序迭代键。

请参考Trie - Wiki了解更多信息和参考资料。

- josh

Answer 5

如果唯一的要求是判断一个单词是否包含在一个永不改变的字典中，而不需要任何关于该单词的其他信息（例如拼写检查），那么Bloom过滤器是用于此任务的高效数据结构。

如果有其他数据需要与每个需要查找的单词相关联，std::map是一个很好的通用起点。

如果需要自动完成（当输入了部分单词时），可以使用前缀树（trie）。

- rwong

---

布隆过滤器是一种概率性数据结构；它不能给出明确的是/否答案。虽然可能存在误判，但不会漏判。字典树也是一个好主意。 - Billy ONeal

Answer 6

如果你愿意自己动手解决问题，并且你的字典是固定的，那么完美哈希是一个不错的选择。它保证了常数级别的查找时间。

- Mark Ransom

---

我在一两年前遇到了这个确切的问题（生成固定字典），很失望地发现完美哈希几乎需要一个双层数据结构，因此每次查找需要多次内存读取。结果比普通的链式哈希表更慢。 - Jason Orendorff

顺便说一下，这是我最终编写用于生成表格的代码：http://hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/qsgen.py#l1488，以及用于探测它的代码：http://hg.mozilla.org/tracemonkey/file/e555673c8119/js/src/xpconnect/src/xpcquickstubs.cpp#l70。实际上，它会生成一些长度为3的链（但很少有查找需要遍历任何链）。 - Jason Orendorff