首页 > 代码库 > 【字典树应用】联想用户最想输入的词汇
【字典树应用】联想用户最想输入的词汇
第一章:抛砖引玉
字典树是一种基于链表的数据结构,以统计词频并返回用户最想输入的词汇为例,分享一下字典树的应用心得。
刚建立的用户词库,用户输入两次“hilili”, 输入一次“hilucy”,此时用户再次输入“hi”,我们应该联想到用户可能要输入的单词是“hilili”,以下为统计示例图。
字典树是一种兼顾空间和时间的数据结构,利用公共前缀节约空间,减少比较次数以提高查询和插入效率。
字典树的常见用途:保存大量字符串并进行统计(静态字典树,猜测金山词霸或xxx单词王都有利用到字典树) 、统计用户输入词频和联想用户想要输入的词汇(动态字典树,即用户词库)、字符串排序(域名排序等)。
第二章:小试牛刀
1.定义一个字典树:
1 struct TrieNode
2 {
3 struct TrieNode* next[26];
4 unsigned int count;
5 };
2 {
3 struct TrieNode* next[26];
4 unsigned int count;
5 };
2.创建一个字典树:
1 TrieNode* CreateTrieNode()
2 {
3 TrieNode* head = (TrieNode*)malloc(sizeof(TrieNode));
4 memset(head, 0, sizeof(TrieNode));
5 return head;
6 }
2 {
3 TrieNode* head = (TrieNode*)malloc(sizeof(TrieNode));
4 memset(head, 0, sizeof(TrieNode));
5 return head;
6 }
3.查找字典树:
1 //遍历字符串,如果字符串未全部写入路径则查找失败,否则返回词频
2 unsigned int FindTrieNode(TrieNode* head, char* str)
3 {
4 if(NULL == head)
5 return 0;
6 TrieNode* tmphead = head;
7 int i = 0, cnt = 0;
8 while(str[i])
9 {
10 cnt = str[i] - ‘a‘;
11 if(NULL != tmphead->next[cnt])
12 {
13 tmphead = tmphead->next[cnt];
14 i++;
15 }
16 else
17 {
18 return 0;
19 }
20 }
21 return tmphead->count;
22 }
2 unsigned int FindTrieNode(TrieNode* head, char* str)
3 {
4 if(NULL == head)
5 return 0;
6 TrieNode* tmphead = head;
7 int i = 0, cnt = 0;
8 while(str[i])
9 {
10 cnt = str[i] - ‘a‘;
11 if(NULL != tmphead->next[cnt])
12 {
13 tmphead = tmphead->next[cnt];
14 i++;
15 }
16 else
17 {
18 return 0;
19 }
20 }
21 return tmphead->count;
22 }
4.插入字典树:
1 //遍历整个字符串,创建不存在的字典树路径,并将整个路径的词频++
2 //如果malloc失败,表示进程内存不足,插入字符串失败
3 BOOL InsertTrieNode(TrieNode* head, char* str)
4 {
5 if(NULL == head)
6 {
7 head = (TrieNode*)malloc(sizeof(TrieNode));
8 memset(head, 0, sizeof(TrieNode));
9 }
10 int i = 0, cnt = 0;
11 TrieNode* tmphead = head;
12 while(str[i])
13 {
14 cnt = str[i] - ‘a‘;
15 if(NULL == tmphead->next[cnt])
16 {
17 if(NULL != (tmphead->next[cnt] = (TrieNode*)malloc(sizeof(TrieNode))))
18 memset(tmphead->next[cnt], 0, sizeof(TrieNode));
19 else
20 return FALSE;
21 }
22 tmphead = tmphead->next[cnt];
23 i++;
24 tmphead->count++;
25 }
26 return TRUE;
27 }
2 //如果malloc失败,表示进程内存不足,插入字符串失败
3 BOOL InsertTrieNode(TrieNode* head, char* str)
4 {
5 if(NULL == head)
6 {
7 head = (TrieNode*)malloc(sizeof(TrieNode));
8 memset(head, 0, sizeof(TrieNode));
9 }
10 int i = 0, cnt = 0;
11 TrieNode* tmphead = head;
12 while(str[i])
13 {
14 cnt = str[i] - ‘a‘;
15 if(NULL == tmphead->next[cnt])
16 {
17 if(NULL != (tmphead->next[cnt] = (TrieNode*)malloc(sizeof(TrieNode))))
18 memset(tmphead->next[cnt], 0, sizeof(TrieNode));
19 else
20 return FALSE;
21 }
22 tmphead = tmphead->next[cnt];
23 i++;
24 tmphead->count++;
25 }
26 return TRUE;
27 }
5.统计用户输入频率
1 //更新用户输入频率
2 void UpdateFrequence(TrieNode* head, char* str)
3 {
4 int i = 0, cnt = 0;
5 while(str[i])
6 {
7 cnt = str[i] - ‘a‘;
8 head->next[cnt]->count++;
9 head = head->next[cnt];
10 i++;
11 }
12 }
2 void UpdateFrequence(TrieNode* head, char* str)
3 {
4 int i = 0, cnt = 0;
5 while(str[i])
6 {
7 cnt = str[i] - ‘a‘;
8 head->next[cnt]->count++;
9 head = head->next[cnt];
10 i++;
11 }
12 }
6.联想最可能的词汇
1 //根据已输入的字符串联想出词频最高的一个字符串,即最有可能是用户想要输入的完整字符串。
2 //已输入的字符串必须已经插入字典树
3 //如果存在路径包含的情况,则总是返回最长路径:比如先插入pretty,再插入prettygirl,输入pr则联想词汇为prettygirl
4 char* GetWantedWord(TrieNode* head, char* szSrc, char* szDes, size_t stDesLen)
5 {
6 if(NULL == head || NULL == szSrc || stDesLen <= strlen(szSrc))
7 return szSrc;
8 TrieNode* tmphead = head;
9 int i = 0, cnt = 0;
10 unsigned int uiMax = 0, len = 0;
11 char cMax = ‘a‘;
12 while(szSrc[i])
13 {
14 cnt = szSrc[i] - ‘a‘;
15 tmphead = tmphead->next[cnt];
16 szDes[i] = szSrc[i];
17 len++;
18 i++;
19 }
20 while(1)
21 {
22 uiMax = 0;
23 cMax = ‘a‘;
24 for(int j = 0; j < 26; j++)
25 {
26 if(NULL != tmphead->next[j] && tmphead->next[j]->count > uiMax)
27 {
28 uiMax = tmphead->next[j]->count;
29 cMax = j + ‘a‘;
30 }
31 }
32 if(len < stDesLen && uiMax > 0)
33 szDes[i] = cMax;
34 else
35 {
36 szDes[i] = ‘\0‘;
37 return szDes;
38 }
39 cnt = cMax - ‘a‘;
40 tmphead = tmphead->next[cnt];
41 len++;
42 i++;
43 }
44 szDes[i] = ‘\0‘;
45 return szDes;
46 }
2 //已输入的字符串必须已经插入字典树
3 //如果存在路径包含的情况,则总是返回最长路径:比如先插入pretty,再插入prettygirl,输入pr则联想词汇为prettygirl
4 char* GetWantedWord(TrieNode* head, char* szSrc, char* szDes, size_t stDesLen)
5 {
6 if(NULL == head || NULL == szSrc || stDesLen <= strlen(szSrc))
7 return szSrc;
8 TrieNode* tmphead = head;
9 int i = 0, cnt = 0;
10 unsigned int uiMax = 0, len = 0;
11 char cMax = ‘a‘;
12 while(szSrc[i])
13 {
14 cnt = szSrc[i] - ‘a‘;
15 tmphead = tmphead->next[cnt];
16 szDes[i] = szSrc[i];
17 len++;
18 i++;
19 }
20 while(1)
21 {
22 uiMax = 0;
23 cMax = ‘a‘;
24 for(int j = 0; j < 26; j++)
25 {
26 if(NULL != tmphead->next[j] && tmphead->next[j]->count > uiMax)
27 {
28 uiMax = tmphead->next[j]->count;
29 cMax = j + ‘a‘;
30 }
31 }
32 if(len < stDesLen && uiMax > 0)
33 szDes[i] = cMax;
34 else
35 {
36 szDes[i] = ‘\0‘;
37 return szDes;
38 }
39 cnt = cMax - ‘a‘;
40 tmphead = tmphead->next[cnt];
41 len++;
42 i++;
43 }
44 szDes[i] = ‘\0‘;
45 return szDes;
46 }
7.只是功能测试,不涉及性能,测试代码略。
第三章:写在结束
程序还有待完善,随着程序的运行时间,用户输入越来越多,也出现了不少手误,怎么剔除掉次数较少的手误统计,如果两到三个用户在轮流使用该程序,怎么在用户切换时迅速反应过来?
字典树和hash表都能显著提高程序设计和code的效率,可以说是程序员手中的利器,值得善加利用。
多扯一句吧:怎样才能天然拥有贝克汉姆的经典发型,梳子往右梳,睡觉右躺,左右头发聚一线,这就有了。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。