Fork me on GitHub

Trie(数字树、字典树、前缀树)

Trie简介

术语trie取自retrieval,也被称为数字树、字典树或前缀树,是一种有序树数据结构,哈希树的变种。
根据词源学,trie 的发明者Edward Fredkin把它读作/ˈtriː/ "tree"。但是,其他作者把它读作/ˈtraɪ/ "try"
与二叉查找树不同,树中节点不存储与节点关联的键,而是通过树中的位置定义键。一个节点的所有子孙节点拥有与该节点相同的字符串前缀,根节点与空字符串相关联。并不是每个节点都与值关联,仅叶节点和部分内部节点与值关联。

含有键为”A”、”to”、”tea”、”ted”、”ten”、”i”、”in”和”inn”的trie示例。

trie中的键通常是字符串,但也可以是其它的结构。trie的算法可以很容易地修改为处理其它结构的有序序列,比如一串数字或者形状的排列。比如,bitwise trie中的键是一串位元,可以用于表示整数或者内存地址。
字符串集合X中不存在一个串是另外一个串的前缀 。如何满足这个要求呢?我们可以在X中的每个串后面加入一个特殊字符$(这个字符将不会出现在字母表中)。这样,集合X{bear$、bell$、…. bi$、bid$}一定会满足这个要求。

性质

  • 根节点不包含字符,除根节点外每一个节点都只包含一个字符;
  • 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串;
  • 每个节点的所有子节点包含的字符都不相同。

总结:一个存储长度为n,来自大小为d的字母表中s个串的集合X的标准trie具有性质如下:

  1. 树中每个内部结点至多有d个子结点。
  2. 树有s个外部结点。
  3. 树的高度等于X中最长串的长度。
  4. 树中的结点数为O(n)。

应用

替代其他数据结构

优点

  • trie数据查找与不完美哈希表(链表实现,完美哈希表为数组实现)在最差情况下更快:对于trie,最差情况为O(m),m为查找字符串的长度; 对于不完美哈希表,会有键冲突(不同键哈希相同),最差情况为O(N),N为全部字符产集合个数。典型情况下是O(m)用于哈希计算、O(1)用于数据查找。
  • trie中不同键没有冲突
  • trie的桶与哈希表用于存储键冲突的桶类似,仅在单个键与多个值关联时需要
  • 当更多的键加入trie,无需提供哈希方法或改变哈希方法
  • tire通过键为条目提供了字母顺序

缺点

  • trie数据查找在某些情况下(尤其当数据直接从磁盘或随机访问时间远远高于主内存的辅助存储设备时)比哈希表慢
  • 当键为某些类型时(例如浮点数)之类的键,前缀链很长且前缀不是特别有意义。然而bitwise trie能够处理标注IEEE单精度和双精度浮点数。
  • 一些trie会比哈希表消耗更多空间:对于trie,每个字符串的每个字符都可能需要分配内存;对于大多数哈希表,为整个条目分配一块内存。

字典表示

Trie树是一种哈希树的变种,典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度地减少无谓的字符串比较,查询效率比哈希表高。
典型应用是预测文本排序(常被搜索引擎系统用于文本词频统计)、字典自动完成、字符串近似匹配(拼写检查、断字)。

实现

trie基本操作有:查找、插入和删除。

trie数据查找的方法为

  1. 从根结点开始一次搜索;
  2. 取得要查找关键词的第一个字母,并根据该字母选择对应的子树并转到该子树继续进行检索;
  3. 在相应的子树上,取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。
  4. 迭代过程……
  5. 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。

Test类

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
package Trie;
import java.lang.reflect.Field;
import java.util.Map;
import org.junit.Before;
import org.junit.Test;
public class TrieTest {
private Trie trie;
@Before
public void setUp() {
trie = new Trie();
trie.addWord("to");
trie.addWord("tea");
trie.addWord("ted");
trie.addWord("ten");
trie.addWord("inn");
trie.addWord("a");
}
//增加字符串
@Test
public void add(){
try{
//因为trie中的root属性是私有的,所以要通过暴力反射来得到它
Field fieldY = trie.getClass().getDeclaredField("root");
fieldY.setAccessible(true);//暴力反射
Node node = (Node)fieldY.get(trie);
//打印出这个前缀树,每个字符后面对应一个数字,代表节点层次,好画节点图
printTrie(node,1);
}catch(Exception e){
e.printStackTrace();
}
}
//判断该前缀树中是否有该字符串或前缀
@Test
public void hasStr(){
String str = "toaa";
if(str != null){
if(trie.containsWord(str)){
System.out.println(str + " is a word");
}else{
if(trie.containsPrefix(str)){
System.out.println(str + " is a prefix");
}else{
System.out.println(str + " not found");
}
}
}
}
//打印出这个前缀树,每个字符后面对应一个数字,代表节点层次,好画节点图
public void printTrie(Node node,int i){
if(node == null) return;
try{
//因为node中的children属性是私有的,所以要通过暴力反射来得到它
Field fieldY = node.getClass().getDeclaredField("children");
fieldY.setAccessible(true);//暴力反射
@SuppressWarnings("unchecked")
Map<Character,Node> children = (Map<Character,Node>)fieldY.get(node);
for(char c :children.keySet()){
System.out.print(""+c + i+"\t");
printTrie(node.getChild(c),i+1);
}
}catch(Exception e){
e.printStackTrace();
}
}
}

