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

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

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

效果如下(/ω＼)

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

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

• 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。

该文件的结构非常简单，

一个固定的文件头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上，ncws