【中文分词系列】 2. 基于切分的新词发现

算法

新词发现过程就是根据语料判断给定片段是不是真的成词了，而所谓成词就是它相对独立，不可切分。那为什么不反过来呢？为什么我们不去找一下哪些片段不能成词呢？

根据前面的说法，我们说片段的凝固度大于一定程度时，片段可能成词（接下来要去考虑它的边界熵）。那这不就是说，如果片段的凝固度低于一定程度时，这个片段就不可能成词了吗？那么我们就可以在原来的语料中把它断开了。

我们可以做适当的简化，如果a,b是语料中相邻两字，那么可以统计(a,b)成对出现的次数#(a,b)，继而估计它的频率P(a,b)，然后我们分别统计a,b出现的次数#a,#b，然后估计它们的频率P(a),P(b)，如果

P(a,b) / P(a)P(b) < α(α是给定的大于1的阈值)

那么就应该在原来的语料中把这两个字断开。这个操作本质上就是——我们根据这个指标，对原始语料进行初步的分词！在完成初步分词后，我们就可以统计词频了，然后根据词频来筛选。

我们现在只用了两个指标：频数和凝固度，去掉了计算量最大的边界熵，而且，在计算凝固度时，我们只需要计算二字片段的凝固度，省掉了更多字片段的凝固度计算，但是，由于我们是基于切分的方式做的，因此我们少了很多计算量，但理论上却能够得任意长度的词语！

实现

看上去很完美——计算量少了，功能更强了。实际效果如何呢？笔者用了30万篇微信公众号的文章（约1GB）进行实验，发现效果是可以让人满意的，用时10分钟左右。

下面给出实现代码，很短，纯Python，并且不用第三方库的支持，而且内存非常友好，这里的texts可以是一个列表，也可以是一个迭代器（每次返回一篇文章），配合tqdm库，可以方便地显示进度。最后，在统计时，用到了加γ平滑法，以缓解出现不合理的词。以前做这些统计计算的时候，不用想就用Pandas了，最近尝试了一下Python原生的一些库，发现也相当好用呢～

from collections import defaultdict

from itertools import tee

import re 

def count_words(texts, min_count=10, min_proba=1, gamma=0.5):

    segments = [defaultdict(int), defaultdict(int)]

    for text in texts:

        for i in range(2):

            for j in range(len(text)-i):

                segments[i][text[j: j+i+1]] += 1

    segments[0] = {i:j+gamma for i,j in segments[0].iteritems()}

    segments[1] = {i:j+gamma for i,j in segments[1].iteritems()}

    nb_words = sum(segments[0].values())**2/sum(segments[1].values())

    strong_segments = {i: nb_words*j/(segments[0][i[0]]*segments[0][i[1]]) for i,j in segments[1].iteritems() if j >= min_count}

    strong_segments = {i:j for i,j in strong_segments.iteritems() if j >= min_proba}

    return strong_segments 

def filter_words(texts):

    for text in texts:

        for t in re.split(u'[^\u4e00-\u9fa50-9a-zA-Z]+', text):

            yield t 

def find_words(texts, min_count=10, min_proba=1):

    texts_for_count, texts_for_cut = tee(filter_words(texts))

    strong_segments = count_words(texts_for_count, min_count, min_proba)

    words = defaultdict(int)

    for text in texts_for_cut:

        if text:

            s = text[0]

            for i in range(len(text)-1):

                if text[i:i+2] in strong_segments:

                    s += text[i+1]

                else:

                    words[s] += 1

                    s = text[i+1]

    return {i:j for i,j in words.iteritems() if j >= min_count}

分析

当然，这个算法不能说完全没有缺点，还是有些问题值得探讨的。

一般情况下，为了得到更细粒度的词语（避免分出太多无效的长词），我们可以选择较大的α，比如α=10，但是这带来一个问题：一个词语中相邻两个字的凝固度不一定很大。一个典型的例子是“共和国”，“和”跟“国”都是很频繁的字，“和国”两个字的凝固度并不高（在微信文本中大概为3左右），如果α太大就会导致切错了这个词语（事实上，是“共和”跟“国”的凝固度高），这些例子还有很多，比如“林心如”的“心如”凝固度就不大（当然，如果语料来源于娱乐圈，那又另当别论）。而如果设置α=1，则需要更大的语料库才能使得词库完备起来。这是在使用本算法时需要仔细考虑的。