the implementation of prefix tree and compare prefix tree with hard match
本项目是对前缀树的实现以及测试它与硬匹配算法的优劣程度
suffix.c和suffix.h文件的主要内容有
(1)前缀树的建立(函数名Build_tree)
函数Build_tree 有两个参数:
第一个参数path,需要给出建立的前缀树所需要的数据集的文本路径;
第二个参数reverse,当它为1时,建立的是后缀匹配树;当它为0时建立的是前缀匹配树;
返回值root,它是一个建立好的前缀树树根;
(2)前缀树匹配(函数名Search_Tree)
函数Search_Tree有4个参数:
第一个参数Pstr,待匹配的字符串;
第二个参数root,前缀树(后缀树)树根;
第三个参数father,当前节点的父亲节点,其作用是判断当前节点是否是根节点,因为根节点不存数据,所以一般情况下,该参数应与第二个参数相同。
第四个参数reverse,该参数的作用是配合前缀匹配树(后缀匹配树)来使用的。当前缀树的建立的时候,reverse=1,此时,使用前缀树匹配时,这里应该为1;当前缀树的建立的时候,reverse=0,此时,使用后缀树匹配时,这里也应该为0。
返回值1为成功匹配,0为匹配失败。
(3)打印前缀树(后缀树)(函数名Print_Tree)
函数Print_Tree有4个参数:
第一个参数root,前缀树(后缀树)树根;
第二个参数father,当前节点的父亲节点,其作用是判断当前节点是否是根节点,因为根节点不存数据,所以一般情况下,该参数应与第一个参数相同;
第三个参数num,其作用时记录将要打印的字符串的长度,起始值一般设为0;
第四个参数reverse,该参数的作用是配合前缀匹配树(后缀匹配树)来使用的。当前缀树的建立的时候,reverse=1,此时,使用前缀树匹配,这里应该为1,打印前缀树;当前缀树的建立的时候,reverse=0,此时,使用后缀树匹配时,这里应该为0,打印后缀树。
(4)硬匹配(函数名strandstr)
函数strandstr有两个参数:
第一个参数path,需要给出硬匹配进行匹配时所需要原始的数据集的文本路径;
第二个参数str,待匹配字符串
返回值1为成功匹配,0为匹配失败。
test.c对前缀匹配树、硬匹配算法的效率进行测试
test1.c单独对前缀树算法进行测试
test2.c单独对应匹配算法
需要注意的是这里面本人使用的是绝对路径,所以如需正常使用,请自行阅读代码并更改路径。