又稱(chēng)單詞查找樹(shù)，Trie樹(shù)，是一種樹(shù)形結(jié)構(gòu)，是一種哈希樹(shù)的變種。典型應(yīng)用是用于統(tǒng)計(jì)，排序和保存大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是：利用字符串的公共前綴來(lái)節(jié)約存儲(chǔ)空間，最大限度地減少無(wú)謂的字符串比較，查詢(xún)效率比哈希表高。
字典樹(shù)與字典很相似,當(dāng)你要查一個(gè)單詞是不是在字典樹(shù)中,首先看單詞的第一個(gè)字母是不是在字典的第一層,如果不在,說(shuō)明字典樹(shù)里沒(méi)有該單詞,如果在就在該字母的孩子節(jié)點(diǎn)里找是不是有單詞的第二個(gè)字母,沒(méi)有說(shuō)明沒(méi)有該單詞,有的話(huà)用同樣的方法繼續(xù)查找.字典樹(shù)不僅可以用來(lái)儲(chǔ)存字母,也可以?xún)?chǔ)存數(shù)字等其它數(shù)據(jù)。
Trie的數(shù)據(jù)結(jié)構(gòu)定義：
#define MAX 26
typedef struct Trie
{
Trie *next[MAX];
int v; //根據(jù)需要變化
};
Trie *root;
next是表示每層有多少種類(lèi)的數(shù)，如果只是小寫(xiě)字母，則26即可，若改為大小寫(xiě)字母，則是52，若再加上數(shù)字，則是62了，這里根據(jù)題意來(lái)確定。
v可以表示一個(gè)字典樹(shù)到此有多少相同前綴的數(shù)目，這里根據(jù)需要應(yīng)當(dāng)學(xué)會(huì)自由變化。
Trie的查找（最主要的操作）：
(1) 每次從根結(jié)點(diǎn)開(kāi)始一次搜索；
(2) 取得要查找關(guān)鍵詞的第一個(gè)字母，并根據(jù)該字母選擇對(duì)應(yīng)的子樹(shù)并轉(zhuǎn)到該子樹(shù)繼續(xù)進(jìn)行檢索； (3) 在相應(yīng)的子樹(shù)上，取得要查找關(guān)鍵詞的第二個(gè)字母,并進(jìn)一步選擇對(duì)應(yīng)的子樹(shù)進(jìn)行檢索。
(4) 迭代過(guò)程……
(5) 在某個(gè)結(jié)點(diǎn)處，關(guān)鍵詞的所有字母已被取出，則讀取附在該結(jié)點(diǎn)上的信息，即完成查找。
這里給出生成字典樹(shù)和查找的模版：
生成字典樹(shù)：
void createTrie(char *str)
{
int len = strlen(str);
Trie *p = root, *q;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
if(p->next[id] == NULL)
{
q = (Trie *)malloc(sizeof(Trie));
q->v = 1; //初始v==1
for(int j=0; j<MAX; ++j)
q->next[j] = NULL;
p->next[id] = q;
p = p->next[id];
}
else
{
p->next[id]->v++;
p = p->next[id];
}
}
p->v = -1; //若為結(jié)尾，則將v改成-1表示
}
接下來(lái)是查找的過(guò)程了：
int findTrie(char *str)
{
int len = strlen(str);
Trie *p = root;
for(int i=0; i<len; ++i)
{
int id = str[i]-'0';
p = p->next[id];
if(p == NULL) //若為空集，表示不存以此為前綴的串
return 0;
if(p->v == -1) //字符集中已有串是此串的前綴
return -1;
}
return -1; //此串是字符集中某串的前綴
}
對(duì)于上述動(dòng)態(tài)字典樹(shù)，有時(shí)會(huì)超內(nèi)存，比如
HDOJ 1671 Phone List，這是就要記得
釋放空間了：
int dealTrie(Trie* T)
{
int i;
if(T==NULL)
return 0;
for(i=0;i<MAX;i++)
{
if(T->next[i]!=NULL)
deal(T->next[i]);
}
free(T);
return 0;
}
題目分析+解答報(bào)告：
HDOJ 1251 統(tǒng)計(jì)難題：
http://www.wutianqi.com/?p=1364
HDOJ 1671 Phone List
http://www.wutianqi.com/?p=1366
這里還有幾個(gè)字典樹(shù)的相關(guān)資料，我上傳了RaySource里了，順便和大家分享下：
算法合集之《淺析字母樹(shù)在信息學(xué)競(jìng)賽中的應(yīng)用》
字典樹(shù)
posted on 2010-09-24 09:17
Tanky Woo 閱讀(2238)
評(píng)論(1) 編輯 收藏 引用