树或平衡二叉搜索树来存储字典？

我想存储英文单词词典（n个单词）并给出一个单词（字符长度为m），词典能够告诉，如果单词存在于词典中或不。这将是一个适当的数据结构？

平衡二叉搜索树？如在C++ STL关联数据结构等集，地图

或

完成对字符串字典树

一些复杂性分析：在平衡BST ，时间将是（log n）的*米（比较2个字符串需要每个字符需要O（m）个时间）

如果在每个节点，我们可以在O（1）时间分支出来，我们可以使用O（m）在每个节点上，我们可以在O（1）中分支时间无效。在每个节点处，最大可能的分支将是26.如果我们想要O（1）在一个节点上，我们将在每个节点的字符上保留一个短的数组索引。这将炸毁空间。在trie中的几个级别之后，分支会减少，所以最好保留下一个节点字符和指针的链表。

什么看起来更实用？任何其他的权衡？

感谢，

来源

2011-06-08 xyz

我想说的是使用Trie，或者更好的方式是使用其更高效的空间表亲Directed Acyclic Word Graph (DAWG)。

它具有与Trie相同的运行时特性（插入，查找，删除），但重叠了常见的后缀以及常见的前缀，这可以大大节省空间。

来源

2011-06-08 13:22:57 luke

感谢您提供指向DAWG的指针 - 这是我的一个新DS。 – xyz 2011-06-08 13:34:54

+1对于Trie数据结构 – brainydexter 2011-06-13 17:19:50

由于OP指定的唯一要求是密钥检索，因此我没有看到为什么Trie是比哈希表更好的数据结构。哈希表比Trie表现得更好，实现起来更简单。在C++ STL的上下文中，你可以使用std :: unordered_set – minism 2013-04-26 04:42:47

二进制搜索将是更容易实现和它一定会涉及到最多几十比较字符串。鉴于您事先知道数据，您可以构建一个平衡二叉树，以便可以预测并轻松理解性能。考虑到这一点，我会使用一个标准的二叉树（可能使用C++的set，因为它通常以树的形式实现）。

来源

2011-06-08 13:20:50

一个简单的解决方案是将dict作为已排序的\ n分隔的单词存储在磁盘上，将其加载到内存中并执行二分搜索。这里唯一的非标准部分是当你进行二分搜索时，你必须向后扫描一个单词的开头。

这是一些代码！（它假定全局wordlist指向加载字典，并wordlist_end这只是加载的字典结束后百分点。

// Return >0 if word > word at position p. 
// Return <0 if word < word at position p. 
// Return 0 if word == word at position p. 
static int cmp_word_at_index(size_t p, const char *word) { 
    while (p > 0 && wordlist[p - 1] != '\n') { 
    p--; 
    } 
    while (1) { 
    if (wordlist[p] == '\n') { 
     if (*word == '\0') return 0; 
     else return 1; 
    } 
    if (*word == '\0') { 
     return -1; 
    } 
    int char0 = toupper(*word); 
    int char1 = toupper(wordlist[p]); 
    if (char0 != char1) { 
     return (int)char0 - (int)char1; 
    } 
    ++p; 
    ++word; 
    } 
} 

// Test if a word is in the dictionary. 
int is_word(const char* word_to_find) { 
    size_t index_min = 0; 
    size_t index_max = wordlist_end - wordlist; 
    while (index_min < index_max - 1) { 
    size_t index = (index_min + index_max)/2; 
    int c = cmp_word_at_index(index, word_to_find); 
    if (c == 0) return 1; // Found word. 
    if (c < 0) { 
     index_max = index; 
    } else { 
     index_min = index; 
    } 
    } 
    return 0; 
}

这种方法的一个巨大优势是，字典存储在人类可读的方式并且你不需要任何花哨的代码来加载它（分配一块内存并一次读取（）它）

如果你想使用一个trie，你可以使用一个包和后缀压缩的表示形式，下面是Donald Knuth的学生Franklin Liang的一个链接，他在论文中写了这个技巧。

http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.123.7018&rep=rep1&type=pdf

它采用了简单的文字字典代表性的存储一半，为您提供了一个线索的速度，并且可以（如文字字典表示）在磁盘上存储整个事情，在一个加载走。

它使用的技巧是将所有trie节点打包到单个数组中，并在可能的情况下将它们交错。除了像常规trie中的每个阵列位置中的新指针（以及词尾标记位）之外，您还可以存储此节点用于的字母 - 这可以让您知道该节点对于您的状态是否有效或者它来自重叠节点。阅读链接的文档以获得更全面更清晰的解释，以及将树状结构包装到此阵列中的算法。

实现所描述的后缀压缩和贪婪包装算法并不是微不足道的，但它很容易。

来源

2011-06-08 14:04:07

如果这是C++，您还应该考虑std::tr1::unordered_set。（如果你有C++ 0x，你可以使用std::unordered_set。）

这只是在内部使用一个哈希表，我会打赌在实践中，它会超出任何树状结构。实施起来也是微不足道的，因为你没有什么可实施的。

来源

2011-06-08 16:56:55 Nemo

+1规定的要求只是快速查找，没有要求重新排序，调整大小，随机访问，插入/删除等。哈希地图非常适合，并且如你所说可能会更快 - 哈希时间通常会跳跃直接到所需的桶，而树需要访问许多中间页面页 - 更多地颠覆缓存。取决于硬件/操作系统/系统负载/字典大小等。 – 2011-06-09 02:00:17

行业标准是将字典存储在散列表中，并具有一个分期O（1）查找时间。空间在行业中并不是至关重要的，特别是由于分布式计算的进步。

散列表是谷歌如何实现其自动完成功能。具体来说，将每个词的前缀作为关键字，并将该词作为哈希表中的值。

来源

2011-06-18 05:31:50

字典中的查找时间是'O（m）'时间（其中'm'是密钥的长度），就像Trie一样。事实上，没有数据结构可以违反最小限制，因为您需要读取整个密钥以确定要读取哪个值。 – semicolon 2017-06-29 15:07:12

树或平衡二叉搜索树来存储字典？

回答

相关问题