前缀树

编辑:品尝网互动百科 时间:2019-12-15 20:55:35
编辑 锁定
本词条缺少信息栏名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
trie树常用于搜索提示。如当输入一个网址,可以自动搜索出可能的选择。当没有完全匹配的搜索结果,可以返回前缀最相似的可能。

前缀树实现

编辑
trie树实际上是一个DFA,通常用转移矩阵表示。行表示状态,列表示输入字符,(行, 列)位置表示转移状态。这种方式的查询效率很高,但由于稀疏的现象严重,空间利用效率很低。也可以采用压缩的存储方式即链表来表示状态转移,但由于要线性查询,会造成效率低下。
于是人们提出了下面两种结构。[1] 

前缀树三数组Trie

三数组Trie(Tripple-Array Trie)结构包括三个数组:base,next和check.

前缀树二数组Trie

二数组Trie(Double-Array Trie)包含base和check两个数组。base数组的每个元素表示一个Trie节点,即一个状态;check数组表示某个状态的前驱状态。

前缀树实例

编辑
这是一个用于词频统计的程序范例,因使用了getline(3),所以需要glibc才能链接成功,没有glibc的话可以自行改写。代码由“JohnBull”捐献,遵从GPL版权声明。[1] 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TREE_WIDTH 256
#define WORDLENMAX 128
struct trie_node_st {
    int count;
    struct trie_node_st *next[TREE_WIDTH];
};
static struct trie_node_st root={0, {NULL}};
static char *spaces=" \t\n/.\"\'()";
static int insert(const char *word)
{
    int i;
    struct trie_node_st *curr, *newnode;
    if (word[0]=='\0') {
        return 0;
    }
    curr = &root;
    for (i=0; ; ++i) {
        if (word[i] == '\0') {
            break;
        }
        if (curr->next[ word[i] ] == NULL) {
            newnode=(struct trie_node_st*)malloc(sizeof(struct trie_node_st));
            memset(newnode, 0, sizeof(struct trie_node_st));
            curr->next[ word[i] ] = newnode;
        }
        curr = curr->next[ word[i] ];
    }
    curr->count ++;
    return 0;
}
static void printword(const char *str, int n)
{
    printf("%s\t%d\n", str, n);
}
static int do_travel(struct trie_node_st *rootp)
{
    static char worddump[WORDLENMAX+1];
    static int pos=0;
    int i;
    if (rootp == NULL) {
        return 0;
    }
    if (rootp->count) {
        worddump[pos]='\0';
        printword(worddump, rootp->count);
    }
    for (i=0;i<TREE_WIDTH;++i) {
        worddump[pos++]=i;
        do_travel(rootp->next[i]);
        pos--;
    }
    return 0;
}
int main(void)
{
    char *linebuf=NULL, *line, *word;
    size_t bufsize=0;
    int ret;
    while (1) {
        ret=getline(&linebuf, &bufsize, stdin);
        if (ret==-1) {
            break;
        }
        line=linebuf;
        while (1) {
            word = strsep(&line, spaces);
            if (word==NULL) {
                break;
            }
            if (word[0]=='\0') {
                continue;
            }
            insert(word);
        }
    }
    /* free(linebuf); */
    do_travel(&root);
    exit(0);
}
参考资料
词条标签:
非科学 科学