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

2014-03-15  来源:本站原创  分类:系统架构  人气:7 

记得第一次了解中文分词算法是在 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 万多个地名,这让中国地名的识别便利了很多。

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

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

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

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

相关文章
  • 漫话中文自动分词和语义识别(上):中文分词算法 2014-03-15

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

  • 漫话中文自动分词和语义识别(下):句法结构和语义结构 2013-12-24

    这篇文章是漫话中文分词算法的续篇.在这里,我们将紧接着上一篇文章的内容继续探讨下去:如果计算机可以对一句话进行自动分词,它还能进一步整理句子的结构,甚至理解句子的意思吗?这两篇文章的关系十分紧密,因此,我把前一篇文章改名为了<漫话中文自动分词和语义识别(上)>,这篇文章自然就是它的下篇.我已经在很多不同的地方做过与这个话题有关的演讲了,在这里我想把它们写下来,和更多的人一同分享. 什么叫做句法结构呢?让我们来看一些例子."白天鹅在水中游",这句话是有歧义的,它可能指的是&q

  • CNNIC李晓东:今年有望用上中文前缀邮件 2013-12-09

    CNNIC副主任李晓东 新浪科技讯 9月24日消息,今天在南京举行的第七届中国互联网大会上,中国互联网络信息中心(CNNIC)副主任李晓东在做客新浪科技现场访谈间时表示,今年有望用上中文前缀邮件,而.中国域名在明年也必将开通. 以下为访谈实录摘选: 主持人马全智:李主任您这次过来参会,主要想跟大家分享哪些方面的话题? 李晓东:一个方面关于中国域名的进展,因为域名的事情是国际组织管理的,我们期望快速开通服务,它将在2009年生效,到时候我们的网民就可以去申请服务了.另外一个事情,是关于中文邮件,这

  • 中文分词算法 之 基于词典的逆向最大匹配算法 2014-03-21

    在之前的博文中介绍了基于词典的正向最大匹配算法,用了不到50行代码就实现了,然后分析了词典查找算法的时空复杂性,最后使用前缀树来实现词典查找算法,并做了3次优化. 下面我们看看基于词典的逆向最大匹配算法的实现,实验表明,对于汉语来说,逆向最大匹配算法比(正向)最大匹配算法更有效,如下代码所示: public static List<String> segReverse(String text){ Stack<String> result = new Stack<>();

  • 中文分词算法 之 词典机制性能优化与测试 2014-03-28

    在之前的两篇博文中文分词算法 之 基于词典的正向最大匹配算法和中文分词算法 之 基于词典的逆向最大匹配算法中,我们对分词实现和词典实现都做了优化,本文对词典实现做进一步优化,并和之前的多个实现做一个对比,使用的词典下载地址,使用的测试文本下载地址. 优化TrieV3的关键在于把虚拟根节点(/)的子节点(词表首字母)提升为多个相互独立的根节点,并对这些根节点建立索引.优化的依据是根节点(词表首字母)的数量庞大,索引查找的速度远远超过二分查找. 下面看看进一步优化后的TrieV4和之前的TrieV3

  • PHP中文处理 中文字符串截取(mb_substr)和获取中文字符串字数 2014-12-12

    PHP中文处理 中文字符串截取(mb_substr)和获取中文字符串字数,需要的朋友可以参考下. 一.中文截取:mb_substr() mb_substr( $str, $start, $length, $encoding ) $str,需要截断的字符串 $start,截断开始处,起始处为0 $length,要截取的字数 $encoding,网页编码,如utf-8,GB2312,GBK 实例: <?php $str='脚本之家:http://www.jb51.net'; echo mb_subs

  • 基于稀疏图上的Johnson算法的详解 2014-10-17

    本篇文章介绍了,稀疏图上的Johnson算法的详解.需要的朋友参考下 算法步骤简述: 1.计算图G加入新结点后的图G',加入的新结点0到所有原结点之间距离为0,同时形成新的边集E': 2.使用Bellman-Ford算法处理G',并形成0结点到各结点的最小距离d. 3.如果Bellman-Ford算法检测出有负权回路则提示FALSE并退出,否则继续. 4.对所有G'中的顶点v,根据0结点到v的最小距离,将h(v)设置为这个值. 5.对所有的边w(u,v),权值更新为w(u,v)+h(u)-h(v

  • 不同浏览器上中文文件名的上传/下载乱码问题 2012-08-12

    浏览器能正确识别的编码格式,只要按照这样的编码来设置对应的Content-Disposition,那么应该就不会出现中文文件名的乱码问题了. 首先,Content-Disposition值可以有以下几种编码格式 1. 直接urlencode: Content-Disposition: attachment; filename="struts2.0%E4%B8%AD%E6%96%87%E6%95%99%E7%A8%8B.chm" 2. Base64编码: Content-Disposit

  • 解决svn在AIX5.3上中文显示成乱码的问题 2009-08-20

    前段时间在AIX5.3上成功安装了svn1.6.3,在svn commit时录入中文信息后,在aix上查看(svn log)时显示正常,但是在windows上查看日志时显示的是乱码.另外在windows上提交中文名的文件或者下载中文名的文件到AIX上时,文件名显示的是乱码. 摸索很久发现svn不同平台间传输用的编码都是UTF8,各个平台展现时用的各自的编码,由于不一致导致展现的是乱码.在AIX上用local可以看到: LANG=english_us.8859 LC_COLLATE="C"

  • 在Hadoop上运行基于RMM中文分词算法的MapReduce程序 2012-01-29

    我知道这个文章标题很"学术"化,很俗,让人看起来是一篇很牛B或者很装逼的论文!其实不然,只是一份普通的实验报告,同时本文也不对RMM中文分 词算法进行研究.这个实验报告是我做高性能计算课程的实验里提交的.所以,下面的内容是从我的实验报告里摘录出来的,当作是我学习hadoop分享出来的 一些个人经验. 实验目标 学习编写 Hadoop 上的 MapReduce 程序. 使用 Hadoop 分布式计算小说<倚天屠龙记>里的中文单词频率,比较张无忌身边的两个女人周芷若与赵敏谁在小

  • 嵌入式Qt方案中文显示系列:应用程序本地中文显示的实现 2013-04-02

    嵌入式Qt应用程序进行中文显示有两种解决方案,一种是直接在代码中使用中文,利用QTextCodec类来实现,另一种是使用qt平台的国际化支持机制,通过语言翻译来实现.第一种方案直接明了,相对来说也简单方便一点,除了编码时麻烦点(来回切换输入法),而第二种方法的优点是具有良好的扩展性,代码中全部使用英文,然后使用中文翻译文件来进行语言翻译,当需要其它语言方案时,只需要添加翻译文件就可以.这里先介绍第一种方案,之后再写第二方案的文章. 方案实现 直接使用中文,利用QTextCodec类来实现中文的显

  • 中文分词算法 之 基于词典的正向最大匹配算法 2014-03-18

    基于词典的正向最大匹配算法(最长词优先匹配),算法会根据词典文件自动调整最大长度,分词的好坏完全取决于词典. 算法流程图如下: Java实现代码如下: /** * 基于词典的正向最大匹配算法 * @author 杨尚川 */ public class WordSeg { private static final List<String> DIC = new ArrayList<>(); private static final int MAX_LENGTH; static{ try

  • 中文分词算法 之 基于词典的正向最小匹配算法 2014-04-04

    在之前的博文中介绍了基于词典的正向最大匹配算法,比如我们切分句子: 中华人民共和国万岁万岁万万岁,使用正向最大匹配算法的切分结果为:[中华人民共和国, 万岁, 万岁, 万万岁],可以看到,切分出来的词是很长的,粒度很粗,如果我们想要切分出很细粒度的词,该怎么办呢? 本文介绍正向最小匹配算法,该算法和正向最大匹配算法相得益彰,一个强调细粒度,一个强调粗粒度. 使用正向最小匹配算法,必须注意的一点是:词典中不能有单字词,词的长度至少为2!我们看正向最小匹配算法和正向最大匹配算法的代码比较: 切分效果

  • 中文分词算法 之 基于词典的逆向最小匹配算法 2014-04-04

    在之前的博文中介绍了基于词典的逆向最大匹配算法,比如我们切分句子: 中华人民共和国万岁万岁万万岁,使用逆向最大匹配算法的切分结果为:[中华人民共和国, 万岁, 万岁, 万万岁],可以看到,切分出来的词是很长的,粒度很粗,如果我们想要切分出很细粒度的词,该怎么办呢? 本文介绍逆向最小匹配算法,该算法和逆向最大匹配算法相得益彰,一个强调细粒度,一个强调粗粒度. 使用逆向最小匹配算法,必须注意的一点是:词典中不能有单字词,词的长度至少为2!我们看逆向最小匹配算法和逆向最大匹配算法的代码比较: 切分效果

  • 如何识别上传前检测的图像是有效的方法 2014-08-05

    看看这个! 如果图像数据是正确的,可以取得高宽 但如果是随便选择其他非web图像文件,则取不到高宽 需要判断当前的selected文件是否为图像? [Ctrl+A 全选 注:如需引入外部Js需刷新才能执行]

  • 三种中文分词算法优劣比较 2011-05-18

    http://blog.csdn.net/liuzongshun/archive/2009/05/27/4216403.aspx

  • 设计模式 分析模式 华容道 中文分词算法...... - 少即是多 - 专注 2012-05-17

    http://www.cnblogs.com/zhenyulu/ http://www.dofactory.com/Patterns/Patterns.aspx

  • xampp本地mysql环境phpmyadmin中文正常但是程序读取时中文问号的解决方法 2014-05-15

    先看下 SHOW VARIABLES LIKE 'CHARACTER_SET_%' 发现有latin1, 于是打开my.ini ## UTF 8 Settings init-connect=\'SET NAMES utf8\' collation_server=utf8_unicode_ci character_set_server=utf8 #skip-character-set-client-handshake #character_sets-dir="/xampp/mysql/share/

  • iteye上的一个算法题目:国王.毒酒.侍卫 2011-04-22

    http://www.iteye.com/topic/1010940 这应该是就是一个二维数组的解,10*10的,呵呵

  • [转发重要论文]顶中区N200: 一个中文视觉词汇识别特有的脑电反应 2012-07-01

    [转发重要论文]顶中区N200: 一个中文视觉词汇识别特有的脑电反应 话说原来一直在等<科学通报>网络版发布本论文,都准备好了花钱下载,没想到作者提供免费版了,太让人高兴了,在这里贴一下,很重要的一个研究成果! http://zhuanti.netbig.com/zhangxuexin/ <科学通报> 语言是人类智力活动的中心, 词汇是语言的基本单位, 研究词汇识别的神经机制对理解思维和人脑信息加工意义重大. 研究发现, 中文读者看到中文词后约 200 毫秒, 以脑顶.中部为中心,