漫话中文自动分词和语义识别(上):中文分词算法

    记得第一次了解中文分词算法是在 Google 黑板报 上看到的,当初看到那个算法时我彻底被震撼住了,想不到一个看似不可能完成的任务竟然有如此神奇巧妙的算法。最近在詹卫东老师的《中文信息处理导论》课上再次学到中文分词算法,才知道这并不是中文分词算法研究的全部,前前后后还有很多故事可讲。在没有建立统计语言模型时,人们还在语言学的角度对自动分词进行研究,期间诞生了很多有意思的理论。

    中文分词的主要困难在于分词歧义。“结婚的和尚未结婚的”,应该分成“结婚/的/和/尚未/结婚/的”,还是“结婚/的/和尚/未/结婚/的”?人来判断很容易,要交给计算机来处理就麻烦了。问题的关键就是,“和尚未”里的“和尚”也是一个词,“尚未”也是一个词,从计算机的角度看上去,两者似乎都有可能。对于计算机来说,这样的分词困境就叫做“交集型歧义”。

    有时候,交集型歧义的“歧义链”有可能会更长。“中外科学名著”里,“中外”、“外科”、“科学”、“学名”、“名著”全是词,光从词库的角度来看,随便切几刀下去,得出的切分都是合理的。类似的例子数不胜数,“提高产品质量”、“鞭炮声响彻夜空”、“努力学习语法规则”等句子都有这样的现象。在这些极端例子下,分词算法谁优谁劣可谓是一试便知。


    最简单的,也是最容易想到的自动分词算法,便是“最大匹配法”了。也就是说,从句子左端开始,不断匹配最长的词(组不了词的单字则单独划开),直到把句子划分完。算法的理由很简单:人在阅读时也是从左往右逐字读入的,最大匹配法是与人的习惯相符的。而在大多数情况下,这种算法也的确能侥幸成功。不过,这种算法并不可靠,构造反例可以不费吹灰之力。例如,“北京大学生前来应聘”本应是“北京/大学生/前来/应聘”,却会被误分成“北京大学/生前/来/应聘”。

    维护一个特殊规则表,可以修正一些很机械的问题,效果相当不错。例如,“不可能”要划分成“不/可能”,“会诊”后面接“断”、“疗”、“脉”、“治”时要把“会”单独切出,“的确切”后面是抽象名词时要把“的确切”分成“的/确切”,等等。

    还有一个适用范围相当广的特殊规则,这个强大的规则能修正很多交集型歧义的划分错误。首先我们要维护一个一般不单独成词的字表,比如“民”、“尘”、“伟”、“习”等等;这些字通常不会单独划出来,都要跟旁边的字一块儿组成一个词。在分词过程中时,一旦发现这些字被孤立出来,都重新考虑它与前面的字组词的可能。例如,在用最大匹配法切分“为人民服务”时,算法会先划出“为人”一词,而后发现“民”字只能单独成词了。查表却发现,“民”并不能单独划出,于是考虑进行修正——把“为人”的“人”字分配给“民”字。巧在这下“为”和“人民”正好都能成词,据此便可得出正确的划分“为/人民/服务”。

 
    不过,上述算法归根结底,都是在像人一样从左到右地扫描文字。为了把问题变得更加形式化,充分利用计算机的优势,我们还有一种与人的阅读习惯完全不同的算法思路:把句子作为一个整体来考虑,从全局的角度评价一个句子划分方案的好坏。设计自动分词算法的问题,也就变成了如何评估分词方案优劣的问题。最初所用的办法就是,寻找词数最少的划分。注意,每次都匹配最长的词,得出的划分不见得是词数最少的,错误的贪心很可能会不慎错过一些更优的路。因而,在有的情况下,最少词数法比最大匹配法效果更好。若用最大匹配法来划分,“独立自主和平等互利的原则”将被分成“独立自主/和平/等/互利/的/原则”,一共有 6 个词;但词数更少的方案则是“独立自主/和/平等互利/的/原则”,一共只有 5 个词。

    当然,最少词数法也会有踩大便的时候。“为人民办公益”的最大匹配划分和最少词数划分都是“为人/民办/公益”,而正确的划分则是“为/人民/办/公益”。同时,很多句子也有不止一个词数最少的分词方案,最少词数法并不能从中选出一个最佳答案。不过,把之前提到的“不成词字表”装备到最少词数法上,我们就有了一种简明而强大的算法:

    对于一种分词方案,里面有多少词,就罚多少分;每出现一个不成词的单字,就加罚一分。最好的分词方案,也就是罚分最少的方案。

    这种算法的效果出人意料的好。“他说的确实在理”是一个很困难的测试用例,“的确”和“实在”碰巧也成词,这给自动分词带来了很大的障碍。但是“确”、“实”、“理”通常都不单独成词的,因此很多切分方案都会被扣掉不少分:

      他/说/的/确实/在理 (罚分:1+1+1+1+1 = 5 )
      他/说/的确/实/在理 (罚分:1+1+1+2+1 = 6 )
      他/说/的确/实在/理 (罚分:1+1+1+1+2 = 6 )

    正确答案胜出。

    需要指出的是,这个算法并不需要枚举所有的划分可能。整个问题可以转化为图论中的最短路径问题,利用动态规划效率则会更高。

    算法还有进一步加强的余地。大家或许已经想到了,“字不成词”有一个程度的问题。“民”是一个不成词的语素,它是绝对不会单独成词的。“鸭”一般不单独成词,但在儿歌童谣和科技语体中除外。“见”则是一个可以单独成词的语素,只是平时我们不常说罢了。换句话说,每个字成词都有一定的概率,每个词出现的频率也是不同的。

    何不用每个词出现的概率,来衡量分词的优劣?于是我们有了一个更标准、更连续、更自动的改进算法:先统计大量真实语料中各个词出现的频率,然后把每种分词方案中各词的出现概率乘起来作为这种方案的得分。利用动态规划,不难求出得分最高的方案。

    以“有意见分歧”为例,让我们看看最大概率法是如何工作的。查表可知,在大量真实语料中,“有”、“有意”、“意见”、“见”、“分歧”的出现概率分别是 0.0181 、 0.0005 、 0.0010 、 0.0002 、 0.0001 ,因此“有/意见/分歧”的得分为 1.8×10-9 ,但“有意/见/分歧”的得分只有 1.0×10-11 ,正确方案完胜。

    这里的假设是,用词造句无非是随机选词连在一块儿,是一个简单的一元过程。显然,这个假设理想得有点不合理,必然会有很多问题。考虑下面这句话:

      这/事/的确/定/不/下来

    但是概率算法却会把这个句子分成:

      这/事/的/确定/不/下来

    原因是,“的”字的出现概率太高了,它几乎总会从“的确”中挣脱出来。

    其实,以上所有的分词算法都还有一个共同的大缺陷:它们虽然已经能很好地处理交集型歧义的问题,却完全无法解决另外一种被称为“组合型歧义”的问题。所谓组合型歧义,就是指同一个字串既可合又可分。比如说,“个人恩怨”中的“个人”就是一个词,“这个人”里的“个人”就必须拆开;“这扇门的把手”中的“把手”就是一个词,“把手抬起来”的“把手”就必须拆开;“学生会宣传部”中的“学生会”就是一个词,“学生会主动完成作业”里的“学生会”就必须拆开。这样的例子非常多,“难过”、“马上”、“将来”、“才能”、“过人”、“研究所”、“原子能”都有此问题。究竟是合还是分,还得取决于它两侧的词语。到目前为止,所有算法对划分方案的评价标准都是基于每个词固有性质的,完全不考虑相邻词语之间的影响;因而一旦涉及到组合型歧义的问题,最大匹配、最少词数、概率最大等所有策略都不能实现具体情况具体分析。

    于是,我们不得不跳出一元假设。此时,便有了那个 Google 黑板报上提到的统计语言模型算法。对于任意两个词语 w1 、 w2 ,统计在语料库中词语 w1 后面恰好是 w2 的概率 P(w1, w2) 。这样便会生成一个很大的二维表。再定义一个句子的划分方案的得分为 P(∅, w1) · P(w1, w2) · … · P(wn-1, wn) ,其中 w1, w2, …, wn 依次表示分出的词。我们同样可以利用动态规划求出得分最高的分词方案。这真是一个天才的模型,这个模型一并解决了词类标注、语音识别等各类自然语言处理问题。

    至此,中文自动分词算是有了一个漂亮而实用的算法。

 
 
    但是,随便拿份报纸读读,你就会发现我们之前给出的测试用例都太理想了,简直就是用来喂给计算机的。在中文分词中,还有一个比分词歧义更令人头疼的东西——未登录词。中文没有首字母大写,专名号也被取消了,这叫计算机如何辨认人名地名之类的东西?最近十年来,中文分词领域都在集中攻克这一难关。

    在汉语的未定义词中,中国人名的规律是最强的了。根据统计,汉语姓氏大约有 1000 多个,其中“王”、“陈”、“李”、“张”、“刘”五大姓氏的覆盖率高达 32% ,前 400 个姓氏覆盖率高达 99% 。人名的用字也比较集中,“英”、“华”、“玉”、“秀”、“明”、“珍”六个字的覆盖率就有 10.35% ,最常用的 400 字则有 90% 的覆盖率。虽然这些字分布在包括文言虚词在内的各种词类里,但就用字的感情色彩来看,人名多用褒义字和中性字,少有不雅用字,因此规律性还是非常强的。根据这些信息,我们足以计算一个字符串能成为名字的概率,结合预先设置的阈值便能很好地识别出可能的人名。

    可是,如何把人名从句子中切出来呢?换句话说,如果句中几个连续字都是姓名常用字,人名究竟应该从哪儿取到哪儿呢?人名以姓氏为左边界,相对容易判定一些。人名的右边界则可以从下文的提示确定出来:人名后面通常会接“先生”、“同志”、“校长”、“主任”、“医生”等身份词,以及“是”、“说”、“报道”、“参加”、“访问”、“表示”等动作词。

    但麻烦的情况也是有的。一些高频姓氏本身也是经常单独成词的常用字,例如“于”、“马”、“黄”、“常”、“高”等等。很多反映时代性的名字也是本身就成词的,例如“建国”、“建设”、“国庆”、“跃进”等等。更讨厌的就是那些整个名字本身就是常用词的人了,他们会彻底打乱之前的各种模型。如果分词程序也有智能的话,他一定会把所有叫“高峰”、“汪洋”的人拖出去斩了;要是听说了有人居然敢叫“令计划”,估计直接就崩溃了。

    还有那些恰好与上下文组合成词的人名,例如:

     费孝通向人大常委会提交书面报告
     邓颖超生前使用过的物品

    这就是最考验分词算法的句子了。

    相比之下,中国地名的用字就分散得多了。北京有一个地方叫“臭泥坑”,网上搜索“臭泥坑”,第一页全是“臭泥坑地图”、“臭泥坑附近酒店”之类的信息。某年《重庆晨报》刊登停电通知,上面赫然印着“停电范围包括沙坪坝区的犀牛屙屎和犀牛屙屎抽水”,读者纷纷去电投诉印刷错误。记者仔细一查,你猜怎么着,印刷并无错误,重庆真的就有叫“犀牛屙屎”和“犀牛屙屎抽水”的地方。

    好在,中国地名数量有限,这是可以枚举的。中国地名委员会编写了《中华人民共和国地名录》,收录了从高原盆地到桥梁电站共 10 万多个地名,这让中国地名的识别便利了很多。

    真正有些困难的就是识别机构名了,虽然机构名的后缀比较集中,但左边界的判断就有些难了。更难的就是品牌名了。如今各行各业大打创意战,品牌名可以说是无奇不有,而且经常本身就包含常用词,更是给自动分词添加了不少障碍。

    最难识别的未登录词就是缩略语了。“高数”、“抵京”、“女单”、“发改委”、“北医三院”都是比较好认的缩略语了,有些缩略语搞得连人也是丈二和尚摸不着头脑。你能猜到“人影办”是什么机构的简称吗?打死你都想不到,是“人工影响天气办公室”。

    汉语中构造缩略语的规律很诡异,目前也没有一个定论。初次听到这个问题,几乎每个人都会做出这样的猜想:缩略语都是选用各个成分中最核心的字,比如“安全检查”缩成“安检”,“人民警察”缩成“民警”等等。不过,反例也是有的,“邮政编码”就被缩成了“邮编”,但“码”无疑是更能概括“编码”一词的。当然,这几个缩略语已经逐渐成词,可以加进词库了;不过新近出现的或者临时构造的缩略语该怎么办,还真是个大问题。

    说到新词,网络新词的大量出现才是分词系统真正的敌人。这些新词汇的来源千奇百怪,几乎没有固定的产生机制。要想实现对网络文章的自动分词,目前来看可以说是相当困难的。革命尚未成功,分词算法还有很多进步的余地。

