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

云水居

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

 
 
 

日志

 
 

中文字典的索引与树的存储与访问  

2010-11-03 21:13:58|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

查看全文


中文字典可以使用索引与树两种存储与访问方式:
索引
索引的存储方式很简单,first指向第一个子节点,next指向下一个兄弟节点。
如下图所示:
root有四个子节点 son1 son2 son3 sonx
son1有两个子节点son11 son12
访问方式为:
root->first获得root的第一个子节点son1,然后通过son1->next获得root的第二个子节点son2,son2->next获得son3,son3->next获得sonx
然后从son1->first获得son1的第一个子节点son11,然后通过son11->next获得son1的第二个子节点son12

中文字典的索引与树的存储与访问 - hankjin - 云水居
 

哈希字典树
从前面的索引结构可以看出,要访问sonx节点,要通过root->first->next->next->next,才能达到,如果一个节点有几百几千个子节点,访问的复杂度将会非常大。
根据前面的索引,可以生成哈希字典树,将每个节点的所有子节点指针存储在一个指针数组中,这样就可以利用哈希的特性快速定位到子节点。复杂度为c

中文字典的索引与树的存储与访问 - hankjin - 云水居
 代码:
从CSDN上下载一个字典http://d.download.csdn.net/down/382024/oldfox126
然后使用以下命令转换得到字典文件
iconv -f gbk -t utf-8 dict_chs_gbk.txt |awk '{print $1}' | tee cndict.in
然后编译执行下面的代码文件即可:
/*
 * @desc: index and tree
 * @date: 2010-11-3
 * @author: hankjin
 * @version: 1.0
 * @platform: ubuntu 10.04
 * @tree:index = 40:1
 */
#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
    wchar_t value;        //value
    bool isword;        //is end of word or middle
    _node(wchar_t v){
    sons=NULL;
    first=next=NULL;
    used=0;
    value=v;
    isword=false;
    }
}node;
//add a element to index
void indexadd(node *root, wchar_t *word);
//convert index to tree
void index2tree(node *root);
//find by index
bool indexfind(node *root, wchar_t *word);
//find by tree
bool treefind(node *root, wchar_t *word);
//tree hash
inline int treehash(node *p, wchar_t 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;
    }
}
locale lang("en_US.utf-8");
wifstream fin("cndict.in");
wifstream fin1("cndict.in");
wifstream fin2("cndict.in");
int main(){
    fin.imbue(lang);
    fin1.imbue(lang);
    fin2.imbue(lang);

    node root(' ');
    wchar_t tmp[MAXN];
    //build index
    while(fin>>tmp){
    indexadd(&root, tmp);
    }
    //convert from index to tree,

查看全文

  评论这张
 
阅读(991)| 评论(0)
推荐 转载

历史上的今天

评论

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

页脚

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