python 中文分词技术介绍和基于分词算法-前向最大匹配算法/后向最大匹配/双向最大匹配

 Pala   2017-10-31 17:45   106 人阅读   条评论

1. 中文分词介绍

英语句子中单词与单词之间以空格分开,有着清晰的边界。而中文句子中词语与词语之间却没有明显的分隔边界,词语是理解与分析句子的最小基本单元,因此分词是中文自然语言处理的第一步,也是中文自然语言处理相比英文自然语言处理不同的一步。中文分词的基本问题是:为语句中的词语添加合适的分隔边界使其反应句子的本意。例如:将“南京市长江大桥”分词得到“南京/市/长江大桥”。更一般地,假设句子 S = C1C2C3…Cn 由 n 个汉字C1, C2, …Cn 组成,分词算法需要将其正确的划分为 C1C2/C3C4C5/…/Cn,其中 C1C2 和 C3C4C5 分别为一个词语。中文分词存在的主要困难有 [1]:

  • 未登录词:分词所使用的词典不可能覆盖所有的词,没有被词典收录的词就称为未登录词或者新词。其主要包括专有名词(人名、地名、机构名等)、重叠词(例如:“高高兴兴”)、派生词(例如:“一次性/用品”)等。

  • 分词歧义:例如,“乒乓球拍卖完了”可以切分为“乒乓/球拍/卖完了”,也可以切分为“乒乓球/拍卖/完了”,类似这样的歧义称为交集型歧义。一般地,如果汉字串 AJB 满足 AJ 和 JB 同时为词,则称 AJB 为交集型切分歧义,其中 J 被称为交集串。除此之外,还有一种歧义称为组合型歧义。例如,对于词语“起身”,在语境“他站/起/身/来”应该切分开;而在语境“他/明天/起身/去/北京”则不应该被切分开。一般地,如果汉字串 AB 满足 A,B,AB 同时为词,则称 AB 为组合型切分歧义。

2. 基于匹配的分词算法

基于匹配的分词算法,也被称为 基于词典的分词算法 ,或者简单地称作是“ 查词典 ”。顾名思义,其基本的思想就是不断找出句子中的字符串,然后去字典查找该字符串是否在字典内:如果在字典内则匹配成功,切出该词;否则,减小字符串长度,继续查找,直到是单个汉字为止。

根据对句子扫描方向的不同,基于匹配的算法可以分为 前向匹配算法  后向匹配算法  双向匹配算法 三种,下面分别进行介绍。

2.1 前向最大匹配算法

前向最大匹配算法(Forward Maximum Match, FMM)的基本思想是,从左至右扫描语句中的子串,如果子串在字典中,则匹配成功,切出该词;否则减少子串的长度,继续查找,直到子串是单个汉字为止(单个汉字被认为总是在字典中)。具体步骤如下:

  1. 设字典中最长词的长度为 MAX_L;当前匹配长度 L = MAX_L;当前带切分语句等于整个语句,即 S = Sentence;当前切分结果的集合 Res = {};

  2. 取 S = C1C2C3…CL…Cn 的前 L 个字符,在字典中查找 C1C2C3…CL 是否为合法词语,如果找到,则匹配成功,转入4;

  3. 如果字典中找不到词语 C1C2C3…CL,则匹配失败;将匹配串长度减去1,即 L = L – 1,转入2继续尝试匹配;重复2-3直到匹配为止;

  4. 将匹配串 C1C2C3…CL 放入结果集 Res 中,即 Res = Res + C1C2C3…CL;更新句子 S = C{L+1}C{L+2}…Cn;如果带切分句子 S 为空,则返回切分结果 Res,算法结束;否则转入2。

根据上述算法描述,Python 实现为:

def ForwardMaximumMatch(sentence, word_dict, max_word_length):
""" 中文分词的最大前向匹配算法
"""
s = sentence
segment_result = []

