Trie

一種用於儲存關聯陣列的有序樹,通常以字串作為鍵值

電腦科學中,trie,又稱字首樹字典樹,是一種有序,用於儲存關聯陣列,其中的鍵通常是字串。與二叉搜尋樹不同,鍵不是直接儲存在節點中,而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的字首,也就是這個節點對應的字串,而根節點對應空字串。一般情況下,不是所有的節點都有對應的值,只有葉子節點和部分內部節點所對應的鍵才有相關的值。

一個儲存了8個鍵的trie結構,"A", "to", "tea", "ted", "ten", "i", "in", "inn".

Trie這個術語來自於retrieval。trie的發明者Edward Fredkin把它讀作/ˈtr/ "tree"。[1][2]但是,其他作者把它讀作/ˈtr/ "try"。[1][2][3]

在圖示中,鍵標註在節點中,值標註在節點之下。每一個完整的英文單詞對應一個特定的整數。Trie可以看作是一個確定有限狀態自動機,儘管邊上的符號一般是隱含在分支的順序中的。

鍵不需要被顯式地儲存在節點中。圖示中標註出完整的單詞,只是為了演示trie的原理。

trie中的鍵通常是字串,但也可以是其它的結構。trie的演算法可以很容易地修改為處理其它結構的有序序列,比如一串數字或者形狀的排列。比如,bitwise trie中的鍵是一串位元,可以用於表示整數或者主記憶體地址。

應用

編輯

trie樹常用於搜尋提示。如當輸入一個網址,可以自動搜尋出可能的選擇。當沒有完全匹配的搜尋結果,可以返回字首最相似的可能。[4]

實現方式

編輯

trie樹實際上是一個確定有限狀態自動機(DFA),通常用轉移矩陣表示。行表示狀態,列表示輸入字元,(行,列)位置表示轉移狀態。這種方式的查詢效率很高,但由於稀疏的現象嚴重,空間利用效率很低。也可以採用壓縮的儲存方式即鏈結串列來表示狀態轉移,但由於要線性查詢,會造成效率低下。

於是人們提出了下面兩種結構。[5]

三陣列Trie

編輯

三陣列Trie(Triple-Array Trie)結構包括三個陣列:base,next和check.

二陣列Trie

編輯

二陣列Trie(Double-Array Trie)包含base和check兩個陣列。base陣列的每個元素表示一個Trie節點,即一個狀態;check陣列表示某個狀態的前驅狀態。

實例

編輯

這是一個用於詞頻統計的程式範例,因使用了getline(3),所以需要glibc才能連結成功,沒有glibc的話可以自行覆寫。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TREE_WIDTH 256

#define WORDLENMAX 128

struct trie_node_st {
        int count;
        int pass; //add a count for the part-include for example 'this is' then the 'is' is hited two times 
        struct trie_node_st *next[TREE_WIDTH];
};

static struct trie_node_st root={0, 0, {NULL}};

static const char *spaces=" \t\n/.\"\'()";

void myfree(struct trie_node_st * rt)
{
	for(int i=0; i<TREE_WIDTH; i++){
		if(rt->next[i]!=NULL){
			myfree(rt->next[i]);
			rt->next[i] = NULL;
		}
	}
	free(rt);
	return;
}

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;
                }
                curr->pass++;//count
                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+rootp->pass);
        }
        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);
                }
        }

        do_travel (&root);

        free (linebuf);

	for(int i=0; i<TREE_WIDTH; i++){
		if(root.next[i]!=NULL){
			myfree(root.next[i]);
		}
	}

        exit (0);
}

參考資料

編輯
  1. ^ 1.0 1.1 Black, Paul E. trie. Dictionary of Algorithms and Data Structures. 國家標準技術研究所. 2009-11-16 [2012-07-08]. (原始內容存檔於2010-05-19). 
  2. ^ 2.0 2.1 Franklin Mark Liang. Word Hy-phen-a-tion By Com-put-er (PDF) (Doctor of Philosophy論文). Stanford University. 1983 [2010-03-28]. (原始內容 (PDF)存檔於2010-05-19). 
  3. ^ Knuth, Donald. 6.3: Digital Searching. The Art of Computer Programming Volume 3: Sorting and Searching 2nd. Addison-Wesley. 1997: 492. ISBN 0-201-89685-0. 
  4. ^ 米嘉. 大规模中文文本检索中的高性能索引研究 (碩士論文). [2005]. 
  5. ^ An Implementation of Double-Array Trie. [2012-07-19]. (原始內容存檔於2009-03-19).