字典树

发表于 | 分类于 | | 阅读次数:

字典树，又名Trier树，可以用于单词的查找和统计。
字典树的示例如下图所示，其中，若根节点为第0层，则第k层节点表示字典中单词前k个字符，从根节点至树中标黄节点的路径表示以该节点字符为末尾的单词，例如，too、tooth、tea、two等。
172655272

字典树中的节点可用以下结构体表示:

1
2
3
4
5
6
7
typedef struct TNode 
{ 
    char value;//表示该节点存储的字符 
    int count;//表示以该节点字符为末尾的单词出现的次数 
    bool endFlag;//表示该节点是否是单词的末尾 
    TNode* childList[26];//表示下一个字符 
}TNode,*DTree;

字典树的初始化和插入单词操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
//初始化字典树 
void Init(DTree &tree) 
{ 
    int i; 
    tree=(DTree)malloc(sizeof(TNode)); 
    tree->value = ' ';//根节点的字符为空 
    tree->count = 0; 
    tree->endFlag = false; 
    for (i=0;i<26;i++) tree->childList[i] = NULL; 
} 

//将单词插入字典树中 
//从根节点开始从上至下，将单词字符从左至右逐步插入到字典树中 
void Insert(DTree tree,char string[],int len) 
{ 
    int i,j; 
    TNode* node = tree; 
    for (i=0;i<len;i++)          
    {                   
        //若节点存在，则直接访问下一个节点                   
        //若该节点是单词最后一个字符，则将endFlag置为true，并将count加1                   
        if (node->childList[string[i]-'a']!=NULL) 
        { 
            node = node->childList[string[i]-'a']; 
            if (i==len-1)  
            { 
                node->endFlag = true; 
                node->count++; 
            } 
        } 
        //若节点不存在，则新建节点并初始化 
        //若该节点是单词最后一个字符，则将endFlag置为true，否则置为false，并将count加1 
        else 
        { 
            node->childList[string[i]-'a'] = (TNode*)malloc(sizeof(TNode)); 
            node = node->childList[string[i]-'a']; 
            node->value = string[i]; 
            for (j=0;j<26;j++) node->childList[j] = NULL; 
            node->endFlag = false; 
            if (i==len-1)  
            { 
                node->endFlag = true; 
                node->count++; 
            }            
        } 
    } 
}

字典树可用于计算某个文本中出现次数最多的前k个单词：遍历文本中的单词，将每个单词插入到字典树中，重复的单词实际不再添加，而是将原有单词末尾节点中的count加1，最后，字典树中根节点到所有endFlag为true的节点的路径为文本中出现的所有单词，节点中的count值为这些单词出现的次数，通过排序可以得到出现次数最多的前k个单词。