while s:
    # 当前句子非空,按照最大长度切出一个词
    match_len = max_word_length
    match_len = min(match_len, len(s))

    while True:
        # 按照当前长度切出一个词
        word = s[0:match_len]
        # 如果当前切出的词在字典中,注意:单个汉字被认为总是在字典中
        # 则切走当前词,并更新s,进行下一轮的切分
        if len(word) == 1 or word in word_dict:
            word = s[0:match_len]
            segment_result.append(word)
            s = s[match_len:]
            break
        # 否则,如果当前切出的词不在字典中,则减小切分长度,重新尝试切分
        else:
            match_len = match_len - 1

return segment_result

为了测试算法的效果,笔者以搜狗实验室的互联网词库(SogouW)作为词典 ,设最大词长为6,对朱自清的《背影》进行了中文分词,其结果如下:

我与/父亲/不/相见/已/二年/余/了/,/我/最不/能/忘记/的是/他的背影/。/那年/冬天/,/祖母/死了/,/父亲/的/差使/也/交/卸/了/,/正是/祸不单行/的/日子/,/我/从/北京/到/徐州/,/打算/跟着/父亲/奔丧/回家/。/到/徐州/见着/父亲/,/看见/满/院/狼藉/的/东西/,/又/想起/祖母/,/不禁/簌簌/地/流下/眼泪/。/父亲/说/,/“/事已/如此/,/不必/难过/,/好在/天/无/绝/人/之路/!/” 回家/变卖/典/质/,/父亲/还了/亏空/;/又/借钱/办了/丧事/。/这些日子/,/家中/光景/很/是/惨淡/,/一半/为了/丧事/,/一半/为了/父亲/赋闲/。/丧事/完毕/,/父亲/要到/南京/谋事/,/我也要/回/北京/念书/,/我们/便/同行/。 到/南京/时/,/有/朋友/约/去/游逛/,/勾留/了/一日/;/第二日/上午/便/须/渡江/到/浦/口/,/下午/上车/北去/。/父亲/因为/事/忙/,/本已/说/定/不送/我/,/叫/旅馆里/一个/熟识/的/茶房/陪我/同去/。/他再/三/嘱咐/茶房/,/甚/是/仔细/。/但他/终于/不放心/,/怕/茶房/不妥/帖/;/颇/踌躇/了/一会/。/其实/我那/年/已/二十岁/,/北京/已/来往/过/两三次/,/是/没有/甚么/要紧/的/了/。/他/踌躇/了/一会/,/终于/决定/还是/自己/送我/去/。/我/两三/回/劝他/不必/去/;/他只/说/,/“/不要紧/,/他们/去/不好/!/” 我们/过了/江/,/进了/车站/。/我买/票/,/他/忙着/照看/行李/。/行李/太多了/,/得/向/脚夫/行/些/小费/,/才可/过去/。/他便/又/忙着/和他/们/讲价钱/。/我那/时/真是/聪明/过分/,/总/觉/他说/话/不大/漂亮/,/非/自己/插嘴/不可/。/但他/终于/讲/定了/价钱/;/就送/我上/车/。/他给/我/拣/定了/靠/车门/的/一张/椅子/;/我将/他给/我做/的/紫/毛/大衣/铺好/坐位/。/他/嘱/我/路上/小心/,/夜里/警醒/些/,/不要/受凉/。/又/嘱托/茶房/好好/照应/我/。/我心里/暗笑/他的/迂/;/他们/只认/得/钱/,/托/他们/直/是/白/托/!/而且/我这/样/大年/纪/的人/,/难道/还不能/料理/自己/么/?/唉/,/我现在/想想/,/那时/真是太/聪明/了/! 我说道/,/“/爸爸/,/你走/吧/。/”/他/望/车外/看了看/,/说/,/“/我买/几个/橘子/去/。/你就/在此/地/,/不要走/动/。/”/我看/那边/月台/的/栅栏/外/有几个/卖东西/的/等着/顾客/。/走到/那边/月台/,/须/穿过/铁道/,/须/跳下去/又/爬上去/。/父亲/是一个/胖子/,/走过去/自然/要/费事/些/。/我本/来/要去/的/,/他不/肯/,/只好/让他/去/。/我看见/他戴着/黑/布/小/帽/,/穿着/黑/布/大马/褂/,/深/青/布/棉/袍/,/蹒跚/地走/到/铁道/边/,/慢慢/探身/下去/,/尚不/大/难/。/可是他/穿过/铁道/,/要/爬上/那边/月台/,/就不/容易/了/。/他用/两手/攀/着/上面/,/两脚/再向/上/缩/;/他/肥胖/的/身子/向左/微/倾/,/显出/努力/的/样子/。/这时/我看见/他的背影/,/我的/泪/很快/地/流下/来了/。/我赶紧/拭/干了/泪/,/怕他/看见/,/也/怕/别人/看见/。/我再/向外/看时/,/他已/抱了/朱红/的/橘子/望/回/走了/。/过/铁道/时/,/他先/将/橘子/散/放在/地上/,/自己/慢慢/爬下/,/再/抱起/橘子/走/。/到/这边/时/,/我赶紧/去/搀/他/。/他和/我走/到/车上/,/将/橘子/一股脑儿/放在/我的/皮大衣/上/。/于是/扑扑/衣/上/的/泥土/,/心里/很/轻松/似/的/,/过/一会/说/,/“/我走了/;/到/那边/来信/!/”/我/望着他/走出去/。/他走/了/几步/,/回过/头/看见/我/,/说/,/“/进去/吧/,/里边/没人/。/”/等他/的/背影/混入/来来往往/的人/里/,/再找/不着/了/,/我便/进来/坐下/,/我的眼泪/又来了/。 近几年来/,/父亲/和我/都是/东奔西走/,/家中/光景/是/一日/不如/一日/。/他/少年/出外/谋生/,/独力/支持/,/做/了/许多/大事/。/那知/老/境/却/如此/颓唐/!/他/触目伤怀/,/自然/情/不能自已/。/情/郁/于/中/,/自然/要/发/之于/外/;/家庭/琐屑/便往/往/触/他/之/怒/。/他/待我/渐渐/不同/往日/。/但/最近/两年/的/不见/,/他/终于/忘却/我的/不好/,/只是/惦记/着/我/,/惦记/着/我的/儿子/。/我/北/来/后/,/他写/了/一/信/给我/,/信中/说道/,/“/我/身体/平安/,/惟/膀子/疼痛/利害/,/举/箸/提笔/,/诸多/不便/,/大约/大/去/之/期/不远/矣/。/”/我读/到此/处/,/在/晶莹/的/泪光/中/,/又/看见/那/肥胖/的/,/青/布/棉/袍/,/黑/布/马褂/的/背影/。/唉/!/我不/知/何时/再/能与/他/相见/!

