精华内容
下载资源
问答
  • 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树)实现词频查找

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

         碎碎念:

     在大学数据结构中,有关于树的应用部分。其中一个就是利用树来进行词频的统计,我们主要希望的是查询效率高,对于树来说查询效率和插入都比较快,时间复杂度都能做到较好。
     我们来看一段来自百度百科对trie树的解释:

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

         我们来对比几种树:

          AVL树:  最早的平衡二叉树之一。应用相对其他数据结构比较少。windows对进程地址空间的管理用到了AVL树。
         红黑树: 平衡二叉树,广泛用在C++的STL中。如map和set都是用红黑树实现的。
          B/B+树: 用在磁盘文件组织 数据索引和数据库索引。
          Trie树(字典树): 用在统计和排序大量字符串,如自动机。

    现在我们来讨论讨论Trie树的构建吧!
         
          我使用的环境是Visual Studio 2015 、使用c语言
          (c语言的指针真的是要控制好,不然出现很多野指针或者其他的就会被气疯)
     
    废话不说了,开始吧!

      算法描述:
      
    1. 整体数据结构的关系图(程序中还有栈结构,在这里不是主要的,不展示)

    (注:字典树中的结点结构)

    如上图,我们利用单词前缀重复多的特点,建立这样一棵树,由于我们是以树的形式对词频进行存储,我们会发现查找效率会变高,而且占用的空间会明显减少。又由于我们分析的小说文章中包含的词都是反复出现的,所以结点数会较少。如果我们查找(‘zzzz...十个z字母的单词’),我们发现最多会查找260次就能查到,但是用其他的方法(emmm你们可以验证一下)

    (注:树结构示例)


    (树结点信息结构体 记录树的信息)


     上边就是对树结构的描述,以及语言上的实现。

            2.关键算法流程图


    (主要方法一:分析文件)



    程序的大致流程


    (主要方法二:将单词传入树)


    (主要方法二:将单词传入树)


    (注:主函数逻辑)

    整体描述:

    我们采用链、树、以及堆栈来完成题目要求,采用的树在理论上深度是可以无限加深的,所以单词长度是无限的。

    在操作上,先获取文件,用户输入文件路径,打开文件。

    输入成功,打开文本进行分析,分析完毕进行树的遍历,按照字典序输出。

    完成以上操作用户可以选择重新遍历树,也可以查找树中的某个单词,查询词频和词频数。

    这里最关键的就是对树的构建,因为插入时会有bug

    下面贴一下我的代码,(因为我初学可能代码风格不是很好)


    主要方法一:

    //传入树以及字符串检测有就加数 没有就加结点

    int magicFindWord(letterNode*opNode,char*opString, treeInfo*infoConter) {

     

        //初始化变量

        int max_string_length =MAX_STRING_LENGTH;

        letterNode *currentNode=opNode;//记录当前操作的结点

        letterNode *currentHeadNode = currentNode;//记录每一层的第一个结点

        letterNode *trunkNode=NULL;

        letterNode addNode;//需要添加的结点

        int getWordNum = 0;

        int areYouFind = 0;//记录查找的状态

     

        for (int i =0;i<strlen(opString)&&i < max_string_length; i++)

        {

            areYouFind= 0;

            currentHeadNode= currentNode;//记录头结点

           

            for (;currentNode;)//寻找插入位子 或者寻找单词完结点

            {

                if (currentNode->currentChar==opString[i])//在树中找到字母

                {

                    areYouFind= 1;

                    if ((i+1 == strlen(opString)) || (i+1 == max_string_length))//找到并且是最后一个字母

                    {

                        currentNode->wordNum++;

                        infoConter->wordTotalSize++;

                        if (currentNode->wordNum==1)//找到后计数器加一

                        {

                            infoConter->wordTotalNum++;

                        }

                        getWordNum = currentNode->wordNum;

                        areYouFind = 100;

                        break;

                    }

                    break;

                }

                currentNode = currentNode->nextNode;

            }

           

            if (areYouFind==0)//没找到创建新结点

            {

                addNode.wordNum = 0;

     

                if (i+1>=strlen(opString)||i+1>= max_string_length)//该字母为单词最后一个单词,计数器加一

                {

                    addNode.wordNum= 1;

                    infoConter->wordTotalNum++;

                    infoConter->wordTotalSize++;

                    getWordNum= addNode.wordNum;

                    addNode.nextNode= NULL;

                    addNode.nextTrunk= NULL;

                }

                else//字母不是单词最后一个,创建下一层的头结点

                {

                    trunkNode= (letterNode*)malloc(sizeof(letterNode));

                    trunkNode->currentChar=opString[i + 1];

                    trunkNode->wordNum= 0;

                    trunkNode->nextNode= NULL;

                    trunkNode->nextTrunk= NULL;

     

                    addNode.nextTrunk= trunkNode;

                }

     

                addNode.currentChar = opString[i];

     

                insertNode(currentHeadNode, addNode);//在树(下一层的链中)中插入结点

     

                currentNode = trunkNode;

     

            }

     

            if(areYouFind==1&&!currentNode->nextTrunk)//找到该单词并且下一层无结点

            {

                trunkNode = (letterNode*)malloc(sizeof(letterNode));//创建下一层的头结点

                trunkNode->currentChar = opString[i + 1];

                trunkNode->wordNum = 0;

                trunkNode->nextNode = NULL;

                trunkNode->nextTrunk = NULL;

     

                currentNode->nextTrunk= trunkNode;

                currentNode = currentNode->nextTrunk;

            }elseif(areYouFind == 1)//找到该单词并且下一层有结点

            {

                currentNode = currentNode->nextTrunk;

            }

     

            if (areYouFind==100)

            {

                break;

            }

        }

     

        return getWordNum ;

    }

    主要方法二:

    //分析文件中的文本

    int analysisText(letterNode*opNode,FILE*opFile, treeInfo*infoConter){

        char toolCharArray[100];//用来读取文件中的字符

        int letterNum=0;

        int max_string_length =MAX_STRING_LENGTH;

        char *opString;

        opString = (char *)malloc((max_string_length+1)*sizeof(char));

        opString[0] = 0;

        opString[max_string_length] = 0;

        int hh=0;

        while (fgets(toolCharArray, 100,opFile) != NULL)//逐行读取opFile所指向文件中的内容到toolCharArray中

        {

           

            for (int i = 0; i < 100-1; i++)

            {

                if ((toolCharArray[i]>='a'&&toolCharArray[i]<='z')|| (toolCharArray[i] >= 'A'&&toolCharArray[i] <='Z'))//检测是否为字母

                {

                   

                    if (letterNum<max_string_length)

                    {

                        if (toolCharArray[i]<97)//大写转小写字母

                        {

                            toolCharArray[i]+= 32;

                        }

                        opString[letterNum] = toolCharArray[i];

                    }

                    letterNum++;

                }

                else

                {

                    if (letterNum>0)//检测到一个单词记录结束存入树中

                    {

                        if (letterNum<max_string_length)

                        {

                            opString[letterNum]='\0';

                        }

                        printf("%s", opString);

                       

                        magicFindWord(opNode,opString,infoConter);//放入树中

                        letterNum = 0;

                    }

                }

            }

        }

       

        free(opString);

        opString = NULL;

        return 0;

    }

     

    主方法:

    int main() {

     

       

        FILE* file = getAFile();//获取用户文件

     

        //初始化结点信息树和信息记录

        letterNode opNode;

        treeInfo infoConter;

        initTree(&opNode);

        initTreeInfo(&infoConter);

     

        //分析文件

        analysisText(&opNode,file,&infoConter);

        printf("\n\n\n分析文章结束\n");

     

     

        //遍历产生字典树

        traverseTree(&opNode, infoConter);

        //获取用户想要的搜索结果*/

     

       

        char useOpChar[100] = {'!'};

        while (useOpChar[0]!='q'&& useOpChar[0] !='Q')

        {

            printf("\n\n\n 分析并 输出字典树结束,请进行下列操作");

            printf("\n  f/F查找   t/T遍历字典树 q/Q退出程序");

            printf("\n\n 输入操作符:");

            scanf_s("%s", &useOpChar, 10);

            system("cls");

            printf("\n\n");

            switch (useOpChar[0])

            {

            case't':;

            case'T': {traverseTree(&opNode, infoConter);break; }

            case'f':;

            case'F': {

                char sss[100] ="you";

                printf("请输入要查找的词(enter结束输入):");

                scanf_s("%s", &sss, 100);

                printf("\n\n%s的频数为:%d\n", sss,getWordNum(&opNode, sss));

                double freque = (double)getWordNum(&opNode, sss) * 100 / infoConter.wordTotalSize;

                printf("%s的频率为:%f%c \n", sss, freque, 37);

                break; }

            default: {break; }

            }

        }

       

        destroyTree(&opNode, &infoConter);

        return 0;

    }

    以下是运行结果截图(我把扫描到的字母也打印出来了,看起来可能会比较乱):






    展开全文
  • 功能: 通过字典等算法模拟了一个输入法频率提示工具。 原理: 没记错的话是用的字典频率的统计方式做的。
  • 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'   
    展开全文
  • 文章目录一、单词介绍二、实现思路2.1 词频统计和单词查找2.2 敏感词屏蔽三、代码实现 前几天都看一个敏感词屏蔽算法的文章,写的挺好,顺着思路写了下去,实现了一下,算法效率还是杠杠的。。。 一、单词介绍 ...


    前几天都看一个敏感词屏蔽算法的文章,写的挺好,顺着思路写了下去,实现了一下,算法效率还是杠杠的。。。

    一、单词树介绍

    利用的是单词树的算法,先看看什么叫单词树。单词树也叫trie 树也称为字典树。最大的特点就是共享字符串的公共前缀来达到节省空间的目的。

    例如,字符串 "abc"和"abd"构成的单词树如下:

    在这里插入图片描述

    树的根节点不存任何数据,每整个个分支代表一个完整的字符串。像 abc 和 abd 有公共前缀 ab,所以我们可以共享节点 ab。如果再插入 abf,则变成这样:

    在这里插入图片描述

    这样看来能实现的功能就很显而易见了,例如词频统计,单词查找,还有就是游戏里的敏感词屏蔽。

    二、实现思路

    来具体说说实现的思路吧。

    2.1 词频统计和单词查找

    这两个都是同一种思路。即下面代码里的find_word_exists函数,词频统计加个累计就好了。

    关键在创建单词树的时候,需要添加子节点,另外还要标记单词是否在此处是完整单词。然后将一个个字符插入即可。

    2.2 敏感词屏蔽

    这个稍微复杂点。即下面代码里的sensitive_word_filter函数。

    需要三个指针来遍历实现,两个在检查的单词上,一个在单词树上。

    1、首先指针 p1 指向 root,指针 p2 和 p3 指向字符串第一个字符

    在这里插入图片描述

    2、然后从字符串的 a 开始,检测有没有以 a 作为前缀的敏感词,直接判断 p1 的孩子节点中是否有 a 这个节点就可以了,显然这里没有。接着把指针 p2 和 p3 向右移动一格。

    在这里插入图片描述

    3、然后从字符串 b 开始查找,看看是否有以 b 作为前缀的字符串,p1 的孩子节点中有 b,这时,我们把 p1 指向节点 b,p2 向右移动一格,不过,p3不动。

    在这里插入图片描述

    4、判断 p1 的孩子节点中是否存在 p2 指向的字符c,显然有。我们把 p1 指向节点 c,p2 向右移动一格,p3不动。

    在这里插入图片描述

    5、判断 p1 的孩子节点中是否存在 p2 指向的字符d,这里没有。这意味着,不存在以字符b作为前缀的敏感词。这时我们把p2和p3都移向字符c,p1 还是还原到最开始指向 root。

    在这里插入图片描述

    6、和前面的步骤一样,判断有没以 c 作为前缀的字符串,显然这里没有,所以把 p2 和 p3 移到字符 d。

    在这里插入图片描述

    到这里应该差不多懂了。。。后面都一样。那开始动手实践。

    三、代码实现

    这里的词频统计,单词查找和敏感词屏蔽都实现了,如下;

    #include <iostream>
    #include <stdio.h>
    using namespace std;
    
    #pragma pack(1)
    struct trie_node
    {
        static const int letter_count = 26;
        int count;  // 字符的次数
        bool is_terminal; // 完整单词的标志
        char letter; // 当前节点的字符
        trie_node* childs[letter_count]; // 子节点
    
        trie_node(): letter(0), count(1), is_terminal(false)
        {
            for(int i = 0; i < letter_count; ++i)
            {
                childs[i] = NULL;
            }
        }
    };
    #pragma pack()
    
    class trie
    {
    private:
        trie_node* _root_node;
    public:
        trie(): _root_node(NULL)
        {
        }
        ~trie()
        {
            delete_trie(_root_node);
        }
    
        trie_node* create()
        {
            trie_node* node = new trie_node();
            return node;
        }
    
        void insert(const char* str)
        {
            if(NULL == _root_node || NULL == str)
            {
                _root_node = create();
            }
            trie_node* next_node = _root_node;
    
            while(*str != 0)
            {
                int index = *str - 'a';
                if(NULL == next_node->childs[index])
                {
                    next_node->childs[index] = create();
                }
                else
                {
                    next_node->childs[index]->count++;
                }
                next_node = next_node->childs[index];
                next_node->letter = *str;
                str++;
            }
    
            next_node->is_terminal = true;
        }
    
        bool find_word_exists(const char* str)
        {
            if(NULL == _root_node || NULL == str)
            {
                printf("condition is null\n");
                return false;
            }
    
            trie_node* cur_node = _root_node;
    
            do
            {
                cur_node = cur_node->childs[*str - 'a'];
                if(NULL == cur_node)
                {
                    return false;
                }
                str++;
            }while (*str != 0);
    
            return cur_node->is_terminal; /* 直接看当前是否有完整单词的标志 */
        }
    
        void sensitive_word_filter(char* str)
        {
            if(NULL == _root_node || NULL == str)
            {
                printf("condition is null\n");
                return ;
            }
    
            char* pre = str;
            char* cur = str;
            trie_node* cur_node = _root_node;
    
            do
            {
                int index = *cur - 'a';
                if(NULL != cur_node->childs[index])
                {
                    if(cur_node->childs[index]->is_terminal == true) /* 找到敏感词 */
                    {
                        while(pre != cur) /* 替换敏感词 */
                        {
                            *pre = '*';
                            pre++;
                        }
                        *pre = '*';
    
                        // 向后移动,重新开始单词树查找
                        cur++;
                        pre = cur;
                        cur_node = _root_node;
                        continue;
                    }
                    cur_node = cur_node->childs[index];
                    cur++;
                }
                else
                {
                    /* 单词树需要重新开始查找。检测的文本向后移动一步(前面的指针)然后查找 */
                    pre++;
                    cur = pre;
                    cur_node = _root_node;
                }
            }while (*cur != 0);
    
            return;
        }
    
        void delete_trie(trie_node* node)
        {
            if(NULL == node)
            {
                return ;
            }
            for (int i = 0; i < trie_node::letter_count; i++)
            {
                if(NULL != node->childs[i])
                {
                    delete_trie(node->childs[i]);
                }
            }
            delete node;
        }
    };
    
    
    
    int main(int argc, char** argv)
    {
        if(argc < 2)
        {
            printf("Usage: ./a.out word\n");
            return -1;
        }
    
        char* word = NULL;
        if(NULL != argv[1])
        {
            word = argv[1];
        }
        else
        {
            return -2;
        }
    
        trie trie_tree = trie();
        trie_tree.insert("apps");
        trie_tree.insert("apply");
        trie_tree.insert("append");
        trie_tree.insert("back");
        trie_tree.insert("backen");
        trie_tree.insert("basic");
    
        /*1. 词频统计,和单词查找*/
        bool is_find = trie_tree.find_word_exists(word);
        if(is_find)
        {
            printf("find word\n");
    
        }
        else
        {
            printf("not find\n");
        }
    
        /*2. 敏感词屏蔽*/
        trie_tree.sensitive_word_filter(word);
        printf("word = %s\n", word);
    
        return 0;
    }
    
    

    ./a.out apps
    运行结果:

    find word
    word = ****
    

    ./a.out backhahaha
    运行结果:

    not find
    word = ****hahaha
    

    原理参考链接:https://blog.csdn.net/m0_37907797/article/details/103272967

    展开全文
  • 字典实现词频统计

    2020-08-24 16:01:25
    Trie树(字典树) 字典树又叫前缀树,是处理字符串常用的数据结构,最近和朋友一起粗略写了一下关于字典树的词频统计。 一、功能介绍 文件流读写单词; 将读到的单词插入树中; 打印树,打印出单词和个数以及词频;...
  • 典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希...
  •  如果我们有and,as,at,cn,com这些关键词,那么trie树(zidianshu)? 从上面的图中,我们或多或少的可以发现一些好玩的特性。  第一:根节点不包含字符,除根节点外的每一个子节点都包含一个字符。 ...
  • Trie树统计词频、排序、查找

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

    万次阅读 2014-10-15 20:37:27
    最近在学习的时候,经常看到使用Trie树数据结构来解决问题,比如“ 有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。” 该如何解决? 有一种方案...
  • Trie树 c++实现

    千次阅读 2015-08-15 17:29:12
    Trie,又称单词查找、前缀,是一种多叉结构。 与二叉查找不同,键不是直接保存在节点中,而是由节点在中的位置决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符...
  • Trie树统计词频

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

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

    2021-10-10 17:08:06
    介绍Trie树及Double Array Trie优化
  • Trie树是一种数据结构,对于词频统计,文本检索非常有效![在这里插入图片描述](https://img-blog.csdnimg.cn/20200402204937680.jpg#pic_center Trie树的大小取决与要统计的文本的字母个数。比如只统计26个英文字母...
  • 第二题:词频统计 实现 【问题描述】 编写程序统计一个英文文本文件中每个单词的出现次数(词频统计),并将统计结果按单词字典序输出到屏幕上。 要求:程序应用二叉排序(BST)来存储和统计读入的单词。 注...
  • Trie树又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共...
  • 引入现在有这样一个问题, 给出$n$个...这时候就需要一种强大的数据结构——字典树基本性质字典树,又叫Trie树、前缀树,用于统计,排序和保存大量的字符串,经常被搜索引擎系统用于文本词频统计。基本思想: 利用字...
  • 转载这篇关于字典的原因是看到腾讯面试相关的题:就是在海量数据中找出某一个数,比如2亿QQ号中查找出某一个特定的QQ号。。 有人提到字典,我就顺便了解下字典。 [转自:...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,170
精华内容 1,268
关键字:

trie树词频统计