You only get one shot, do not miss your chance to blow.
你只有一发子弹，不要错过引爆全场的机会。
引言
trie树又称“字典树”。关键词提示功能在日常生活中非常常用，通常只需要输出前缀，它就会给出相应的提示。呢具体是怎么实现的呢？本文主要分享了基于trie树的一个简易的搜索提示以及trie树常用的应用场景。所有源码均已上传至github:链接
ps:Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起。
模拟搜索关键词提示功能
本次实现其实也可以改造一下，将用户习惯(输入内容)存成一颗trie树
以how，hi，her，hello，so，see为例
声明一个tire类
这里偷了个小懒，整了一个内部类。
public class TrieNode {
/**
* 字符
*/
public char data;
/**
* 子节点
*/
TrieNode[] children;
/**
* 标识
*/
boolean isEndingChar;
TrieNode(char data) {
children = new TrieNode[26];
isEndingChar = false;
this.data = data;
}
}复制代码初始化
通常根节点是不存储任何信息的，起一个占位符的作用
/**
* 根节点
*/
private TrieNode root;
/**
* 预制单词数量
*/
private int count;
/**
* 提示词列表
*/
private List<String> list;
/**
* 输入值
*/
private String pattern;
/**
* 存储一个无意义的字符
*/
private TrieTree() {
root = new TrieNode('/');
count = 0;
list = new ArrayList<>();
}复制代码插入
private void insert(char[] txt) {
TrieNode p = root;
for (char c : txt) {
//当前字符的ASCII码 - 'a'的 ASCII码
int index = c - 'a';
if (null == p.children[index]) {
TrieNode node = new TrieNode(c);
p.children[index] = node;
}
p = p.children[index];
}
++count;
p.isEndingChar = true;
}复制代码查询
private boolean contains(String pattern) {
char[] patChars = pattern.toCharArray();
TrieNode p = root;
for (char patChar : patChars) {
int index = patChar - 'a';
if (null == p.children[index])
return false;
p = p.children[index];
}
return p.isEndingChar;
}复制代码模糊提示匹配
private void match() {
char[] patChars = pattern.toCharArray();
TrieNode p = root;
for (char patChar : patChars) {
int index = patChar - 'a';
if (null == p.children[index])
return;
p = p.children[index];
}
//开始遍历 p,将所有匹配的字符加入strs
traversal(p, "");
}复制代码递归遍历节点
private void traversal(TrieNode trieNode, String str) {
if (null != trieNode) {
str += trieNode.data;
if (trieNode.isEndingChar) {
String curStr = pattern.length() == 1 ?
str : pattern + str.substring(pattern.length() - 1);
if (!list.contains(curStr))
list.add(curStr);
return;
}
for (int i = 0; i < trieNode.children.length; i++) {
traversal(trieNode.children[i], str);
}
}
}复制代码测试代码
人为构造一个tire树
ps：这里的存储会导致树很高，比如 l l o，其实可以合成llo，也就是缩点优化。这里暂时不实现了。
private void initTries() {
// how，hi，her，hello，so，see
// /
// h s
// e i o o e
// l w e
// l
// o
char[] how = "how".toCharArray();
insert(how);
char[] hi = "hi".toCharArray();
insert(hi);
char[] her = "her".toCharArray();
insert(her);
char[] hello = "hello".toCharArray();
insert(hello);
char[] so = "so".toCharArray();
insert(so);
char[] see = "see".toCharArray();
insert(see);
}复制代码测试代码
public static void main(String[] args) {
TrieTree trieTree = new TrieTree();
trieTree.initTries();
String str = "hello";
boolean res = trieTree.contains(str);
System.out.println("trie树是否包含" + str + "返回结果:" + res);
trieTree.pattern = "h";
trieTree.match();
System.out.println("单字符模糊匹配 " + trieTree.pattern + ":");
trieTree.printAll();
trieTree.list.clear();
trieTree.pattern = "he";
trieTree.match();
System.out.println("多字符模糊匹配 " + trieTree.pattern + ":");
trieTree.printAll();
}复制代码测试结果
trie树实战
未完待续...
end
您的点赞和关注是对我最大的支持，谢谢！