可以看到,总体来说,FMM 算法的分词效果还是可以的。然而也存在一些问题,首先对于未登录词不友好,例如“/第二日/上午/便/须/渡江/到/浦/口”,其中“浦口”应该是一个词,然而 FMM 算法并未识别出来。其次,对于交集型歧义不友好,例如:“/总/觉/他说/话/不大/漂亮/”,其中“他说话”可以切分为“他说/话”或者“他/说话”,这里应该是后者,然而由于 FMM 从左至右扫描,导致切分成前者。此外,由于 FMM 也是优先匹配长词,因此对于组合型歧义也不能很好的解决,例如:“他站起身来”将被切分为“他/站/起身/来”,而不是正确的“他/站/起/身/来”。由于以上缺点,FMM算法通常不单独使用,而是与其他算法配合使用。

2.2 后向最大匹配

后向最大匹配算法(Backward Maximum Match, BMM)前向最大匹配 FMM 基本相同,唯一不同的是,后向最大匹配 BMM 按照从右至左的顺序扫描并切词。该算法的提出是因为人们发现,汉语通常将要描述的主体对象放置在句子后面。BMM 的分词效果通常比 FMM 要好,FMM 的错误切分率为 1 / 169,而 BMM 的错误切分率仅为 1 / 245 [1]。举个例子:“南京市长江大桥”,FMM 的输出为“南京/市长/江/大桥”,而 BMM 的输出为“南京/市/长江大桥”,后者的切分更加合理。BMM 的 Python 实现为:

