精华内容
下载资源
问答
  • Trie树词频统计实例

    千次阅读 2015-07-26 00:00:07
    Trie树词频统计实例

    Trie树简介

    Trie树,也叫前缀字典树,是一种较常用的数据结构。常用于词频统计,
    字符串的快速查找,最长前缀匹配等问题以及相关变种问题。

    数据结构表现形式如下图所示:
    这里写图片描述

    Trie树的根为空节点,不存放数据。每个节点包含了一个指针数组,数组大小通常为26,即保存26个英文字母(如果要区分大小则数组大小为52,如果要包括数字,则要加上0-9,数组大小为62)。
    可以想象它是一棵分支很庞大的树,会占用不少内存空间;不过它的树高不会唱过最长的字符串长度,所以查找十分快捷。典型的用空间换取时间。

    全英圣经词频统计

    全英圣经TXT文件大小有4m,若要对它进行词频统计等相关操作,可以有许多方法解决。
    我觉得可以用如下方式:

    1. pthon字典数据结构解决
    2. 在linux下利用sed & awk 文本处理程序解决
    3. C++ STL map解决
    4. Trie树解决

    前三种实现比较简单快捷,不过通过自己封装Trie树可以练习一下数据结构!感受一下数据结构带来的效率提升,何乐而不为。

    下面则是我的具体实现,如有纰漏,敬请指正!

    1)自定义头文件

    WordHash用来记录不重复的单词及其出现次数
    TrieTree类封装得不太好,偷懒把很多属性如行数,单词总数等都放在public域

    #ifndef _WORD_COUNT_H
    #define _WORD_COUNT_H
    
    #include<stdio.h>
    #include<string.h>
    #include<string>
    #include<fstream>
    #include<sstream>
    #include<vector>
    #include<iterator>
    #include<algorithm>
    #include<iostream>
    
    using std::string;
    using std::vector;
    
    typedef struct tag {
        char word[50];  //单个单nt show_times; //出现次数
        int show_times; //出现次数
    }WordHash;
    
    const int child_num = 26;
    
    //字典树节点
    typedef struct Trie {
        int count;
        struct Trie *next_char[child_num];
        bool is_word;
    
        //节点构造函数
        Trie(): is_word(false) {
            memset(next_char,NULL,sizeof(next_char));
        }
    }TrieNode;
    
    class TrieTree {
     public:
        TrieTree();
        void insert(const char *word);
        bool search(const char *word);
        void deleteTrieTree(TrieNode *root);
        inline void setZero_wordindex(){ word_index = 0; }
    
        int word_index;
        WordHash *words_count_table; //词频统计表
        int lines_count;
        int all_words_count; //单词总数
        int distinct_words_count;  //不重复单词数
    
     private:
        TrieNode *root; //字典树根节点
    };
    
    //文本词频统计类
    class WordStatics {
     public:
        void open_file(string filename);
        void write_file();
    
        void set_open_filename(string input_path);
        string& get_open_filename();
    
        void getResult();
        void getTopX(int x);
    
     private:
        vector<string> words;  //保存文本中所有单词
        TrieTree dictionary_tree; //字典树
    
        vector<WordHash> result_table; //结果词频表
        string open_filename; //将要处理的文本路径
        string write_filename; //词频统计结果文件
    };
    
    
    
    #endif
    

    具体类成员函数cpp文件
    1)字典树构造函数

    #include<iostream>
    #include "word_count.h"
    
    using namespace std;
    
    
    //字典树构造函数
    TrieTree::TrieTree() {
        root = new TrieNode();
        //词频统计表,记录单词和出现次数
        word_index = 0;
        lines_count = 0;
        all_words_count = 0;
        distinct_words_count = 0;
        words_count_table = new WordHash[30000];
    }

    2)读取文本中的单词,逐个插入到字典树中,创建字典树。
    (仅实现了能够处理全为小写字母的文本,本人先将圣经文件做了一些简单处理)

    //建立字典树,将单词插入字典树
    void TrieTree::insert(const char *word) {
        TrieNode *location = root; //遍历字典树的指针
    
        const char *pword = word;
    
        //插入单词
        while( *word ) {
            if ( location->next_char[ *word - 'a' ] == NULL ) {
                TrieNode *temp = new TrieNode();
                location->next_char[ *word - 'a' ] = temp;
            }    
    
            location = location->next_char[ *word - 'a' ];
            word++;
        }
        location->count++;
        location->is_word = true; //到达单词末尾
        if ( location->count ==1 ) {
            strcpy(this->words_count_table[word_index++].word,pword);
            distinct_words_count++;
        }
    }

    3)按单词查找字典树,获取其出现次数

    //查找字典树中的某个单词
    bool TrieTree::search(const char *word) {
        TrieNode *location = root;
    
        //将要查找的单词没到末尾字母,且字典树遍历指针非空
        while ( *word && location ) {
            location = location->next_char[ *word - 'a' ];
            word++;
        }
    
        this->words_count_table[word_index++].show_times = location->count;
        //在字典树中找到单词,并将其词频记录到词频统计表中
        return (location != NULL && location->is_word);
    }

    4)删除字典树

    //删除字典树,递归法删除每个节点
    void TrieTree::deleteTrieTree(TrieNode *root) {
        int i;
        for( i=0;i<child_num;i++ ) {
            if ( root->next_char[i] != NULL ) {
                deleteTrieTree(root->next_char[i]);
            }
        }
        delete root;
    }

    5)WordStatics类相关成员函数定义

    void WordStatics::set_open_filename(string input_path) {
        this->open_filename = input_path;
    }
    
    string& WordStatics::get_open_filename() {
        return this->open_filename;
    }
    
    void WordStatics::open_file(string filename) {
        set_open_filename(filename);
        cout<<"文件词频统计中...请稍后"<<endl;
    
        fstream fout;
        fout.open(get_open_filename().c_str());  
    
        const char *pstr;
        while (!fout.eof() ) { //将文件单词读取到vector中
            string line,word;
            getline(fout,line);
            dictionary_tree.lines_count++;
    
            istringstream is(line);  
            while ( is >> word ) {
                pstr = word.c_str();
                dictionary_tree.all_words_count++;
                words.push_back(word);
            }
        } 
    
        //建立字典树
        vector<string>::iterator it;
        for ( it=words.begin();it != words.end();it++ ) {
            if ( isalpha(it[0][0]) ) { 
               dictionary_tree.insert( (*it).c_str() );
            }
        }
    
    }
    void WordStatics::getResult() {
        cout<<"文本总行数:"<<dictionary_tree.lines_count<<endl;
        cout<<"所有单词的总数 : "<<dictionary_tree.all_words_count-1<<endl;
        cout<<"不重复单词的总数 : "<<dictionary_tree.distinct_words_count<<endl;
    
        //在树中查询不重复单词的出现次数
        dictionary_tree.setZero_wordindex();
        for(int i=0;i<dictionary_tree.distinct_words_count;i++) {
            dictionary_tree.search(dictionary_tree.words_count_table[i].word);
            result_table.push_back(dictionary_tree.words_count_table[i]);
        }
    }

    6)对统计结果进行排序,依照用户输入输出前N词频的单词

    bool compare(const WordHash& lhs,const WordHash& rhs) {
        return lhs.show_times > rhs.show_times ;
    }
    
    void WordStatics::getTopX(int x) {
        sort(result_table.begin(),result_table.end(),compare);
        cout<<"文本中出现频率最高的前5个单词:"<<endl;
        for( int i = 0; i<x; i++) {
            cout<<result_table[i].word<<": "<<result_table[i].show_times<<endl;
        }
    }

    运行结果:

    这里写图片描述

    仅供参考,记录自己的学习历程。
    还有许多地方不太合理,需要改进,慢慢提升自己的编程能力!

    展开全文
  • 一个简单的C语言程序:用Trie树实现词频统计和单词查询
  • Trie树统计词频

    2015-06-10 02:00:37
    Trie树是一种数据结构,对于词频统计,文本检索非常有效。 Trie树的大小取决与要统计的文本的字母个数。比如只统计26个英文字母的话,单词最大长度为10的话,占用的空间最多是26^10。但实际上并没有这...
        

    Abstract

    介绍Trie树的性质和构造方法。
    最终用来统计一片文章各个单词出现的频率。

    最终结果:
    最终结果

    Trie

    Trie树是一种数据结构,对于词频统计,文本检索非常有效。
    Trie树的大小取决与要统计的文本的字母个数。比如只统计26个英文字母的话,单词最大长度为10的话,占用的空间最多是26^10。但实际上并没有这么恐怖。因为没有abc这样的单词。

    在Trie中,将没一个字母作为一个node,其中含有几个信息

    c#define R 26
    typedef struct node
    {
        int value;// ASCII码
        int frequecy;//c出现的频率
        struct node* child[R];//有R个孩子,初始为NULL
    
    }Node;
    

    下面用hello这个单词举例子。
    第一个节点是h,且h有一个孩子l。往后类似。到了最后的o,此时才是一个真正的单词,所以o的frequecy为1.
    图片描述
    建立Trie树的时候,每次都是从Root出发,当再次遇到单词hello时,还是顺着这条路走下来,到o的时候将frequecy=2。
    如果碰到的单词是helloworld,则插入后的结果为
    图片描述
    可以看到,frequency>0的节点,说明从root到这个节点的路径上的所有字母节点构成了一个单词,且单词出现的频率就是frequecy。

    所以,树的高度与文本中的单词的最大长度有关,但实际上最长的单词也没几个字母……尤其是当不同的单词具有相同前缀的时候,前缀的路径是共用的。利用这个性质,Trie在前缀搜索上变现也不错。

    当拿到一个文本文档时,我们可以通过一遍扫描将trie建立,通过遍历trie得到所有词出现的频率。

    示例代码地址trie

    展开全文
  • Trie树实现词频统计与查找

    千次阅读 2017-01-15 14:56:55
    #encoding:utf-8 from collections import defaultdict import sys reload(sys) sys.setdefaultencoding('utf8') class LBTrie: ... simple implemention of Trie in Python. """ def __ini
    #encoding:utf-8
    from collections import defaultdict
    import sys
    reload(sys) 
    sys.setdefaultencoding('utf8') 
    class LBTrie:  
        """ 
        simple implemention of Trie in Python.  
        """  
        def __init__(self):  
            self.trie = {}  
            self.size = 0  
    
        #添加单词   
        def add(self, word):  
            p = self.trie 
            dicnum = 0 
            word = word.strip()  
            for c in word:  
                if not c in p:  
                    p[c] = {}
                dicnum+=1  
                p = p[c] 
    
    
            if word != '':  
                #在单词末尾处添加键值''作为标记,即只要某个字符的字典中含有''键即为单词结尾  
                p[''] = ''   
            if dicnum == len(word):
                return True
        #查询单词        
        def search(self, word):  
            p = self.trie  
            word = word.lstrip()  
            for c in word:  
                if not c in p:  
                    return False  
                p = p[c]  
            #判断单词结束标记''  
            if '' in p:  
                return True  
            return False            
    
        #打印Trie树的接口  
        def output(self):  
            #print '{'  
            self.__print_item(self.trie)      
            #print '}'  
            return  self.__print_item(self.trie)
    
        #实现Trie树打印的私有递归函数,indent控制缩进  
        def __print_item(self, p, indent=0):       
            if p:  
                ind = '' + '\t' * indent  
                for key in p.keys():  
                    label = "'%s' : " % key  
                    print ind + label + '{'  
                    self.__print_item(p[key], indent+1)
    
                print ind + ' '*len(label) + '}'    
    
    def codeutil(strs):
             return strs.decode('utf8','ignore').encode('GBK','ignore').decode('GBK','ignore')
    
    if __name__ == '__main__':  
        trie_obj = LBTrie()  
        #添加单词  
        corpus = open('content.txt','r')
        tree = open('tree.txt','w+')
        countdic = defaultdict(int)
        for record in corpus.readlines():
            recordlist = record.split(' ')
            for word in recordlist:
                check = trie_obj.add(codeutil(word))
                if check:
                    countdic[word] += 1
        resortedcountdic = sorted(countdic.items(), key=lambda item: item[1], reverse=True)
        for tup in resortedcountdic:
         tree.write(''.join(codeutil(tup[0]))+'\t'+str(tup[1])+'\t')
        #查找单词       
        if trie_obj.search(codeutil('氨基酸')):  
            print 'Yes'  
        else:  
            print 'No'   
    展开全文
  • Trie树统计词频、排序、查找

    千次阅读 2015-09-08 22:12:53
    Trie树利用字符串的公共前缀降低了查询时间的开销,提高了查询的效率。 字典树的插入,删除和查找都非常简单,用一个一重循环即可。 1. 从根节点开始一次搜索 2. 取得要查找关键词的第一个字母,并根据该字母选择...

    Trie树利用字符串的公共前缀降低了查询时间的开销,提高了查询的效率。

    字典树的插入,删除和查找都非常简单,用一个一重循环即可。

    1. 从根节点开始一次搜索

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

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

    4. 迭代过程...

    5. 在某个节点处,关键词的所有字母已被取出,则读取附在该节点上的信息,即完成查找

    package algrithm;
    
    public class dictionaryTree2 {
    
    	private int SIZE=26;
    	private TreeNode root;//字典的根
    	
    	public dictionaryTree2() {
    		// TODO Auto-generated constructor stub
    		root=new TreeNode();
    	}
    	
    	private class TreeNode
    	{
    		 private int num; //词频统计
    		 private TreeNode []son;//每一层都是由26字母开头的,即所有的节点
    		 private boolean isWord;//是不是最后一个节点
    		 private char val;//节点的值
    		
    		TreeNode()
    		{
    			num=1;
    			son=new TreeNode[SIZE];
    			isWord=false;
    		}
    	}
    	
    	public void insert(String str)
    	{
    		if(str==null||str.length()==0)
    			return ;
    		TreeNode node=root;
    		char[] letters=str.toCharArray();
    		for(int i=0,len=str.length();i<len;i++)
    		{
    			int pos=letters[i]-'a';
    			if(node.son[pos]==null)
    			{
    				node.son[pos]=new TreeNode();
    				node.son[pos].val=letters[i];
    			}
    			else
    			{
    				node.son[pos].num++;
    			}
    			node=node.son[pos];
    		}
    		node.isWord=true;
    	}
    	
    	public int countNums(String str){  //计算单词的数量
            if(str==null||str.length()==0){  
                return -1;  
            }  
            TreeNode node=root;  
            char[] letters=str.toCharArray();  
            for(int i=0,len=str.length();i< len;i++){  
                int pos=letters[i]-'a';  
                if(node.son[pos]==null){  
                    return 0;  
                }else{  
                    node=node.son[pos];  
                }  
            }  
            return node.num;  
        }  
    	
        // 在字典树中查找一个完全匹配的单词.  
        public boolean search(String str) {  
            if (str == null || str.length() == 0) {  
                return false;  
            }  
            TreeNode node = root;  
            char[] letters=str.toCharArray();  
            for (int i = 0, len = str.length(); i < len; i++) {  
                int pos = letters[i] - 'a';  
                if (node.son[pos] != null) {  
                    node = node.son[pos];  
                } else {  
                    return false;  
                }  
            }  
            return node.isWord;  
        }  
       
        public TreeNode getRoot(){  
            return this.root;  
        }  
        
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    
    		dictionaryTree2 tree = new dictionaryTree2();  
    	        String[] strs={"beer","banana", "band","bee", "you","young","that"};
    	        for(String str : strs){  
    	            tree.insert(str);
    	        }
    	        System.out.println(tree.search("bee"));
    	        System.out.println(tree.countNums("ba"));
    	      
    	}
    
    }
    

    输出结果:

    true
    2

    展开全文
  • Trie树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共...
  • //trie.h #ifndef __TRIE_H__ #define __TRIE_H__ #include #include #include #include #include namespace alg { const int NUMWORD = 26; class Trie { private: class node { public: in
  • 文章目录一、单词介绍二、实现思路2.1 词频统计和单词查找2.2 敏感词屏蔽三、代码实现 前几天都看一个敏感词屏蔽算法的文章,写的挺好,顺着思路写了下去,实现了一下,算法效率还是杠杠的。。。 一、单词介绍 ...
  •  如果我们有and,as,at,cn,com这些关键词,那么trie树(zidianshu)? 从上面的图中,我们或多或少的可以发现一些好玩的特性。  第一:根节点不包含字符,除根节点外的每一个子节点都包含一个字符。 ...
  • 字典树(trie树)实现词频查找

    千次阅读 2018-01-30 12:16:20
    其中一个就是利用树来进行词频统计,我们主要希望的是查询效率高,对于树来说查询效率和插入都比较快,时间复杂度都能做到较好。  我们来看一段来自百度百科对trie树的解释:  字典树又称单词查找树,Trie...
  • trie树统计字符串

    2020-10-11 11:37:55
    Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大...
  • 字典实现词频统计

    2020-08-24 16:01:25
    Trie树(字典树) 字典树又叫前缀树,是处理字符串常用的数据结构,最近和朋友一起粗略写了一下关于字典树的词频统计。 一、功能介绍 文件流读写单词; 将读到的单词插入树中; 打印树,打印出单词和个数以及词频;...
  • Trie树Trie树,又称字典树,单词查找树或者前缀树,是一种用于快速检索的多叉树结构。应用经常被搜索引擎系统用于文本词频统计。同时,它也是很多算法和复杂数据结构的基础,如后缀树,AC自动机等优点最大限度地减少...
  • Trie树:应用于统计和排序

    千次阅读 2017-03-27 11:08:42
    1. 什么是trie树,转自http://blog.csdn.net/hguisu/article/details/8131559  1.Trie树 (特例结构树) ...典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频
  • 它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,能在常数时间O(len)内实现插入和查询操作,是一种以空间换取时间的数据结构,广泛用于词频统计和输入统计领域。 来看看Trie树长...
  • Trie树

    2020-01-21 21:36:35
    前言 明天期末考试了,中午今天就不做题了,复习一下Trie树吧。 Trie树 普通Tire树 ...典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。 ...
  • 剑指Offer——Trie树(字典树)

    万次阅读 多人点赞 2016-09-07 21:21:30
    剑指Offer——Trie树(字典树)Trie树 Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 850
精华内容 340
关键字:

trie树词频统计