2019-04-23 20:57:35 qq_24034545 阅读数 67
  • Oracle数据

    本课程主要讲解如下内容:Oracle体系结构、Oracle 基础管理、SQL 语言、Sequence和同义词、数据字典及用户管理、E-R模型、Power Designer设计工具。在本课程讲解之中会提供有相应的练习习题以及综合案例分析,帮助读者迅速掌握Oracle数据库的核心开发技能。官方QQ群:612148723。

    61531 人正在学习 去看看 李兴华

摘要

博客内容主要介绍了字典树的概念、结构、操作、Java语言实现及应用。

1.字典树的概念

字典树(Trie-Tree)又可以称为单词查找树或键树,是一种树形结构,一种哈希树的变种。可以应用于统计和排序大量的字符串,所以经常被搜索引擎系统用于文本词频统计。其优点为最大限度地减少无谓的字符串比较,查询效率比哈希表还要高。字典树的核心思想为空间换时间。它利用字符串的公共前缀来降低查询时间的开销,以达到提高效率的目的。

2.字典树的结构

字典树的结构如图1所示,其特点可以归纳如下。

                                                                      

                                                                                                          图1 字典树结构图

(1)其根结点不包含字符,其他结点只包含一个字符;

(2)节点的每个字节点所包含的字符是不同的;

(3)从根结点到任意节点所经过的路径,连接起来就是该结点对应的字符串;

(4)如果字符的种数为n,则每个结点的出席为n,这也是空间换时间的体现;

(5)插入查找的复杂度为O(n),n为字符串长度。

图1中的字典树由字符串"abc","ab",“bd”,"dda"四个字符串组成。构建过程为:根结点不包含任何字符,遍历第一个字符串"abc",首字母为'a',将其接到根结点的子节点中,再将'b'接到'a'的子结点中,最后将'c'接到'b'的子节点中,并标红注明该结点处可以构成一个单词。遍历第十个字符串"ab",发现'a'->'b'已经存在,则将'b'标红注明该结点可以构成一个单词,如此迭代下去。

3.字典树的操作

字典树的操作主要有插入、删除、查找等。

3.1 插入

字典树的插入过程即字典树的建立过程,其复杂度为O(n*len),n为字符串个数,len为字符串平均长度。

3.2 删除

从字典树中删除某个单词时,可以以递归的形式进行。如从图1中的字典树中删除"ab",它与"abc"同边。

3.3 查找

字典树的查找操作复杂度是O(len),len为字符串的长度。此外,字典树的建立与查找是可以同时进行的。

4.字典树的实现(Java语言)

public KeyNotFound extends Exception {
    public KeyNotFound(String message) {
        super(message);
    }
}

public class Trie {
    class TrieNode {
        char curr;
        TrieNode[] children;
        private boolean isEnd;
        String data; 
        private int count;
        TrieNode (char curr, boolean isEnd, String data) {
            // Cast all the chars to lower case
            curr = Character.toLowerCase(curr);
            this.curr = curr;
            this.isEnd = isEnd;
            this.data = data;
            this.children = new TrieNode[26];
            this.count = 1;
        }

        void setEnd(boolean end) {
            this.isEnd = end;
        }

        void increaseCount() {
            this.count++;
        }

        int getCount() {
            return this.count;
        }

        void decreaseCount() {
            this.count--;
        }
    }

    private TrieNode root;

    public Trie() {
        /** Initialize the Trie. */
        this.root = new TrieNode(' ', false, "");
    }