def BackwardMaximumMatch(sentence, word_dict, max_word_length):
""" 中文分词的最大后向匹配算法
"""
s = sentence
segment_result = []

while s:
    match_len = max_word_length
    match_len = min(match_len, len(s))

    while True:
        # 从右至左切出最大匹配词
        word = s[-match_len:]
        # 如果当前词在词典内,则切出最右边的词,并更新带切词句子s
        if len(word) == 1 or word in word_dict:
            segment_result.append(word)
            s = s[0:-match_len]
            break
        # 否则,当前词不再词典内,则减少匹配长度,继续尝试切分
        else:
            match_len = match_len - 1

# 由于是自右至左切词,需要对列表进行反转
segment_result.reverse()

return segment_result

2.3 双向最大匹配

双向匹配(Bi-direction Matching,BM)算法就是对一个句子同时用 FMM 和 BMM 进行切分,然后加入一些人工规则消歧以期得到较好的分词效果。

Sun M.S. 和 Benjamin K.T.(1995)的研究表明,中文中 90.0% 左右的句子,正向最大匹配法和逆向最大匹配法完全重合且正确,只有大概 9.0% 的句子两种切分方法得到的结果不一样,但其中必有一个是正确的(歧义检测成功),只有不到 1.0% 的句子,或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的,或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对(歧义检测失败)。这正是双向匹配法在实用中文信息处理系统中得以广泛使用的原因所在。这里我们定义如下简单的规则:

  1. 如果 FMM 和 BMM 切分结果相同,直接输出任意一个结果;

  2. 如果 FMM 和 BMM 的切分结果不同:

  3. a) 如果非词典词个数不同,则选取非词典词个数少的切分结果;

    b) 如果非词典词个数相同,选择单字词个数少的切分结果;

    c) 如果单字词个数相同,选择总词数少的切分结果;

    d) 以上都相同,返回 BMM 的切分结果。

Python 代码实现为

def BiDirectionMatching(sentence, word_dict, max_word_length):
    """ 中文分词的双向匹配算法
    """
    FMM_res = ForwardMaximumMatch(sentence, word_dict, max_word_length)
    BMM_res = BackwardMaximumMatch(sentence, word_dict, max_word_length)

    FMM_in_dict = []
    FMM_not_in_dict = []
    FMM_single = []
    for word in FMM_res:
        if len(word) == 1:
            FMM_single.append(word)
        else:
            if word in word_dict:
                FMM_in_dict.append(word)
            else:
                FMM_not_in_dict.append(word)

    BMM_in_dict = []
    BMM_not_in_dict = []
    BMM_single = []
    for word in BMM_res:
        if len(word) == 1:
            BMM_single.append(word)
        else:
            if word in word_dict:
                BMM_in_dict.append(word)
            else:
                BMM_not_in_dict.append(word)

    same_res = True
    if len(FMM_res) != len(BMM_res):
        same_res = False
    else:
        for i in range(len(FMM_res)):
            if FMM_res[i] != BMM_res[i]:
                same_res = False
                break
    # 1. FMM 和 BMM 结果完全相同,返回任意一个
    if same_res == True:
        return FMM_res
    # 2. 返回不在词典中词数少的那个结果
    elif len(FMM_not_in_dict) != len(BMM_not_in_dict):
        if len(FMM_not_in_dict) < len(BMM_not_in_dict):
            return FMM_res
        else:
            return BMM_res
    # 3. 返回单字词数少的结果 
    elif len(FMM_single) != len(BMM_single):
        if len(FMM_single) < len(BMM_single):
            return FMM_res
        else:
            return BMM_res
    # 4. 都相同,返回 BMM 的结果
    else:
        return BMM_res

原文网址:http://xinfengli.me/post/Chinese-word-segment/

本文地址:http://chenxm.cc/post/451.html
版权声明:本文为原创文章,版权归 Pala 所有,欢迎分享本文,转载请保留出处!