首页 > 代码库 > 用哈希算法优化字典树空间结构
用哈希算法优化字典树空间结构
字典树是前缀匹配问题中常用的数据结构,查询速度可以达到O(len),len为待查序列的长度,但是字典树的空间消耗非常大,对于基于字母表的英文单词,每个节点要存储26个指针指向下一节点,很有可能有不少空的,很浪费。
考虑在节点中用哈希表来存储子节点指针,键值为单个字母,这样对于模式中没有的字母就省掉了空指针的空间,同样可以达到O(1)的选择分支速度。
1 //用map作哈希表 2 class Node 3 { 4 public: 5 bool is_word = false; 6 map<char, Node *> children; 7 ~Node() 8 { 9 for (int i = 0; i < 26; ++i) 10 { 11 if (children.find(‘a‘ + i) != children.end()) delete children[‘a‘ + i]; 12 } 13 } 14 void insert(const string _Word) 15 { 16 Node *p = this; 17 for (int i = 0; i < _Word.size(); ++i) 18 { 19 char curr = _Word[i]; 20 if (p->children.find(curr) == p->children.end()) 21 { 22 p->children.insert(map<char, Node *>::value_type{ curr,new Node() }); 23 } 24 p = p->children[curr]; 25 } 26 p->is_word = true; 27 } 28 bool has_prefix(const string &_Word) 29 { 30 Node *p = this; 31 int i = 0; 32 for (; i < _Word.size(); ++i) 33 { 34 char curr = _Word[i]; 35 if (p->children.find(curr) == p->children.end()) 36 { 37 if (p->is_word)return true; 38 else return false; 39 } 40 else 41 { 42 p = p->children[curr]; 43 } 44 } 45 return false; 46 } 47 };
用哈希算法优化字典树空间结构
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。