    public void insert(String word, String data) {
        /** Inserts a word and corresponding data into the trie. */
        char[] chars = word.toCharArray();
        TrieNode currPos = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            // If a node corresponding to current substring does not exists, create one.
            if (currPos.children[index] == null) {
                TrieNode newNode = new TrieNode(chars[i], false, ""); 
                currPos.children[index] = newNode;
            }
            // If this is the end of the word, store the data in to the Trie and set end.
            if (i == chars.length - 1) {
                currPos.children[index].setEnd(true);
                currPos.children[index].data = data;
            }
            // Move one level down
            currPos = currPos.children[index];
        }
    }

    public boolean search(String word) {
        /** Returns if the word is in the Trie. */
        char[] chars = word.toCharArray();
        TrieNode currPos = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            // If no match find, return false
            if (currPos.children[index] == null) {
                return false;
            }
            if (i == chars.length - 1 && currPos.children[index].isEnd) {
                return true;
            }
            currPos = currPos.children[index];
        }
        return false;
    }

    public boolean startsWith(String prefix) {
        /** Returns if there is any word in the Trie that starts with the given prefix. */
        char[] chars = prefix.toCharArray();
        TrieNode currPos = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            if (currPos.children[index] == null) {
                return false;
            }
            currPos = currPos.children[index];
        }
        return true;
    }

    public String getData(String key) throws KeyNotFound {
        /** 
         * Gets the corresponding data for the given key if the key exists in the Trie.
         * Throw KeyNotFound error if no such key exists
         */   
        char[] chars = key.toCharArray();
        TrieNode currPos = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            // If no match find, return empty string
            if (currPos.children[index] == null) {
                throw new KeyNotFound("Given key does not exists in the Trie!");
            }
            currPos = currPos.children[index];
        }
        if (!currPos.isEnd) {
            throw new KeyNotFound("Given key does not exists in the Trie!");
        }
        return currPos.data;
    }

    public boolean setData(String key, String newData) {
        /**
         * Change the data of an existing key.
         * If changed successfully, return true.
         * If the key doesn't exists, return false.
         */
        char[] chars = key.toCharArray();
        TrieNode currPos = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            // If no match find, cannot store the data, return false
            if (currPos.children[index] == null) {
                return false;
            }
            currPos = currPos.children[index];
        }
        if (!currPos.isEnd) {
            return false;
        }
        currPos.data = newData;
        return true;
    }

    public void delete(String word) {
        /**
         * Delete the given word in the Trie if exists
         */
        // If the word doesn't exist in the Trie, should delete anything
        if (!search(word)) {
            return;
        }
        char[] chars = word.toCharArray();
        TrieNode currPos = this.root;
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 'a';
            TrieNode tmp = currPos.children[index];
            if (currPos.children[index].getCount() == 1) {
                currPos.children[index] = null;
            } else {
                currPos.children[index].decreaseCount();
            }

            // if a word is deleted but the prefix still exists, delete the data and flip isEnd flag.
            if (i == chars.length - 1) {
                if (currPos.children[index] != null) {
                    currPos.children[index].data = "";
                    currPos.children[index].setEnd(false);
                }
            }
            currPos = tmp;
        }

    }
}

5.字典树的应用

海量数据情况下,trie树的应用

适用范围:数据量大,重复多,但是数据种类小可以放入内存

基本原理及要点:实现方式,节点孩子的表示方式

1、一个文本文件,大约有一万行,每行一个词,要求统计出其中最频繁出现的前10个词,请给出思想,给出时间复杂度分析.

答:先用trie树统计每个词出现的次数,时间复杂度是O(n*le)(le表示单词的平均长度);

然后是用小顶堆找出出现最频繁的前10个词,时间复杂度是O(n*lg10)。

2、寻找热门查询

原题:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录,这些查询串的重复读比较高,虽然总数是1千万,但是如果去除重复和,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就越热门。请你统计最热门的10个查询串,要求使用的内存不能超过1G。

答:利用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小顶堆来对出现频率进行排序。

 

3.1000万字符串,其中有些是相同的(重复),需要把重复的全部去掉,保留没有重复的字符串。

答:使用hash_map或者trie树。

      比如trie树,在构建trie树的过程中,如果某个字符串已经存在于trie中则不输出,否则输出到文本中,这样就可以得到不重复的字符串。

hash_map的速度会要快一些,因为在添加一个字符串的时候,hashmap直接用哈希函数就能定位,然后选择是否写入文件,但是trie树需要在子节点中比较。

trie树对hashmap的优势是,在大量重复的单词中,trie树需要的内存会低一些。

参考:

[1] Trie树详解及其应用 - 作者:hackbuteer1

[2] 字典树(java实现)- 作者:XD_fybdw

[3] Trie(字典树)的Java实现 - 作者:耀凯考前突击大师

2019-01-31 21:47:06 qq_41900081 阅读数 85
  • Oracle数据

    本课程主要讲解如下内容:Oracle体系结构、Oracle 基础管理、SQL 语言、Sequence和同义词、数据字典及用户管理、E-R模型、Power Designer设计工具。在本课程讲解之中会提供有相应的练习习题以及综合案例分析,帮助读者迅速掌握Oracle数据库的核心开发技能。官方QQ群:612148723。

    61531 人正在学习 去看看 李兴华

