精华内容
下载资源
问答
  • 中文trie树

    千次阅读 2011-07-01 10:31:00
    这几天被汉字trie树小折腾了一下。 开始的时候想直接将单字节作为字典树的节点建树,虽然各个树的节点可能只是多字节字符的一部分,但是基本功能也能够支持。后来发现似乎有些问题,比如在做前向最大匹配分词的时候...

    这几天被汉字trie树小折腾了一下。

    开始的时候想直接将单字节作为字典树的节点建树,虽然各个树的节点可能只是多字节字符的一部分,但是基本功能也能够支持。后来发现似乎有些问题,比如在做前向最大匹配分词的时候,对于未登录词无法确定当前字符是单字节还是多字节,如果通过编码规则进行判定的话倒也可以,但是跟建树过程南辕北辙。

    然后想到了utf16字符编码对所有字符统一采用16位定长处理,这样的话只要对待处理字符串每两字节进行一次截取就能得到完整字符,当然树的节点也是这样有意义的完整字符。可是问题依然存在,fgets() 这种函数肯定用不了,因为utf16中充斥这各种值为0和a的字节,对于fgets()来说a就是行尾。linux中对宽字节字符处理函数经常莫名其妙罢工,例如fgetws()读取文件的时候总是直接返回NULL,各种不给力。。。

    最后还是回到utf8,通过对utf8编码方式分析,utf8是一种变长编码方式,通过首字节即可判断出当前字符字节数。这样在建树时候就可以以字符作为节点,无论是单字节字符(ASCII)还是三字节字符(绝大多数汉字)都可以存入trie树中,在对字符串分析时同样可以轻松确定字符长度

    展开全文
  • 剑指Offer——Trie树(字典树)

    万次阅读 多人点赞 2016-09-07 21:21:30
    剑指Offer——Trie树(字典树)Trie树 Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频...

    剑指Offer——Trie树(字典树)

    Trie树

        Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

        Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

        Trie树也有它的缺点,Trie树的内存消耗非常大。当然,或许用左儿子右兄弟的方法建树的话,可能会好点。可见,优化的点存在于建树过程中。

     和二叉查找树不同,在trie树中,每个结点上并非存储一个元素。trie树把要查找的关键词看作一个字符序列,并根据构成关键词字符的先后顺序构造用于检索的树结构。在trie树上进行检索类似于查阅英语词典。

    3个基本性质

       1.根节点不包含字符,每条边代表一个字符。

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

       3.每个节点的所有子节点包含的字符都不相同。

    字典树的构建

      题目:给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,求第一次出现在第几个位置。

      分析:这题当然可以用hash来解决,但是本文重点介绍的是trie树,因为在某些方面它的用途更大。比如说对于某一个单词,我们要询问它的前缀是否出现过。这样hash就不好搞了,而用trie还是很简单。

      假设我要查询的单词是abcd,那么在他前面的单词中,以b,c,d,f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的,在以a开头中的单词中,我们只要考虑以b作为第二个字母的,一次次缩小范围和提高针对性,这样一个树的模型就渐渐清晰了。

      好比假设有b,abc,abd,bcd,abcd,efg,hii 这6个单词,我们构建的树就是如下图这样的(图片来自百度百科):

        如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为红色,就表示这个单词存在,否则不存在。

        那么,对于一个单词,我只要顺着他从根走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色,就相当于插入了这个单词。

        这样一来我们查询和插入可以一起完成(重点体会这个查询和插入是如何一起完成的,稍后,下文具体解释)。

      我们可以看到,trie树每一层的节点数是26^i(26个英文字母)级别的。所以为了节省空间,我们用动态链表,或者用数组来模拟。空间的花费,不会超过单词数×单词长度。

      已知n个由小写字母构成的平均长度为10的单词,判断其中是否存在某个串为另一个串的前缀子串。下面对比3种方法:

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

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

      3.使用trie:因为当查询如字符串abc是否为某个字符串的前缀时,显然以b,c,d....等不是以a开头的字符串就不用查找了。所以建立trie的复杂度为O(n*len),而建立+查询在trie中是可以同时执行的,建立的过程也就可以称为查询的过程,hash就不能实现这个功能。所以总的复杂度为O(n*len),实际查询的复杂度也只是O(len)。(说白了,就是Trie树的平均高度h为len,所以Trie树的查询复杂度为O(h)=O(len)。好比一棵二叉平衡树的高度为logN,则其查询,插入的平均时间复杂度亦为O(logN))。

    查询

        Trie树是简单但实用的数据结构,通常用于实现字典查询。我们做即时响应用户输入的AJAX搜索框时,就是Trie树。本质上,Trie是一棵存储多个字符串的树。相邻节点间的边代表一个字符,这样树的每条分支代表一则子串,而树的叶节点则代表完整的字符串。和普通树不同的地方是,相同的字符串前缀共享同一条分支。下面,再举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:

        可以看出:

        每条边对应一个字母。

        每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。

      单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。

      查询操纵非常简单。比如要查找int,顺着路径i -> in -> int就找到了。

      搭建Trie的基本算法也很简单,无非是逐一把每个单词的每个字母插入Trie。插入前先看前缀是否存在。如果存在,就共享,否则创建对应的节点和边。比如要插入单词add,就有下面几步:

      考察前缀"a",发现边a已经存在。于是顺着边a走到节点a。

      考察剩下的字符串"dd"的前缀"d",发现从节点a出发,已经有边d存在。于是顺着边d走到节点ad

      考察最后一个字符"d",这下从节点ad出发没有边d了,于是创建节点ad的子节点add,并把边ad->add标记为d。

    查找分析

      在trie树中查找一个关键字的时间和树中包含的结点数无关,而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。

        如果要查找的关键字可以分解成字符序列且不是很长,利用trie树查找速度优于二叉查找树。例如:若关键字长度最大是5,则利用trie树,利用5次比较可以从26^5=11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行次比较。

    应用

    1. 字符串检索,词频统计,搜索引擎的热门查询

      事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。

       举例:

        1、有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

        2、给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。

        3、给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

        4、1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串。请怎么设计和实现?

        5、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析。

        6、寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G(京东笔试题简答题与此类似)。

        (1) 请描述你解决这个问题的思路;

        (2) 请给出主要的处理流程,算法,以及算法的复杂度。

    2. 字符串最长公共前缀

        Trie树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。举例:

        1) 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少.  解决方案:

      首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线(Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。

        而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:

          1. 利用并查集(Disjoint Set),可以采用经典的Tarjan 算法;

          2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;

    3.  排序

          Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。

          举例:给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。

    4. 作为其他数据结构和算法的辅助结构

       如后缀树,AC自动机等。

    举例

       下面以字典树的构建与单词查找为例。

     

    TrieTreeNode.java

     

     

    package cn.edu.ujn.trieTree;
     
    public class TrieTreeNode {
        int nCount;	//记录该字符出现次数  
        char ch; //记录该字符  
        TrieTreeNode[] child;	// 记录子节点  
        final int MAX_SIZE = 26;
        public TrieTreeNode() {  
            nCount=1;  
            child = new TrieTreeNode[MAX_SIZE];
        }  
    }

     

    TrieTree.java

     

    package cn.edu.ujn.trieTree;
     
    public class TrieTree {
        //字典树的插入和构建  
        public void createTrie(TrieTreeNode node,String str){  
            if (str == null || str.length() == 0) {  
                return;
            }
            char[] letters = str.toCharArray();
            for (int i = 0; i < letters.length; i++) {  
                int pos = letters[i] - 'a';	  // 用相对于a字母的值作为下标索引,也隐式地记录了该字母的值  
                if (node.child[pos] == null) {
                    node.child[pos] = new TrieTreeNode();
                }else {
                    node.child[pos].nCount++;
                }
                node.ch = letters[i];              
                node = node.child[pos];              
            }  
        }  
        
        //字典树的查找  
        public int findCount(TrieTreeNode node,String str){  
            if (str == null || str.length() == 0) {  
                return -1;
            }  
            char[] letters = str.toCharArray();
            for (int i = 0; i < letters.length; i++) {  
                int pos = letters[i] - 'a';
                if (node.child[pos] == null) {    
                    return 0;     
                }else {  
                    node = node.child[pos];  
                }           
            }
            return node.nCount;
        }  
     
    }

     

    Test.java

     

    package cn.edu.ujn.trieTree;
     
    public class Test {
    public static void main(String[] args) {
    /**
     * Problem Description 老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计
     * 出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
     */
    String[] strs = { "banana", "band", "bee", "absolute", "acm" };
    String[] prefix = { "ba", "b", "band", "abc" };
    TrieTree tree = new TrieTree();
    TrieTreeNode root = new TrieTreeNode();
     
    for (String s : strs) {
    tree.createTrie(root, s);
    }
    // tree.printAllWords();
    for (String pre : prefix) {
    int num = tree.findCount(root, pre);
    System.out.println(pre + " " + num);
    }
    }
    }

     

    小结

      看过上面的代码,是否发现这个代码有什么问题呢?尽管这个实现方式查找的效率很高,时间复杂度是O(m),m是要查找的单词中包含的字母的个数。但是确浪费大量存放空指针的存储空间。因为不可能每个节点的子节点都包含26个字母的。所以对于这个问题,字典树存在的意义是解决快速搜索的问题,所以采取以空间换时间的作法也毋庸置疑。

        Trie树占用内存较大,例如:处理最大长度为20、全部为小写字母的一组字符串,则可能需要 2620 个节点来保存数据。而这样的树实际上稀疏的十分厉害,可以采用左儿子右兄弟的方式来改善,也可以采用需要多少子节点则添加多少子节点来解决(不要类似网上的示例,每个节点初始化时就申请一个长度为26的数组)。

    Wiki上提到了采用三数组Trie(Tripple-Array Trie)和二数组Trie(Double-Array Trie)来解决该问题,此外还有压缩等方式来缓解该问题。

    示例优化

    TrieTreeNode.java

     

     

    package cn.edu.ujn.trieTreeMap;
     
    import java.util.HashMap;
    import java.util.Map;
     
    public class TrieNode {
        int nCount;	//记录该字符出现次数  
        Map<Character, TrieNode> childdren;	// 记录子节点  
        public TrieNode() {  
            nCount = 1;  
            childdren = new HashMap<Character, TrieNode>();
        }  
    }

     

    TrieTree.java

     

     

    package cn.edu.ujn.trieTreeMap;
     
    // 利用Map动态创建节点
    public class TrieTree {
     
        // 字典树的插入和构建
        public void insert(TrieNode node, String word) {
            for (int i = 0; i < word.length(); i++) {
                Character c = new Character(word.charAt(i));
                if (!node.childdren.containsKey(c)) {
                    node.childdren.put(c, new TrieNode());
                }else{
                	node.childdren.get(c).nCount++;
                }
                node = node.childdren.get(c);
            }
        }
     
        // 字典树的查找
        public int search(TrieNode node, String word) {
            for (int i = 0; i < word.length(); i++) {
                Character c = new Character(word.charAt(i));
                if (!node.childdren.containsKey(c)) {
                    return 0;
                }
                node = node.childdren.get(c);
            }
            return node.nCount;
        }
     
    }

     

    Test.java

     

    package cn.edu.ujn.trieTreeMap;
     
    public class Test {
    public static void main(String[] args) {
    /**
     * Problem Description 老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计
     * 出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
     */
    String[] strs = { "banana", "band", "bee", "absolute", "acm" };
    String[] prefix = { "ba", "b", "band", "abc" };
    TrieTree tree = new TrieTree();
    TrieNode node = new TrieNode();
    for (String s : strs) {
    tree.insert(node, s);
    }
    // tree.printAllWords();
    for (String pre : prefix) {
    int num = tree.search(node, pre);
    System.out.println(pre + " " + num);
    }
    }
    }

     

    计算结果如下:

      经过以上方法的改进,可避免冗余节点的存在。将字典树的优势进一步放大。当然,也可以使用左儿子右兄弟的形式创建字典树。此方法后续介绍~

    文件读入

     

    package cn.edu.ujn.trieTreeMap;
     
    import java.io.BufferedReader;
    import java.io.File;
    import java.io.FileInputStream;
    import java.io.InputStreamReader;
     
    public class Test {
    public static void main(String[] args) {
    /**
     * Problem Description 老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计
     * 出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
     */
    String[] strs = { "banana", "band", "bee", "absolute", "acm" };
    String[] prefix = { "网易", "软件", "band", "abc" };
    TrieTree tree = new TrieTree();
    TrieNode node = new TrieNode();
            BufferedReader br = null;  
            try {  
                File file= new File("C://Users//SHQ//Desktop//Offer.txt");  
                //读取语料库words.txt  
                br = new BufferedReader(new InputStreamReader(new FileInputStream(file.getAbsolutePath()),"GBK"));  
                String word="";  
                while ((word = br.readLine()) != null) {  
                	tree.insert(node, word);
                }
            }catch (Exception e) {
    // TODO: handle exception
            	e.printStackTrace();
    }
    /*for (String s : strs) {
    tree.insert(node, s);
    }*/
    // tree.printAllWords();
    for (String pre : prefix) {
    int num = tree.search(node, pre);
    System.out.println(pre + " " + num);
    }
    }
    }

     

    计算结果如下:

        Offer.txt文本内容如下:

        可知计算结果正确。而且出现了中文字符,对于数字的操作同理。而利用第一种方法就无法实现固定分配内存。只能使用动态分配机制。

    美文美图

     

    展开全文
  • Trie树 原理 又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,能在常数时间O(len)内实现插入和查询操作,是一种以...

    Trie树

    原理

    又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,能在常数时间O(len)内实现插入和查询操作,是一种以空间换取时间的数据结构,广泛用于词频统计和输入统计领域。

    来看看Trie树长什么样,我们从百度找一张图片:

    enter description here

    字典树在查找时,先看第一个字是否在字典树里,如果在继续往下,如果不在,则字典里不存在,因此,对于一个长度为len的字符串,可以在O(len)时间内完成查询。

    实现trie树

    怎么实现trie树呢,trie树的关键是一个节点要在O(1)时间跳转到下一级节点,因此链表方式不可取,最好用数组来存储下一级节点。问题就来了,如果是纯英文字母,长度26的数组就可以搞定,N个节点的数,就需要N个长度为26的数组。但是,如果包含中文等字符呢,就需要N个65535的数组,特别占用存储空间。当然,可以考虑使用map来存储下级节点。

    定义一个Node,包含节点的Character word,以及下级节点nexts和节点可能附件的值values:

    public static class Node<T> {
            Character word;
    
            List<T> values;
    
            Map<Character, Node> nexts = new HashMap<>(24);
    
            public Node() {
            }
    
            public Node(Character word) {
                this.word = word;
            }
    
            public Character getWord() {
                return word;
            }
    
            public void setWord(Character word) {
                this.word = word;
            }
    
            public void addValue(T value){
                if(values == null){
                    values = new ArrayList<>();
                }
                values.add(value);
            }
    
            public List<T> getValues() {
                return values;
            }
    
            public Map<Character, Node> getNexts() {
                return nexts;
            }
    
            /**
             * @param node
             */
            public void addNext(Node node) {
                this.nexts.put(node.getWord(), node);
            }
    
            public Node getNext(Character word) {
                return this.nexts.get(word);
            }
        }
    

    来看如何构建字典树,首先定义一棵树,包含根节点即可

    
        public static class Trie<T> {
            Node<T> rootNode;
    
            public Trie() {
                this.rootNode = new Node<T>();
            }
    
            public Node<T> getRootNode() {
                return rootNode;
            }
    
        }

    构建树,拆分成单字,然后逐级构建树。

     public static class TrieBuilder {
            public static  Trie<String> buildTrie(String... values){
                Trie<String> trie = new Trie<String>();
                for(String sentence : values){
                    // 根节点
                    Node<String> currentNode = trie.getRootNode();
                    for (int i = 0; i < sentence.length(); i++) {
                        Character character = sentence.charAt(i);
                        // 寻找首个节点
                        Node<String> node = currentNode.getNext(character);
                        if(node == null){
                            // 不存在,创建节点
                            node = new Node<String>(character);
                            currentNode.addNext(node);
                        }
                        currentNode = node;
                    }
    
                    // 添加数据
                    currentNode.addValue(sentence);
                }
    
                return trie;
            }

    Trie树应用

    比如判断一个词是否在字典树里,非常简单,逐级匹配,末了判断最后的节点是否包含数据:

       public boolean isContains(String word) {
                if (word == null || word.length() == 0) {
                    return false;
                }
                Node<T> currentState = rootNode;
                for (int i = 0; i < word.length(); i++) {
                    currentState = currentState.getNext(word.charAt(i));
                    if (currentState == null) {
                        return false;
                    }
                }
                return currentState.getValues()!=null;
            }

    测试代码:

            public static void main(String[] args) {
    
                Trie trie = TrieBuilder.buildTrie("刘德华","刘三姐","刘德刚","江姐");
                System.out.println(trie.isContains("刘德华"));
                System.out.println(trie.isContains("刘德"));
                System.out.println(trie.isContains("刘大大"));
            }

    结果:

    true
    false
    false

    双数组Trie树

    在Trie数实现过程中,我们发现了每个节点均需要 一个数组来存储next节点,非常占用存储空间,空间复杂度大,双数组Trie树正是解决这个问题的。双数组Trie树(DoubleArrayTrie)是一种空间复杂度低的Trie树,应用于字符区间大的语言(如中文、日文等)分词领域。

    原理

    双数组的原理是,将原来需要多个数组才能表示的Trie树,使用两个数据就可以存储下来,可以极大的减小空间复杂度。具体来说:

    使用两个数组base和check来维护Trie树,base负责记录状态,check负责检查各个字符串是否是从同一个状态转移而来,当check[i]为负值时,表示此状态为字符串的结束。

    上面的有点抽象,举个例子,假定两个单词ta,tb,base和check的值会满足下面的条件:
    base[t] + a.code = base[ta]
    base[t] + b.code = base[tb]
    check[ta] = check[tb]

    在每个节点插入的过程中会修改这两个数组,具体说来:

    1、初始化root节点base[0] = 1; check[0] = 0;

    2、对于每一群兄弟节点,寻找一个begin值使得check[begin + a1…an] == 0,也就是找到了n个空闲空间,a1…an是siblings中的n个节点对应的code。

    3、然后将这群兄弟节点的check设为check[begin + a1…an] = begin

    4、接着对每个兄弟节点,如果它没有孩子,令其base为负值;否则为该节点的子节点的插入位置(也就是begin值),同时插入子节点(迭代跳转到步骤2)。

    码表:
       胶    名    动    知    下    成    举    一    能    天    万    
    33014 21517 21160 30693 19979 25104 20030 19968 33021 22825 19975 
    
    DoubleArrayTrie{
    char =      ×    一    万     ×    举     ×    动     ×     下    名    ×    知      ×     ×    能    一    天    成    胶
    i    =      0 19970 19977 20032 20033 21162 21164 21519 21520 21522 30695 30699 33023 33024 33028 40001 44345 45137 66038
    base =      1     2     6    -1 20032    -2 21162    -3     5 21519    -4 30695    -5    -6 33023     3  1540     4 33024
    check=      0     1     1 20032     2 21162     3 21519  1540     4 30695     5 33023 33024     6 20032 21519 20032 33023
    size=66039, allocSize=2097152, key=[一举, 一举一动, 一举成名, 一举成名天下知, 万能, 万能胶], keySize=6, progress=6, nextCheckPos=33024, error_=0}

    首层:一[19968],万[ 19975]
    base[一] = base[0]+19968-19968 = 1
    base[万] = base[0]+19975-19968 =

    实现

    参考 双数组Trie树(DoubleArrayTrie)Java实现
    开源项目:https://github.com/komiya-atsushi/darts-java

    双数组Trie+AC自动机

    参见:http://www.hankcs.com/program/algorithm/aho-corasick-double-array-trie.html

    结合了AC自动机+双数组Trie树:
    AC自动机能高速完成多模式匹配,然而具体实现聪明与否决定最终性能高低。大部分实现都是一个Map<Character, State>了事,无论是TreeMap的对数复杂度,还是HashMap的巨额空间复杂度与哈希函数的性能消耗,都会降低整体性能。

    双数组Trie树能高速O(n)完成单串匹配,并且内存消耗可控,然而软肋在于多模式匹配,如果要匹配多个模式串,必须先实现前缀查询,然后频繁截取文本后缀才可多匹配,这样一份文本要回退扫描多遍,性能极低。

    如果能用双数组Trie树表达AC自动机,就能集合两者的优点,得到一种近乎完美的数据结构。在我的Java实现中,我称其为AhoCorasickDoubleArrayTrie,支持泛型和持久化,自己非常喜爱。


    作者:Jadepeng
    出处:jqpeng的技术记事本--http://www.cnblogs.com/xiaoqi
    您的支持是对博主最大的鼓励,感谢您的认真阅读。
    本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

    转载于:https://www.cnblogs.com/xiaoqi/p/Trie.html

    展开全文
  • Trie树

    2016-06-24 11:53:01
    Trie树(字典树) 方法介绍 1.1、什么是Trie树Trie树,即字典树,又称单词查找树或键树,是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它...
  • Trie树(字典树)

    2019-03-22 19:27:48
    剑指Offer——Trie树(字典树)Trie树    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统...
  • trie树(前缀树)

    2018-11-13 10:39:30
    Trie 树, 又称字典树,单词查找树。它来源于retrieval(检索)中取中间四个字符构成(读音同try)。用于存储大量的字符串以便支持快速模式匹配。主要应用在信息检索领域。 Trie 有三种结构: 标准...标准 Trie树的...
  • 数据结构八-Trie树

    2019-07-27 01:08:29
    1 Trie树的使用场景 搜索引擎中的搜索词建议 2 什么是Trie树 trie树是利用字符串之间的公共前缀,将重复的前缀合并在一起。 3 Trie树代码实现 4 Trie树适合解决的问题 4.1 Trie树的缺点:耗内存 4.2 Trie树与...
  • Trie树分词

    2019-08-02 06:43:55
    最近在看Ansj中文分词的源码,以前没有涉足过这个领域,所以需要做一些笔记。...Trie树也称字典树,能在常数时间O(len)内实现插入和查询操作,是一种以空间换取时间的数据结构,广泛用于词频统计和输入统计领域。...
  • 你了解Trie树

    2019-10-03 12:42:03
    Trie树,也叫字典树,所以自然也是一个树形结构.Trie树是一种专门用来处理字符串匹配的数据结构,用来在一组字符串集合中快速查找某个字符串
  • Trie树 字典树 前缀树

    2018-07-26 17:58:01
    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少...
  • 双数组trie树

    千次阅读 2018-03-27 18:21:21
    搜索树包括B_树、B+树、Trie树等以及它们的各种变形。用Trie树搜索一个关键码的时间与关键码本身及其长度有关,最快是O(1),即在第一层即可判断是否搜索到,最坏的情况是O(n),n为Trie树的层数。 Trie树的缺点是占...
  • 字符串匹配算法(Trie树

    千次阅读 多人点赞 2019-06-25 01:25:37
    Trie树概念2. Trie树操作2.1 存储2.2 插入2.3 查询 1. Trie树概念 Trie树,也叫字典树,它是一个树形结构。是一种专门处理字符串匹配的数据结构,用来解决在一组字符串集合中快速查找某个字符串。 Trie树本质,...
  • Trie树结构

    2016-06-27 20:26:54
    之前说搜索提示的时候留了一个尾巴,就是Trie树的结构没有说,这一篇简单的说一下Trie树的实现方式。 1. Trie树是什么 在计算机科学中,trie,又称前缀树或字典树,是一种有序树,用于保存关联数组,其中的键通常是...
  • Trie 中文名为字典,是一种字符串的高效处理算法。 Trie 实现的功能就是快速的查找一堆字符串里面有没有某个串是另一个串的前缀,后缀等等。 2. 详解 2.1 Trie 的概念 Trie 首先是一棵,比如下面这棵...
  • Trie树是一种很常用的树结构,它被广泛用于各个方面,比如字符串检索、中文分词、求字符串最长公共前缀和字典排序等等,而且在输入法中也能看到Trie树的身影。 什么是Trie树 Trie树通常又称为字典树、单词查找树或...
  • Trie树算法

    千次阅读 2015-03-11 22:16:05
    第一眼看到Trie树算法,首先明白的就是他一定是用树形结构实现的算法。后来实现完整个算法才知道其实他也是压缩树,类似于哈弗曼编码和CF-Tree,因为树中保留了公共的前缀,减少了不必要的重复存储空间。所以查询...
  • 对双数组Trie树(Double-Array Trie)...然后,利用这些方法构造了一个中文分词系统,并与其他几种分词方法进行对比,结果表明,优化后的双数组Trie树插入速度和空间利用率得到了很大提高,且分词查询效率也得到了提高.
  • Trie树也被称为字典树,通过这个名字,可以明显知道这种树的结构:像字典一样进行查找的树(想想采用拼音法查找汉字的时候的过程,实质上就是一个逐字母匹配的过程)。Trie树就是利用了这种思想构造出来的多插查找...
  • trie php,Trie树的php实现

    2021-04-09 11:09:27
    本文原创,转载请注明出处/*** Trie树** @author iamlaobie@gmail.com* @since 2012-08-19*/class Trie{/*** 树的存储*/private $_tree = array();/*** 插入一个新词** @param $word 词* @param $data 词附加属性*/...
  • Trie树—高级树型结构

    2020-04-06 01:16:04
    文章目录Trie树的基本概念Trie树的特点Trie树的数据结构插入查找删除操作Trie树的应用 Trie树的基本概念 Trie 树中文名叫字典树、前缀树等等。这些名字暗示其与字符的处理有关,事实也确实如此,它主要用途就是将...
  • 搜索功能一般都有根据你的输入快速显示对应关键字的功能,比如你输入”刘”...下面将使用Trie树(字典树)来实现此功能。 一、什么是Trie树 Trie书又名字典树,字典是由一组词组成的集合,而字典树对这个集合进行了结

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,300
精华内容 1,320
关键字:

中文trie树