字典树详解

树结构无论是组织数据，还是行使特定功能都是一种强大的武器，今天我们来详细解读一下字典树。

字典树：

字典树是一种特殊的搜索树，可以用来统计字符串数量，统计前缀词频。

字典树有以下基本性质：

1.有一个根节点，但根节点无数据。

2.每个节点有N个出度（N为组成字符串的字符的类型数目），即字典树是个N叉树

3.节点中有判断是否为单词的bool型标志位。

其实字典树可以根据我们的需要进行适当的变动我自己尝试些了一个字典树的类，在此分享一下：

基本数据结构组成：

 1 package com.choi.tools;
 2 
 3 public class TrieTree {
 4 
 5     final Trie root = new Trie();
 6     
 7     class Trie {
 8         int preCount = 0;
 9         int wordCount = 0;
10         Trie[] next = new Trie[52];
11 
12         public Trie() {
13             for (int i = 0; i < 52; i++) {
14                 next[i] = null;
15             }
16         }
17     }
18 }

这里我做了没有使用bool型变量来确定到某一节点的路径是否组成单词，而是利用wordCount来计数该节点组成的单词数目，用preCount来记录root到该节点的路径作为prefix的

数目。

相关函数：

 1 synchronized public void insert(String s) throws NullPointerException {
 2         if (s == null) {
 3             throw new NullPointerException();
 4         }
 5         int L = s.length();
 6         Trie p = root;
 7         for (int i = 0; i < L; i++) {
 8             int id = getId(s.charAt(i));
 9             if(id==-1){
10                 System.out.println("插入s时，有非法字符");
11                 return ;
12             }
13             if (p.next[id] == null) {
14                 p.next[id] = new Trie();
15             }
16             p.next[id].preCount++;
17             p = p.next[id];
18         }
19         p.wordCount++;
20     }
21 
22     public int findWord(String s){
23         if(s==null){
24             return 0;
25         }
26         int L = s.length();
27         Trie p = root;
28         int i = 0;
29         for(; i<L; i++){
30             int id = getId(s.charAt(i));
31             if(id==-1){
32                 return 0;
33             }
34             if(p.next[id]==null)
35                 break;
36             p = p.next[id];
37         }
38         if(i==L)
39             return p.wordCount;
40         else 
41             return 0;
42     }
43     
44     public int findPrefix(String s){
45         if(s==null){
46             return 0;
47         }
48         int L = s.length();
49         Trie p = root;
50         int i = 0;
51         for(; i<L; i++){
52             int id = getId(s.charAt(i));
53             if(p.next[id]==null)
54                 break;
55             p = p.next[id];
56         }
57         return p.preCount;
58     }
59     
60     private int getId(char c){
61         int id = 0;
62         if (c <= 'z' && c >= 'a') {
63             id = c - 'a';
64         } else if (c <= 'Z' && c >= 'A') {
65             id = c - 'A';
66         } else {
67             return -1;
68         }
69         return id;
70     }

insert函数我用synchronized修饰，使该字典树能够支持并发操作。提供了两个获得统计量的函数：findPrefix，findWord 分别统计前缀的数目，和单词的数量。

对异常的处理：

插入操作：如果参数为null，则抛出NullPointerException；如果插入字符串包含非法字符，则跳过不插入，并输出错误信息到控制台。

find操作：如果参数为空和遇到包含非法字符的字符串都范围0，表示没有找到。

操作分析：

根据字典树数据结构的特征，可知插入一个字符串的时间复杂度为O(k)（k为字符串的长度），空间复杂度以这段代码为例每个节点大概占52*4+4+4个字节，一个字符占一个字节，也就是说当我们存储一个字符串时的空间大小为k*216个字节空间，这个量还是很大的，但是如果考虑到字典树的应用场景，这恰恰是其优点了，字典树通常用于大量的文本单词统计，当一个单词反复出现超过216次时，那么多出的次数就好似不占空间了，而对于一部小说而言216是很容易超过的数字。

其实当数据量小的时候我们可以考虑HashTable，key存字符串，value存字符串出现的数目。其实hashtable的时间效率并不比字典树好，反而会稍稍慢一些，因为对每个字符串算hash值时的时间复杂度也是O(k)，并且其还要处理hash冲突。

总之如果数据量小可以考虑hashtabe，如果数据量大那字典树是个非常不错的选择。

GitHub传送门：https://github.com/choitony/TrieTree/tree/master 欢迎阅读，指正！

字典树 详解

字典树详解