Trie字典树

图片 2

传统的Trie实现简单,但是占用的空间实在是难以接受,特别是当字符集不仅限于英文26个字符的时候,爆炸起来的空间根本无法接受。

(本文转自百度搜索第一个CSDN博客)

双数组Trie就是优化了空间的Trie树,原理本文就不讲了,请参考An Efficient
Implementation of Trie Structures,本程序的编写也是参考这篇论文的。

一、知识简介

  最近在看字符串算法了,其中字典树、AC自动机和后缀树的应用是最广泛的了,下面将会重点介绍下这几个算法的应用。
  字典树(Trie)可以保存一些字符串->值的对应关系。基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串。

Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k)
,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关。Hash 表号称是
O(1) 的,但在计算 hash 的时候就肯定会是 O(k)
,而且还有碰撞之类的问题;Trie 的缺点是空间消耗很高。
  至于Trie树的实现,可以用数组,也可以用指针动态分配,我做题时为了方便就用了数组,静态分配空间。
Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
Trie树的基本性质可以归纳为:

关于几点论文没有提及的细节和与论文不一一致的实现:

(1)根节点不包含字符,除根节点意外每个节点只包含一个字符。

1.对于插入字符串,如果有一个字符串是另一个字符串的子串的话,我是将结束符也作为一条边,产生一个新的结点,这个结点新节点的Base我置为0

(2)从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。

所以一个字符串结束也有2中情况:一个是Base值为负,存储剩余字符(可能只有一个结束符)到Tail数组;另一个是Base为0。

(3)每个节点的所有子节点包含的字符串不相同。

Trie树有一些特性:

所以在查询的时候要考虑一下这两种情况

1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。

2.对于第一种冲突(论文中的Case
3),可能要将Tail中的字符串取出一部分,作为边放到索引中。论文是使用将尾串左移的方式,我的方式直接修改Base值,而不是移动尾串。

2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。

下面是java实现的代码,可以处理相同字符串插入,子串的插入等情况

3)每个节点的所有子节点包含的字符都不相同。
/*  
 * Name:   Double Array Trie  
 * Author: Yaguang Ding  
 * Mail: dingyaguang117@gmail.com  
 * Blog: blog.csdn.net/dingyaguang117  
 * Date:   2012/5/21  
 * Note: a word ends may be either of these two case:  
 * 1. Base[cur_p] == pos  ( pos<0 and Tail[-pos] == 'END_CHAR' )  
 * 2. Check[Base[cur_p] + Code('END_CHAR')] ==  cur_p  
 */ 

import java.util.ArrayList;  
import java.util.HashMap;  
import java.util.Map;  
import java.util.Arrays;  

public class DoubleArrayTrie {  
    final char END_CHAR = '';  
    final int DEFAULT_LEN = 1024;  
    int Base[]  = new int [DEFAULT_LEN];  
    int Check[] = new int [DEFAULT_LEN];  
    char Tail[] = new char [DEFAULT_LEN];  
    int Pos = 1;  
    Map<Character ,Integer> CharMap = new HashMap<Character,Integer>();  
    ArrayList<Character> CharList = new ArrayList<Character>();  

    public DoubleArrayTrie()  
    {  
        Base[1] = 1;  

        CharMap.put(END_CHAR,1);  
        CharList.add(END_CHAR);  
        CharList.add(END_CHAR);  
        for(int i=0;i<26;++i)  
        {  
            CharMap.put((char)('a'+i),CharMap.size()+1);  
            CharList.add((char)('a'+i));  
        }  

    }  
    private void Extend_Array()  
    {  
        Base = Arrays.copyOf(Base, Base.length*2);  
        Check = Arrays.copyOf(Check, Check.length*2);  
    }  

    private void Extend_Tail()  
    {  
        Tail = Arrays.copyOf(Tail, Tail.length*2);  
    }  

    private int GetCharCode(char c)  
    {  
        if (!CharMap.containsKey(c))  
        {  
            CharMap.put(c,CharMap.size()+1);  
            CharList.add(c);  
        }  
        return CharMap.get(c);  
    }  
    private int CopyToTailArray(String s,int p)  
    {  
        int _Pos = Pos;  
        while(s.length()-p+1 > Tail.length-Pos)  
        {  
            Extend_Tail();  
        }  
        for(int i=p; i<s.length();++i)  
        {  
            Tail[_Pos] = s.charAt(i);  
            _Pos++;  
        }  
        return _Pos;  
    }  

