上一篇文章讲的是基于词典和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,则需要更大的语料库才能使得词库完备起来。这是在使用本算法时需要仔细考虑的。