字典树的实现和应用

发表于 | 分类于
字数统计: 1,295 | 阅读时长 ≈ 6

字典树的实现和应用

1.概述

1.1 基础概念

字典树,又称为单词查找树,Tire树,它是一种树形结构,它是一种hash树的变种.

字典树-1

1.2 基本性质

  • 根节点不包含字符,除根节点外的每一个节点包含一个字符
  • 从根节点到某一个节点,路上结果的字符链接起来,就是该节点对应的字符串.
  • 每个节点对应的字符串都不相同

1.3 应用场景

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

2. 代码实现

2.1 定义字典树节点

字典树节点包含四个关键的属性,分别是

  • 由根节点至该节点组成的字符串出现的次数
  • 所有的子节点(子节点也是字典树节点)
  • 是否是叶子节点
  • 节点的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class TrieNode {
    int num; //单词出现次数
    TrieNode[] sons; //所有的子节点
    boolean isEnd; //是否是叶子节点
    char val; //节点值

    public TrieNode(char val) {
        num = 1;
        sons = new TrieNode[26]; // 26个小写字母
        isEnd = false;
        this.val = val;
    }
    public TrieNode() {
        num = 1;
        sons = new TrieNode[26]; // 26个小写字母
        isEnd = false;
        this.val = val;
    }
}

2.2 构建一颗字典树

字典树有关键属性

  • 节点数
  • 根节点
1
2
3
4
5
6
7
8
9
10
11
public class TrieTree {

    private TrieNode root; // 根节点
    private int size; // 总结点个数, 不包含跟节点

    //初始化字典树
    TrieTree(){
        root = new TrieNode();
        size = 0;
    }
}

2.3 插入节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

public void insert(String str){
    if(str == null || str.length() == 0) return;
    TrieNode node = root;
    char[] chars = str.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        int pos = chars[i] - 'a';
        if(node.sons[pos] == null){
            node.sons[pos] = new TrieNode(chars[i]);
            size++;
        }else{
            node.sons[pos].num++;
        }
        node = node.sons[pos];
    }
    node.isEnd = true;
}

2.4 查询路径为当前字符串的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
  /**
     * 查询包含该字符串的最后一个节点
     * 返回null则表示不包含
     * @param str
     * @return
     */
public TrieNode getNode(String str) {
        if (str == null || str.length() == 0) return null;
        TrieNode node = root;
        char[] chars = str.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int pos = chars[i] - 'a';
            if (node.sons[pos] == null) return null;
            node = node.sons[pos];
        }
        return node;
    }

2.5 计算包含前缀的单词数量

1
2
3
4
5
6
7
8
9
10
/**
 * 计算前缀的单词数量
 * @param prefix
 * @return
 */
public int countPrefix(String prefix){
    if(prefix == null || prefix.length() == 0) return -1;
    TrieNode node = getNode(prefix);
    return node !=null ? node.num : 0;
}

2.6 查询是否包含该字符串

1
2
3
4
5
6
7
8
/**
    * 查询字是否包含该字符串
    * @param str
    */
   public boolean has(String str){
       TrieNode node = getNode(str);
       return node !=null;
   }

2.7 查询是否完美包含该字符串

1
2
3
4
5
6
7
8
9
/**
    * 是否完美包含该字符串,接字符串长度
    * @param str
    * @return
    */
   public boolean perfectHas(String str){
       TrieNode node = getNode(str);
       return node !=null ? node.isEnd : false;
   }

2.8 前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void preTraverse(){
       TrieNode node = root;
       if(node == null) return;
       for (TrieNode child:node.sons
            ) {
           preTraverse(child,"");
       }
   }

   private void preTraverse(TrieNode node,String str) {
       if(node == null) return;
       String val = str + node.val;
       if(node.isEnd) System.out.println(val);
       for (TrieNode child:node.sons) {
           preTraverse(child,val);
       }
   }

3. 应用

leetcode-820.单词的压缩编码

https://leetcode-cn.com/problems/short-encoding-of-words/

3.1 解题思路

例如，如果这个列表是 [“time”, “me”, “bell”]，我们就可以将其表示为 S = “time#bell#” 和 indexes = [0, 2, 5]。

我们可以先构建一个如下字典树.

字典树-2

通过字典树,就可以求出本题的解.

3.2 解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public int minimumLengthEncoding(String[] words) {
        if(words.length == 1) return words[0].length() + 1;
        // 按照字符串长度排序,保证先插入长的字符串,后插入短的字符串,这样,只要判断插入的字符串中有新
      	//的节点,则表示在总长度上加上字符串长度并+1(#的长度)
        Arrays.sort(words,(String str1,String str2)-> str2.length() - str1.length());
        Trie trie = new Trie();
        for (int i = 0; i < words.length; i++) {
			//插入所有字符串
            trie.insert(words[i]);
        }
        return trie.length;
    }
}
// 构建字典树节点 去除了不需要的信息
//这里 节点的值,也不需要,如果单纯为了解题,可以把val也去掉.
class Node{
    char val;
    Node[] sons = new Node[26];
    Node(){}
    Node(char val){
        this.val = val;
    }
}
// 构建字典树,新增了一个字段,length 表示压缩的字符串长度
class Trie{
    Node root;
   int size = 0;
   int length = 0;
    Trie(){
       root = new Node();
   }
  //插入字符串,这里将字符串倒叙插入
   void insert(String str){
        if(str == null || str.length() == 0) return;
        Node node = root;
       char[] chars = str.toCharArray();
       for (int i = chars.length-1; i >= 0; i--) {
           int pos = chars[i] - 'a';
           if(node.sons[pos] == null){
               node.sons[pos] = new Node(chars[i]);
               size++;
               // 如果最后一个字节 是新的节点,则我们就在压缩后字符串长度 加上当前字符串长度 和 #号长度1
               if(i == 0) length+=chars.length+1;
           }
           node = node.sons[pos];
       }
   }
}
0%