    private int x_check(Integer []set)  
    {  
        for(int i=1; ; ++i)  
        {  
            boolean flag = true;  
            for(int j=0;j<set.length;++j)  
            {  
                int cur_p = i+set[j];  
                if(cur_p>= Base.length) Extend_Array();  
                if(Base[cur_p]!= 0 || Check[cur_p]!= 0)  
                {  
                    flag = false;  
                    break;  
                }  
            }  
            if (flag) return i;  
        }  
    }  

    private ArrayList<Integer> GetChildList(int p)  
    {  
        ArrayList<Integer> ret = new ArrayList<Integer>();  
        for(int i=1; i<=CharMap.size();++i)  
        {  
            if(Base[p]+i >= Check.length) break;  
            if(Check[Base[p]+i] == p)  
            {  
                ret.add(i);  
            }  
        }  
        return ret;  
    }  

    private boolean TailContainString(int start,String s2)  
    {  
        for(int i=0;i<s2.length();++i)  
        {  
            if(s2.charAt(i) != Tail[i+start]) return false;  
        }  

        return true;  
    }  
    private boolean TailMatchString(int start,String s2)  
    {  
        s2 += END_CHAR;  
        for(int i=0;i<s2.length();++i)  
        {  
            if(s2.charAt(i) != Tail[i+start]) return false;  
        }  
        return true;  
    }  

    public void Insert(String s) throws Exception  
    {  
        s += END_CHAR;  

        int pre_p = 1;  
        int cur_p;  
        for(int i=0; i<s.length(); ++i)  
        {  
            //获取状态位置  
            cur_p = Base[pre_p]+GetCharCode(s.charAt(i));  
            //如果长度超过现有,拓展数组  
            if (cur_p >= Base.length) Extend_Array();  

            //空闲状态  
            if(Base[cur_p] == 0 && Check[cur_p] == 0)  
            {  
                Base[cur_p] = -Pos;  
                Check[cur_p] = pre_p;  
                Pos = CopyToTailArray(s,i+1);  
                break;  
            }else 
            //已存在状态  
            if(Base[cur_p] > 0 && Check[cur_p] == pre_p)  
            {  
                pre_p = cur_p;  
                continue;  
            }else 
            //冲突 1:遇到 Base[cur_p]小于0的,即遇到一个被压缩存到Tail中的字符串  
            if(Base[cur_p] < 0 && Check[cur_p] == pre_p)  
            {  
                int head = -Base[cur_p];  

                if(s.charAt(i+1)== END_CHAR && Tail[head]==END_CHAR)    //插入重复字符串  
                {  
                    break;  
                }  

                //公共字母的情况,因为上一个判断已经排除了结束符,所以一定是2个都不是结束符  
                if (Tail[head] == s.charAt(i+1))  
                {  
                    int avail_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1))});  
                    Base[cur_p] = avail_base;  