理解Trie:

Trie又称单词查找树,是一种树形结构,是哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。
优点:非常适合操作字符串,利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。
缺点:虽然不同单词共享前缀,但其实trie是一个以空间换时间的算法,每个结点只存储一个字符浪费了

Trie树的一些特性:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符,每个结点拥有26个子结点j
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同
  4. 如果字符的种数为n,则每个结点的出度为n,这也是空间换时间的体现,浪费了很多的空间
  5. 插入查找的复杂度为O(n),n为字符串长度。

Java版本1实现:

package trie;

public class Trie {
	private class Node{
		boolean isWord;
		Node[] next = new Node[26];
		
		public Node(boolean isWord) {
			this.isWord = isWord;
		}
		
		public Node() {
			this(false);
		}
	}
	
	private Node root;
	private int size;
	
	public Trie() {
		root = new Node();
	}
	
	//获·得Trie中存储的单词数量
	public int getSize() {
		return size;
	}
	
	//向Trie中添加一个单词word
	public void add(String word){
		 Node cur = root;
			for(char c : word.toCharArray()) {
				if(cur.next[c - 'a'] == null)
					cur.next[c - 'a'] = new Node();
				cur = cur.next[c - 'a'];
			}
			
			if(!cur.isWord) {
				cur.isWord = true;
			}
	}
	
	//搜索Trie中是否包含单词word
	public boolean contains(String word) {
		
		if(word.equals(""))
			return false;
		
		Node cur = root;
		for(int i = 0 ; i < word.length() ; i ++) {
			char c = word.charAt(i);
			if(cur.next[c - 'a'] == null) 
				return false;
			cur = cur.next[c -'a'];
		}
		
		return cur.isWord;
	}
	
	//搜索Trie中是否包含前缀prefix的单词
	public boolean isPrefix(String prefix) {
		
		if(prefix.equals(""))
			return false;
		
		Node cur = root;
		for(int i = 0 ; i < prefix.length() ; i ++) {
			char c = prefix.charAt(i);
			if(cur.next[c -'a'] == null) 
				return false;
			cur = cur.next[c - 'a'];
		}
		
		return true;
	}
	
	public static void main(String[] args) {
		Trie trie = new Trie();

		trie.add("apple");
		System.out.println(trie.contains("apple"));   // 返回 true
		System.out.println(trie.contains("app") );   // 返回 false
		System.out.println(trie.isPrefix("app")); // 返回 true
		trie.add("app");   
		System.out.println(trie.contains("app"));     // 返回 true
	}
}

Java版本2实现:

package tree;

import java.util.TreeMap;

public class Trie {
	private class Node{
		boolean isWord;
		TreeMap<Character,Node> next;
		
		public Node(boolean isWord) {
			this.isWord = isWord;
			next = new TreeMap<Character,Node>();
		}
		
		public Node() {
			this(false);
		}
	}
	
	private Node root;
	private int size;
	
	public Trie() {
		root = new Node();
	}
	
	//获·得Trie中存储的单词数量
	public int getSize() {
		return size;
	}
	
	//向Tire中添加一个单词word
	public void add(String word){
		
		Node cur = root;
		for(int i = 0 ; i < word.length() ; i ++) {
			char c = word.charAt(i);
			if(cur.next.get(c) == null) 
				cur.next.put(c, new Node());
			cur = cur.next.get(c);
		}
		
		if(!cur.isWord) {
			cur.isWord = true;
			size++;
		}
	}
	
	//搜索Trie中是否包含单词word
	public boolean contains(String word) {
		
		Node cur = root;
		for(int i = 0 ; i < word.length() ; i ++) {
			char c = word.charAt(i);
			if(cur.next.get(c) == null) 
				return false;
			cur = cur.next.get(c);
		}
		
		return cur.isWord;
	}
	
	//搜索Trie中是否包含前缀prefix的单词
	public boolean isPrefix(String prefix) {
		
		if(prefix.equals(""))
			return false;
		
		Node cur = root;
		for(int i = 0 ; i < prefix.length() ; i ++) {
			char c = prefix.charAt(i);
			if(cur.next.get(c) == null) 
				return false;
			cur = cur.next.get(c);
		}
		
		return true;
	}
	
