其它综合

Trie树_字典树(字符串排序)简介及实现

互联网 2014-03-28其它综合4664

有时，我们会碰到对字符串的排序，若采用一些经典的排序算法，则时间复杂度一般为O(n*lgn)，但若采用Trie树，则时间复杂度仅为O(n)

1.综述

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie树结构的优点在于：
1）不限制子节点的数量；
2）自定义的输入序列化，突破了具体语言、应用的限制，成为一个通用的框架；
3）可以进行最大Tokens序列长度的限制；
4）根据已定阈值输出重复的字符串；
5）提供单个字符串频度查找功能；
6）速度快，在两分钟内完成1998年1月份人民日报（19056行）的重复字符串抽取工作。

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");  //已经插入了
       }
}

有时，我们会碰到对字符串的排序，若采用一些经典的排序算法，则时间复杂度一般为O(n*lgn)，但若采用Trie树，则时间复杂度仅为O(n)。

Trie树又名字典树，从字面意思即可理解，这种树的结构像英文字典一样，相邻的单词一般前缀相同，之所以时间复杂度低，是因为其采用了以空间换取时间的策略。

下图为一个针对字符串排序的Trie树(我们假设在这里字符串都是小写字母)，每个结点有26个分支，每个分支代表一个字母，结点存放的是从root节点到达此结点的路经上的字符组成的字符串。

将每个字符串插入到trie树中，到达特定的结尾节点时，在这个节点上进行标记，如插入"afb"，第一个字母为a，沿着a往下，然后第二个字母为f，沿着f往下，第三个为b，沿着b往下，由于字符串最后一个字符为'\0'，因而结束，不再往下了，然后在这个节点上标记afb.count++，即其个数增加1.

之后，通过前序遍历此树，即可得到字符串从小到大的顺序。

实现代码如下（g++、VC++都编译通过）：

复制代码代码如下:

#include <iostream>
#include <string.h>
using namespace std;
#define NUM 26
class Node
{
public:
    int count; //记录该处字符串个数
    Node* char_arr[NUM];  //分支
    char* current_str;   //记录到达此处的路径上的所有字母组成的字符串
    Node();
};
class Trie
{
public:
    Node* root;
    Trie();
    void insert(char* str);
    void output(Node* &node, char** str, int& count);
};
//程序未考虑delete动态内存
int main()
{
    char** str = new char*[12];
    str[0] = "zbdfasd";
    str[1] = "zbcfd";
    str[2] = "zbcdfdasfasf";
    str[3] = "abcdaf";
    str[4] = "defdasfa";
    str[5] = "fedfasfd";
    str[6] = "dfdfsa";
    str[7] = "dadfd";
    str[8] = "dfdfasf";
    str[9] = "abcfdfa";
    str[10] = "fbcdfd";
    str[11] = "abcdaf";
    //建立trie树
    Trie* trie = new Trie();
    for(int i = 0; i < 12; i++)
        trie->insert(str[i]);
    int count = 0;
    trie->output(trie->root, str, count);
    for(int i = 0; i < 12; i++)
        cout<<str[i]<<endl;
    return 0;
}
Node::Node()
{
    count = 0;
    for(int i = 0; i < NUM; i++)
        char_arr[i] = NULL;
    current_str = new char[100];
    current_str[0] = '\0';
}
Trie::Trie()
{
    root = new Node();
}
void Trie::insert(char* str)
{
    int i = 0;
    Node* parent = root;
    //将str[i]插入到trie树中
    while(str[i] != '\0')
    {
        //如果包含str[i]的分支存在，则新建此分支
        if(parent->char_arr[str[i] - 'a'] == NULL)
        {
            parent->char_arr[str[i] - 'a'] = new Node();
            //将父节点中的字符串添加到当前节点的字符串中
            strcat(parent->char_arr[str[i] - 'a']->current_str, parent->current_str);
            char str_tmp[2];
            str_tmp[0] = str[i];
            str_tmp[1] = '\0';
            //将str[i]添加到当前节点的字符串中
            strcat(parent->char_arr[str[i] - 'a']->current_str, str_tmp);
            parent = parent->char_arr[str[i] - 'a'];
        }
        else
        {
            parent = parent->char_arr[str[i] - 'a'];
        }
        i++;
    }
    parent->count++;
}
//采用前序遍历
void Trie::output(Node* &node, char** str, int& count)
{
    if(node != NULL)
    {
        if(node->count != 0)
        {
            for(int i = 0; i < node->count; i++)
                str[count++] = node->current_str;
        }
        for(int i = 0; i < NUM; i++)
        {
            output(node->char_arr[i], str, count);
        }
    }
}