精华内容
下载资源
问答
  • Trie字典树

    2019-10-11 20:27:58
    一)Trie字典树简介 Trie字典树又可以称为前缀树。 典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。 优点:利用字符串的公共前缀来减少查询时间,...

    一)Trie字典树简介

    Trie字典树又可以称为前缀树。

    典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。

    优点:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

     

    二)Trie字典树模型

    该模型就没有用具体的单词创建了,随便定义了一些错误单词。

    String[] words = {"abcd", "A", "Accd", "ab", "B", "ccc", "abe", "abf", "abhh"};

    备注:橘黄色的节点表示一个完整的单词尾部。

     

    三)Trie字典树

    原理:利用Map中的TreeMap存储字典树的节点信息。

    第一步:定义Trie字典树结构

    import java.util.Map;
    import java.util.TreeMap;
    
    /**
     * Trie字典树
     * @author ouyangjun
     */
    public class TrieTree {
    	
        // 字典类
        static class Node {
            boolean isWord; // 标识是否属于一个完整的词语
            Character key;  // 节点的值, 作为子节点的key
            int prefixNum;  // 表示有多少个词, 以此单词为前缀
            Map<Character, Node> next; // 节点的所有子节点,用Map来保存 (Map next)
    		
            Node() {
                next = new TreeMap<Character, Node>();
            }
    		
            Node(boolean isWord, Character key, int prefixNum) {
                this();
                this.isWord = isWord;
                this.key = key;
                this.prefixNum = prefixNum;
            }
        }
    	
        private Node root; // 根节点
        private int size;  // 节点数量
    	
        // 初始化
        public TrieTree() {
            root = new Node();
        }
    	
        // 获取根节点
        public Node getRoot() {
            return root;
        }
    
        // 获取节点数量
        public int size() {
            return size;
        }
    	
        // 判断节点是否为空
        public boolean isEmpty() {
            return size()==0;
        }
    }

     

    第二步:新增词语

    说明:先把单词转换成字节数组,再判断每一个字符是否已经存在,如不存在,则属于新增的节点,如字符已存在,则不处理。

    // 新增节点
    public void add(String word) {
        if (word == null || word.length()==0) {
            return;
        }
    		
        Node node = root;
        char[] ch = word.toCharArray(); // 转换成char
        for (char c : ch) {
            // 判断节点是否存在
            Node child = node.next.get(c);
            if (child == null) {
                // 新增节点
                node.next.put(c, new Node(false, c, 0));
            }
            node.next.get(c).prefixNum++;
            node = node.next.get(c); // 查找下一个子节点
        }
    		
        // 如果当前的node已经是一个word,则不需要添加
        if (!node.isWord) {
            size++;
            node.isWord = true;
        }
    }

     

    第三步:查找词语是否存在

    说明:遍历带查找的字符串的字符,如果每个节点都存在,并且待查找字符串的最后一个字符对应的Node的isWord属性为 true,则表示该单词存在。

    // 查找单词是否存在
    public boolean search(String word) {
        if (word == null || word.length()==0) {
            return false;
        }
    		
        Node node = root;
        char[] ch = word.toCharArray(); // 转换成char
        for (char c : ch) {
            // 判断节点是否存在
            Node child = node.next.get(c);
            if (child == null) {
                return false;
            }
            node = child;
        }
        return node.isWord;
    }

     

    第四步:根据词语的前缀查找是否存在

    // 根据词语的前缀查找是否存在
    public int containsPrefix(String word) {
        if (word == null || word.length()==0) {
            return 0;
        }
    		
        Node node = root;
        char[] ch = word.toCharArray(); // 转换成char
        for (char c : ch) {
            // 判断节点是否存在
            Node child = node.next.get(c);
            if (child == null) {
                return 0;
            }
            node = child;
        }
        // 返回数量
        return node.prefixNum;
    }

     

    第五步:删除词语

    场景一如果单词是另一个单词的前缀,只需要把该word的最后一个节点的isWord的改成false。

    场景二如果单词的所有字母的都没有多个分支,删除整个单词。

    场景三:如果单词的除了最后一个字母,其他的字母有多个分支。

    // 删除词语
    public boolean remove(String word) {
        if (word == null || word.length()==0) {
            return false;
        }
    		
        Node childNode = null;
        int childNodeIndex = -1;
    		
        Node node = root;
        char[] ch = word.toCharArray(); // 转换成char
        for (int i=0; i<ch.length; i++) {
            // 判断节点是否存在
            Node child = node.next.get(ch[i]);
            if (child == null) {
                return false;
            }
    			
            // 当前节点的子节点大于1个,记录是否有多个分支
            if (child.next.size() > 1) {
                childNodeIndex = i;
                childNode = child;
            }
    			
            node = child;
        }
    		
        // 场景一: 如果单词是另一个单词的前缀,只需要把该word的最后一个节点的isWord的改成false
        if (!node.next.isEmpty() && node.isWord) {
            node.isWord = false;
            size--;
            return true;
        }
    		
        // 场景二: 如果单词的所有字母的都没有多个分支,删除整个单词
        if (childNodeIndex == -1) {
             root.next.remove(ch[0]);
            size--;
            return true;
        }
    		
        // 场景三: 如果单词的除了最后一个字母,其他的字母有多个分支
        if (childNodeIndex != ch.length - 1) {
            childNode.next.remove(ch[childNodeIndex + 1]);
            size--;
            return true;
        }
        return false;
    }

     

    第六步:根据字典树还原词语,相当于字典树遍历

    // 根据字典树还原词语,相当于字典树遍历
    public void print() {
        Node node = root;
        // 打印
        print(node, "", false);
    }
    	
    private void print(Node node, String word, boolean isWord) {
        // 判断节点是否为空
        if (node != null) {
            // 只输出有效的完整单词,无效的不需要输出
            if (isWord) {
                System.out.print(word + "\t"); // 可以把所有单词存储起来,方便“检验单词是否包含功能”使用
            }
    			
            // 递归所有的单词,并查找是否存在,并循环
            for (Map.Entry<Character,TrieTree.Node> entry : node.next.entrySet()) {
                Node n = node.next.get(entry.getKey());
                //System.out.println(n.key + "(" + n.isWord+ "\t:" + n.prefixNum+")" + n.next);
    				
                print(n, word + entry.getKey(), n.isWord);
            }
        }
    }

     

    第七步:main方法测试

    public static void main(String[] args) {
        TrieTree trie = new TrieTree();
    		
        // 构建Trie字典树
        String[] words = {"abcd", "A", "Accd", "ab", "B", "ccc", "abe", "abf", "abhh"};
        for(String word : words) {
            trie.add(word);
        }
    		
        System.out.println("字典树构建之后所有的单词: ");
        trie.print();
    		
        String word = "abc";
        System.out.println("\n\n单词"+word+"是否存在: " + trie.search(word));
    		
        word = "abf";
        System.out.println("单词"+word+"是否存在: " + trie.search(word));
    		
        word = "ab";
        System.out.println("前缀"+word+"的单词、有多少个单词以它为前缀: " + trie.containsPrefix(word));
    		
        word = "A";
        System.out.println("单词"+word+"是否删除: " + trie.remove(word));
    		
        word = "ccc";
        System.out.println("单词"+word+"是否删除: " + trie.remove(word));
    		
        word = "abdd";
        System.out.println("单词"+word+"是否删除: " + trie.remove(word));
    		
        word = "abe";
        System.out.println("单词"+word+"是否删除: " + trie.remove(word));
    		
        System.out.println("\n删除之后,字典树中所有的单词: ");
        trie.print();
    }

    打印效果图:

     

    识别二维码关注个人微信公众号

    本章完结,待续,欢迎转载!
     
    本文说明:该文章属于原创,如需转载,请标明文章转载来源!

    展开全文
  • Trie 字典树

    2020-07-09 22:06:30
    Trie 字典树 1.1、定义 字典树,顾名思义,是关于“字典”的一棵树。即:它是对于字典的一种存储方式(所以是一种数据结构而不是算法)。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径,...

    Trie 字典树


    1.1、定义

    字典树,顾名思义,是关于“字典”的一棵树。即:它是对于字典的一种存储方式(所以是一种数据结构而不是算法)。这个词典中的每个“单词”就是从根节点出发一直到某一个目标节点的路径,路径中每条边的字母连起来就是一个单词。

    1.2、字典树描述

    其结点具有以下字段:。
    最多 RR 个指向子结点的链接,其中每个链接对应字母表数据集中的一个字母。
    本文中假定 RR 为 26,小写拉丁字母的数量。
    布尔字段,以指定节点是对应键的结尾还是只是键前缀。
    树中黄色节点表示目标节点,在此节点以上可组成一个单词

    // 可获取如下字符串
    a
    abc
    bac
    bbc
    ca
    

    1.3、使用场景

    字典树的本质是把很多字符串拆成单个字符的形式,以树的方式存储起来。所以我们说字典树维护的是”字典“。那么根据这个最基本的性质,我们可以由此延伸出字典树的很多妙用。简单总结起来大体如下:

    • 1、维护字符串集合(即字典)。
    • 2、向字符串集合中插入字符串(即建树)。
    • 3、查询字符串集合中是否有某个字符串(即查询)。
    • 4、统计字符串在集合中出现的个数(即统计)。
    • 5、将字符串集合按字典序排序(即字典序排序)。
    • 6、求集合内两个字符串的LCP(Longest Common Prefix,最长公共前缀)(即求最长公共前缀)。

    自动补全

    在这里插入图片描述

    拼写检查

    在这里插入图片描述

    IP路由(最长前缀匹配)

    打字预测

    单词游戏

    匹配过程

    Java实现 Trie 字典树


    2.1、数据结构

    Java代码实现

    public class TrieNode{
        // 建立数组存储子字符串(建立Node)
        private TrieNode[] links;
    
        // 由于一个单词(小写),最多只有26个字母
        private final int R = 26 ;
        
        //判断当前节点是否为结束节点
        private boolean isEnd;
    
        // 构造函数
        public TireNode(){
          links = new TrieNode[R];
        }
    
        public boolean containsKey(char ch) {
            return links[ch -'a'] != null;
        }
        public TrieNode get(char ch) {
            return links[ch -'a'];
        }
        public void put(char ch, TrieNode node) {
            links[ch -'a'] = node;
        }
        public void setEnd() {
            isEnd = true;
        }
        public boolean isEnd() {
            return isEnd;
        }
    }
    

    2.2、数据操作

    对于树这种数据结构,很多时候我们都比较关注与两点:“查询” 与 “ 插入”数据

    2.2.1、插入数据

    我们通过搜索 Trie 树来插入一个键。我们从根开始搜索它对应于第一个键字符的链接。有两种情况:
    补充每个键在 trie 中表示为从根到内部节点或叶的路径。
    1、链接存在。沿着链接移动到树的下一个子层。算法继续搜索下一个键字符。
    2、链接不存在。创建一个新的节点,并将它与父节点的链接相连,该链接与当前的键字符相匹配。
    重复以上步骤,直到到达键的最后一个字符,然后将当前节点标记为结束节点,算法完成。

    如图

    Java代码实现

        public class Trie{
        
        private TrieNode root ;
        
        public Trie(){
            root = new TrieNoe();
        }
    
        // 插入数据
        public void insert(String word){
            TrieNode node = root ;
        
            for(int i=0;i<word.length() ;i++){
                    char currentChar = word.charAt(i);
                    if(!node.containKeys(currentChar)){
                        node.put(currentChar,new TrieNode());
                    }
                    node = node.get(currentChar);
                }
                node.isEnd();
            }
    
        }
    

    2.2.2、查询数据

    每个键在 trie 中表示为从根到内部节点或叶的路径。我们用第一个键字符从根开始,。检查当前节点中与键字符对应的链接。有两种情况:

    1、存在链接。我们移动到该链接后面路径中的下一个节点,并继续搜索下一个键字符。
    2、不存在链接。若已无键字符,且当前结点标记为 isEnd,则返回 true。否则有两种可能,均返回 false :
    (1)、还有键字符剩余,但无法跟随 Trie 树的键路径,找不到键。
    (2)、没有键字符剩余,但当前结点没有标记为 isEnd。也就是说,待查找键只是Trie树中另一个键的前缀。

    如图

        public class Trie{
        
        private TrieNode root ;
        
        public Trie(){
            root = new TrieNoe();
        }
    
        // 查询数据,并返回结束时的Node点
        public TrieNode searchPrefix(String word){
            TrieNode node = root ; 
            for(inti = 0 ;i<word.length();i++){
                char currentChar = word.charAt(i);
                if(node.containKeys(currentChar)){
                    node = node.get(currentChar);
                }else{
                    return null;
                }
            }
              return node ;
        }
          
    
            // 判断查询结束时,返回node节点为目标节点且不为空 
            public  boolean search(String word){
                TireNode node = searchPrefix(word);
                   return node !=null &&node.isEnd();
            }
        }
    
    

    扩展

    查询Trie树的键前缀

    该方法与在 Trie 树中搜索键时使用的方法非常相似。我们从根遍历 Trie 树,直到键前缀中没有字
    符,或者无法用当前的键字符继续 Trie 中的路径。与上面提到的“搜索键”算法唯一的区别是,到
    达键前缀的末尾时,总是返回 true。我们不需要考虑当前 Trie 节点是否用 “isend” 标记,因为我
    们搜索的是键的前缀,而不是整个键。

    如图

    Java代码实现

    
     public boolean startsWith(String prefix){
        TrieNode node = searchPrefix(prefix);
        return node!=null;
    }
    
    展开全文
  • trie字典树

    2020-02-24 11:28:56
    字典树,顾名思义,是一个树形结构。有唯一的根节点。每次插入一个字符串的时候,首先扫描字符串,然后从第一个字符开始逐个插入。 例如: 插入字符串 "abcd" 1、一定是从根节点开始,用一个节点p指向根节点。 2、...

     字典树,顾名思义,是一个树形结构。有唯一的根节点。每次插入一个字符串的时候,首先扫描字符串,然后从第一个字符开始逐个插入。

    例如: 插入字符串 "abcd"
                1、一定是从根节点开始,用一个节点p指向根节点。
                2、首先判断p是否有一个子节点指向字符当前字符(第一个就是'a'),如果没有就新建一个子节点,并且将trie[p][a]指向新建节点,将当前的指针指向新建节点,否则就直接指向该节点。
                3、继续遍历下一个字符,重复步骤 2。
                4、在插入最后一个字符的时候,将节点p正在end[N]中进行标记,表示该节点是一个字符串结束的位置,目的是为了检索的方便。

    检索字符串的时候也按照插入的方式一个个字符向下走就可以了。用一个end[ N]数组来标记插入的每一个字符串的结束位置,如果检索字符串检索到了(即路径上没有空节点),且最后一个字符所在的节点在end[N]中被标记了,那么说明该字符串存在过。

    #include <bits/stdc++.h>
    #pragma warning (disable:4996)
    #pragma warning (disable:6031)
    #define mem(a, b) memset(a, b, sizeof a)
    using namespace std;
    const int N = 310;
    int trie[N][26];
    int cnt;
    int root;
    bool nd[N];
    void insert(char* s) {
    	int len = strlen(s);
    	int p = root;
    	for (int i = 0; i < len; i++) {
    		if (trie[p][s[i] - 'a'] == 0) {
    			++cnt;
    			trie[p][s[i] - 'a'] = cnt;
    		}
    		p = trie[p][s[i] - 'a'];
    	}
    	nd[p] = 1;
    }
    bool check(char* s) {
    	int len = strlen(s);
    	int p = root;
    	for (int i = 0; i < len; i++) {
    		if (trie[p][s[i] - 'a'] == 0)return false;
    		p = trie[p][s[i] - 'a'];
    	}
    	return nd[p];
    }
    int main()
    {
    	root = 0;
    	cnt = 0;
    	mem(nd, 0);
    	mem(trie, 0);
    	char s[10];
    	for (int i = 0; i < 5; i++) {
    		scanf("%s", s);
    		insert(s);
    	}
    	for (int i = 0; i < 10; i++) {
    		scanf("%s", s);
    		if (check(s)) {
    			printf("Yes : %s\n", s);
    		}
    		else printf("NO : Sorry\n");
    	}
    	return 0;
    }

     

    展开全文
  • 数据结构与算法(十一)Trie字典树

    万次阅读 多人点赞 2018-06-16 10:02:57
    Trie字典树的基本概念 Trie字典树的基本操作 插入 查找 前缀查询 删除 基于链表的Trie字典树 Set性能对比 LeetCode相关线段树的问题 LeetCode第208号问题 LeetCode第211号问题 LeetCode第677号问题 Trie字典树...

    本文主要包括以下内容:

    1. Trie字典树的基本概念
    2. Trie字典树的基本操作
      1. 插入
      2. 查找
      3. 前缀查询
      4. 删除
    3. 基于链表的Trie字典树
    4. 基于Trie的Set性能对比
    5. LeetCode相关线段树的问题
      1. LeetCode第208号问题
      2. LeetCode第211号问题
      3. LeetCode第677号问题

    Trie字典树的基本概念

    上一篇我们介绍了 线段树(Segment Tree),本文主要介绍Trie字典树。

    通过前面的介绍我们知道一个线性表的顺序查找的时间复杂度为O(n);二分搜索树的查找为O(log n),它们都和数据结构中的元素个数相关。关于线性表和二分搜索树的时间复杂度分析有需要的可以查看 Set集合和BinarySearchTree的时间复杂度分析

    本文介绍的Trie字典树(主要用于存储字符串)查找速度主要和它的元素(字符串)的长度相关[O(w)]。

    Trie字典树主要用于存储字符串,Trie 的每个 Node 保存一个字符。用链表来描述的话,就是一个字符串就是一个链表。每个Node都保存了它的所有子节点。

    例如我们往字典树中插入see、pain、paint三个单词,Trie字典树如下所示:

    这里写图片描述

    也就是说如果只考虑小写的26个字母,那么Trie字典树的每个节点都可能有26个子节点。

    Trie字典树的基本操作

    插入

    本文是使用链表来实现Trie字典树,字符串的每个字符作为一个Node节点,Node主要有两部分组成:

    1. 是否是单词 (boolean isWord)
    2. 节点所有的子节点,用map来保存 (Map next)

    例如插入一个paint单词,如果用户查询pain,尽管 paint 包含了 pain,但是Trie中仍然不包含 pain 这个单词,所以如果往Trie中插入一个单词,需要把该单词的最后一个字符的节点的 isWord 设置为 true。所以为什么Node需要存储 是否是单词 这个属性。

    节点的所有子节点,通过一个Map来存储,key是当前子节点对应的字符,value是子节点。

    实现的伪代码如下:

    public void add(String word) {
    	Node current = root;
    	char[] cs = word.toCharArray();
    	for (char c : cs) {
    		Node next = current.next.get(c);
    		if (next == null) {
    		    //一个字符对应一个Node节点
    			current.next.put(c, new Node());
    		}
    		current = current.next.get(c);
    	}
    	//current就是word的最后一个字符的Node
    	
    	//如果当前的node已经是一个word,则不需要添加
    	if (!current.isWord) {
    		size++;
    		current.isWord = true;
    	}
    }
    
    

    查找

    Trie查找操作就比较简单了,遍历带查找的字符串的字符,如果每个节点都存在,并且待查找字符串的最后一个字符对应的Node的 isWord 属性为 true ,则表示该单词存在,伪代码如下:

    public boolean contains(String word) {
    	Node current = root;
    	for (int i = 0; i < word.length(); i++) {
    		char c = word.charAt(i);
    		Node node = current.next.get(c);
    		if (node == null) {
    			return false;
    		}
    		current = node;
    	}
    	//current就是word的最后一个字符的Node
    	return current.isWord;
    }
    
    

    前缀查询

    前缀查询和上面的查询操作基本类似,就是不需要判断 isWord

    public boolean containsPrefix(String prefix) {
        Node current = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            Node node = current.next.get(c);
            if (node == null) {
                return false;
            }
            current = node;
        }
        return true;
    }
    
    

    删除

    Trie的删除操作就稍微复杂一些,主要分为以下3种情况:

    如果单词是另一个单词的前缀

    如果待删除的单词是另一个单词的前缀,只需要把该单词的最后一个节点的 isWord 的改成false

    比如Trie中存在 pandapan 这两个单词,删除 pan ,只需要把字符 n 对应的节点的 isWord 改成 false 即可

    如下图所示

    这里写图片描述

    如果单词的所有字母的都没有多个分支,删除整个单词

    如果单词的所有字母的都没有多个分支(也就是说该单词所有的字符对应的Node都只有一个子节点),则删除整个单词

    例如要删除如下图的see单词,如下图所示:

    这里写图片描述

    如果单词的除了最后一个字母,其他的字母有多个分支

    这里写图片描述

    基于链表的Trie字典树

    public class Trie {
    
        private Node root;
    
        private int size;
    
        private static class Node {
            public boolean isWord;
            public Map<Character, Node> next;
    
            public Node() {
                next = new TreeMap<>();
            }
    
            public Node(boolean isWord) {
                this();
                this.isWord = isWord;
            }
    
        }
    
        public Trie() {
            root = new Node();
        }
    
        public int size() {
            return size;
        }
    
        public boolean isEmpty() {
            return size == 0;
        }
    
        /**
         * 插入操作
         *
         * @param word 单词
         */
        public void add(String word) {
            Node current = root;
            char[] cs = word.toCharArray();
            for (char c : cs) {
                Node next = current.next.get(c);
                if (next == null) {
                    current.next.put(c, new Node());
                }
                current = current.next.get(c);
            }
            //如果当前的node已经是一个word,则不需要添加
            if (!current.isWord) {
                size++;
                current.isWord = true;
            }
        }
    
    
        /**
         * 是否包含某个单词
         *
         * @param word 单词
         * @return 存在返回true,反之false
         */
        public boolean contains(String word) {
            Node current = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                Node node = current.next.get(c);
                if (node == null) {
                    return false;
                }
                current = node;
            }
            //如果只存在 panda这个词,查询 pan,虽然有这3个字母,但是并不存在该单词
            return current.isWord;
        }
    
    
        /**
         * Trie是否包含某个前缀
         *
         * @param prefix 前缀
         * @return
         */
        public boolean containsPrefix(String prefix) {
            Node current = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                Node node = current.next.get(c);
                if (node == null) {
                    return false;
                }
                current = node;
            }
            return true;
        }
    
    
        /*
         * 1,如果单词是另一个单词的前缀,只需要把该word的最后一个节点的isWord的改成false
         * 2,如果单词的所有字母的都没有多个分支,删除整个单词
         * 3,如果单词的除了最后一个字母,其他的字母有多个分支,
         */
    
        /**
         * 删除操作
         *
         * @param word
         * @return
         */
        public boolean remove(String word) {
            Node multiChildNode = null;
            int multiChildNodeIndex = -1;
            Node current = root;
            for (int i = 0; i < word.length(); i++) {
                Node child = current.next.get(word.charAt(i));
                //如果Trie中没有这个单词
                if (child == null) {
                    return false;
                }
                //当前节点的子节点大于1个
                if (child.next.size() > 1) {
                    multiChildNodeIndex = i;
                    multiChildNode = child;
                }
                current = child;
            }
            //如果单词后面还有子节点
            if (current.next.size() > 0) {
                if (current.isWord) {
                    current.isWord = false;
                    size--;
                    return true;
                }
                //不存在该单词,该单词只是前缀
                return false;
            }
            //如果单词的所有字母的都没有多个分支,删除整个单词
            if (multiChildNodeIndex == -1) {
                root.next.remove(word.charAt(0));
                size--;
                return true;
            }
            //如果单词的除了最后一个字母,其他的字母有分支
            if (multiChildNodeIndex != word.length() - 1) {
                multiChildNode.next.remove(word.charAt(multiChildNodeIndex + 1));
                size--;
                return true;
            }
            return false;
        }
    }
    
    

    基于Trie的Set性能对比

    在前面的Set集合和BinarySearchTree的时间复杂度分析中我们分别使用了基于链表和基于二分搜索树实现的Set,对两本英文原著进行简单的词频统计。

    现在使用Trie实现下Set集合,然后三者性能做一个比较,还是以傲慢与偏见双城记战争与和平三本原著作为数据源。

    傲慢与偏见(Pride and Prejudice)的性能对比

    Pride and Prejudice
    	Total words: 125901
    	Total different words: 6530
    
    TrieSet       Time: 0.099788784
    BSTSet        Time: 0.339963625
    LinkedListSet Time: 3.554973381
    

    从中可以看出傲慢与偏见不同的单词只有6000左右,阅读难度不是很大。

    双城记(A Tale of Two Cities)的性能对比

    A Tale of Two Cities
    	Total words: 141489
    	Total different words: 9944
    
    TrieSet       Time: 0.119505174
    BSTSet        Time: 0.331334495
    LinkedListSet Time: 5.26063235
    

    战争与和平(War and peace)的性能对比

    War and Peace
    	Total words: 602359
    	Total different words: 16725
    
    
    TrieSet       Time: 0.09750872
    BSTSet        Time: 0.233328074
    

    以上关于原著词汇的统计只是简单的对比单词是否一致,并没有考虑一个单词的过去式、进行时等时态,只要字符串不一致都把它当作不同的单词。

    更多关于Trie的话题

    上面实现的Trie中,我们是使用TreeMap来保存节点的所有的子节点,也可以使用HashMap来保存所有的子节点,效率更高:

    public Node() {
        next = new HashMap<>();
    }
    

    当然我们也可以使用一个定长的数组来存储所有的子节点,效率比HashMap更高,因为不需要使用hash函数:

    public Node(boolean isWord){
        this.isWord = isWord;
        next = new Node[26];//只能存储26个小写字母
    }
    

    Trie查询效率非常高,但是对空间的消耗还是挺大的,这也是典型的空间换时间。

    可以使用 压缩字典树(Compressed Trie) ,但是维护相对来说复杂一些。

    如果我们不止存储英文单词,还有其他特殊字符,那么维护子节点的集合可能会更多。

    可以对Trie字典树做些限制,比如每个节点只能有3个子节点,左边的节点是小于父节点的,中间的节点是等于父节点的,右边的子节点是大于父节点的,这就是三分搜索Trie字典树(Ternary Search Trie)

    LeetCode相关线段树的问题

    LeetCode第208号问题

    问题描述:

    实现一个 Trie (前缀树),包含 insert, search, 和 startsWith 这三个操作。

    示例:

    Trie trie = new Trie();
    
    trie.insert("apple");
    trie.search("apple");   // 返回 true
    trie.search("app");     // 返回 false
    trie.startsWith("app"); // 返回 true
    trie.insert("app");   
    trie.search("app");     // 返回 true
    

    问题说明:

    你可以假设所有的输入都是由小写字母 a-z 构成的。
    保证所有输入均为非空字符串。

    这个问题在我们实现的 Trie字典树 中已经实现了这个功能了,add()就是对应的insert(),contains()就是对应的search(),starcontainsPrefix()就是对应的startsWith(),这里就不贴代码了。

    LeetCode第211号问题

    问题描述:

    设计一个支持以下两种操作的数据结构:

    void addWord(word)
    bool search(word)
    search(word) 
    

    可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z. 可以表示任何一个字母。

    示例:

    addWord("bad")
    addWord("dad")
    addWord("mad")
    search("pad") -> false
    search("bad") -> true
    search(".ad") -> true
    search("b..") -> true
    

    问题说明:

    你可以假设所有单词都是由小写字母 a-z 组成的。

    这个问题就是上一个问题的基础上加上 . 的处理,稍微复杂点。

    如果下一个字符是 . ,那么需要遍历该节点的所有子节点,对所有子节点的处理就是一个递归程序:

    public boolean searchByWildCard(String express) {
        return search(root, express, 0);
    }
    
    
    private boolean search(Node node, String express, int index) {
        //如果已经到了待查询字符串的尾端了
        if (index == express.length()) {
            return node.isWord;
        }
        char c = express.charAt(index);
        if (c != '.') {
            Node nextChar = node.next.get(c);
            if (nextChar == null) {
                return false;
            }
            return search(nextChar, express, index + 1);
        } else {//如果是通配符
            Map<Character, Node> nextNodes = node.next;
            //遍历所有的子节点
            for (Map.Entry<Character, Node> entry : nextNodes.entrySet()) {
                if (search(entry.getValue(), express, index + 1)) {
                    return true;
                }
            }
            return false;
        }
    }
    
    

    LeetCode第677号问题

    问题描述:

    实现一个 MapSum 类里的两个方法,insert 和 sum。

    对于方法 insert,你将得到一对(字符串,整数)的键值对。字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。

    对于方法 sum,你将得到一个表示前缀的字符串,你需要返回所有以该前缀开头的键的值的总和。

    示例 1:

    输入: insert("apple", 3), 输出: Null
    输入: sum("ap"), 输出: 3
    输入: insert("app", 2), 输出: Null
    输入: sum("ap"), 输出: 5
    

    总结一句话就是,求出所有符合该前缀的字符串的键值的总和。

    节点需要保存一个键值,用于求和。节点Node不需要维护 isWord 这个属性了,因为不关注是不是一个单词。

    class Node {
        public int value;
        public Map<Character, Node> next;
    }
    
    
    public int sum(String prefix) {
        Node cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            Node node = cur.next.get(c);
            if (node == null) {
                return 0;
            }
            cur = node;
        }
        
        //cur指向prefix的最后一个字符的Node
        
        //对每个以prefix为前缀的node进行累加
        return countValue(cur);
    }
    
    private int countValue(Node node) {
        int result = node.value;
        for (char c : node.next.keySet()) {
            result += countValue(node.next.get(c));
        }
        return result;
    }
    
    

    上面三个LeetCode的问题答案,都可以在我的github上查看

    Reference

    本文主要内容和大纲是学习了慕课网 liuyubobobo 老师的视频《算法大神带你玩转数据结构 从入门到精通》
    有需要的同学可以看看, 真心不错. 墙裂推荐… 最好能加上自己的思考和理解.


    下面是我的公众号,干货文章不错过,有需要的可以关注下,有任何问题可以联系我:

    公众号:  chiclaim

    文本相关源代码github

    展开全文
  • Trie 字典树 前缀树

    千次阅读 2019-10-14 21:08:42
    Trie 字典树 前缀树
  • trie 字典树

    2014-07-20 21:21:12
    Code highlighting produced by Actipro CodeHighlighter (freeware)http://www.CodeHighlighter.com/-->#define MAX 26 ...typedef struct Trie {  Trie *next[MAX];  int v; //根据需要变化 };  
  • 第十章 Trie字典树 10-1 什么是Trie字典树 10-2 Trie字典树基础 10-3 Trie字典树的查询 10-4 Trie字典树的前缀查询 10-5 Trie字典树和简单的模式匹配 10-6 Trie字典树和字符串映射 10-7 更多和Trie字典树相关的话题 ...
  • 10.3 Trie字典树查询

    2020-05-24 22:25:21
    10.3 Trie字典树查询 Tip:本博客内容是通过学习慕课网bobo老师视频做的笔记总结,不用于任何商业用途,只用于帮助更多技术爱好者。 (1) Trie字典树的Java语言实现案例 // 判断Trie树中是否存在某个单词 public ...
  • 文章目录1、什么是字典树2、Trie字典树节点信息3、Trie字典树的实现3.1、Trie构造函数的实现3.2、添加元素3.3、查询操作3.4、前缀搜索最后 1、什么是字典树   字典树是一种专门处理字符串设计的一种数据结构。我们...
  • trie 字典树 (前缀树)什么是字典树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。字典...
  • 10.2 Trie字典树基础

    2020-05-24 16:04:55
    10.2 Trie字典树基础 Tip:本博客内容是通过学习慕课网bobo老师视频做的笔记总结,不用于任何商业用途,只用于帮助更多技术爱好者。 (1) Trie字典树的Java语言实现案例 package com.wwl.trie; import java.util...
  • trie 字典树 前缀树

    2019-05-03 11:15:14
    trie 字典树 前缀树 又称为单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串,所以经常被搜索引擎系统用于文本词频统计。优点是:利用字符串的公共前缀来...

空空如也

空空如也

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

trie字典树