字典树(trie树)实现词频查找 |
您所在的位置：网站首页 › 字典树查找所有包含指定前缀的字符串 › 字典树(trie树)实现词频查找 |
字典树(trie树)实现词频查找
碎碎念:
在大学数据结构中，有关于树的应用部分。其中一个就是利用树来进行词频的统计，我们主要希望的是查询效率高，对于树来说查询效率和插入都比较快，时间复杂度都能做到较好。
我们来看一段来自百度百科对trie树的解释:
字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
我们来对比几种树:
AVL树: 最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
红黑树: 平衡二叉树，广泛用在C++的STL中。如map和set都是用红黑树实现的。
B/B+树: 用在磁盘文件组织 数据索引和数据库索引。
Trie树(字典树): 用在统计和排序大量字符串，如自动机。
现在我们来讨论讨论Trie树的构建吧！
我使用的环境是Visual Studio 2015 、使用c语言
（c语言的指针真的是要控制好，不然出现很多野指针或者其他的就会被气疯）
废话不说了，开始吧！
算法描述:
1.
整体数据结构的关系图（程序中还有栈结构，在这里不是主要的，不展示）
（注:字典树中的结点结构）
如上图，我们利用单词前缀重复多的特点，建立这样一棵树，由于我们是以树的形式对词频进行存储，我们会发现查找效率会变高，而且占用的空间会明显减少。又由于我们分析的小说文章中包含的词都是反复出现的，所以结点数会较少。如果我们查找（‘zzzz...十个z字母的单词’），我们发现最多会查找260次就能查到，但是用其他的方法（emmm你们可以验证一下）
（注：树结构示例）
（树结点信息结构体 记录树的信息） 上边就是对树结构的描述，以及语言上的实现。2.关键算法流程图
（主要方法一：分析文件）
程序的大致流程
（主要方法二：将单词传入树） 
（主要方法二：将单词传入树） 
（注：主函数逻辑） 整体描述: 我们采用链、树、以及堆栈来完成题目要求，采用的树在理论上深度是可以无限加深的，所以单词长度是无限的。 在操作上，先获取文件，用户输入文件路径，打开文件。 输入成功，打开文本进行分析，分析完毕进行树的遍历，按照字典序输出。 完成以上操作用户可以选择重新遍历树，也可以查找树中的某个单词，查询词频和词频数。 这里最关键的就是对树的构建，因为插入时会有bug下面贴一下我的代码，（因为我初学可能代码风格不是很好）
主要方法一： //传入树以及字符串检测有就加数 没有就加结点 int magicFindWord(letterNode*opNode,char*opString, treeInfo*infoConter) {
//初始化变量 int max_string_length =MAX_STRING_LENGTH; letterNode *currentNode=opNode;//记录当前操作的结点 letterNode *currentHeadNode = currentNode;//记录每一层的第一个结点 letterNode *trunkNode=NULL; letterNode addNode;//需要添加的结点 int getWordNum = 0; int areYouFind = 0;//记录查找的状态
for (int i =0;i if (currentNode->currentChar==opString[i])//在树中找到字母 { areYouFind= 1; if ((i+1 == strlen(opString)) || (i+1 == max_string_length))//找到并且是最后一个字母 { currentNode->wordNum++; infoConter->wordTotalSize++; if (currentNode->wordNum==1)//找到后计数器加一 { infoConter->wordTotalNum++; } getWordNum = currentNode->wordNum; areYouFind = 100; break; } break; } currentNode = currentNode->nextNode; }
if (areYouFind==0)//没找到创建新结点 { addNode.wordNum = 0;
if (i+1>=strlen(opString)||i+1>= max_string_length)//该字母为单词最后一个单词，计数器加一 { addNode.wordNum= 1; infoConter->wordTotalNum++; infoConter->wordTotalSize++; getWordNum= addNode.wordNum; addNode.nextNode= NULL; addNode.nextTrunk= NULL; } else//字母不是单词最后一个，创建下一层的头结点 { trunkNode= (letterNode*)malloc(sizeof(letterNode)); trunkNode->currentChar=opString[i + 1]; trunkNode->wordNum= 0; trunkNode->nextNode= NULL; trunkNode->nextTrunk= NULL;
addNode.nextTrunk= trunkNode; }
addNode.currentChar = opString[i];
insertNode(currentHeadNode, addNode);//在树（下一层的链中）中插入结点
currentNode = trunkNode;
}
if(areYouFind==1&&!currentNode->nextTrunk)//找到该单词并且下一层无结点 { trunkNode = (letterNode*)malloc(sizeof(letterNode));//创建下一层的头结点 trunkNode->currentChar = opString[i + 1]; trunkNode->wordNum = 0; trunkNode->nextNode = NULL; trunkNode->nextTrunk = NULL;
currentNode->nextTrunk= trunkNode; currentNode = currentNode->nextTrunk; }elseif(areYouFind == 1)//找到该单词并且下一层有结点 { currentNode = currentNode->nextTrunk; }
if (areYouFind==100) { break; } }
return getWordNum ; } 主要方法二： //分析文件中的文本 int analysisText(letterNode*opNode,FILE*opFile, treeInfo*infoConter){ char toolCharArray[100];//用来读取文件中的字符 int letterNum=0; int max_string_length =MAX_STRING_LENGTH; char *opString; opString = (char *)malloc((max_string_length+1)*sizeof(char)); opString[0] = 0; opString[max_string_length] = 0; int hh=0; while (fgets(toolCharArray, 100,opFile) != NULL)//逐行读取opFile所指向文件中的内容到toolCharArray中 {
for (int i = 0; i < 100-1; i++) { if ((toolCharArray[i]>='a'&&toolCharArray[i]= 'A'&&toolCharArray[i] if (toolCharArray[i] if (letterNum>0)//检测到一个单词记录结束存入树中 { if (letterNum
FILE* file = getAFile();//获取用户文件
//初始化结点信息树和信息记录 letterNode opNode; treeInfo infoConter; initTree(&opNode); initTreeInfo(&infoConter);
//分析文件 analysisText(&opNode,file,&infoConter); printf("\n\n\n分析文章结束\n");
//遍历产生字典树 traverseTree(&opNode, infoConter); //获取用户想要的搜索结果*/
char useOpChar[100] = {'!'}; while (useOpChar[0]!='q'&& useOpChar[0] !='Q') { printf("\n\n\n 分析并 输出字典树结束，请进行下列操作"); printf("\n f/F查找 t/T遍历字典树 q/Q退出程序"); printf("\n\n 输入操作符:"); scanf_s("%s", &useOpChar, 10); system("cls"); printf("\n\n"); switch (useOpChar[0]) { case't':; case'T': {traverseTree(&opNode, infoConter);break; } case'f':; case'F': { char sss[100] ="you"; printf("请输入要查找的词（enter结束输入）："); scanf_s("%s", &sss, 100); printf("\n\n%s的频数为:%d\n", sss,getWordNum(&opNode, sss)); double freque = (double)getWordNum(&opNode, sss) * 100 / infoConter.wordTotalSize; printf("%s的频率为:%f%c \n", sss, freque, 37); break; } default: {break; } } }
destroyTree(&opNode, &infoConter); return 0; } 以下是运行结果截图(我把扫描到的字母也打印出来了，看起来可能会比较乱):
|
【本文地址】
今日新闻 |
推荐新闻 |