前缀树

是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。

字典树又称为前缀树或Trie树，是处理字符串常见的数据结构。假设组成所有单词的字符仅是“a”~”z”，请实现字典树结构，并包含以下四个主要功能：

void insert(String word)：添加word，可重复添加。
void delete(String word)：删除word，如果word添加过多次，仅删除一次。
boolean search(String word)：查询word是否在字典树中。
int prefixNumber(String pre)：返回以字符串pre为前缀的单词数量。
思考：

字典树的介绍。字典树是一种树形结构，优点是利用字符串的公共前缀来节约存储空间。

基本性质：

字典树的基本性质如下：

根节点没有字符路径。除根节点外，每一个节点都被一个字符路径找到。
从根节点到某一节点，将路径上经过的字符连接起来，为扫过的对应字符串。
每个节点向下所有的字符路径上的字符都不同。

也不需要记，看了实现，很自然的性质就理解了。

每个结点内有一个指针数组，里面有二十六个指针，分别指向二十六个字母。

如果指向某个字母的指针为空，那就是以前没有遇到过这个前缀。

搜索的方法为：

(1) 从根结点开始一次搜索；

(2) 取得要查找关键词的第一个字母，并根据该字母选择对应的子树并转到该子树继续进行检索；

(3) 在相应的子树上，取得要查找关键词的第二个字母,并进一步选择对应的子树进行检索。

(4) 迭代过程……

(5) 在某个结点处，关键词的所有字母已被取出，则读取附在该结点上的信息，即完成查找。

其他操作类似处理

插入也一样，只是转到某个子树时，没有子树，那就创建一个新节点，然后对应指针指向新节点即可。

我们给出定义就更清楚了：

public static class TrieNode {
	public int path; //表示由多少个字符串共用这个节点
	public int end;//表示有多少个字符串是以这个节点结尾的
	public TrieNode[] map;
    //哈希表结构，key代表该节点的一条字符路径，value表示字符路径指向的节点
	public TrieNode() {
	    path = 0;
	    end = 0;
	    map = new TrieNode[26];
	}
}

path和end都是有用的，接下来会说明

insert：

	    public static class Trie {
	        private TrieNode root;//头
	 
	        public Trie() {
	            root = new TrieNode();
	        }
	 
	        public void insert(String word) {
	            if (word == null) {
	                return;
	            }//空串
	            char[] chs = word.toCharArray();
	            TrieNode node = root;
	            int index = 0; //哪条路
	            for (int i = 0; i < chs.length; i++) {
	                index = chs[i] - 'a'; //0~25
	                if (node.map[index] == null) {
	                    node.map[index] = new TrieNode();
	                }//创建，继续
	                node = node.map[index];//指向子树
	                node.path++;//经过加1
	            }
	            node.end++;//本单词个数加1
	        }

	        public boolean search(String word) {
	            if (word == null) {
	                return false;
	            }
	            char[] chs = word.toCharArray();
	            TrieNode node = root;
	            int index = 0;
	            for (int i = 0; i < chs.length; i++) {
	                index = chs[i] - 'a';
	                if (node.map[index] == null) {
	                    return false;//找不到
	                }
	                node = node.map[index];
	            }
	            return node.end != 0;//end标记有没有以这个字符为结尾的字符串
	        }

delete：

	        public void delete(String word) {
                  //如果有
	            if (search(word)) {
	                char[] chs = word.toCharArray();
	                TrieNode node = root;
	                int index = 0;
	                for (int i = 0; i < chs.length; i++) {
	                    index = chs[i] - 'a';
	                    if (node.map[index].path-- == 1) {//path减完之后为0
	                        node.map[index] = null;
	                        return;
	                    }
	                    node = node.map[index];//去子树
	                }
	                node.end--;//次数减1
	            }
	        }

prefixNumber：

 public int prefixNumber(String pre) {
	            if (pre == null) {
	                return 0;
	            }
	            char[] chs = pre.toCharArray();
	            TrieNode node = root;
	            int index = 0;
	            for (int i = 0; i < chs.length; i++) {
	                index = chs[i] - 'a';
	                if (node.map[index] == null) {
	                    return 0;//找不到
	                }
	                node = node.map[index];
	            }
	            return node.path;//返回经过的次数即可
	        }

好处：

1.利用字符串的公共前缀来节约存储空间。

2.最大限度地减少无谓的字符串比较，查询效率比较高。例如：若要查找的字符长度是5，而总共有单词的数目是26^5＝11881376，利用trie树，利用5次比较可以从11881376个可能的关键字中检索出指定的关键字，而利用二叉查找树时间复杂度是O( log2n )，所以至少要进行log211881376=23.5次比较。可以看出来利用字典树进行查找速度是比较快的。

应用：

<1.字符串的快速检索

<2.字符串排序

<3.最长公共前缀：abdh和abdi的最长公共前缀是abd，遍历字典树到字母d时，此时这些单词的公共前缀是abd。

<4.自动匹配前缀显示后缀

我们使用辞典或者是搜索引擎的时候，输入appl，后面会自动显示一堆前缀是appl的东东吧。

那么有可能是通过字典树实现的，前面也说了字典树可以找到公共前缀，我们只需要把剩余的后缀遍历显示出来即可。

相关推荐

发表回复