                    Check[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;  
                    Base[avail_base+GetCharCode(s.charAt(i+1))] = -(head+1);  
                    pre_p = cur_p;  
                    continue;  
                }  
                else 
                {  
                    //2个字母不相同的情况,可能有一个为结束符  
                    int avail_base ;  
                    avail_base = x_check(new Integer[]{GetCharCode(s.charAt(i+1)),GetCharCode(Tail[head])});  

                    Base[cur_p] = avail_base;  

                    Check[avail_base+GetCharCode(Tail[head])] = cur_p;  
                    Check[avail_base+GetCharCode(s.charAt(i+1))] = cur_p;  

                    //Tail 为END_FLAG 的情况  
                    if(Tail[head] == END_CHAR)  
                        Base[avail_base+GetCharCode(Tail[head])] = 0;  
                    else 
                        Base[avail_base+GetCharCode(Tail[head])] = -(head+1);  
                    if(s.charAt(i+1) == END_CHAR)   
                        Base[avail_base+GetCharCode(s.charAt(i+1))] = 0;  
                    else 
                        Base[avail_base+GetCharCode(s.charAt(i+1))] = -Pos;  

                    Pos = CopyToTailArray(s,i+2);  
                    break;  
                }  
            }else 
            //冲突2:当前结点已经被占用,需要调整pre的base  
            if(Check[cur_p] != pre_p)  
            {  
                ArrayList<Integer> list1 = GetChildList(pre_p);  
                int toBeAdjust;  
                ArrayList<Integer> list = null;  
                if(true)  
                {  
                    toBeAdjust = pre_p;  
                    list = list1;  
                }  

                int origin_base = Base[toBeAdjust];  
                list.add(GetCharCode(s.charAt(i)));  
                int avail_base = x_check((Integer[])list.toArray(new Integer[list.size()]));  
                list.remove(list.size()-1);  

                Base[toBeAdjust] = avail_base;  
                for(int j=0; j<list.size(); ++j)  
                {  
                    //BUG   
                    int tmp1 = origin_base + list.get(j);  
                    int tmp2 = avail_base + list.get(j);  

                    Base[tmp2] = Base[tmp1];  
                    Check[tmp2] = Check[tmp1];  

                    //有后续  
                    if(Base[tmp1] > 0)  
                    {  
                        ArrayList<Integer> subsequence = GetChildList(tmp1);  
                        for(int k=0; k<subsequence.size(); ++k)  
                        {  
                            Check[Base[tmp1]+subsequence.get(k)] = tmp2;  
                        }  
                    }  

                    Base[tmp1] = 0;  
                    Check[tmp1] = 0;  
                }  

                //更新新的cur_p  
                cur_p = Base[pre_p]+GetCharCode(s.charAt(i));  

                if(s.charAt(i) == END_CHAR)  
                    Base[cur_p] = 0;  
                else 
                    Base[cur_p] = -Pos;  
                Check[cur_p] = pre_p;  
                Pos = CopyToTailArray(s,i+1);  
                break;  
            }  
        }  
    }  

    public boolean Exists(String word)  
    {  
        int pre_p = 1;  
        int cur_p = 0;  

        for(int i=0;i<word.length();++i)  
        {  
            cur_p = Base[pre_p]+GetCharCode(word.charAt(i));  
            if(Check[cur_p] != pre_p) return false;  
            if(Base[cur_p] < 0)  
            {  
                if(TailMatchString(-Base[cur_p],word.substring(i+1)))  
                    return true;  
                return false;  
            }  
            pre_p = cur_p;  
        }  
        if(Check[Base[cur_p]+GetCharCode(END_CHAR)] == cur_p)  
            return true;  
        return false;  
    }  

    //内部函数,返回匹配单词的最靠后的Base index,  
    class FindStruct  
    {  
        int p;  
        String prefix="";  
    }  
    private FindStruct Find(String word)  
    {  
        int pre_p = 1;  
        int cur_p = 0;  
        FindStruct fs = new FindStruct();  
        for(int i=0;i<word.length();++i)  
        {  
            // BUG  
            fs.prefix += word.charAt(i);  
            cur_p = Base[pre_p]+GetCharCode(word.charAt(i));  
            if(Check[cur_p] != pre_p)  
            {  
                fs.p = -1;  
                return fs;  
            }  
            if(Base[cur_p] < 0)  
            {  
                if(TailContainString(-Base[cur_p],word.substring(i+1)))  
                {  
                    fs.p = cur_p;  
                    return fs;  
                }  
                fs.p = -1;  
                return fs;  
            }  
            pre_p = cur_p;  
        }  
        fs.p =  cur_p;  
        return fs;  
    }  

    public ArrayList<String> GetAllChildWord(int index)  
    {  
        ArrayList<String> result = new ArrayList<String>();  
        if(Base[index] == 0)  
        {  
            result.add("");  
            return result;  
        }  
        if(Base[index] < 0)  
        {  
            String r="";  
            for(int i=-Base[index];Tail[i]!=END_CHAR;++i)  
            {  
                r+= Tail[i];  
            }  
            result.add(r);  
            return result;  
        }  
        for(int i=1;i<=CharMap.size();++i)  
        {  
            if(Check[Base[index]+i] == index)  
            {  
                for(String s:GetAllChildWord(Base[index]+i))  
                {  
                    result.add(CharList.get(i)+s);  
                }  
                //result.addAll(GetAllChildWord(Base[index]+i));  
            }  
        }  
        return result;  
    }  

    public ArrayList<String> FindAllWords(String word)  
    {  
        ArrayList<String> result = new ArrayList<String>();  
        String prefix = "";  
        FindStruct fs = Find(word);  
        int p = fs.p;  
        if (p == -1) return result;  
        if(Base[p]<0)  
        {  
            String r="";  
            for(int i=-Base[p];Tail[i]!=END_CHAR;++i)  
            {  
                r+= Tail[i];  
            }  
            result.add(fs.prefix+r);  
            return result;  
        }  

        if(Base[p] > 0)  
        {  
            ArrayList<String> r =  GetAllChildWord(p);  
            for(int i=0;i<r.size();++i)  
            {  
                r.set(i, fs.prefix+r.get(i));  
            }  
            return r;  
        }  

        return result;  
    }  

}
4)如果字符的种数为n,则每个结点的出度为n,这也是空间换时间的体现,浪费了很多的空间。

测试代码:

5)插入查找的复杂度为O(n),n为字符串长度。

基本思想(以字母树为例):

import java.io.BufferedReader;  
import java.io.FileInputStream;  
import java.io.IOException;  
import java.io.InputStream;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.Scanner;  

import javax.xml.crypto.Data;  

public class Main {  

