Shell's Home

Apr 12, 2012 - 1 minute read - Comments

segment的核心数据结构空间和时间效率估量

首先我们简述核心词典的目标。词典最主要的目标是,给定一句句子S,匹配出所有和句子开始拥有完整匹配的词语。所谓完整匹配,就是句子开始的一定长度的连续序列和词语相等。例如,中华,中华人民,中华人民共和国,都是句子:中华人民共和国今天成立了,的完整匹配。

要解决这个问题,直观方式是使用tied tree。但是中文的tied tree非常不好实现。英文的tied tree在一个节点上最多拥有不超过26个子节点,而中文的在根上面会拥有6000个以上的子节点,使用同样的结构在子节点上会浪费大量内存。

我们先跳过tied树本身的细节,来讨论如何使用python内置数据结构高效简洁的完成这一工作。作为一个读比写高频很多的结构,无疑hash table是一个非常适合的结构。我在hash table的性能分析中说过,hash table的查询性能是O(1)量级的。无疑,可以使用hash tree来高速完成查找。同时注意一点,词语的最小长度是2,因此不存在只有一级的结构。所以,hash tree的第一级结构可以从2开始,而不是1。

实现效果如何?我们正式给出的词典拥有127K的词汇量,平均第二级宽度为6.8,因此大致可以推算出,第一级的词典含有元素19K个左右。python源码解析中说过,当表项小于50000个时,扩张大小为当前活跃表项的4倍,最高填充率不超过2/3,即填充率最低25%,最高66%。平均来说,填充率应当在45%上下波动,我们以0.5计算,实际上一级词典的Entry个数应当是40K个上下。在源码Include/dictobject.h:50有给出Entry的结构,这应当是三个平台相关的数据结构,以贝壳的64位系统而言,长度应当是24字节。忽略掉辅助结构,一级词典的大小应当是960K,即约1M。而词典指向的数据,即2字长的str对象本身头部长度24字节,辅助数据长度12字节,数据长度4字节(utf-16编码的两个unicode),null term1字节,共计41字节。由于python对象是8字节对齐,因此实际占用48字节。19K个数据总计占用912K。

二级表项平均长度6.8,这个长度很难估量。因为5的话总表项刚好是8,而6就会增长到24,我们取中间数20做一个估量值(因为6.8毕竟大大偏离了5),一个词典的大小应当是480字节,加上头部大约是512字节(算的粗糙点吧),19K个词典就是8.5M左右。指向的对象长度更加难估量,我们粗糙点按照96字节一个对象(别忘记了,unicode对象不但成员多,而且超出了BOM,一个字占4字节),127K个对象大约是12M内存。而float内部使用C的double类型,一个对象占据32字节,127K个对象占据4M内存。

以上总计,初级词典本身占用1M,关键字占1M。二级索引占据10M,关键字占12M,频率数据占4M。总计28M内存,基本上一个12.7W词的词典,大小2.5M,占据30M内存,这就是dict核心词典的空间效率估量。

时间复杂度估量更加复杂,不过我们可以简化来说。初级索引需要多少时间?O(1)量级,毋庸置疑。问题是二级词典的复杂度,异常难算。凑合一下,按照比较6.8次计算(因为必须通过遍历才能知道全部的匹配)索引出一个句子所有的完整匹配的时间复杂度O应当为O(n),其中n是平均二级索引宽度。目前而言,实际测量结果,平均6.8。当词汇量大于一定值后,随着词典的加大,这个值基本是线性增加的,我们粗略的可以认为O(n)即是正比于词典大小。

而后我们顺便给出分词核心算法在处理一句话时的效率估量吧,证明太长,这里写不下。假定句子长度S,词典大小N,匹配数目M,分词算法的时间复杂度量级为O(N*M*S),有兴趣的可以帮我复核一下,这个证明颇为困难,不知道有没有证错。在实际运行的时候,匹配数目会跟着词典的增长而增长,而句子长度则相对固定。当然,明眼人一眼就可以看出,所谓匹配数据随着词典增长而增长,其中并不是正比的。而是O(1)<O<O(n)。因此我们可以看作时间复杂度为O(N)<O<O(N\^2),具体是什么,做不出来。

然后是纯粹的tied tree的性能估量。讲到tied tree,我们就必须要提到如何实现一个有效的tied tree。实际上纯粹用区域哈希映射太浪费内存了,而顺序查找太浪费时间。比较折衷的办法还是只有——dynamic hash table。

不过这次我们就可以控制一下哈希表的大小了。对于大小不超过6W的哈希,我建议采用crc32,虽然离散度并不高,但是作为一个近似填满的hash table的hash key足矣(这点需要实际考察一下)。如果是自己实现,表项直接存字符串,连指针都不需要,采用开链法。总计大小1M即可以保存所有的一级数据。

二级数据就无法这么偷懒了,因为二级结构中字符串长度不定。但是以数据展开大小只有2.4M来看,无论这一级别如何扩张,字符串本身大小不应当超过3M。开链法一个节点24字节,平均填充率0.5计算,14个表项一个词典(这个也可以自行控制了),336个字节一个词典,乘以19K个dict。大约6.23M。127K个频率数据1M,这是常规占用。

以上总计,初级词典本身占用1M,二级结构本身占用10M,不超过20M应当就可以构建起一个高效的核心数据结构。由于实现类似,时间复杂度也类似,就不详细推论了。

以上还有一点可改进之处,dict作为二级存储的绝对劣势在于,必须要对比全部词典才能确定完全匹配数量,于是时间复杂度正比于词典大小。严格的tied树只需要沿着顺序进行几次索引即可,复杂度取决于词语长度——基本来说和词典大小无关。按照这个推论,实现一个紧凑的,高效的二级小结构,可能比较有利于减小总体大小,增加工作速度。