上一篇文章讲的是基于词典和AC自动机的快速分词。基于词典的分词有一个明显的优点，就是便于维护，容易适应领域。如果迁移到新的领域，那么只需要添加对应的领域新词，就可以实现较好地分词。当然，好的、适应领域的词典是否容易获得，这还得具体情况具体分析。本文要讨论的就是新词发现这一部分的内容。
算法
新词发现过程就是根据语料判断给定片段是不是真的成词了，而所谓成词就是它相对独立，不可切分。那为什么不反过来呢？为什么我们不去找一下哪些片段不能成词呢？
根据前面的说法，我们说片段的凝固度大于一定程度时，片段可能成词（接下来要去考虑它的边界熵）。那这不就是说，如果片段的凝固度低于一定程度时，这个片段就不可能成词了吗？那么我们就可以在原来的语料中把它断开了。
我们可以做适当的简化，如果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，则需要更大的语料库才能使得词库完备起来。这是在使用本算法时需要仔细考虑的。
客服一