首先我们简述核心词典的目标。词典最主要的目标是，给定一句句子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树只需要沿着顺序进行几次索引即可，复杂度取决于词语长度——基本来说和词典大小无关。按照这个推论，实现一个紧凑的，高效的二级小结构，可能比较有利于减小总体大小，增加工作速度。