注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水居

云在青山水在天,人在江湖不得闲

 
 
 

日志

 
 

字典树(Trie)->中文字典树(哈希字典树)  

2010-10-27 22:03:33|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

查看全文


字典树,又名Trie树,是字符串操作中一个常见的数据结构,例如用来查单词。其实字典树可以看做一个26或52节点的B树,这是因为英文字符只有26个大写和26个小写字母。
但是在存储中文时,问题就出来了:常用的汉字大概有5万个,因此,如果中文字典树也用Trie的方式存储,就会出现每个节点占用空间太大的问题。
这样在处理中文字符时,就不得不对传统的字典树进行改进。拼音表示和哈希表示
拼音表示:
将中文用拼音表示,然后就可以用传统Trie的方式保存和处理了。这种方式比较简单,但存在多音字的问题,所以只能解决有限的问题。

哈希表示:
每个节点的子节点用一个哈希表存储,这样就不用浪费太大的空间,而且查询速度上可以保留哈希的复杂度O(1)
例如:
“我”的下一个可能为“们,是,爱,说”
就可以为我建立一个大小为7的哈希表,作为子节点,将这四个字存入哈希表中。
这样就解决了汉字字典树的浪费空间的问题,保持了字典树的复杂度。
字典树(Trie)-中文字典树(哈希字典树) - hankjin - 云水居
 
 
如上图所示的一个哈希字典树,包括单词“我是谁”,“我是人”,“我们”,“我爱”,“我说”
每个节点包含一个指针sons(指向哈希表),一个整数used(表示子节点的个数),一个素数size(表示哈希表的大小,值为大于2*used的素数)。如上图所示“我”有四个子节点,所以used=4, size=11, sons指向一个大小为11的哈希表,哈希表中存储着子节点的指针或NULL。
复杂度分析:
如果不用字典树,则要用索引的方式存储与读取,而定位每一级元素的时间,理论上需要n/2的复杂度,如果用二分搜索的方式,复杂度可以降到log2N,但这种哈希字典树使用哈希,复杂度为常数级(哈希冲突),效果明显比索引要好。
代码:
这段代码思想是这样的,但是没有使用中文。
/*
 * @desc: index and tree
 * @date: 2010-11-3
 * @author: hankjin
 */
#include <iostream>
#include <fstream>
#include <cmath>
#include <cstring>
#include <ctime>
using namespace std;
#define MAXN 40

typedef struct _node{
    struct _node *first;    //first element of index
    struct _node *next;        //next element of index
    struct _node **sons;    //hash array
    int size;            //hash array size
    int used;            //son number
    char value;            //value
    bool isword;        //is end of word or middle
    _node(char v){
    sons=NULL;
    first=next=NULL;
    used=0;
    value=v;
    isword=false;
    }
}node;
//add a element to index
void indexadd(node *root, char *word);
//convert index to tree
void index2tree(node *root);
//find by index
bool indexfind(node *root, char *word);
//find by tree
bool treefind(node *root, char *word);
//tree hash
inline int treehash(node *p, char value){
    return (int)value % p->size;
}
//calc hash array size, accord to son number.
//rule: least prime number which is larger then 2 times son number
//eg: if a node has 5 son, 11 is the least prime larger then 2*5
inline int hashfactor(int x){
    if(x<3)//at least 3
    return 3;
    for(int i, res=x/2*4+1; ; res+=2){
    for(i=3; i<=sqrt(res); i+=2){//is prime
        if(res%i==0)
        break;
    }
    if(res%i!=0)
        return res;
    }
}

ifstream fin("/usr/share/dict/words");
ifstream fin1("/usr/share/dict/words");
ifstream fin2("/usr/share/dict/words");
int main(){
    node root(' ');
    char tmp[MAXN];
    //build index
    while(fin>>tmp){
    indexadd(&root, tmp);
    }
&nbs

查看全文

  评论这张
 
阅读(6943)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017