郑州网站建设费用,微信公众号制作编辑器,wordpress启用主题无效,wordpress 越来越慢前言 今天具体分析一下trie树#xff0c;包括#xff1a;原理分析#xff0c;应用场合#xff0c;复杂度分析#xff0c;与hash的比较#xff0c;源码展现。大部分内容来自互联网#xff0c;文中会注明出处。 原理分析 主要是hash树的变种#xff0c;先看下图#xff…前言 今天具体分析一下trie树包括原理分析应用场合复杂度分析与hash的比较源码展现。大部分内容来自互联网文中会注明出处。 原理分析 主要是hash树的变种先看下图 每一个点存储一个字符所以trie字典树的key不是每个字符串而是一条链。其原理就是充分利用了公共字符串这样在查找时就不需要做重复工作了。并且查找的复杂度可以维持在O(len),len为字符串的长度原因很简单我们只需沿着从根到节点的一条路径就可以了。插入也是类似的原理。 建立的过程 每个节点包括三个信息26个指针假设查询26个英文小写字母每个节点的后继节点可能出现26个字母当中的任何一个故需26个指针当然对于不存在的后继结点设置为NULL标志位此标志位主要是为了识别是否为字符串为一个单词第三个为附加信息看具体应用场合可以为字符出现的次数也可以为前缀的个数字符串的个数总之灵活应用就是。 查询的过程 与建立过程原理雷同只是没有创建新节点的过程 删除的过程 很少见如果非要删除则采用递归从下往上挨个delete即可 应用场合 我直接转载http://www.cnblogs.com/aiyelinglong/archive/2012/04/09/2439777.html trie树的应用 1.有一个1G大小的一个文件里面每一行是一个词词的大小不超过16字节内存限制大小是1M。返回频数最高的100个词。 2.1000万字符串其中有些是重复的需要把重复的全部去掉保留没有重复的字符串。请怎么设计和实现 3.一个文本文件大约有一万行每行一个词要求统计出其中最频繁出现的前10个词请给出思想给出时间复杂度分析。 4.寻找热门查询搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来每个查询串的长度为1-255字节。假设目前有一千万个记录这些查询串的重复读比较高虽然总数是1千万但是如果去除重复和不超过3百万个。一个查询串的重复度越高说明查询它的用户越多也就越热门。请你统计最热门的10个查询串要求使用的内存不能超过1G。 后缀树的应用 1.查找字符串O是否在字符串S中。 方案用S构造后缀树按在trie中搜索字串的方法搜索O即可。 原理若O在S中则O必然是S的某个后缀的前缀。 例如leconte查找Ocon是否在S中则Ocon必然是Sleconte的前缀。 2.指定字符串T在字符串S中的重复次数。 方案用S’$’构造后缀树搜索T节点下的叶子节点数目即为重复次数 原理如果T在S中重复了两次则S应有两个后缀以T为前缀重复次数自然统计出来了。 3.字符串S中的最长重复子串 方案原理同2具体做法是找到最深的非叶子节点。 这个深指从root所经历过的字符个数最深非叶子节点所经历的字符串起来就是最长重复子串。为什么非要是叶子节点呢因为既然是要重复的当然叶子节点个数要2 4.两个字符串S1,S2的最长公共子串而非以前所说的最长公共子序列因为子序列是不连续的而子串是连续的。 方案将S1#S2$作为字符串压入后缀树找到最深的非叶子节点且该节点的叶子节点既有#也有$. 5.最长回文子串 复杂度分析 前文已经提及建立的时间复杂度为O(n*len),查询插入都为O(len)。空间复杂度就比较大了这也是它的一个缺点主要是指针得占用空间。 与hash的比较 首先比较创建的复杂度创建的复杂度hash为O(n*len3)(n指字符串的个数len指字符串的长度)原理可见我的博文hash 一个海量数据的实现里面有段代码 int SDBMHash(char* str) { int hash 0; while(*str!\0) { hash *str (hash 6) (hash 16) - hash; } return (hash 0x7FFFFFFF); } 分析3具体指int hash 0; 和return (hash 0x7FFFFFFF);有人会说这也算几乎没影响但是大家想想每个字符串多俩次操作当字符串很大时就不是俩次的问题了可能是10的几次方了还有一次是hash表的操作。查询和插入同样的道理每个字符串多两个操作。所以hash的时间复杂度不如trie的。这还是小case在很多方面hash没法跟trie比的比如查找前缀字符串trie几乎用不到O(len)hash的操作就复杂多了并且前缀字符串还要额外的hashmap。空间方面可能hash 节省但是恰恰就是因为trie牺牲了空间才换如此巨大的时间效果。 源码展现 我自己创建了一个txt文件里面有很多单词一行一个利用trie统计某个单词出现的频数可在我的资源文件里下到工程文件里面有一个txt。可以在txt里复制同一个单词多次然后查询就可以看到它存在的次数了。 #includeiostream
#includecstring
#includefstream
using namespace std; const int n26;
typedef struct Trie_node
{ int count; // 统计单词前缀出现的次数 struct Trie_node* next[n]; // 指向各个子树的指针 bool exist; // 标记该结点处是否构成单词 }TrieNode , *Trie; TrieNode* createTrieNode()
{ TrieNode* node (TrieNode *)malloc(sizeof(TrieNode)); node-count 0; node-exist false; memset(node-next , 0 , sizeof(node-next)); // 初始化为空指针 return node;
} void Trie_insert(Trie root, char* word)
{ Trie node root; char *p word; int id; while( *p ) { id *p - a; if(node-next[id] NULL) { node-next[id] createTrieNode(); } node node-next[id]; // 每插入一步相当于有一个新串经过指针向下移动 p; //node-count 1; // 这行代码用于统计每个单词前缀出现的次数也包括统计每个单词出现的次数 } node-exist true;// 单词结束的地方标记此处可以构成一个单词 node-count;
} int Trie_search(Trie root, char* word)
{ Trie node root; char *p word; int id; while( *p ) { id *p - a; node node-next[id]; p; if(node NULL) {coutendlword在文件中不存在;return 0; }} if(node-existtrue)coutendlword出现了node-count次;return node-count; }const int num5000;//产生一个txt文件模拟字符串
void createStrTXT()
{for(int i0;inum;i){ char temp[12]{\n,\r,rand()%2697,rand()%2697,rand()%2697,rand()%2697,rand()%2697,rand()%2697,rand()%2697,rand()%2697,rand()%2697,\0};char*strtemp;ofstream ofs(str.txt,ios::app);ofsstr;}
}
void establishTrieTree(Trie root)
{ifstream ifs(str.txt);char str[10]; int i0;while(ifsstr){Trie_insert(root,str);cout插入单词strendl;i;}cout总共插入i个单词;}
int main(void)
{ //初始化rootTrie rootcreateTrieNode();//createStrTXT();establishTrieTree( root);Trie_search(root,zxuglsdsm);return 0;
} 测试图
