海量数据处理-Trie树

http://blog.csdn.net/beiyeqingteng/article/details/6981263

http://blog.csdn.net/zmazon/article/details/8227610#

关注Trie 这种结构已经很久，Trie有一个很有趣的用途，那就是自动提示。而且，前不久在一次面试里，也需要用Trie来解答。所以，在此对这个数据结构进行总结。

Trie，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。
它有3个基本性质：

1，根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2，从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3，每个节点的所有子节点包含的字符都不相同。

下面这个图就是Trie的表示，每一条边表示一个字符，如果结束，就用星号表示。在这个Trie结构里，我们有下面字符串，比如do, dork, dorm等，但是Trie里没有ba, 也没有sen，因为在a, 和n结尾，没有结束符号（星号）。

                                   

我们来看看Trie树的特点：根节点为空值，剩下每一个节点保存一个字母。知道这些就够了！

我们再来看看这棵树能干什么？如果从根节点遍历到某一个节点把路径节点的值连在一起就构成了一个字符串，利用这个特点很容易想到这棵树的第一个功能能帮我们查找某一个单词是否在树中（需要在每一个节点设置一个标志，表示从根节点到此节点是否构成一个单词）；如果该单词存在，我们可以利用它实现第二个功能：去除重复单词；同样如果该词存，在我们还可以看出它的第三个功能：统计单词频率；因为这是一个树形结构我们利用这个特点很容易看出它的第四个功能能帮我们查找N个单词的最长公共前缀；如果我们按顺序遍历输出整棵树，发现它的第五个功能：对字符串排序。


这棵树创建看起来比较容易，就有一个问题需要我们考虑：父节点如何保存孩子节点？ 主要有两种方式供大家参考：

1.因为是英文字符，我们可以用Node[26]来保存孩子节点(如果是数字我们可以用Node[10])，这种方式最快，但是并不是所有节点都会有很多孩子，所以这种方式浪费的空间太多

2.用一个链表根据需要动态添加节点。这样我们就可以省下不小的空间，但是缺点是搜索的时候需要遍历这个链表，增加了时间复杂度。

class TrieNode{//结点类private static final int NUMBER = 26;private char _value;private boolean _isWord;//从根节点到这个节点存不存在一个单词TrieNode[] _children = new TrieNode[NUMBER];//子结点集合public TrieNode(char c) {this.setValue(c);}public char getValue() {return _value;}public void setValue(char _value) {this._value = _value;}public boolean isWord() {return _isWord;}public void setIsWord(boolean _isWord) {this._isWord = _isWord;}}public class TrieTree {static String[] _words = {"add","am","good","the","think"};//待插入单词private boolean searchWord(TrieNode _root, String _word) {if(null == _root || null == _word || "".equals(_word))return false;char[] cs = _word.toCharArray();//将字符串转化为字符数组for(int i = 0; i < cs.length; i++){int index;if(cs[i] >= 'A' && cs[i] <= 'Z'){index = cs[i]-'A';}else if(cs[i] >= 'a' && cs[i] <= 'z') index = cs[i] - 'a';elsereturn false;TrieNode child_node = _root._children[index];if(null != child_node){//找到相同字符if(child_node.isWord())//如果找到该单词return true;} if(null == child_node)//如果在i层没找到相同字符 return false;_root = child_node;//重设根节点}return false;}private void insertIntoTree(TrieNode _root, String _word) {//插入一个单词if(null == _root || null == _word || "".equals(_word))return;char[] cs = _word.toCharArray();//将字符串转化为字符数组for(int i = 0; i < cs.length; i++){int index;//对应的索引值if(cs[i] >= 'A' && cs[i] <= 'Z'){index = cs[i]-'A';}else if(cs[i] >= 'a' && cs[i] <= 'z') index = cs[i] - 'a';elsereturn;TrieNode child_node = _root._children[index];if(null == child_node){//如果没找到TrieNode new_node = new TrieNode(cs[i]);//创建新节点if(i == cs.length-1)//如果遍历到该单词最后一个字符new_node.setIsWord(true);//把该单词存在树中_root._children[index] = new_node;//连接该节点_root = new_node;}else_root = child_node;//更新树根}}private void printTree(TrieNode _root,char[] _word,int index) {if(_root == null)return;if(_root.isWord()){//如果根节点到此节点构成一个单词则输出for(char c : _word){if(c != ' ')System.out.print(c);}System.out.println();}for(TrieNode node : _root._children){//遍历树根孩子节点if(node != null){//回溯法遍历该树_word[index++] = node.getValue();printTree(node,_word,index);_word[index] = ' ';index--;}}}public static void main(String[] args){TrieTree _tree = new TrieTree();//创建一棵树TrieNode _root = new TrieNode(' ');//创建根节点for(String word : _words)//插入单词_tree.insertIntoTree(_root,word);char[] _word = new char[20];_tree.printTree(_root,_word,0);//打印树中单词boolean status = _tree.searchWord(_root,"think");//查询树中是否存在某单词System.out.println(status);} }

总结

以上是生活随笔为你收集整理的海量数据处理-Trie树的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。