简介
Trie 树又叫字典查找树。顾名思义,字典查找树,主要解决的就是字符串的查找。有以下两个优势。
首先 Trie 树,是一棵树。树是由需要建立的所有词构成。
假设我们有,bee 、sea、 shells,she,sells,几个单词。我们可以使用这几个单词构建一棵树。
通过图片我们就可以直观的看出 Trie 的数据结构。这个棵树是由若干节点,链接而成,节点可以指向下一个节点,也可以指向空。从 root 节点开始,顺着链接随便找某个链接往下,直到最低端,经过的路径正好是上文的单词。
为了方便使用代码表示。可以考虑每个节点使用数组表示。每个节点都含有一个数组,数组的大小为R,R 是数组的基数,对应每个可能出现的字符。R 的选取取决于报错的字符的类型,如果只包含英文则256 就可以了。如果是中文就需要 65536。
字符和键值都保存在数据结构中。
所以实现代码如下:
public class TrieST<Value> {
public static final int R = 256;
private Node root;
private static class Node {
public Object val; // 键值
public Node[] next = new Node[R];
}
}
对于数据结构的键值的读写方法,我可以使用递归的方式进行查询
private Node get(Node x, String key, int d) {
// 1
if (x == null) {
return null;
}
//2
if (d == key.length()) {
return x;
}
//3
char c = key.charAt(d);
//4
return get(x.next[c], key, d + 1);
}
public Value get(String key) {
Node x = get(root, key, 0);
if (x == null) {
return null;
}
return (Value) x.val;
}
对于递归的我们需要考虑两个问题。递归的退出的条件是什么,如何进入下一层递归。
对于 Node get(Node x, String key, int d)
,入参 x
是当前的节点,key 是需要查找的字字符串,d 是目前递归到的层数,也可以理解为,我们逐个遍历 key 的时候的下标。
我们按照注释逐行讲解一下:
我们再来看 put 方法:
private Node put(Node x, String key, Value val,int d) {
//1
if(x == null) {
x= new Node();
}
//2
if(d == key.length()){
x.val = val;
return x;
}
//3
char c = key.charAt(d);
//4
x.next[c] = put(x.next[c],key,val,d + 1);
return x;
}
public void put(String key,Value val){
root = put(root,key,val,0);
}
put 方法和 get 方法非常类似,习惯上来说我们在保存数据的时候,都需要先查询一下看看数据存不存在,如果存在直接返回,如果不存在再插入数据。Trie 数的插入也是这个思路。
我们按照注释逐行讲解一下:
看完这 Put 和 Get 方法。我们再回顾一下 Trie 的性质。
查询的次数,只和代码中的 key 的长度有关,与字典的大小没有关系。
如果没有命中的数据,查询的次数小于等于 key 的长度 。
这里先着重介绍一下 Trie 树的其中一个应用 ”前缀匹配“。
我们在搜索框里面输入一个词的时候,通常会收到提示的列表如下图:
输入 flink 的时候,搜索引擎会提示联想出用户可能的输入,提升用户体验。
有了上面的 Trie 树的介绍。具体实现这个功能就比较简单了。
回到我们原有的例子,假设词库里面有单词 bee 、sea、 shells,she,sells。如果用户输入 se 两个字符,我们应该会向用户提示 se 开始的词:sea 和 sells。
结合图片,我们要找到 se 开头的字符。我们首先要定位出图中红色的链条,然后把红色 e 的所有子链找出来。当然如果 e 的子链特别多,我们就需要考虑对子链进行截断。具体怎么截断我们以后会的文章里面可能会讲解。
我们先看代码:
private void collect(Node x, String pre, Queue<String> q){
//3
if(x == null){
return;
}
//4
if(x.val != null){
q.add(pre);
}
//5
for(char c = 0;c < R; c++){
collect(x.next[c],pre + c, q);
}
}
public Iterable<String> keysWithPrefix(String pre){
//1
Queue<String> q = new LinkedList<String>();
//2
collect(get(root,pre,0),pre,q);
return q;
}
逐条解释一下:
get(root,pre,0)
就是为了找出上图中标红的 e节点。然后把 e 节点放到 collect()
方法中。我们只需要调用方法 keysWithPrefix("se")
即可。
Trie 树在查询的时间复杂度是 O(k) 与词库的大小无关。 但是,有利必有弊。
利用数组表示节点实现的 Trie 树非常占用空间。
如果运用在英文文本处理中,假设单词的平均长度是 11 个字符,R 的大小是 256,100万个键构成的树大约有 2亿5千万个链接数。
是典型的空间换时间应用。