89 条评论

  • Liana

    沙发+膜拜中文系大牛

  • error 404

    文科生geek真可怕!

  • biohu

    希望M牛以后多发一些这类科普文章

  • morrowind

    让Google翻译来翻译一下这篇文章,不知道准确度如何,嘿嘿。

  • Milo

    這種統計方式應該稱為bigram。
    http://en.wikipedia.org/wiki/Bigram

  • bones7456

    人影办 这种人都分不出的词,就不要折腾了吧,说明本身就不该作为一个词。

  • 路人

    毕业论文就是做中文搜索引擎。
    现在常用的是从左到右最大匹配和从右到左反向最大匹配的结合算法,取分词最小的一个结果。分词数相同时取反向最大匹配。因为中文往往倾向以单词结束句子而不是单字。
    不过单纯的中文分词和语义识别还是区别很大的,例如统计分词法就不能用来做语义识别……

  • sgd

    马尔可夫链

  • Fandy Wang

    发现我们的LTP(http://ir.hit.edu.cn/demo/ltp/)处理上面提到的两个句子还是没问题的。网路新词可否通过百科这种UGC自动丰富呢?!(当然,不是直接爬取加入词表就行的,还要验证其质量,可信程度,如紧密度,频率!)

  • 路人

    哈工大在中文处理方面的研究很丰富阿,有很多值得参考的资料。
    应该可以直接把百科的条目抓取下来丰富语料库。

  • aijisud

    正在学习《自然语言处理》…
    表示可能遇到这样的的算法…

  • xslidian

    试试 Chrome 的分词(双击文字自动选中词语) 还挺准的…
    最麻烦的就是网络上的语料…

  • 丕子

    用过中科院那个 还有庖丁解牛那个

  • shizhao

    人名地名这么难办,倒不如建议国家恢复专名号的使用….天朝的行政力多强大啊。。。

  • 大浆糊

    逆向最大匹配其实算是基础算法里比较好的
    未登录词的问题, 工业界通过算法来做的好像没什么动静, 通过集体智慧的方式积累语料, 快速添加新词, 工业界都这么折腾. 各大公司都在做输入法软件, 搜索引擎的检索词什么的也是发现新词的好语料.

  • wincss

    人影办。。。从我第一次看见这个词就深刻记在我心中了

  • 文雨

    数学之美与浪潮之巅 google的一个研究员写的,忘了是不是从这里看到的,非常不错的文章

  • Maigo

    我最近正在做一个日语注音的项目,结果发现分词也成问题。尤其是人名地名神马的。我用的训练集的注音也基本是软件生成的,修订人名地名的时候还得一个一个地去考证…

  • Maigo

    我最近在做一个日语注音的项目,发现分词也成问题,尤其是人名地名神马的。要命的是,我用的训练集的注音也是软件生成的,修订人名地名的时候还得一个个去考证…

  • Maigo

    日本外交部长原一也说,南京市长江大桥神马的最讨厌了…

  • multiple1902

    向前輩致敬。我終于走進這一塊了。

  • Fleeting Years

    @xslidian :chrome应该是内置了一个中文词表的。

  • MCKelvin

    这里有个蛮不错的 一个中文语言处理系统项目。http://code.google.com/p/nlpbamboo/

  • 碳碳

    “山木因为强奸门而被迫辞职”
    ——这人这么还会去强奸门啊
    “佟大为妻子生下一名女婴”
    ——佟大是谁,这么厉害!

  • Jeff

    @multiple1902: 在这看到学长了……

  • kkcocogogo

    有什么实际用途
    语音识别?

  • 御手洗破

    M67牛又发现了有趣的东西啊……
    云计算来统计如何呢?虽然我不知道具体是什么意思……

  • 噗哧

    已取得文凭的和尚/未取得文凭的干部
    梁启/超生前/住在这里
    阿拉斯加遭强暴/风雪袭击致XX人死亡
    巴塞罗/那一场大雪
    武汉市长/江大桥
    杭州市长/春药店
    今后三年/中将/翻两番
    乒乓球/拍卖完了
    粮食不卖/给八路军
    台湾国/中学生
    三大全国/性交易/市场布局渝中
    一次/性生活/补助
    一次/性交/纳百元
    西哈努克亲/王八日到京
    人的正确思想是从天上掉下来的--(翻页)--吗?

  • LostAbaddon

    我在想一件事情,中文划词里面是否可以引入这样的机制:
    1,找出动词;
    2,找出这个动词之后可以跟那些适配的名词、形容词和副词,这里一般可以分为三种:1,动+名副;2,动+名+副;3,名副+动。
    3,找出这个动词之后与之前的适配词,如果能找到则表示这的确是一个动词,如果不能那就表示这要么是划分错误,要么就是人名。

    比如“他说的确实在里”,如果将“说”当作是一个动词,那么后面要么是名词,要么是副词,而且也不是所有副词都适合修饰“说”。而在这个句子中,“说”后面跟着的是“的确”前面是“他”,但“的确”作为后置副词的时候是不能用来修饰“说”的,除非是前置副词,所以这里“说”就不是一个合格的动词,划分错误,只能划分“说的”,是一个名词。
    还比如“费孝通向人大常委会提交书面报告”,可以划分为“费孝”“通向”“人大常委会”“提交”“书面报告”,但“通向”作为动词且后置是一个名词的时候,第三部分跟的就不能是动词“提交”,所以不能将“通向”看作是一个动词来用。而“向”作为动词,其后跟一个名词的时候第三部分可以是动词也可以是名词,所以符合要求,这么一来“费孝通”就只能是名字了。
    “邓颖超生前使用过的物品”也是如此,“超生”作为动词的话,后置副词不可能是“前”,一般都说“XXX永不超生”,没说超生还分前后的。当然,这里就要引入一定的使用概率了。
    当然,这样的做法似乎对于“一次性生活补助”是没啥作用的,因为也的确可能出现“一次”“性生活”“补助”的用法,而“佟大为妻子生下一名女婴”这个没话说,这种用法的确有,而且如果一个正常人类不知道栋大为这个人的话,也的确会想:咋还有为妻子生孩子的男人?

  • nova2358

    现在中文分词工具一般都用CRF来做吧,效果算是比较好的。基本都拿统计方法来做了。
    未登录词OOV的确是很头疼的,许多新生的词“飞信”这样的,往往都是别不出来。不知道通过动态的更新词典能否解决这个问题。

  • Mystery

    用谷歌输入法的飘过

  • LLP

    很有意思~膜拜M大牛~

  • yh

    看ls各位的讨论表示
    1.看来这东西,好的算法必须要用概率。。
    2.人应该是同时进行分词和语法解析的,不太可能不考虑语法就特别好的完成分词。。。

  • 熊猫

    第一次来,这个网站很好。很多有用有趣新奇的东东

  • naeioi

    学问是经验的积累,才能是刻苦的忍耐——矛盾
    这句挂在教室墙上的话容易把“才能”分成连词。不只是计算机,好几个同学都理解错了

  • gestapolur

    好久没有看到神牛写计算语言学的东西了

  • yichya

    看完觉得,英语是多么简洁实用,空格,和人名首字母大写,还有主要动词的单一含义,可比不上中文,不仅意义多变,而且很难理解,甚至有时,你都不知道怎么断句。

  • 六翼

    主要动词的“单一含义”??您是在反讽吗?get make take do,这些算“主要动词”么…………

  • 棕发少女

    说实话,每次我都想从第一个字看到最后一个,可无一例外到中段就放弃了,实在超出我脑力范围。这篇和情人节那篇除外。

  • 棕发少女

    气味图书馆,emoi的绿色杯垫,土豆泥,社交网络,黄酒,荤豆花,海扁王,酷圣石,徒步旅行,黄金蟹粉包,雷朋,约伯记,禁闭岛,扭蛋,福尔摩斯,绿皮火车,磨牙,无名指,G-STAR,窃听风云,林夕,粉色T恤,天生杀人狂,陶渊明,嫩牛五方,偶遇,就让这首歌,私奔,南方周末,芒果蛋挞,鬼子来了,搏击俱乐部,黑森林,黑涩会美眉,十四行诗,故弄玄虚,冬眠,港口,不见不散。
    这些我也很喜欢。

  • yichya

    嘿嘿,又是我。不要鄙视我啊,我只是一个语文非常烂的高中生:)

    仅仅到现在我就觉得中文非常不爽了,各种多音字还有些根本不知道怎么写出来的字很让我不爽。

  • hcz

    这句可供测试:逃得了和尚未必逃得了庙

  • pwstudio

    现在做统计的有两类方法较常见:字在词语中的位置信息;字与字之间是否切分的信息;当然都要考虑上下文信息。但机器学习方法耗费资源巨大,没投入使用。

  • jor30cn

    分词其实就是一种量化的过程。中文词语是一个模糊笼统的概念,就像拿一个没有规则的烧杯去计量信息流中的水,一则无法准确计算,二则所得结果毫无意义!英语天生就人为分词,而中文没有,两者相应的语法体系应该不相同。不要说分词,先弄清好汉语到底有多少字更有实际意义。

  • 悲伤的采购

    “汉语中构造缩略语的规律很诡异,目前也没有一个定论”

    “人影办”这种傻x缩略现象只会出现在1949年之后的内地,尤其是国家机关。香港澳门台湾海外华人都很难接受“发改委”之类的缩略语,较年长的广东人也不喜欢,虽然他们已近被媒体逼到习惯了

  • COT

    哇,很神奇啊。虽然我只是门外汉,但还是膜拜神牛

  • Mark

    最大匹配、最小词数、最大P,马尔科夫
    交集型、组合型
    规则集、单字词集、未登录词

    学习

  • Mark

    最大匹配、最小词数、最大 P、马尔科夫
    交集型、组合型
    规则表、单字词表、未登录词

    学习!

  • xnnyygn

    亚洲语系(CJK)分词最简单的就单字和双字,一般用前者就可以了,不会影响普通搜索。
    中文语义分词现在具体的也有些,包括LZ提到的那些方法,不过一来性能不佳,二来处理非中文的有问题甚至有BUG,所以不大用。
    上面的用概率分词的和自然语言理解中的有点像了,不过语言理解时还需要一套框架分析语素,词类等,构建语句模型,比较复杂。

  • RaielZ

    感謝科普哪~

  • orbea jersey

    这个说法怎么样呢?

  • Hobbitz

    。。。膜拜!自己的一个项目里直接用了盘古分词的分词组件,想看看中文分词的算法是怎么样的,没想到如此美妙!

  • Ggc

    再来一个:从中学到大学的知识.
    相信很多人都是这么分的:从/中学/到/大学/的/知识
    但还有一种分法:从中/学到/大学/的/知识

  • 负一的平方根

    联网。。。云分词

  • Haley

    – -中文各种歧义…

  • tsa密码锁

    这个好啊~~学习一下中文分词算法,比较复杂啊

  • J. V. King

    非常好的文章,受教了

  • 孙茂胤

    大牛我发现了个问题,比如这两句话:
    -如你果能一下明看白这文段字,说明已你经精错神乱。
    -如你果能这看句懂话,说你明已神错经乱。
    看样子在快速浏览的时候,人确实不是通过匹配词来分词分析语义的,
    望分析!

  • 哲学工作室

    说得很精彩。这么复杂的东西,不经过严格的梳理和分析,不容易写得这么通俗易懂。欢迎热爱搜索引擎的同仁交流。

  • cervelo

    前輩致敬。我終于走進這一塊了。

  • 汽车模拟器

    膜拜大神~中文分词是学习seo的基础啊

  • 亿恩

    楼太高了,终于下来了

  • Y.S

    相信都是概率问题,我觉得这也是人工智能的一部分。哪天我们能够模拟人类的学习能力,相信就能够解决分词问题。

  • 熊熊熊

    人工影响天气 给跪了~

  • qzshadow

    大赞啊!好久没看到这么诙谐的科技小品文了!

  • 忍者罗曼蒂

    这篇轻松导论式的文章将我现在看到的好多问题都串在了一起,而且还有更为丰富的例句,非常有帮助。谢谢,希望看到和输入法研究相关的文章。

  • FOTT陈文超

    点个赞,既幽默有明了

  • 小松

    正在学习中

  • 预言家

    令计划。。。
    真有先见之明

  • Adrian

    这篇文章非常棒!通俗又系统地讲述了语言处理的状况与困难。点赞!

发表评论