记得第一次了解中文分词算法是在 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 万多个地名，这让中国地名的识别便利了很多。
真正有些困难的就是识别机构名了，虽然机构名的后缀比较集中，但左边界的判断就有些难了。更难的就是品牌名了。如今各行各业大打创意战，品牌名可以说是无奇不有，而且经常本身就包含常用词，更是给自动分词添加了不少障碍。
最难识别的未登录词就是缩略语了。“高数”、“抵京”、“女单”、“发改委”、“北医三院”都是比较好认的缩略语了，有些缩略语搞得连人也是丈二和尚摸不着头脑。你能猜到“人影办”是什么机构的简称吗？打死你都想不到，是“人工影响天气办公室”。
汉语中构造缩略语的规律很诡异，目前也没有一个定论。初次听到这个问题，几乎每个人都会做出这样的猜想：缩略语都是选用各个成分中最核心的字，比如“安全检查”缩成“安检”，“人民警察”缩成“民警”等等。不过，反例也是有的，“邮政编码”就被缩成了“邮编”，但“码”无疑是更能概括“编码”一词的。当然，这几个缩略语已经逐渐成词，可以加进词库了；不过新近出现的或者临时构造的缩略语该怎么办，还真是个大问题。
说到新词，网络新词的大量出现才是分词系统真正的敌人。这些新词汇的来源千奇百怪，几乎没有固定的产生机制。要想实现对网络文章的自动分词，目前来看可以说是相当困难的。革命尚未成功，分词算法还有很多进步的余地。
文章转自Matrix67博客，原文地址： http://www.matrix67.com/blog/archives/4212
你可能还喜欢下面这些文章
漫话中文自动分词和语义识别（下）：句法结构和语义结构
这篇文章是漫话中文分词算法的续篇。在这里，我们将紧接着上一篇文章的内容继续探讨下去：如果计算机可以对一句话进行自动分词，它还能进一步整理句子的结构，甚至理解句子的意思吗？这两篇文章的关系十分紧密，因此，我把前一篇文章改名为了《漫话中文自动分词和语义识别（上）》，这篇文章自然就是它的下篇。我已经在很多不同的地方做过与这个话题有关的演讲了，在这里我想把它们写下来，和更多的人一同分享。什么叫做句法结构呢？让我们来看一些例子。“白天鹅在水中游”，这句话是有歧义的，它可能指的是“白天有一只鹅在水中游”，也可能指的是“有一只白天鹅在水中游”。不同的分词方案，产生了不同的意义。有没有什么句子，它的分词方案是
murmur hash，一个更快的hash算法
在打算搭建memcache集群的时候，使用了crc3算法来对key进行hash，然而发现该算法性能比较低，于是寻找一个高性能，低碰撞的hash算，很高兴有前人已经为我们发明了这种算法——murmur。MurmurHash算法：高运算性能，低碰撞率，由Austin Appleby创建于2008年，现已应用到Hadoop、libstdc++、nginx、libmemcached等开源系统。2011年 Appleby被Google雇佣，随后Google推出其变种的CityHash算法。MurmurHash算法，自称超级快的hash算法，是FNV的4-5倍。官方数据如下：OneAtATime – 35
记一次进程异常退出的问题排查
机器搬家之后，之前一直稳定的PHP多进程程序子进程突然异常退出，但是退出的不是很频繁，查看进程日志并也没有发现有什么导致退出的，问题比较诡异。于是开启了一段问题排查之路。首先查看内核日志，使用dmesg，拉到最后发现有一些这样的错误，看来确实是崩溃了。 php: segfault at 7f6443ee18c8 ip 00007f6443ee18c8 sp 00007fff4d4ba818 error 15 in libc-2.17.so php: segfault at 0 ip 000000000075919d sp 00007fff0c6e0578 error 4 in php trap
记录一下使用中PDO出现的一个问题：Cannot execute queries while other unbuffered queries are active. Consider using PDOStatement::fetchAll().
在使用PDO的时候，一条sql语句打死都不执行，dump一下errorInfo试试，出现这样的错误信息问题描述居然告诉我还有语句没有执行完成？当前的查询未能执行，逗我么！考虑使用fetchAll，或者开启缓冲查询，行，你说得对....问题出现的使用场景服务器服务器为linux，安装了一个什么面板套件之类的，不是自家机器，也懒得去折腾，在本地的windows环境并没有该问题。程序笔者在对数据库的一个计数字段进行更新的时候，首先会先查询这个记录是否存在，如果存在则进行更新，如果不存在则先插入。问题就出现在记录不存在的时候，当我查询这条不存在的记录时候，发现这个记录不存在，然后进行插入，发现之前的查
并发任务分配问题
这是在工作中遇到的实际问题和解决过程。问题已经被抽象成并发任务的分配问题。问题如果有 n 组数据均分给 m 个处理器处理，那么每个处理器分到的数据是 。如果n组数据的类型有差异，其中有a组是一类数据，剩余 n-a 组是另一类数据。只有同类数据才能被一次性处理，那么该如何分配？这个问题在现实中是存在的。比如HTTP并发请求处理一些数据。数据被批量送来，但类型不一样。为了节省耗时，我们希望并发处理这些不同的数据。并发数是确定好的。现在需要计算每个请求处理的数量，以便我们能给每一个请求打包数据。求解n 组数据交给 m 个处理器处理，每个处理器最多分到 组数据，这是毫无疑问的。如果 n 组数据中有
mysql varchar类型探秘
mysql中varchar能够存储可变长度的字符串。过去我做的诸多业务中，一般存储短字符串的需求，都会使用varchar类型，并且定义长度为255，也就是varchar(255)。不过为了探究varchar这种类型到底是怎么存储的，它的最大长度能达到多少，我决定区翻一下mysql文档学习一下。varchar怎么存储经过一番了解，varchar最大能存储的长度为65535字节。存储字符串的时候，会将字符串的长度存在首部，接着才是内容。当varchar存储的字符个数小于或等于255的时候，首部需要一个字节来记录字符的个数。当内容大于255的字符的时候，首部需要2个自己来保存长度。varchar能存
一致性哈希的php实现
未来项目可能要上memcache集群，memcache集群的key分配完全在客户端完成，服务端不做任何处理，这里对key进行分配节点的最优方式就是使用一致性哈希。记得以前用mysql进行分库分表的时候，通常会用一个求余作为哈希函数，这样一些id就能对应相应的表了。不过使用mysql的时候，我们不需要考虑这些节点失效问题，以及节点增加或者减少的问题（在此之前应该做好足够的计划和准备），但是对于缓存，通常就比较宽松了，允许节点失效问题，但是普通的hash分配在节点失效之后，大部分的缓存位置都改变了，这显然个灾难，这个时候就要考虑一致性hash了，在增加或者删除节点，只有小部分的key会受影响。一致
utf8编码原理
在我的程序中，基本都使用utf8来编码（除非历史原因，实在是无法转换）。但我用的php在处理中文语言的时候，总显得有些生硬，总感觉没有处理英文那么流畅。比如为什么统计字符的数目要远大于汉字的个数？为什么截断中文乱码？为什么一串英文所组成的字符串可以使用数组的方式访问但是中文字符串为什么就是乱码？等等等等之类的问题。这一切的一切，都是因为对utf8编码不了解所导致的！虽然我们有mb_string这个扩展的对中文有很友好的支持，但对于编码原理，还是需要好好的了解一下。但对于初学者，我想你未必有耐心看完这篇文章，可以跳过直接看程序实例，这篇文章可以作为实例程序的参考作用。
Redis主从模式下从库过期的key仍然能够被读到的解决方案
Redis主从模式下，当对一个key设定过期时间，到期之后从库依然能够读取到数据。这个问题困扰了我很久，相信很多人都遇到过这种问题了。（前提是你不去读主库，并且redis版本在3.2以下）。经过一番搜寻，发现很多人遇到的问题和我一样。主Redissetex test 20 1+OKget test$11ttl test:18从Redisget test$11ttl test:7以上都没问题，然而过几秒再看从Redisttl test:-1get test$11test这个key已经过期了，然而还是可以获取到test的值。在使用Redis做锁的时候，如果直接取读从库的值，这就有大问题了。为什么从
GDB入门：使用bt查看程序出core的调用栈
当程序崩溃的时候，会产生一个core文件。我们可以称它为进程死亡现场。排查进程死亡就和破案一样，找到案发现场，仔细排查每个细节，抽丝剥茧，最终定位原因。很幸运我们有一个强大的工具调查现场信息。这个工具就是GDB。下面我们就来看看如何用GDB排查问题。首先以一个越界访问数组的程序为例，如下：#include #include void core() { std::vector<int> a; std::cout << a;}int main() { core(); return 0;}执行上面的代码将会产生一个core文件。假设我们的core文件为