    public static void main(String[] args) throws Exception {  
        ArrayList<String> words = new ArrayList<String>();  
        BufferedReader reader = new BufferedReader(new InputStreamReader(new FileInputStream("E:/兔子的试验学习中心[课内]/ACM大赛/ACM第四届校赛/E命令提示/words3.dic")));  
        String s;  
        int num = 0;  
        while((s=reader.readLine()) != null)  
        {  
            words.add(s);  
            num ++;  
        }  
        DoubleArrayTrie dat = new DoubleArrayTrie();  

        for(String word: words)  
        {  
            dat.Insert(word);  
        }  

        System.out.println(dat.Base.length);  
        System.out.println(dat.Tail.length);  

        Scanner sc = new Scanner(System.in);  
        while(sc.hasNext())  
        {  
            String word = sc.next();  
            System.out.println(dat.Exists(word));  
            System.out.println(dat.FindAllWords(word));  
        }  

    }  

}
1、插入过程

对于一个单词,从根开始,沿着单词的各个字母所对应的树中的节点分支向下走,直到单词遍历完,将最后的节点标记为红色,表示该单词已插入Trie树。

下面是测试结果,构造6W英文单词的DAT,大概需要20秒

2、查询过程

同样的,从根开始按照单词的字母顺序向下遍历trie树,一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色,则表示该单词不存在,若最后的节点标记为红色,表示该单词存在。

我增长数组的时候是每次长度增加到2倍,初始1024

二、字典树的数据结构:

利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。
下面以英文单词构建的字典树为例,这棵Trie树中每个结点包括26个孩子结点,因为总共有26个英文字母(假设单词都是小写字母组成)。
则可声明包含Trie树的结点信息的结构体:

typedef struct Trie_node  
{  
    int count;                    // 统计单词前缀出现的次数  
    struct Trie_node* next[26];   // 指向各个子树的指针  
    bool exist;                   // 标记该结点处是否构成单词    
}TrieNode , *Trie;  

其中next是一个指针数组,存放着指向各个孩子结点的指针。
如给出字符串”abc”,”ab”,”bd”,”dda”,根据该字符串序列构建一棵Trie树。则构建的树如下:

图片 1

Trie树的根结点不包含任何信息,第一个字符串为”abc”,第一个字母为’a’,因此根结点中数组next下标为’a’-97的值不为NULL,其他同理,构建的Trie树如图所示,红色结点表示在该处可以构成一个单词。很显然,如果要查找单词”abc”是否存在,查找长度则为O(len),len为要查找的字符串的长度。而若采用一般的逐个匹配查找,则查找长度为O(len*n),n为字符串的个数。显然基于Trie树的查找效率要高很多。
如上图中:Trie树中存在的就是abc、ab、bd、dda四个单词。在实际的问题中可以将标记颜色的标志位改为数量count等其他符合题目要求的变量。
已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

1、
最容易想到的:即从字符串集中从头往后搜,看每个字符串是否为字符串集中某个字符串的前缀,复杂度为O(n^2)。

2、
使用hash:我们用hash存下所有字符串的所有的前缀子串。建立存有子串hash的复杂度为O(nlen)。查询的复杂度为O(n)
O(1)= O(n)。

3、
使用Trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b、c、d….等不是以a开头的字符串就不用查找了,这样迅速缩小查找的范围和提高查找的针对性。所以建立Trie的复杂度为O(nlen),而建立+查询在trie中是可以同时执行的,建立的过程也就可以成为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(nlen),实际查询的复杂度只是O(len)。

Base和Check数组的长度为131072

三、Trie树的操作

在Trie树中主要有3个操作,插入、查找和删除。一般情况下Trie树中很少存在删除单独某个结点的情况,因此只考虑删除整棵树。

1、插入
假设存在字符串str,Trie树的根结点为root。i=0,p=root。
1)取str[i],判断p->next[str[i]-97]是否为空,若为空,则建立结点temp,并将p->next[str[i]-97]指向temp,然后p指向temp;
若不为空,则p=p->next[str[i]-97];
2)i++,继续取str[i],循环1)中的操作,直到遇到结束符’’,此时将当前结点p中的
exist置为true。
2、查找
假设要查找的字符串为str,Trie树的根结点为root,i=0,p=root
1)取str[i],判断判断p->next[str[i]-97]是否为空,若为空,则返回false;若不为空,则p=p->next[str[i]-97],继续取字符。
2)重复1)中的操作直到遇到结束符’’,若当前结点p不为空并且 exist
为true,则返回true,否则返回false。
3、删除
删除可以以递归的形式进行删除。

Tail的长度为262144

图片 2

You can leave a response, or trackback from your own site.

Leave a Reply

网站地图xml地图