由字典树想到的
由字典树想到的
- 字典树
- 双数组树
- AC自动机双数组树
基于数组实现的字典树
public class TrieST<Value> {
private static int R = 256;
private Node root;
public static class Node{
private Object val;
private Node[] next = new Node[R];
}
public Value get(String key) {
Node x = get(root, key, 0);
if (x == null) {
return null;
}
return (Value) x.val;
}
private Node get(Node x, String key, int d) {
if (x == null) {
return null;
}
if (d == key.length()) {
return x;
}
char c = key.charAt(d);
return get(x.next[c], key, d + 1);
}
public void put(String key, Value val) {
root = put(root, key, val, 0);
}
private Node put(Node x, String key, Value val, int d) {
if (x == null) {
x = new Node();
}
if (d == key.length()) {
x.val = val;
return x;
}
char c = key.charAt(d);
x.next[c] = put(x.next[c], key, val, d + 1);
return x;
}
public static void main(String[] args) {
TrieST<String> stringTrieST = new TrieST<>();
stringTrieST.put("a", "1");
String val = stringTrieST.get("a");
System.out.println(val);
}
}
- 基于数组实现的字典树,每个节点都有一个长度为R的数组。空间复杂度高。
- 查找成功的时间复杂度为O(logN)
基于HashMap实现的字典树
import java.util.HashMap;
import java.util.Map;
public class MapTrieST<Value> {
private Node root;
private static class Node{
private Object val;
private Map<Character, Node> next = new HashMap<>();
}
public Value get(String key) {
Node x = get(root, key, 0);
// if (x == null) {
// return null;
// }
return (Value) x.val;
}
private Node get(Node x, String key, int d) {
if (x == null) {
return null;
}
if (d == key.length()) {
return x;
}
Character ch = key.charAt(d);
return get(x.next.get(ch), key, d + 1);
}
public void add(String key, Value val) {
root = add(root, key, val, 0);
}
private Node add(Node x, String key, Value val, int d) {
if (x == null) {
x = new Node();
}
if (d == key.length()) {
x.val=val;
return x;
}
Character ch = key.charAt(d);
x.next.put(ch, add(x.next.get(ch), key, val, d + 1));
return x;
}
public static void main(String[] args) {
MapTrieST<String> mapTrieST = new MapTrieST<>();
mapTrieST.add("i", "1");
mapTrieST.add("love", "2");
mapTrieST.add("u", "3");
System.out.println(mapTrieST.get("i"));
System.out.println(mapTrieST.get("l"));
System.out.println(mapTrieST.get("u"));
System.out.println(mapTrieST.get("x"));
}
}
- 使用HashMap来保存所有的孩子节点,当孩子节点很多时,Map不可避免地存在Hash冲突的问题
- 空间利用率要比基于数组实现的字典树高
- 基于数组实现的字典树,访问下一个节点时是通过数组下标进行定位;基于HashMap实现的字典树访问下一个节点是通过Hash查找定位,时间复杂度可以都认为是O(1)
双数组字典树
针对普通的基于数组实现的字典树的一个优化,大大提高了空间利用率。
引入AC自动机的双数组字典树
在双数组字典树的基础上引入AC自动机,从而具有多模式匹配的功能。
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。双数组字典树和ACDAT(引入了AC自动机的双数组字典树)可参考hancks的开源项目。
一些问题:
字典树与红黑树的对比
key的有序性?是否有效支持更新操作?
特殊字符的匹配命中
基于数组的实现字典树是通过数组下标寻找下一个节点的,如果有些十分特殊的字符超出了数组的表示范围,那就无法用来字典树匹配特殊字符了。
有一种不太优雅的实现思路是:基于HashMap来实现字典树,但是HashMap的Key并不是词典中的词,而是每一个字符的编码。这样,不管是什么样的特殊字符,它都有一个编码,用这个编码作为Key,就能构造含有特殊的字典树了。
中文分词中为什么会用到双数组字典树?
参考资料
双数组Trie树(DoubleArrayTrie)Java实现
原文:https://www.cnblogs.com/hapjin/p/10174870.html
更多精彩