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

To be completed

我回来了

 
 
 

日志

 
 

双数组字典树(Double-Array Trie)  

2010-12-25 01:46:38|  分类: 中文信息处理 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
中文信息处理期末作业要做一个简单的分词系统,影响分词速度的关键是如何建立索引,很容易想到建立一个字典树,但是字典树空间开销太大,而且不像英文只有26个字母,中文至少有6000多个常用字,开一棵6000多叉树显然不切实际,用压缩存储的方式又会影响到查找的效率,如何做到既保持字典树高效的查找效率又节省空间开销,有人提出了采用了双数组的方式存储字典树。
原理很简单,用一个base数组进行状态转移,用check数组来验证,英文资料对原理讲解得很清楚。有了英文论文,当然会有国内的人把它用在中文分词上,不过我找到了几篇都有些含糊,主要参考《双数组Trie树算法优化及其应用研究》。
由于英文的字母表很小,采用直接插入的方式速度也很快,这样做有时需要重新分配base和check的指向,在处理中文时,还需要专门记录下每个结点的状态转移,然后就可以按照英文资料中的方法做了。
不过我为了让编码更直观,也更贴近中文论文的叙述(具体论文是怎么实现的我还不得而知),先用邻接表建立了一棵字典树,然后再通过遍历整棵树把它转换成双数组表示,这样做不需要英文资料中的Relocate函数,目前5万个词条直观上的创建速度还挺快,如果还需要优化可以像英文资料里一样把空闲位置用链表串起来。
具体时间和空间的消耗交给别的同学去测试。
  评论这张
 
阅读(1145)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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