正文
标准Trie字典树学习二：Java实现方式之一
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
特别声明：
博文主要是学习过程中的知识整理，以便之后的查阅回顾。部分内容来源于网络（如有摘录未标注请指出）。内容如有差错，也欢迎指正！
系列文章：
1. 标准Trie字典树学习一：原理解析
2.标准Trie字典树学习二：Java实现方式之一
Trie树基于Java的一种简单实现， 上代码。
1. 定义节点类TrieNode
/**
* TrieNode 节点类
* @author Konrad created on 2017/10/28
*/
public class TrieNode {
private LinkedList<TrieNode> children; //子节点
private char data; //节点字符
private int freq; //频率
boolean isEnd; //是否为叶子节点 public TrieNode(char data){
this.children = new LinkedList<>();
this.freq = 0;
this.isEnd = false;
this.data = data;
} public TrieNode childNode(char c){
if(null != children){
for(TrieNode child : children){
if(child.getData() == c){
return child;
}
}
}
return null;
} public LinkedList<TrieNode> getChildren() {
return children;
} public void setChildren(LinkedList<TrieNode> children) {
this.children = children;
} public char getData() {
return data;
} public void setData(char data) {
this.data = data;
} public int getFreq() {
return freq;
} public void setFreq(int freq) {
this.freq = freq;
} public void addFreq(int step){
this.freq += step;
} public void subFreq(int step){
this.freq -= step;
} public boolean isEnd() {
return isEnd;
} public void setEnd(boolean end) {
isEnd = end;
}
}
2. 定义Trie树类TrieTree
/**
* TrieTree Trie树类
*
* @author Konrad created on 2017/10/28
*/
public class TrieTree {
private TrieNode root; public TrieTree() {
this.root = new TrieNode(' ');
} //查找是否存在
public boolean search(String word) {...} //查找返回节点
public TrieNode searchNode(String word) {...} //插入
public void insert(String word) {...} //移除
public void remove(String word) {...} //获取词频
public int getFreq(String word) {...}
}
3. 插入节点
public void insert(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
TrieNode child = current.childNode(word.charAt(i));
if (null != child)
current = child;
else {
current.getChildren().add(new TrieNode(word.charAt(i)));
current = current.childNode(word.charAt(i));
}
current.addFreq(1);
}
current.setEnd(true);
}
4.查找节点
//查找是否存在
public boolean search(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
if (null == current.childNode(word.charAt(i)))
return false;
else
current = current.childNode(word.charAt(i));
} if (current.isEnd())
return true;
else
return false;
} //查找返回节点
public TrieNode searchNode(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
if (null == current.childNode(word.charAt(i)))
return null;
else
current = current.childNode(word.charAt(i));
} if (current.isEnd())
return current;
else
return null;
}
5.删除节点
//移除
public void remove(String word) {
if (!search(word))
return; TrieNode current = root;
for (char c : word.toCharArray()) {
TrieNode child = current.childNode(c);
if (child.getFreq() == 1) {
current.getChildren().remove(child);
return;
}else{
child.subFreq(1);
current = child;
}
}
current.setEnd(false);
}
6.获取某个词的频率
//获取词频
public int getFreq(String word) {
TrieNode trieNode = searchNode(word);
if(null != trieNode){
return trieNode.getFreq();
}else{
return 0;
}
}
7.代码测试
/**
* @author Konrad created on 2017/10/28
*/
public class TrieTreeDemo {
public static void main(String[] args) {
String sentence = "today is good day what is you name at facebook how do you do what are you doing here";
TrieTree trieTree = new TrieTree();
for (String str : sentence.split(" ")) {
trieTree.insert(str); //插入节点，构建Trie树
} //判断是否存在
System.out.println("Does the word 'facebook' exists: " + trieTree.search("facebook"));
//统计do的词频
System.out.println("Frequent of the word 'you': " + trieTree.getFreq("do")); //移除today
System.out.println("Does the word 'today' exists - before remove: " + trieTree.search("today"));
trieTree.remove("today");
System.out.println("Does the word 'today' exists - after remove: " + trieTree.search("today"));
}
}
输出结果：
这只是Trie树的实现方法之一，也可以使用其他不同方式来实现。
