1.trie是一个n叉树
一个微软的实习生为了解决手机通讯录软件查询储存了多个
联系人而研发了这个trie
trie又称之为前缀树
- 什么是trie?
什么是trie.png
tire是一个n叉树，每一个节点包含单词的标记，以key--value形式的当前字符与下一个节点的映射(由于设计原因，下一个节点的单词标记储蓄的为上一个节点key的单词标记)
二、trie中的操作实现
- trie中添加一个节点:非递归
add、递归put - trie的查询操作:非递归
contain、递归include - trie的前缀查询(LeetCode上208号问题):
isPrefix - Trie的删除操作:
remove
Trie的删除操作.png
import java.util.TreeMap;
public class Trie {
private class Node {
public boolean isWord;
public TreeMap<Character, Node> current; /**总感觉叫做next有点别扭*/
public Node(boolean isWord) {
this.isWord = isWord;
this.current = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
private int size;
public Trie() {
this.root = new Node();
size = 0;
}
/** 获得Tril中储存的单词的数量*/
public int getSize() {
return this.size;
}
/** 向trie中添加一个节点,非递归实现*/
public void add(String word) {
Node cur = root;
for(int i = 0; i < word.length(); i ++) {
char c = word.charAt(i);
if(cur.current.get(c) == null)
cur.current.put(c, new Node());
cur = cur.current.get(c); // 这里有一个坑！要注意
}
if(!cur.isWord) {
size ++;
cur.isWord = true;
}
}
/** 向trie中添加一个节点，递归实现，思路与传统的有点不一样*/
public void put(String word) {
put(root, 0, word);
}
private void put(Node cur, int index, String word) {
if(!cur.current.containsKey(word.charAt(index)))
cur.current.put(word.charAt(index), new Node());
cur = cur.current.get(word.charAt(index));
if(index == word.length() - 1) {
if(!cur.isWord){
cur.isWord = true;
size ++;
}
return;
}
put(cur, ++index, word);
}
/** trie的查询操作，非递归实现*/
public boolean contain(String word) {
Node cur = root;
for(int i = 0; i < word.length(); i ++) {
if(!cur.current.containsKey(word.charAt(i)))
return false;
cur = cur.current.get(word.charAt(i));
}
return cur.isWord;
}
/** trie 的查询操作，递归实现*/
public boolean include(String word) {
return include(root, 0, word);
}
private boolean include(Node cur, int index, String word) {
char c = word.charAt(index);
if(!cur.current.containsKey(c))
return false;
cur = cur.current.get(c);
if(index == word.length() - 1)
return cur.isWord;
return include(cur, ++index, word);
}
/** trie的前查询，只要包含被查询的前缀，就返回true*/
public boolean isPrefix(String prefix) {
Node cur = root;
for (int i = 0; i < prefix.length(); i++) {
char c = prefix.charAt(i);
if(!cur.current.containsKey(c))
return false;
cur = cur.current.get(c);
}
return true;
}
/**查询字典中是否包含一个字符串，模糊匹配, 比如
* f.....d 这种，从根节点开始，.表示可以匹配任意字符！
* 递归实现*/
public boolean search(String word) {
return search(root, 0, word);
}
private boolean search(Node node, int index, String word) {
if(index == word.length())
return node.isWord;
char c = word.charAt(index);
if(c != '.') {
if(node.current.containsKey(c))
return search(node.current.get(c), index + 1, word);
else
return false;
} else {
for (char ch :node.current.keySet()) {
if(search(node.current.get(ch), index + 1, word))
return true;
}
return false;
}
}
/**删除一个字符串；递归：回溯判断的思想,确认删除下一个节点就
* 返回true,否则就返回false*/
public boolean remove(String word) {
return remove(root, 0, word);
}
/**当遍历到单词的末尾，有三种情况
* 1. 当前并没有标记此单词，只是碰巧遇到了一个前缀
* 2. 当前节点标记了此单词，但是也是一个前缀
* 3. 当前节点标记了此单词，是末尾节点。
*
**当回溯删除到一定节点，有两种情况
* 1. 当前节点是公共节点，不能删除
* 2. 当前节点只有一个子节点，可以删除
* */
private boolean remove (Node node, int index, String word) {
if(index == word.length()) {
if(!node.isWord)
return false;
if(node.current.size() != 0) {
node.isWord = false;
return false;
}
return true;
}
char c = word.charAt(index);
if(node.current.get(c) == null)
return false;
boolean charge = remove(node.current.get(c), ++index, word);
if(charge && node.current.size() == 1) {
node.current.remove(c);
return true;
}
return false;
}
public static void main(String[] args) {
Trie trie = new Trie();
trie.add("abcdefg");
trie.add("abcdeft");
trie.add("dsldsaf.dfak");
trie.add("asdfierdsfe3");
trie.add("lokjjwdgh");
trie.add("asrgtaolfeolag");
trie.remove("abcdeft");
trie.remove("dsldsaf");
System.out.println(trie.contain("asrgtaolfeolag"));
}
}
- 简单的模式匹配:leetCode-211
import java.util.TreeMap;
public class WordDictionary { // WordDictionary Trie211
private class Node {
public boolean isWord;
public TreeMap<Character, Node> current; /**总感觉叫做next有点别扭*/
public Node(boolean isWord) {
this.isWord = isWord;
this.current = new TreeMap<>();
}
public Node() {
this(false);
}
}
private Node root;
public WordDictionary() {
this.root = new Node();
}
/** 向trie中添加一个节点,非递归实现*/
public void addWord(String word) {
Node cur = root;
for(int i = 0; i < word.length(); i ++) {
char c = word.charAt(i);
if(cur.current.get(c) == null)
cur.current.put(c, new Node());
cur = cur.current.get(c); // 这里是一个坑！！！！
}
if(!cur.isWord) {
cur.isWord = true;
}
}
public boolean search(String word) {
return search(root, 0, word);
}
private boolean search(Node node, int index, String word) {
if(index == word.length())
return node.isWord;
char c = word.charAt(index);
if(c != '.') {
if(node.current.containsKey(c))
return search(node.current.get(c), ++index, word);
else
return false;
} else {
for (char ch :node.current.keySet()) {
if(search(node.current.get(ch), ++index, word))
return true;
}
return false;
}
}
}
- Map Sum Pairs:leetCode-677
import java.util.TreeMap;
public class MapSum {
private class Node {
public int value;
public TreeMap<Character, Node> next;
public Node(int value) {
this.value = value;
this.next = new TreeMap<>();
}
public Node() {
this(0);
}
}
public Node root;
public MapSum() {
this.root = new Node();
}
public void insert(String key, int val) {
Node node = root;
for (int i = 0; i < key.length(); i++) {
char c = key.charAt(i);
if(!node.next.containsKey(c))
node.next.put(c, new Node());
node = node.next.get(c);
}
node.value = val;
}
public int sum(String prefix) {
Node node = root;
for(int i = 0; i< prefix.length(); i ++) {
char c = prefix.charAt(i);
if(!node.next.containsKey(c))
return 0;
node = node.next.get(c);
}
return sum(node);
}
private int sum(Node node) {
int count = node.value;
for(char c : node.next.keySet())
count += sum(node.next.get(c));
return count;
}
public static void main(String[] args) {
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
System.out.println(mapSum.sum("ap"));
mapSum.insert("app", 2);
System.out.println(mapSum.sum("ap"));
mapSum.insert("apply", 3);
System.out.println(mapSum.sum("ap"));
}
}
三、更多和Trie相关的话题
Trie的局限性 :最大的问题，空间问题
class Node{
boolean isWord;
TreeMap<Character, Node> next;
}
对于这个问题，有一个优化--压缩字典树
1.Compressed Trie
压缩字典树.png
但是带来的问题是 维护成本增高了
2.Ternary Search Trie 三分搜索树
三分搜索树1.png
三分搜索树2.png
字符串模式识别 后缀树
更多字符串问题 (计算机科学领域研究的非常深入的一个问题：代码？网页？等等.....)
-
- 子串查询算法
- KMP
- Boyer-Moore
- Rabin-Karp
- 文件压缩(对一个非常大的字符串压缩)
- 模式匹配(正则表达式引擎)
- 编译原理(编译Java源码的Java编译器)
- DNA 生命科学领域
等等...
