字典树(前缀树)--Trie
2019-09-30 本文已影响0人
叫我胖虎大人
什么是字典树
是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
主要用于解决的问题
- 查询字符串
与字典的对比
如果有n个条目
- 使用树结构,查询的时间复杂度是O(logn)
- 使用trie,查询每个条目的时间复杂度和字典中的总条目无关.
时间复杂度为O(w),w为查询单词的长度.且大多数单词的长度小于10
结构分析
Trie结构示意图
每个节点有若干指向下个节点的指针,考虑不同的语言,不同的环境.
class Node{
//是否结尾,不能完全 通过叶子节点来判断是一个单词
boolean isWord();
Map<char,Node> next;
}
完整代码
import java.util.Stack;
import java.util.TreeMap;
public class Trie {
private class Node {
public boolean isWord;
//通过next指向下一个节点.是通过线段,而不是节点,头一个节点为空
public TreeMap<Character, Node> next;
public Node(boolean isWord) {
this.isWord = isWord;
next = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
root = new Node();
size = 0;
}
/**
* 获取Trie的词的数量
*
* @return Trie的大小
*/
public int getSize() {
return size;
}
/**
* 向Trie中添加一个新的单词
*
* @param word 新的单词
*/
public void add(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
//如果后继节点不是指向c,创建一个新的节点
if (cur.next.get(c) == null) {
cur.next.put(c, new Node());
}
cur = cur.next.get(c);
}
//判断是否已经存在,如果已经存在,不再进行size++操作
if (!cur.isWord) {
//标示一个词的结尾(不一定是叶子节点,因为一个词可能是另外一个词的前缀)
cur.isWord = true;
size++;
}
}
/**
* 向Trie中添加一个新的单词
*
* @param word 新的单词
*/
public void recursionAdd(String word) {
add(root, word, 0);
}
/**
* 递归写法调用方法实现递归添加
*
* @param node 传入要进行添加的节点
* @param word 传入要进行添加的单词
*/
public void add(Node node, String word, int index) {
// 确定终止条件,这个终止条件在没加index这个参数时,很难确定
// 此时一个单词已经遍历完成了,如果这个结束节点没有标记为单词,就标记为单词
if (!node.isWord && index == word.length()) {
node.isWord = true;
size++;
}
if (word.length() > index) {
char addLetter = word.charAt(index);
// 判断trie的下个节点组中是否有查询的字符,如果没有,就添加
if (node.next.get(addLetter) == null) {
node.next.put(addLetter, new Node());
}
// 基于已经存在的字符进行下个字符的递归查询
add(node.next.get(addLetter), word, index + 1);
}
}
/**
* 查询单词word是否在Trie当中
*
* @param word 待查询的字符串
* @return 返回的结果
*/
public boolean contains(String word) {
Node cur = root;
for (int i = 0; i < word.length(); i++) {
char c = word.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return cur.isWord;
}
/**
* 查询单词word中是否在Trie中接口(递归写法)
*
* @param word 单词
* @return 是否存在
*/
public boolean recursionContains(String word) {
return contains(root, word, 0);
}
/**
* 查询word中是否在Trie中递归写法
*
* @param node 当前节点
* @param word 单词
* @param index 字符串所在索引
* @return 是否存在
*/
private boolean contains(Node node, String word, int index) {
if (index == word.length()) {
return node.isWord;
}
char c = word.charAt(index);
if (node.next.get(c) == null) {
return false;
} else {
return contains(node.next.get(c), word, index + 1);
}
}
/**
* 查询是否在Trie中有单词以prefix为前缀
*
* @param prefix 前缀
* @return
*/
public boolean isPrefix(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if (cur.next.get(c) == null) {
return false;
}
cur = cur.next.get(c);
}
return true;
}
/**
* 删除单词
*
* @param word 要删除的单词,注意是单词而不是前缀
* @return 是否删除成功, 存在则成功
*/
public boolean remove(String word){
// 将搜索沿路的节点放入栈中
Stack<Node> stack = new Stack<>();
stack.push(root);
for(int i = 0; i < word.length(); i ++){
if(!stack.peek().next.containsKey(word.charAt(i))) {
return false;
}
//如果存在的压入栈,如果存在则将该单词所有的节点以及root节点压入栈中
stack.push(stack.peek().next.get(word.charAt(i)));
}
if(!stack.peek().isWord) {
return false;
}
// 将该单词结尾isWord置空
stack.peek().isWord = false;
size --;
// 如果单词最后一个字母的节点的next非空，
// 说明trie中还存储了其他以该单词为前缀的单词，直接返回,不进行删除操作
if(stack.peek().next.size() > 0) {
return true;
} else {
stack.pop();
}
// 自底向上删除,word.length() - 1是因为扇面已经pop了一个
for(int i = word.length() - 1; i >= 0; i --){
stack.peek().next.remove(word.charAt(i));
// 如果一个节点的isWord为true，或者是其他单词的前缀，则直接返回
if(stack.peek().isWord || stack.peek().next.size() > 0) {
return true;
}
stack.pop();
}
return true;
}
}
注意:
- 在Trie的Node节点当中,使用了TreeMap作为底层实现,TreeMap的底层实现是红黑树,红黑树是很高效的（各项操作均为O(logn)），但是，一定要注意，复杂度分析关注的是n趋于无穷的情况。对于小样本数据，一个复杂的复杂度更优的算法，很有可能比不上一个简单的复杂度更低的算法。因为常数项的不同。
- 对于Trie来说，有一个重要的时间开销。由于Trie消耗的空间比较大（每个节点会有若干个指针），所以给这些承载指针的空间（TreeMap，HashMap或者数组）开辟内存也是一个额外的时间消耗.
解决空间消耗的方案
-
压缩字典树
将不被重用的字符放在同一个节点当中,但是在插入一个新的单词的时候,就会存在拆出单词的操作
压缩字典树
-
三分搜索词典树(Ternary Search Trie)
三分搜索词典树
查找演示
演示图
从
d节点的上方出发,寻找到节点d,那么将进入d的下一个节点k;
节点d出发,其下一节点为k,要寻找的节点是o,o比k大,所以是k的右子节点
同理,寻找g节点,g比i小,所以是进入左子节点
参考课程:慕课网-玩转数据结构 从入门到进阶
参考博客:http://www.pianshen.com/article/5454344862/