Trie类及对应Node类

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package Trie;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Trie {
private Node root = new Node("");
public Trie() {}
//将数据列表加入到前缀树中
public Trie(List<String> argInitialWords) {
for (String word:argInitialWords) {
//将一个字符串加入到前缀树中
addWord(word);
}
}
//将一个字符串加入到前缀树中
public void addWord(String argWord) {
char argChars[] = argWord.toCharArray();
Node currentNode = root;
//判断该字符的每一个字符是否在前缀树中,如果在的话,Node=子Node,循环判断
for (int i = 0; i < argChars.length; i++) {
if (!currentNode.containsChildValue(argChars[i])) {
currentNode.addChild(argChars[i], new Node(currentNode.getValue() + argChars[i]));
}
currentNode = currentNode.getChild(argChars[i]);
}
currentNode.setIsWord(true);
}
//是否包含了前缀(不用考虑node.isWord())
public boolean containsPrefix(String argPrefix) {
return contains(argPrefix, false);
}
//是否包含了字符串(包含,并且node.isWord() == true)
public boolean containsWord(String argWord) {
return contains(argWord, true);
}
//得到该字符串对应的Node(node.isWord() == true)
public Node getWord(String argString) {
Node node = getNode(argString);
return node != null && node.isWord() ? node : null;
}
//得到该前缀的Node,(不用考虑node.isWord())
public Node getPrefix(String argString) {
return getNode(argString);
}
private boolean contains(String argString, boolean argIsWord) {
Node node = getNode(argString);
return (node != null && node.isWord() && argIsWord) ||
(!argIsWord && node != null);
}
//得到该前缀的Node,(不用考虑node.isWord())
private Node getNode(String argString) {
Node currentNode = root;
char argChars[] = argString.toCharArray();
//一个字符一个字符往下找,如果最后找到的Node为null,则说明该字符串没有;如果不为null就返回这个node,在这个node的value属性对应了该字符串
for (int i = 0; i < argChars.length && currentNode != null; i++) {
currentNode = currentNode.getChild(argChars[i]);
if (currentNode == null) {
return null;
}
}
return currentNode;
}
}
/**
* 该类一共有三个属性
* 1.value指的是到该节点的前缀字符串
* 2.children指的是该节点下的所有节点;key用以存放下一个字符,value用以存放对应字符的Node
* 3.isValidWord判断该Node是否对应一个字符串
* @author YH
*
*/
class Node {
private final String value;
private Map<Character,Node> children = new HashMap<Character,Node>();
private boolean isValidWord;
public Node(String argValue) {
value = argValue;
}
public boolean addChild(char c, Node argChild) {
children.put(c, argChild);
return true;
}
public boolean containsChildValue(char c) {
return children.containsKey(c);
}
public String getValue() {
return value.toString();
}
//children是一个Map集合,key用以存放字符,value用以存放对应字符的Node
public Node getChild(char c) {
return children.get(c);
}
public boolean isWord() {
return isValidWord;
}
public void setIsWord(boolean argIsWord) {
isValidWord = argIsWord;
}
public String toString() {
return value;
}
}

提高

上述方式用了Node的方式来进行前缀树的操作,这样做需要大量的对象,内存的耗费比较多
但是如果针对的是特定的内容,比如字符串,或者仅仅包含数字和字母的字符串,可以用二维数组的形式来实现前缀树

用二维数组的方式代替节点Node
二维数组的值和第一维的位置确定了一个节点
二维数组的第二维位置为 该节点包含的字符(可以约定对应数字代替的字符)
例如:
ch[0][1] = 1;
ch[1][3] = 2;
ch[1][3]就相当于ch[0][1]的一个子节点,它的第二维位置为该节点包含的字符

「真诚赞赏,手留余香」