	public static void main(String[] args) {
		Trie trie = new Trie();

		trie.add("apple");
		System.out.println(trie.contains("apple"));   // 返回 true
		System.out.println(trie.contains("app") );   // 返回 false
		System.out.println(trie.isPrefix("app")); // 返回 true
		trie.add("app");   
		System.out.println(trie.contains("app"));     // 返回 true
	}
}
2016-08-09 23:08:09 a987073381 阅读数 5606
  • Oracle数据

    本课程主要讲解如下内容:Oracle体系结构、Oracle 基础管理、SQL 语言、Sequence和同义词、数据字典及用户管理、E-R模型、Power Designer设计工具。在本课程讲解之中会提供有相应的练习习题以及综合案例分析,帮助读者迅速掌握Oracle数据库的核心开发技能。官方QQ群:612148723。

    61531 人正在学习 去看看 李兴华

昨天面试电话中的一道题,题目如下:

1、给你一个姓名的集合,查找你的名字是否在里面出现。

我的回答是用set,把集合中所有的姓名放到set集合中,直接用find查找我的姓名在这个集合里面是否出现。

2、追问,如果要搜索姓氏为叶的人,输入关键字叶,那么会出现所有姓为叶的人,应该如何设计?

当时的回答是,姓为key,名为value,存放到multimap中,使用multimap中的count函数统计key为叶的个数,然后用find函数找到第一个key为叶的指针,使用迭代器从该指针向后查找count个元素,判断这count个元素中是否有姓名为叶x的人。后来想想我的方法其实可以优化的,网上的思路基本上都是采用字典树,但仅针对英文单词。如果把字典树和我的在面试时候的方法结合起来就非常棒了(可惜当时没想到>_<)。

什么是字典树?
Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。
对于每个单词,如果直接去查找别的单词是否包括它,那么时间复杂度就是O(n^2),如果采用查找公共前缀,例如对于abcd,只用查找以a为前缀的节点假设为x,对于bcd,只用查找x节点中以b为前缀的节点,依次类推。
下面给出一种常见的英文字典树结构体设计:
#define MAX_CHILD 26
struct trie_node
{
    trie_node()
    {
        count = 0;

        for (int i = 0; i < MAX_CHILD; i++)
        {
            child[i] = NULL;
        }
    }
    int count;//表示以该节点结束的单词的个数
    trie_node *child[MAX_CHILD];//存放孩子节点指针的数组 
};
对于每个节点都有指向26个英文字母的指针,如果字符串到某个节点(叶子节点)结束了,那么把该节点的count加一,代表从根节点到当前节点路径上出现的字母所组成的字符串出现过一次。如果不存在以该字符串为前缀的字符串,那么该叶子节点上的26个指针均为NULL。比如有字符串ae、b、 b、 bac、c、ca、ceh、ceb、cebg、cebg、f、fi。组成的字典树如下图:

然而,存储中文的时候问题就来了,常见的中文汉字有5W个,如果按照上面的来设计,那么每个节点都要存放5W个节点的指针数组,这样会浪费很多空间,因为对于每个几点的5W个指针只用到了极少部分(其他都为NULL)。
我的设计思路:对于每个节点都有map(或hash_map),键值为前缀汉字(单个),实值为指向后续汉字节点的指针。和英文字典树一样,从根节点到当前节点所经过的汉字连接起来成为某个字符串。对于出现过的字符串,该字符串最后一个汉字所在节点的count加一。时间复杂度O((logn)^2)
例如中文字符串:数字、数据、数据集、数据库、数理化、测试、计量、记事本、计算机、计算器。那中文字典树如下:

使用map还是hash_map?
看情况而定,如果出现姓名特别多,而且普遍比较短(比如中文名一般是两三个汉字),用hash_map,这样整个树基本只要2~3层就能搞定,如果姓名很长,还是用map吧,毕竟每个汉字出现频率低,使用hash_map会浪费太多空间,得不偿失。

代码如下:
#include <string>  
#include <map>  
#include <vector>  
#include <iostream>
#define CH_SIZE 3//汉字大小linux为3,win为2
using namespace std;  
  
struct trie_node  
{  
    trie_node()  
    {  
        count = 0;  
    }  
    int count;//表示以该汉字结束的字符串个数  
    map<string, trie_node *> child;//键值为当前汉字,实值为后面汉字节点的指针  
};  
  
