上一篇文章讲的是基于词典和AC自动机的快速分词。基于词典的分词有一个明显的优点,就是便于维护,容易适应领域。如果迁移到新的领域,那么只需要添加对应的领域新词,就可以实现较好地分词。当然,好的、适应领域的词典是否容易获得,这还得具体情况具体分析。本文要讨论的就是新词发现这一部分的内容。

这部分内容在去年的文章《新词发现的信息熵方法与实现》已经讨论过了,算法是来源于matrix67的文章《互联网时代的社会语言学:基于SNS的文本数据挖掘》。在那篇文章中,主要利用了三个指标——频数、凝固度(取对数之后就是我们所说的互信息熵)、自由度(边界熵)——来判断一个片段是否成词。如果真的动手去实现过这个算法的话,那么会发现有一系列的难度。首先,为了得到$n$字词,就需要找出$1\sim n$字的切片,然后分别做计算,这对于$n$比较大时,是件痛苦的时间;其次,最最痛苦的事情是边界熵的计算,边界熵要对每一个片段就行分组统计,然后再计算,这个工作量的很大的。本文提供了一种方案,可以使得新词发现的计算量大大降低。

算法

回顾matrix67的算法做新词发现的过程,应该可以认识到,新词发现做的事情,就是根据语料判断给定片段是不是真的成词了,而所谓成词,就是它相对独立,不可切分。那为什么不反过来呢?为什么我们不去找一下哪些片段不能成词呢?根据前面的说法,我们说片段的凝固度大于一定程度时,片段可能成词(接下来要去考虑它的边界熵)。那这不就是说,如果片段的凝固度低于一定程度时,这个片段就不可能成词了吗?那么我们就可以在原来的语料中把它断开了。

我们可以做适当的简化,如果$a,b$是语料中相邻两字,那么可以统计$(a,b)$成对出现的次数$\#(a,b)$,继而估计它的频率$P(a,b)$,然后我们分别统计$a,b$出现的次数$\#a,\#b$,然后估计它们的频率$P(a),P(b)$,如果
$$\frac{P(a,b)}{P(a)P(b)} < \alpha \quad (\alpha\text{是给定的大于1的阈值})$$
那么就应该在原来的语料中把这两个字断开。这个操作本质上就是——我们根据这个指标,对原始语料进行初步的分词!在完成初步分词后,我们就可以统计词频了,然后根据词频来筛选。

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

实现

看上去很完美——计算量少了,功能更强了。实际效果如何呢?跟matrix67文章中的算法的结果有多少出入?这个还得真的自己试过才能说了算。不过,我用了30万篇微信公众号的文章(约1GB)进行实验,发现效果是可以让人满意的,用时10分钟左右。下面给出实现代码,很短,纯Python,并且不用第三方库的支持,而且内存非常友好,这里的texts可以是一个列表,也可以是一个迭代器(每次返回一篇文章),配合tqdm库,可以方便地显示进度。最后,在统计时,用到了加$\gamma$平滑法,以缓解出现不合理的词。以前做这些统计计算的时候,不用想就用Pandas了,最近尝试了一下Python原生的一些库,发现也相当好用呢~

import pymongo

db = pymongo.MongoClient().baike.items
def texts():
    for a in db.find(no_cursor_timeout=True).limit(1000000):
        yield a['content']

from collections import defaultdict
from itertools import tee
from tqdm import tqdm
import re

class Find_Words:
    def __init__(self, min_count=10, min_proba=1):
        self.min_count = min_count
        self.min_proba = min_proba
        self.chars, self.pairs = defaultdict(int), defaultdict(int)
        self.total = 0.
    def text_filter(self, texts):
        for a in tqdm(texts):
            for t in re.split(u'[^\u4e00-\u9fa50-9a-zA-Z]+', a):
                if t:
                    yield t
    def count(self, texts):
        for text in self.text_filter(texts):
            self.chars[text[0]] += 1
            for i in range(len(text)-1):
                self.chars[text[i+1]] += 1
                self.pairs[text[i:i+2]] += 1
                self.total += 1
        self.chars = {i:j for i,j in self.chars.iteritems() if j >= self.min_count}
        self.pairs = {i:j for i,j in self.pairs.iteritems() if j >= self.min_count}
        self.strong_segments = {i: self.total*j/(self.chars[i[0]]*self.chars[i[1]]) for i,j in self.pairs.iteritems()}
        self.strong_segments = {i:j for i,j in self.strong_segments.iteritems() if j >= self.min_proba}
    def find_words(self, texts):
        self.words = defaultdict(int)
        self.total_words = 0.
        for text in self.text_filter(texts):
            s = text[0]
            for i in range(len(text)-1):
                if text[i:i+2] in self.strong_segments:
                    s += text[i+1]
                else:
                    self.words[s] += 1
                    self.total_words += 1
                    s = text[i+1]
        self.words = {i:j for i,j in self.words.iteritems() if j >= self.min_count}

fw = Find_Words(16, 1)
fw.count(texts())
fw.find_words(texts())

import pandas as pd
words = pd.Series(fw.words).sort_values(ascending=False)

Python流式读取SQL数据的参考代码:

from sqlalchemy import *

def sql_data_generator():
    db = create_engine('mysql+pymysql://user:password@123.456.789.123/yourdatabase?charset=utf8')
    result = db.execution_options(stream_results=True).execute(text('select content from articles'))
    for t in result:
        yield t[0]

分析

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

微信词典

最后分享一份我从最近的30万微信公众号文章(1G左右, 3亿多字)中提取的一份词表,设置了最小凝固度为1,最小频数为100。从表中也可以发现,跟微信具有明显联系的词语都已经被提取出来,并且,这是最新的公众号文章,因此,最近的热点——奥运、王宝强——相关的词语也被提取出来了。

微信词典:dict.txt

参考链接

《非主流自然语言处理——遗忘算法系列(二):大规模语料词库生成》:http://www.52nlp.cn/forgetnlp2


转载到请包括本文地址:http://kexue.fm/archives/3913/

如果您觉得本文还不错,欢迎点击下面的按钮对博主进行打赏。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!