TRIE树的每一个节点为一个包含256个元素的数组,同时指针指向其下一级节点
节点定义如下:
struct trienode
{
int id;
struct trienode *child[256];
}TRIENODE;
如果TRIE树的某个节点的指针为NULL,说明从跟节点到当前节点的路径构成文件B中的一个关键词,
在其节点的id保存该关键词的id;如果指针不为NULL,则id对应为0或者一个无穷大的整数,标志从根节点
到当前节点的路径不是一个完整的关键词。
将关键词转化为二进制无符号char型数组,即对于汉字等双字节字符视为两个无符号char型整数,
每个元素的取值范围在0到255之间。
2:生成文件b的TRIE树
步骤1:依次读取文件b的每一行,对每一行执行步骤2到步骤5
步骤2:读取关键词id和关键词,令为key
步骤3:依次读取key的每一个字符,对每一个字符,执行步骤4;
步骤4:如果该字符对应的指针为NULL,则创建其儿子节点;
步骤5:为当前节点的对应字符id置为关键词id
3:根据A文件生成C文件
步骤1:依次读取文件A的每一行,对每一行执行步骤2到步骤5
步骤2:分别获取当前行关键词、ip地址和时间
步骤3:令关键词key=c1c2...cm,对c1到cm每个字符,执行步骤4
步骤4:获取根节点的第c1个元素指针,转移到节点node1,
根据node1的第c2个元素指针,转移到node2...
根据nodem的第cm个元素,获取关键词的id
步骤5:往文件c中写入一行数据,格式为关键词的id、ip地址和时间
4:复杂度分析
生成文件B的TRIE树过程时间复杂度为O(n*m),其中n为文件b行数,m为文件b关键词的最大长度。TRIE的空间复杂度为O(n*m),n和m含义同上,但由于实际应用中关键词之间可能会有很多前缀相同现象,所以实际耗费空间并不会很高。
生成C文件的时间复杂度同样为O(n*m),n为文件a行数,m为文件a关键词的最大长度,因为有了TRIE树之后,给定一个关键词获得其id的时间复杂度为关键词长度。生成C文件的过程除了TRIE树空间外基本不需要太多额外的空间,空间复杂度为O(1),由于系统有1G的可用内存,TRIE占用的空间在几十兆到200M之间(与关键词集合有关),因此本方法完全可行。