字典树是一种特殊的树形结构，它实际上是26叉树，26个英文字母。
试着画个示意图
这种树为何叫做字典树，是因为它特别适合单词检索
有很高的检索效率
tries tree
图中的蓝色标记表示——从根节点到这个节点为止的路径字母表示一个真实的单词
这棵树理论上可以非常庞大——试想如果写满10个字母长度的树，将会有 一个字符占一个字节，那将会吃掉
GB 但是实际情况不会这么惨， 真实的单词远远比这个数字要稀疏，这使得字典树有实用性
它可以用于
- 自动补全。一些已经出现过的高频词可以出现在列表中，用于输入自动补全，提高输入效率
- 单词查询 。查字典
- 拼写检查。 类似查字典，输入一个词，在字典树中查不到，可以给出错误提示，并且依照相似度可以做一些提醒功能
如何实现呢？
首先基本上要实现的 API 有
search(string word) —— 查找一个单词
insert(string word) —— 插入一个单词
startWith(string prefix)——判断前缀 prefix 是不是在字典中
下面是用C++实现的概要
主要的核心点是
- 每一层需要维护一个子节点，预留26个孔，如果该分叉有词，这个孔就接上一棵子树，否则就断掉。
- 每个节点维护一个终点标记，表示从根节点到这个终结点是不是一个词
一个字典树节点的内存大小大概是多少呢？
class Trie {
public:
Trie() {
isEnd = false;
for (int i = 0; i < 26; ++i) {
childrens[i] = nullptr;
}
}
void insert(string word) {
Trie* node = this;
for (auto c: word) {
if (node->childrens[c - 'a'] == nullptr) {
node->childrens[c - 'a'] = new Trie();
node = node->childrens[c - 'a'];
} else {
node = node->childrens[c - 'a'];
}
}
node->isEnd = true;
}
bool search(string word) {
Trie *node = searchPrefix(word);
return node && node->isEnd;
}
bool startsWith(string prefix) {
Trie *node = searchPrefix(prefix);
return node != nullptr;
}
protected:
Trie* searchPrefix(string word) {
Trie *node = this;
for (char c: word) {
Trie* p = node->childrens[c - 'a'];
if (!p) {
return nullptr;
}
node = p;
}
return node;
}
private:
bool isEnd;
Trie* childrens[26];
};
Q1- 一本牛津词典全部录入一个字典树，会消耗多少内存？
Q2- 有没有更加节省空间的结构？
Q3-对于汉字，同样的补全技术是什么形状？
第一个问题我们做一个估算 牛津词典大概30万个主词汇，这是查维基百科查到的资料，虽然不知道主词汇是什么东东，假设它就是通常语境中的单词，我们设想单词的平均长度是 8 个字符，
那么 拢共就有 个字符
如果不考虑共享前缀——an 和 ant 共享了 an 这个前缀，因此它们一共只生成了 3个 tries节点
然后看看字典树的数据结构
struct Tries {
Tries* children[26];
bool isEnd;
}
这个数据结构在 64位的电脑上，用sizeof(Tries) 测试到的大小是 216 ——为什么是216？64位机器的指针固定长度是 8, 然后结构体的对齐机制会把大小是 1 字节的 bool型扩充为 8 ，因而它的大小就是
于是 估算到一个粗糙的上界—— MB
实际情况不会这么惨，因为很多单词共享前缀，对单词而言，也许每个单词平均只新产生了3-4个 Tries 节点—— 上述估算可能真正只有 250MB 内存就够了。
这个数字大否？有一点点。因为仅仅是一棵树的size。有没有什么办法进行优化节约空间？肯定是有的，首先结构体内的 children 是硬性的空间开辟，对很多字母和前缀而言，它后面跟随的字母可能只有几种，距离26 还有很多，于是，我们可以用更节约空间的 map结构来代替，二者在搜索效率上虽然是 O(lgn) 和 O(1) 的差别，但是 n 很小的情况，它接近O(1)
- 应用场景——如何将一个英文文件的文本中出现词频最高的10个词输出出来？
短文本我们可以粗暴地使用哈希表来弄，用一个计数器即可以统计完成，然后还有做个排序？
1TB以上的文本要怎么做？
第三个问题Q3 汉字要怎么整？
网友评论