class trie  
{  
public:  
    trie();  
    ~trie();  
    void insert_str(string str);//插入字符串  
    trie_node *search_str(string str);//查询字符串  
    trie_node *search_str_pre(string str_pre);//查询字符串前缀  
    void delete_str(string str);//删除字符串  
    vector<string> get_str_pre(string str);//返回所有前缀为str的字符串  
    void clear();//清空  
private:  
    void add_str(trie_node *root, string pre_str, vector<string> &ret);    //递归添加以pre_str为前缀的字符串到ret集合  
private:  
    struct trie_node *root;  
};  
  
trie::trie()  
{  
    root = new trie_node();  
}  
  
trie::~trie()  
{  
}  
  
//插入字符串  
void trie::insert_str(string str)  
{  
     if (root == NULL || str == "")  
     {  
         return ;  
     }  
     trie_node *cur_node = root;  
  
     for (int i = 0; i < str.size();)  
     {  
         string sub_str = str.substr(i, CH_SIZE);  
         map<string, trie_node *>::iterator iter = cur_node->child.find(sub_str);  
  
         if (iter == cur_node->child.end())//如果在map中没有找到则插入新节点  
         {  
            trie_node *tmp_node = new trie_node();  
            cur_node->child.insert(pair<string, trie_node *>(sub_str, tmp_node));  
            cur_node = tmp_node;  
         }  
         else//如果找到了value即为指向下一个节点的指针  
         {  
             cur_node = iter->second;  
         }  
         i = i + CH_SIZE ;  
     }  
  
     cur_node->count++;  
}  
  
//删除字符串  
void trie::delete_str(string str)  
{  
    trie_node *find_node = search_str(str);  
  
    if (find_node)  
    {  
        find_node->count--;  
    }  
}  
  
//查询字符串前缀  
trie_node * trie::search_str_pre(string str)  
{  
    if (str == "")  
    {  
        return root;  
    }  
    if (NULL == root )  
    {  
        return NULL;  
    }  
  
    trie_node *cur_node = root;  
  
    int i;  
    for ( i = 0; i < str.size(); )  
    {  
        string sub_str = str.substr(i, CH_SIZE);  
        map<string, trie_node *>::iterator iter = cur_node->child.find(sub_str);  
  
        if (iter == cur_node->child.end())  
        {  
            return NULL;  
        }  
        else  
        {  
             cur_node = iter->second;  
        }  
        i = i + CH_SIZE;  
    }  
  
    if (i == str.size())  
    {  
        return cur_node;  
    }  
    else  
    {  
        return NULL;  
    }  
}  
  
//查询字符串  
trie_node * trie::search_str(string str)  
{  
    trie_node * find_pre_node = search_str_pre(str);  
  
    if (find_pre_node != NULL)  
    {  
        if (find_pre_node->count == 0)  
        {  
            return NULL;  
        }  
        else  
        {  
             return find_pre_node;  
        }  
    }  
}  
  
//清空  
void trie::clear()  
{  
    vector<trie_node *> que;  
    que.push_back(root);  
  
    while (!que.empty())  
    {  
        for (map<string, trie_node *>::iterator iter = root->child.begin(); iter != root->child.end(); iter++)  
        {  
            que.push_back(iter->second);  
        }  
  
        trie_node *del_node = que.front();  
        que.pop_back();

        delete del_node;  
    }  
}  
  
//递归添加以pre_str为前缀的字符串到ret集合  
void trie::add_str(trie_node *root, string pre_str, vector<string> &ret)  
{  
  
    for (map<string, trie_node *>::iterator iter = root->child.begin(); iter != root->child.end(); iter++)  
    {  
         add_str(iter->second, pre_str + iter->first, ret);  
    }  
  
    if (root->count != 0)  
    {  
         ret.push_back(pre_str);  
    }  
}  
  
//返回所有前缀为str的字符串  
vector<string> trie::get_str_pre(string str)  
{  
    vector<string> ret;  
    trie_node *find_node = search_str_pre(str);  
  
    if (find_node != NULL)  
    {  
        add_str(find_node, str, ret);  
    }  
  
    return ret;  
} 
int main()
{
        trie t;
        int n;
        string str;
        vector<string> ret;

        cout << "please input the num of the dictionary:" << endl;
        cin >> n;

        for (int i = 0; i < n; i++)
        {
                cin >> str;
                t.insert_str(str);
        }

        cout << "please input the key word:" << endl;
        cin >> str;

        ret = t.get_str_pre(str);

        for (vector<string>::iterator iter = ret.begin(); iter != ret.end(); iter++)
        {
                cout << *iter << endl;
        }

        return 0;
}



