本文主要是介绍TRIE树在输入法分词的应用，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
TRIE树，即字典树，可以用于排序、保存大量字符串，在搜索引擎和防火墙中都有着重要的作用。本文使用字典树读取汉语拼音并进行匹配，成功实现了汉语拼音的划分。
先来看看TRIE树的结构：
树从root根节点出发，每个节点都有26个子节点（对应各个字母）。不难发现所有n长度的单词组合都在高度为n的TRIE树中。我们把从root节点出发，到某叶子（或节点）的字母组合称为一个单词。
1.定义以下结构体构造TRIE树：
typedef struct TRIE_NODE_ {struct TRIE_NODE_ *children[26];bool is_word;
} TRIE_NODE;和我们料想的一样，每个节点都有26个子节点，还有一个标记用于表示root节点到该处是不是一个单词。
2.初始化TRIE树：
static TRIE_NODE* TrieAllocateNode() {TRIE_NODE *ret = (TRIE_NODE*) malloc(sizeof(TRIE_NODE));if (!ret) exit(1);ret->is_word = false;memset(ret->children, 0, 26 * sizeof(TRIE_NODE*));return ret;
}3.添加新的单词到树中
void TrieAdd(TRIE_NODE *root, char *text) {for (; *text != '\0'; ++text) { //C中遍历字符串的通用做法if (root->children[(*text) - 'a'] == NULL) {root->children[(*text) - 'a'] = TrieAllocateNode(); //把字母直接减去A的ASCLL码值，可以将字母与26个子节点一一对应。}root = root->children[(*text) - 'a']; //转向下一层树}root->is_word = true; //将该单词标为true
}4.利用深度优先搜索（dfs）分词
void PinyinSolve(TRIE_NODE *root, char *pinyin, char *sp[], int len) { //字典树root，待处理字符串pinyin，分割点标记数组sp，分割点位置lenchar *p = pinyin; TRIE_NODE *proc = root; //获取分割指针p和字典中指针procwhile(true) {if (*p == '\0') break; //字符串处理结束后返回if (proc->is_word) { //是单词时继续递归找出合法子结构sp[len] = p; //每次分割成功都要标记PinyinSolve(root, p, sp, len + 1); //递归，检查每种分割}if (proc->children[(*p) - 'a'] != NULL) { //没到树底就推进指针proc = proc->children[(*p) - 'a'];p++;} else {break;}}if (*p == '\0' && proc->is_word == true) { //到结尾且分割方案可行就打印sp[len] = p;int i;for (i = 0; i <= len; ++i) {char *mb;for (mb = sp[i - 1]; mb < sp[i]; ++mb) { //打出分割点间的字符串printf("%c", *mb);}printf("\n");}printf("----\n"); //给下种分割方案留空}
}完整代码如下：
// gcc 下编译通过
// Copyright (c) 2015年 XiaoJSoft. All rights reserved.
// 字典树词库来自网络
// In ChestnutHeng's Blog ,If you have any questions ，please contact with <u></u>ChestnutHeng@Gmail.com
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
#include <string.h>char *pinyin[] = {"ai","an","ang","ei","ou","ao","ba","bo","bai","bei","bao","ban","ben","bang","beng","bi","bie","biao","bian","bin","bing","pa","po","pai","pao","pou","pan","pen","pang","peng","pi","pie","piao","pian","pin","ping","ma","mo","me","mai","mao","mou","man","men","mang","meng","mi","mie","miao","miu","mian","min","ming","fa","fo","fei","fou","fan","fen","fang","feng","da","tu","de","dai","dei","dao","dou","dan","dang","deng","di","die","diao","diu","dian","ding","ta","te","tai","tao","tou","tan","tang","teng","ti","tie","tiao","tian","ting","na","nai","nei","nao","no","nen","nan","nang","neng","ni","nie","niao","niu","nian","nin","niang","ning","la","le","lai","lei","lao","lou","lan","lang","leng","li","lia","lie","liao","liu","lian","lin","liang","ling","ga","ge","gai","gei","gao","gou","gan","gen","gang","geng","ka","ke","kai","kou","kan","ken","kang","keng","ha","he","hai","hei","hao","hou","hen","hang","heng","ji","jia","jie","jiao","jiu","jian","jin","jiang","jing","qi","qia","qie","qiao","qiu","qian","qin","qiang","qing","xi","xia","xie","xiao","xiu","xian","xin","xiang","xing","zha","zhe","zhi","zhai","zhao","zhou","zhan","zhen","zhang","zheng","cha","che","chi","chai","chou","chan","chen","chang","duo","cheng","sha","she","shi","shai","shao","shou","shan","shen","shang","sheng","re","ri","rao","rou","ran","ren","rang","reng","za","ze","zi","zai","zao","zou","zang","zeng","ca","ce","ci","cai","cao","cou","can","cen","cang","ceng","sa","se","si","sai","sao","sou","san","sen","sang","seng","ya","yao","you","yan","yang","yu","ye","yue","yuan","yi","yin","yun","ying","wa","wo","wai","wei","wan","wen","wang","weng","wu",NULL
}; //这个字典不全， = =坑爹的，不是我写的啊。typedef struct TRIE_NODE_ {struct TRIE_NODE_ *children[26];bool is_word;
} TRIE_NODE;#define MAX_LEN 128char g_Input[MAX_LEN + 1];static TRIE_NODE* TrieAllocateNode() {TRIE_NODE *ret = (TRIE_NODE*) malloc(sizeof(TRIE_NODE));if (!ret) exit(1);ret->is_word = false;memset(ret->children, 0, 26 * sizeof(TRIE_NODE*));return ret;
}void TrieAdd(TRIE_NODE *root, char *text) {for (; *text != '\0'; ++text) {if (root->children[(*text) - 'a'] == NULL) {root->children[(*text) - 'a'] = TrieAllocateNode();}root = root->children[(*text) - 'a'];}root->is_word = true;
}void PinyinSolve(TRIE_NODE *root, char *pinyin, char *sp[], int len) {char *p = pinyin;TRIE_NODE *proc = root;while(true) {if (*p == '\0') break;if (proc->is_word) {sp[len] = p;PinyinSolve(root, p, sp, len + 1);}if (proc->children[(*p) - 'a'] != NULL) {proc = proc->children[(*p) - 'a'];p++;} else {break;}}if (*p == '\0' && proc->is_word == true) {sp[len] = p;int i;for (i = 0; i <= len; ++i) {char *mb;for (mb = sp[i - 1]; mb < sp[i]; ++mb) {printf("%c", *mb);}printf("\n");}printf("----\n");}
}int main(int argc, const char * argv[]) {TRIE_NODE *root = TrieAllocateNode();char **ptr;for (ptr = pinyin; *ptr != NULL; ++ptr) {TrieAdd(root, *ptr);}scanf("%s", g_Input);char *buffer[999];buffer[0] = g_Input;PinyinSolve(root, g_Input, buffer + 1, 0);printf("OK\n");return 0;
}
这篇关于TRIE树在输入法分词的应用的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
