NCWS——Naive Chinese Word Segmentation

Naive Chinese Word Segmentation,蠢萌的中文分词ww

嘛,这学期选了「信息检索」课,然后老师建议我们自己写一下中文分词,我以前遇到要分词的情况一般是用第三方的库,比如scws——Simple Chinese Word Segmentation。这是一个非常好用的库,速度也不错,还默认提供了PHP扩展的编译,使用的是词频词典,并辅以一定的规则识别来达到基本分词。关于scws具体的不再多说,可以去它的官网看看。

这里我只用了最简单的逆向最大匹配来分词,没有加入其他的规则,所以就只能说是naive了。然后需要说明的是词典使用的是scws的词库,然后转为了自己的格式,没有直接用scws的XDB。scws在其下载页面提供了一个XDB的导出工具,我这里是先将XDB导出为文本内容再进行处理的。(ncws只使用了来自scws的公开词库以及对应的词库导出工具)

效果如下(/ω\)

screenshot-ncws

要做一个最简单的逆向最大匹配分词系统并不复杂,在有了词典之后,就按照逆向最大匹配方法本身的思路来写就好。

简单的说一下逆向最大匹配,比如我们给定词典有如下条目

  • AB
  • AAB
  • ABCC
  • BSD

然后我们需要分词的文本是AABABBSDABCC

那么我们可以看到,词典里最长的条目是4个字节,那么我们每次最多读入4个字节就可以保证至少能切分出一个词语。

为了方便,这里用一个’|’分隔文本,在其左边的为读入了的数据,在右边的则还未开始切分

第一次 AABA | BBSDABCC


  1. 在词典里查找AABA,没有则去掉最后一个字符
  2. 在词典里查找AAB,找到,开始下一次

第二次 ABBS | DABCC


  1. 在词典里查找ABBS,没有则去掉最后一个字符
  2. 在词典里查找ABB,继续去掉最后一个字符
  3. 在词典里查找AB,找到,开始下一次

第三次 BSDA | BCC


  1. 在词典里查找BSDA,没有则去掉最后一个字符
  2. 在词典里查找BSD,找到,开始下一次

第四次 ABCC |


  1. 在词典里查找ABCC,找到,开始下一次

此时到达文本末尾,返回所有找到的词语["AAB", "AB", "BSD", "ABCC"],以上就是利用逆向最大匹配的一次完整的文本切分。

Optimization


那么说完了原理,简单的说一下ncws的一点优化。可以看到,在上面的过程中,最多的就是在词典里查找一个string是否存在,而匹配一个string的时间复杂度往往取决于string的长度,为了减小计算量,我们将使用hash,并且在预先处理时,就将词典里的条目用hash代替,这样一来在加载到内存里的时候,就不用再次计算hash了。这里我选择了xxHash,宣称是在64位的电脑上能达到 6 GB/s 的处理速度。

然后就是字典的加载,为了达到最快的速度,我们在转换文本字典时,直接将对应的内存写到一个文件里,并在加载时使用mmap。

该文件的结构非常简单,

Name Start Length (bytes) Value Fixed?
文件头 tag 0 4 MEMO YES
条目数量 count 4 4 count NO
[struct ncws_term_mmap_t] 8 sizeof(struct ncws_term_mmap_t) * count struct ncws_term_mmap_t NO
[[term, attr]] 8 + sizeof(struct ncws_term_mmap_t) * count --- --- NO

一个固定的文件头tag,接下来是4字节的整数,代表这个字典里有多少项,然后跟着一组struct ncws_term_mmap_t,暂且称为struct header部分,最后的就是struct data部分。struct header + struct data部分合称structure部分。

typedef struct ncws_term_mmap_t {
    uint64_t hash;
    uint32_t term_offset;
    double df;
    double idf;
    uint32_t attr_offset;
} ncws_term_mmap_t;
  • hash

hash是该项经XXH64之后的值

  • term_offset

term_offset是该项的真实值在structure部分的偏移值。

  • df

document factor,文档因子

  • idf

inverted document factor,逆文档因子

  • attr_offset

attr_offset是该项的词性(北大标注)在structure部分的偏移值。

这里当时加载之后,直接用了std::unordered_map<uint64_t, struct ncws_term_mmap_t *> _dictionary;,实际上要想再优化的话,可以在预转换时现根据hash的值排序,然后使用一个跳表/三元搜索树简化每次的查找。

源代码在我的Github上,BlueCocoa/ncws

声明: 本文为0xBBC原创, 转载注明出处喵~

发表评论

电子邮件地址不会被公开。 必填项已用*标注