参考:



2019-05-04 20:52:51 qq_42372935 阅读数 70
  • Oracle数据

    本课程主要讲解如下内容:Oracle体系结构、Oracle 基础管理、SQL 语言、Sequence和同义词、数据字典及用户管理、E-R模型、Power Designer设计工具。在本课程讲解之中会提供有相应的练习习题以及综合案例分析,帮助读者迅速掌握Oracle数据库的核心开发技能。官方QQ群:612148723。

    61531 人正在学习 去看看 李兴华

字典树是多叉树,通常用于处理字符串,如存储单词等

字典树的实现

1. 基本类的实现

public class Trie {
	private class Node{
		//指向子结点
		public TreeMap<Character,Node> next;  
		public boolean isWord;
		
		public Node(boolean isWord) {
			this.isWord = isWord;
			next= new TreeMap<>();
		}
		
		public Node() {
			this(false);
		}
	}
	
	private Node root;  //Trie树的根结点
	private int size;   //树中结点个数
	
	public Trie() {
		root = new Node();
		size = 0;
	}
	
	public int getSize() {
		return size;
	}
}

2. 向字典树中添加单词

//向字典树中添加单词
	public void add(String str) {
		Node current = root;
		
		//依次添加str的每一个字母
		for(int i = 0; i < str.length(); ++i) {
			char ch = str.charAt(i);
			
			//映射中不包含键值为ch的条目,则将键值为ch的条目插入其中
			if(current.next.get(ch) == null) {
				current.next.put(ch,new Node());
			}
			//将current指向当前结点的满足条件(键值为ch)的孩子结点
			current = current.next.get(ch);
		}
		
		/*
		 * 更新size大小时需要考虑到前缀问题
		 * 1. 当遍历完传入的单词str时,可能并为到达树中一个单词的结尾
		 * 	  如 str = "pan",Trie中存的是 "panda"
		 * 2. 如果current执行的结点的isWord为false,说明树中还没有存入
		 *   pan这个单词,此时应将n结点的isWord更改为true,并更新size
		 * 3. size指的是树中单词的个数(前缀单词也是单词:pan 和 panda是两个单词)
		 */
		if(!current.isWord) {
			current.isWord = true;
			size++;
		}
	}

3. 查询某一单词是否在字典树中

    /*		
	 * 判断某一单词是否在字典树中
	 * 方法:1. 依次获取单词的每一个字母,作为键值去映射中查找是否有
	 *	          与之对应的条目,若有则进行下一个字母的比对,没有则返回false
	 *	          直至最后一个字母。
	 *		2. 若对单词str遍历完成未发现不匹配的条目,则对current结点的
	 *		  isWord进行判断,若其值为true,说明这是一个前缀单词,且已经
	 *		  存入到当前字典树中,返回true,反之返回false。
	 */
	public boolean contains(String str) {
		Node current = root;
		
		for(int i = 0; i < str.length(); ++i) {
			char ch = str.charAt(i);
			
			if(current.next.get(ch) == null)
				return false;
			current = current.next.get(ch);
		}
		
		return current.isWord;
	}

4. 判断某一字符串是否为字典树中单词的前缀

    /*
	 * 		判断某一字符串时候是单词的前缀(不要求prefix是单词)
	 * 方法(大致思路和contains一致):
	 * 	1.  依次获取字符串prefix的每一个字母,作为键值去映射中查找是否有
	 * 	     与之对应的条目,若有则进行下一个字母的比对,没有则返回false
	 * 	     直至最后一个字母。
	 *  2. 如果循环比对之后为发现不匹配的条目,说明prefix是一个前缀,返回true
	 */
	public boolean isPrefix(String prefix) {
		Node current = root;
		for(int i = 0; i < prefix.length(); ++i) {
			char ch = prefix.charAt(i);
			if(current.next.get(ch) == null)
				return false;
			current = current.next.get(ch);
		}
		return true;
	}
