在電腦科學中，trie，又稱字首樹或字典樹，是一種有序樹，用於儲存關聯陣列，其中的鍵通常是字串。與二叉搜尋樹不同，鍵不是直接儲存在節點中，而是由節點在樹中的位置決定。一個節點的所有子孫都有相同的字首，也就是這個節點對應的字串，而根節點對應空字串。一般情況下，不是所有的節點都有對應的值，只有葉子節點和部分內部節點所對應的鍵才有相關的值。
Trie這個術語來自於retrieval。trie的發明者Edward Fredkin把它讀作/ˈtriː/ "tree"。[1][2]但是，其他作者把它讀作/ˈtraɪ/ "try"。[1][2][3]
在圖示中，鍵標註在節點中，值標註在節點之下。每一個完整的英文單詞對應一個特定的整數。Trie可以看作是一個確定有限狀態自動機，儘管邊上的符號一般是隱含在分支的順序中的。
鍵不需要被顯式地儲存在節點中。圖示中標註出完整的單詞，只是為了演示trie的原理。
trie中的鍵通常是字串，但也可以是其它的結構。trie的演算法可以很容易地修改為處理其它結構的有序序列，比如一串數字或者形狀的排列。比如，bitwise trie中的鍵是一串位元，可以用於表示整數或者主記憶體地址。
應用
trie樹常用於搜尋提示。如當輸入一個網址，可以自動搜尋出可能的選擇。當沒有完全匹配的搜尋結果，可以返回字首最相似的可能。[4]
實現方式
trie樹實際上是一個確定有限狀態自動機(DFA)，通常用轉移矩陣表示。行表示狀態，列表示輸入字元，（行，列）位置表示轉移狀態。這種方式的查詢效率很高，但由於稀疏的現象嚴重，空間利用效率很低。也可以採用壓縮的儲存方式即鏈結串列來表示狀態轉移，但由於要線性查詢，會造成效率低下。
於是人們提出了下面兩種結構。[5]
三陣列Trie（Triple-Array Trie）結構包括三個陣列：base,next和check.
二陣列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);
}
參考資料
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
