Trie樹/字典樹的簡介及實作

Trie樹|字典樹的簡介及實作

1綜述

又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用于統計，排序和儲存大量的字元串（但不僅限于字元串），是以經常被搜尋引擎系統用于文本詞頻統計。

它的優點是：利用字元串的公共字首來節約存儲空間，最大限度地減少無謂的字元串比較，查詢效率比哈希表高。

Trie樹結構的優點在于：

1） 不限制子節點的數量；

2） 自定義的輸入序列化，突破了具體語言、應用的限制，成為一個通用的架構；

3） 可以進行最大Tokens序列長度的限制；

4） 根據已定門檻值輸出重複的字元串；

5） 提供單個字元串頻度查找功能；

6） 速度快，在兩分鐘内完成1998年1月份人民日報（19056行）的重複字元串抽取工作。

優點來源于Linux公社網站(www.linuxidc.com)http://www.linuxidc.com/Linux/2012-04/57911.htm

2性質

它有3個基本性質：

1)     根節點不包含字元，除根節點外每一個節點都隻包含一個字元。

2)     從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串。

3)     每個節點的所有子節點包含的字元都不相同。

3基本操作

其基本操作有:查找、插入和删除,當然删除操作比較少見.我在這裡隻是實作了對整個樹的删除操作,至于單個word的删除操作也很簡單.

4實作方法

搜尋字典項目的方法為：

 (1) 從根結點開始一次搜尋；

 (2) 取得要查找關鍵詞的第一個字母，并根據該字母選擇對應的子樹并轉到該子樹繼續進行檢索；

 (3) 在相應的子樹上，取得要查找關鍵詞的第二個字母,并進一步選擇對應的子樹進行檢索。

 (4) 疊代過程……

(5) 在某個結點處，關鍵詞的所有字母已被取出，則讀取附在該結點上的資訊，即完成查找。

其他操作類似處理

5. Trie原理——Trie的核心思想是空間換時間。利用字元串的公共字首來降低查詢時間的開銷以達到提高效率的目的。

6.代碼實作

const int branchNum = 26; //聲明常量

int i;

struct Trie_node

{

      boolisStr;                //記錄此處是否構成一個串。

      Trie_node*next[branchNum];//指向各個子樹的指針,下标0-25代表26字元

      Trie_node():isStr(false)

      {

             memset(next,NULL,sizeof(next));

      }

};

class Trie

public:

    Trie();

    voidinsert(const char* word);

    boolsearch(char* word);

    voiddeleteTrie(Trie_node *root);

      // voidprintTrie(Trie_node *root);   //new add

private:

   Trie_node* root;

};

Trie::Trie()

    root =new Trie_node();

}

void Trie::insert(const char* word)

{

   Trie_node*location = root;

  while(*word)

    {

      if(location->next[*word-'a'] == NULL)//不存在則建立

        {

          Trie_node *tmp = new Trie_node();

          location->next[*word-'a'] = tmp;

       }  

      location = location->next[*word-'a']; //每插入一步，相當于有一個新串經過，指針要向下移動

      word++;

   }

  location->isStr = true; //到達尾部,标記一個串

}

bool Trie::search(char *word)

      Trie_node*location = root;

      while(*word&& location)

             location= location->next[*word-'a'];

             word++;

      return(location!=NULL && location->isStr);

void Trie::deleteTrie(Trie_node *root)

      for(i =0; i < branchNum; i++)

             if(root->next[i]!= NULL)

             {

                    deleteTrie(root->next[i]);

             }

      deleteroot;

void main() //簡單測試

      Trie t;

      t.insert("a");        

      t.insert("abandon");

      char * c= "abandoned";

      t.insert(c);

      t.insert("abashed");

      if(t.search("abashed"))

         printf("true\n");  //已經插入了