2018-01-17 22:27:32 u012428012 阅读数 1330
  • Oracle数据

    本课程主要讲解如下内容:Oracle体系结构、Oracle 基础管理、SQL 语言、Sequence和同义词、数据字典及用户管理、E-R模型、Power Designer设计工具。在本课程讲解之中会提供有相应的练习习题以及综合案例分析,帮助读者迅速掌握Oracle数据库的核心开发技能。官方QQ群:612148723。

    61531 人正在学习 去看看 李兴华

数据结构 - 哈夫曼树 - 哈希树 - 字典树 - 面试中可能会涉及的树知识点

数据结构是面试中必定考查的知识点,面试者需要掌握几种经典的数据结构:线性表(数组、链表)、栈与队列(二叉树、二叉查找树、平衡二叉树、红黑树)、

本文主要介绍中的一些种类。包括

  • 哈夫曼树
  • 字典树

哈夫曼树

哈夫曼树是一种带权路径长度最短二叉树,也称为最优二叉树。下面用一幅图来说明。

哈夫曼树

它们的带权路径长度分别为:
图a: WPL=5*2+7*2+2*2+13*2=54
图b: WPL=5*3+2*3+7*2+13*1=48
可见,图b的带权路径长度较小,我们可以证明图b就是哈夫曼树(也称为最优二叉树)。

一、如何构建哈夫曼树?

一般可以按下面步骤构建:

  1. 将所有左,右子树都为空的作为根节点。
  2. 在森林中选出两棵根节点的权值最小的树作为一棵新树的左,右子树,且置新树的附加根节点的权值为其左,右子树上根节点的权值之和。注意,左子树的权值应小于右子树的权值。
  3. 从森林中删除这两棵树,同时把新树加入到森林中。
  4. 重复2,3步骤,直到森林中只有一棵树为止,此树便是哈夫曼树。

下面是构建哈夫曼树的图解过程:

哈夫曼树构建过程

二、哈夫曼编码

利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径,对路径上的各分支约定指向左子树的分支表示”0”码,指向右子树的分支表示“1”码,取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码,即是哈夫曼编码

就拿上图例子来说:
A,B,C,D对应的哈夫曼编码分别为:111,10,110,0

用图说明如下:

哈夫曼编码

记住,设计电文总长最短的二进制前缀编码,就是以n个字符出现的频率作为权构造一棵哈夫曼树,由哈夫曼树求得的编码就是哈夫曼编码。


字典树:Trie树

Trie树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。字典树(Trie)可以保存一些 字符串 -> 值 的对应关系。基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。

Trie 的强大之处就在于它的时间复杂度。它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关。Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题;Trie 的缺点是空间消耗很高

典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。

Trie树的基本性质可以归纳为:
(1)根节点不包含字符,除根节点意外每个节点只包含一个字符。
(2)从根节点到某一个节点,路径上经过的字符连接起来,为该节点对应的字符串。
(3)每个节点的所有子节点包含的字符串不相同。
(4)如果字符的种数为n,则每个结点的出度为n,这也是空间换时间的体现,浪费了很多的空间。
(5)插入查找的复杂度为O(n),n为字符串长度。

基本思想(以字母树为例):
1、插入过程
对于一个单词,从根开始,沿着单词的各个字母所对应的树中的节点分支向下走,直到单词遍历完,将最后的节点标记为红色,表示该单词已插入Trie树。
2、查询过程
同样的,从根开始按照单词的字母顺序向下遍历trie树,一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色,则表示该单词不存在,若最后的节点标记为红色,表示该单词存在。

字典树的数据结构

一般可以按下面步骤构建:

利用串构建一个字典树,这个字典树保存了串的公共前缀信息,因此可以降低查询操作的复杂度。

下面以英文单词构建的字典树为例,这棵Trie树中每个结点包括26个孩子结点,因为总共有26个英文字母(假设单词都是小写字母组成)。

则可声明包含Trie树的结点信息的结构体:

typedef struct Trie_node
{
    int count;                    // 统计单词前缀出现的次数
    struct Trie_node* next[26];   // 指向各个子树的指针
    bool exist;                   // 标记该结点处是否构成单词  
}TrieNode , *Trie;

其中next是一个指针数组,存放着指向各个孩子结点的指针。

如给出字符串”abc”,”ab”,”bd”,”dda”,根据该字符串序列构建一棵Trie树。则构建的树如下:

trie树

[数据结构] 字典树

阅读数 421

没有更多推荐了,返回首页