algo

字典树

字典树介绍、实现、应用

Posted by Nova on 2020-03-01

Trie树，又称字典树，单词查找树或者前缀树，是一种用于快速检索的多叉树结构.

如英文字母的字典树是一个26叉树，数字的字典树是一个10叉树。

字典树(Trie树)的实现及应用

特点：只有叶子节点和部分内部节点所对应的键才有相关的值(表示命中查找).
优点：最大限度地减少无谓的字符串比较，查询效率比较高(核心思想是空间换时间，利用字符串的公共前缀来降低查询时间开销)
缺点：空间复杂度高(可采用双数组改善)

1
2
时间复杂度：插入、查找的时间复杂度均为O(N)，其中N为字符串长度
空间复杂度：空间复杂度是26^n级别的，非常庞大（可采用双数组实现改善）
1
2
3
根节点不包含字符，除根节点外每一个节点都只包含一个字符。
从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
每个节点的所有子节点包含的字符都不相同

应用场景

Trie树和DFA，确定有限状态自动机

trie树实际上是一个DFA，通常用转移矩阵表示。行表示状态，列表示输入字符，（行，列）位置表示转移状态。这种方式的查询效率很高，但由于稀疏的现象严重，空间利用效率很低。也可以采用压缩的存储方式即链表来表示状态转移，但由于要线性查询，会造成效率低下。

介绍一下自动机
有穷自动机DFA&NFA

1
2
3
4
自动机：自动机是有限状态机(FSM)的数学模型，也可以叫做 状态机(有限状态机（FSM）的简称).
有限状态机(FSM):具有一个基本内部记忆的抽象机器模型.(有限输入符合集合、有限输出符合集合、有限状态集合、状态函数...)
DFA: 确定有限状态自动机(转移函数：每一个转移都有确定的值)
NFA: 非确定型有限状态自动机(转移函数：每一个转移都几个不确定的值（次态），采取随机转移方式转移到下一个状态)

Trie树的实现

Trie树的创建要考虑的是父节点如何保存孩子节点，主要有链表和数组两种方式：

  1. (不可取)使用节点数组，因为是英文字符，可以用Node[26]来保存孩子节点(如果是数字我们可以用Node[10])，这种方式最快，但是并不是所有节点都会有很多孩子，所以这种方式浪费的空间太多

  2. (查询效率低)用一个链表根据需要动态添加节点。这样我们就可以省下不小的空间，但是缺点是搜索的时候需要遍历这个链表，增加了时间复杂度。

  3. (重点)使用hash表.【针对字符区间大的情况效果更好】

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
50
51
52
53
public class TrieNode{
    public int path; // 所能链接到其他节点的个数.(删除的时候使用:遍历执行path--,path=0时可断开节点)
    public int end;  // 表示以当前节点为结尾的单词的个数,
    public HashMap<Character, TrieNode> next;
    public TrieNode(){
        path = 0;
        end = 0;
        next = new HashMap<>();
    }
}

public class Trie {
    private TrieNode root;
    public Trie(){
        root = new TrieNode();
    }

    public void insert(String word){
        if(word == null || word.equals(""))  return ;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(!node.next.containsKey(ch)) {
                node.next.put(ch,new TrieNode());
            }
            node = node.next.get(ch);
            node.path++;
        }
        node.end++;
    }

    public boolean search(String word){
        if(word == null || word.equals("")) return false;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(!node.next.containsKey(ch)) return false;
            node = node.next.get(ch);
        }
        if(node.end == 0) return false;
        return true;
    }
    public boolean startsWith(String word){
        if(word == null || word.equals("")) return false;
        TrieNode node = root;
        for(int i = 0; i<word.length(); i++){
            char ch = word.charAt(i);
            if(!node.next.containsKey(ch)) return false;
            node = node.next.get(ch);
        }
        return true;
    }
}

以上是hash表实现的字典树，还可使用双数组Trie改善空间().

##双数组Trie树实现

1
双数组Trie的本质是一个确定有限状态自动机（DFA），每个节点代表自动机的一个状态，根据变量不同，进行状态转移，当到达结束状态或无法转移时，完成一次查询操作。在双数组所有键中包含的字符之间的联系都是通过简单的数学加法运算表示，不仅提高了检索速度，而且省去了链式结构中使用的大量指针，节省了存储空间。

相比trie树, 查询速度更快、占用空间更小.

1
2
3
4
5
6
// 双数组构建规则
base[i]+code(x)=j
check[j]=i​
// 含义：
base array的长度是trie树中节点的个数.
code(x): 是字符x的编码，现实中为了方便通常直接用char code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class DoubleArrayTrie {
	private final static int BUF_SIZE = 16384;
	private final static int UNIT_SIZE = 8; // size of int + int
	private static class Node {
		int code;
		int depth;
		int left;
		int right;
	};
	// 标识出 base array 中每个状态的前一个状态: 检验按base做转移的转移正确性
	private int check[];
	// 数组用于记录跳转结构,index为i的那个节点，如果按照字符x转移，会转移到index为j的节点
	private int base[];

	private boolean used[];
	private int size;
	private int allocSize;
	private List<String> key;
	private int keySize;
	private int length[];
	private int value[];
	private int progress;
	private int nextCheckPos;
}

base数组: 用于记录跳转结构,index为i的那个节点，如果按照字符x转移，会转移到index为j的节点
check: 标识出base array中每个状态的前一个状态， 检验按base做转移的转移正确性

base跳转规则: base[i]+code(x)=j 【】
check规则: check[j]=i​

1. 构建base array

双数组Trie树(DoubleArrayTrie)Java实现

FEATURED TAGS
algo
FRIENDS