1
最大匹配法（Forward Maximum Matching method, FMM法）：选取包含6-8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从右向左。
逆向最大匹配法（Backward Maximum Matching method, BMM法）：匹配方向与MM法相反，是从左向右。实验表明：对于汉语来说，逆向最大匹配法比最大匹配法更有效。
给定串：我是中国人
从左往右最长匹配优先：
读入‘我’，一个字当然是一个词
再读入‘是’，查表找‘我是’，不在表中，则‘我’是一个独立的词，‘是’还要下一步判断
读入‘中’‘是中’肯定不在表内，那‘是’也是一个独立的词，‘中’还要下一步判断
读入‘果’，‘中国’在表内
再读入‘人’，’中国人‘也在表内，
此时全部读完，’中国人‘是一个次
结果就是：我是中国人
从右往左也类似
最近折腾毕业论文，搞得人没心情写blog了。于是觉得不如把毕业论文里的东西贴出来当blog算了。这里主要介绍了我自己的中文分词算法，我觉得它比现在开源代码比较多的中文匹配法要好多了。这里的内容没有任何背景知识啥的，毕竟论文里的背景知道我也是从网上粘贴的，呵呵！因此这篇文章的内容可能适合做搜索引擎的人。如果要了解中文分词算法在搜索引擎中的重要性，或者最大匹配法的思想与过程，请去网上搜吧，资料还是蛮多的。
1.1.1 最大匹配法分词的缺陷
尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷，这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点：
一、长度限制
由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大匹配法在效率与词长之间的一种妥协。我们来看一下以下两种情况：
（1）词长过短，长词就会被切错。例如当词长被设成5时，也就意味着它只能分出长度为5以下词，例如当这个词为“中华人民共和国”长度为7的词时，我们只能取出其中的5个字去词库里匹配，例如“中华人民共”，显然词库里是不可能有这样的词存在的。因此我们无法下确的划分出“中华人民共和国”这样的词长大于5的词。
（2）词长过长，效率就比较低。也许有人会认为既然5个字无法满足我们的分词要求，何不将词长加大，例如加到10或者100，毕竟这个世界超过100个字长的词还是很少见的，我们的词长问题不就解决了？然而当词长过长时，我们却要付出另一方面的代价：效率。效率是分词算法、甚至是整个算法理论体系的关键，毕竟算法书里所有的高深的查询或排序算法都是从效率出发的，否则任何笨办法都可以解决分词效率低的问题。设想到我们把字长设成100个词时，我们必须将词从100开始一直往下匹配直到找到要查的字为止，而我们大多数词的字长却只有两三个字，这意味着前97次的匹配算法是徒劳的。
因此我们必须要在词长与效率之间进行妥协，既要求分词尽量准确，又要求我们的词长不能太长。尽管我们可能找到这样一个比较优化的字长值使两者都达到比较满足的状态，但是毕竟不管我们怎么设定，总会有些太长词分出来，或者带来效率问题。
二、效率低
效率低是最大匹配法分词必然会来的问题。即使我们可以将字长设成相当短，例如5（注意，我们不能再缩短字长了，毕竟字长为5以上的词太多了，我们不能牺牲分词的准确），然而当我们的大数词长为2时，至少有3次的匹配算法是浪费掉的。回想一下算法书里提到的最简单的字符匹配与KMP算法之间天差地别的效率，我们知道通过某种方法，这些浪费的掉的匹配时间是可以补回来的。
三、掩盖分词歧义
中文是如此复杂的语言，它的表达方式如此之多，语法文法如此精妙，机械的电脑是很难理解这么复杂的语言，因此它必然会带来歧意性，以下是两个简单的例子：
A.“有意见分歧” （正向最大匹配和逆向最大匹配结果不同）
有意/ 见/ 分歧/
有/ 意见/ 分歧/
B.“结合成分子时” （正向最大匹配和逆向最大匹配结果相同）
结合/ 成分/ 子时/由于词的歧义性使我们在使用最大匹配法分词会产生错误的结果，而且使用正向分词与逆向分词往往会产生截然不同的结果。尽管使用回溯法或计算计算词的使用频率，可以使出现歧义的可能性减少，但是我们知道，这样的结果是不可避免的，因为中文的变化实在太多了。
四、最大匹配的并不一定是想要的分词方式
最大匹配法基于的理念是找到最大的匹配词，但有的时候除了最大匹配词外，我们也可能只需要这个词的一部分。例如“感冒解毒胶囊”是一个完整的词，按照最大匹配法我们无法对它进行拆分了，这样我们输入“感冒”的时候就根本搜不到我们需要的词。这是我们需要的吗？做为生产这种药的厂商，它肯定希望用户输入“感冒”甚至“解毒”，我们都能查到对应的内容。
1.2 设计自己的中文分词算法
1.2.1 设计目标
基于对分词算法的理解和对最大匹配法分词的分析，我们知道我们必须提出不同的解决方案，使分词算法的效率、分词的长度限制甚至歧义处理上得到提高。因此我们提出了如下的设计目标：
一、高效
中文分词算法必须要高效，毕竟效率对于搜索引擎的重要性是不言而喻的。而且我们面对的是海量的数据，而不是一篇几百字或几千字的文章，效率的差别的影响可能会使最后运行效率差几个小时甚至几天。因此我希望我们设计的算法一定要比最大匹配法高，毕竟我们已经常看到最大匹配法的很多次匹配都是浪费在无用功上了，肯定有办法把这些浪费的时间节省回来。
二、无长度限制
最大匹配法的长度限制真是很讨厌的事，我们很难找到词长与效率的之间的平衡。为什么我们需要长度的限制？为什么我们不能设计出任何词长的词（只要词库中存在）都可以分出来？
三、歧义包容
我们相信长度限制的问题总是可以解决的，因为虽然长度限制这个问题很难，但是它是有规律可循的，它是严谨的科学。但是当我们碰到中文歧义时，我知道不管我们怎么努力，它仍然是不可能彻底解决的。因为中文实在太博大精深了，即使有极强的人工智能和机器学习功能，这样的错误仍然是难以避免。既然无法避免？我们为什么不换一个角度去考虑？我们为什么不可以将出现歧义的各种可能性都包含进去，作为分词的参考。例如上述的“有意见分歧”的两种分词方法：
有意/ 见/ 分歧/
有/ 意见/ 分歧/
为什么我们不能把这样两种结果都拿来分词呢？毕竟分词的目的是为了搜索，而不是为了教小孩读出。如果把两种分词的可能性都告诉搜索引擎，搜索引擎会很高兴的，因为这下不管是“有意”还是“意见”，它都可以搜到了。这就是我提出来另一个目标：歧义包容。
1.2.2 算法的突破口—词库
虽然我们的目标已经确定下来了，但是要想出一个更好的算法却是非常难的事。毕竟算法需要的是灵感与突发奇想，这与系统的架构设计和面向对象的设计与编者编码刚好是相反的，象设计模式或重构这样的东西我们需要的实践、总结、再实践。而算法需要的却是当我们在山重水复疑无路的时候会换个角度思考。
但是分词算法的突破口在哪里呢？我们必须要有一个词库，我们必须将全文中的词与词库去匹配，这一切都是不可避免的。
真正要改善是就是我们的匹配过程，我们要减少匹配过程中的浪费，我们要解决匹配中的词长限制。但是我们有什么办法呢？每次的匹配我们必须要去词库中查找一次。怎么改善这样的做法？
我们总是把优化的思路定格在更好的匹配算法，更好地处理词条和全文。但是真正束缚我们的却是词库！是基于关系数据库的词库，我们需要的对词库的改造，我们要让我们的词库更适合用于匹配与分词！
这是几十年来关系数据库带给我们的思维：我们查找的词是数据库的某条记录，通过表格与关系代数，我们总能找到这个词。但是正是关系数据库的这种思维束缚着我们，关系数据库让我们的数据结构及关联表达得清楚又简单，并使某些查询的效率变得很高。但是这不适用于中文分词，有的时候退到几十年前流行的数据库模型也许更适合。这就是层次数据库。
我们要做的是将关系数据库的词按字打散，并存放到层次数据库中。以下就是一个示例：
红色的字表示树上面的字串是可以单独组成一个词的，例如“感冒”它本身是词库里可以找到的词，所有红色的表示的是终止符。而黄色则表示树上面的字串是无法单独成词的，例如“感冒解”是不存在的词。
真的很奇妙，词库经过这样的改装后，所有的匹配的思维都变掉了。任何一个句子都会打散成单字去与树状结构的单字去匹配，词的长度变成了树的高度，每一次的匹配变成了树的遍历，而这种遍历的效率竟然都是线性的！
1.2.3 中文分词算法设计
有了以上的中文词库后，我们分词算法设计就水到渠成的。首先我们来看一下分词的步骤：
（1）首先将要分的全文按标点符号打散成一个一个的句子。这算是预处理的一个步骤，目的是让我们处理的句子短，效率更高。毕竟中间有标点符号的词是不存在的。（注：真正实现时我们是基于lucene的SimpleAnalyzer来做的，因为SimpleAnalyzer本身就是为了将全文打散成句子，因此我们没必要耗费体力去实现这一步）。
（2）我们开始将要处理的句子在树状结构中遍历，如果找到匹配的就继续，如果遇到红色的终止符，我们就发现这个词是一个完整的词了，这样我们就可以把这个词作为一个一个分词了。
（3）从分词后的下一字开始继续做步骤2这样的遍历，如此循环往复就将词分完了。
可以看到，我们字符匹配效率几乎是线性的！我们所要做的只是取出每一个字去树上找到相应的匹配，每次的匹配代价都是O(1)（如果词库用Hash表的话），这样匹配下来的时间复杂度就是字符串本身的长度！对于一个长度为n的字符串来说，它的分词复杂度是O(n)。而最大匹配的平均复杂度是O(n2)。
当然我们这里没有考虑歧义包容与分支处理等情况，但即使加上这些我们复杂度仍然是有限的。
1.2.4 中文分词算法的实现细节
一、建立词库
有了改装词库的基本思想后，建立词库的步骤变得很简单，但是仍然会有好多的细节需要注意。
首先是词库的保存格式。现在最常用的保存数据的方式当然是关系数据库，其次是文件系统中的二进制文件。显然关系数据库对于我们并不适用，而自定义的二进制文件则实现起来比较困难，而且读写的效率也会有问题。因为我们想到了最简单的方法是利用java的serialization的功能，把整个内存中的树状结构直接序列化成磁盘的文本文件是最方便的！而且读写的效率也会相当的高。
第二个问题是树的父子节点的导航。我们的树并不是一颗二叉树，父亲的子节点会有好多！尤其是第一层，我们会把词库中所有的首字都取出来作为根节点的子节点，这意味着如果首字有4000个的话，根节点就有4000个儿子。当然随着树层数的增多，节点的儿子数也会减少，毕竟以“感冒”开头的词在整个词库也只有四十多个，而以“感冒清”开头的词则只有两三个了。这意味着如果设计得不合理，我们树的匹配遍历过程并不完全是线性的。最坏的查找算法是O(N)（N代表儿子数）。当然如果我们建词库时将儿子有序排列，再按照二分查找的方法，则我们的复杂度会减到O(lgN)，这样的复杂度已经可以接受了。但是还有更简单又更快的存储方式，为什么不使用呢？那就是HashMap，毕竟在HashMap里查找东西时它的效率几乎是线性的，而且实现起来要比二分查询简单得多。当然用HashMap要付出存储空间变大的代价，但这样的代价来换取速度与简单性也是的。
第三个问题是找到有终结符的字后，我们必须要将它建成一个完整的词。这时我们必须能从字个往上回溯，直到找到根结点。因此我们在每个节点里都保存了父节点的指针。
有了以上的设计思想，我们就动手建立了我们的词库，词库的来源是中医药数据库的词汇表，因为我们应用一直是围绕中医药的。我们找到了两个最重要的表，这两个表几乎包含了中医药的全部词库：
一体化语言系统词库92112个词
疾病大全、症状、证候20879个词
最后生成的词库是java serialization的一个文件，文件的大小是16M 。当然这跟我们采用HashMap存放父子关联有关，也跟java的对象所占空间有关，虽然将词库按这种方式存放实际上也对词库进行了压缩（以“感”开头的字有数十个，关系数据库里就要保存数十个，但我们在词库只保存了一个“感”）。但文件仍然偏大，因此用oracle将这两个表导出后生成的文件大小是4M。不过这个大小仍然是可以接受的，毕竟效率才是关键。
二、分词查询
虽然刚才对分词算法进行了描述，但实际上实现的时候我们还会碰到很多问题。
1、分支处理。
这是分词算法时歧义包容所必然碰到的问题。为了歧义包容，我们采用了与最大分词法完全不同的理念，我们的理念是将词库中存在词全部收入囊中！而且会发生重叠。例如“感冒解毒胶囊”，由于词库里存在“感冒”、“解毒”和“感冒解毒胶囊”这三个词，因此在分词的时候，我们会分别分出这三个词，这样用户无论输入“感冒”、“解毒”或“感冒解毒胶囊”搜索引擎都会找到相应的结果。
因此当遇到分支时，我们会分解成两条路线！例如当我们匹配到“感冒”的“冒”时，我们会发现一个终止符，代表“感冒”是一个完整的字，将它收录到分词中。接下来我们会分成两支，一支是继续往下走，匹配树的下一层，因为“冒”不是树的叶子，往下走可能会碰到更大的匹配词，例如“感冒解毒胶囊”。而另一支则从根开始，直接用“解”去匹配树的第一层节点，最后发现了“解毒”也是其中的一个词。
2、动态规划法
分支虽然使我们可以消除很多的歧义，但是显然它会带来副作用：导致分词的复杂度变大。
如果一个句子很长时，分词的变化也许会呈指数级的增长，从一开始的两个分支变成四个、八个甚至更多。我们会发现很多句子虽然会有很多分支，但是这些分支又经常会汇聚到一个点，变成一个分支。例如：“感冒解毒胶囊可以治感冒”，我们在分词的时候可能会出现“感冒”，“解毒”，“感冒解毒”，“感冒解毒胶囊”等多个分支，但是当我们到达“囊”这个点的时候，所有的分支又会汇集到一起，因为大家接下来要处理的都是“可以治感冒”这
个字符串。如果有办法让我们在汇聚以后只处理一个分支，那么算法的时间复杂度就不会象原来想象的那么坏。
而这刚好是动态规划法发挥威力的时候，动态规划要解决的问题是Overlapping sub-problem。它的处理方法就是将所有的子问题记录在公有的变量里（这里指的是类变量，它相对于某个method来说是公有变量，而不是真的全局变量）。当我遇到的子问题已经被处理过一次了，就直接跳过。这样节约的结果可以使算法复杂度得到质的改变，当然由于中文的变化多端，我们无法精确估计使用动态规划法后算法复杂度得到了多大的提高。
实际上的动态规划法的实现起来比说起来反而简单，我们只是简单地放了一个HashSet来存放已经分词过的位置：
然后判断的函数也相当的简单：
最后在分词的递归函数中加入这一句判断：
当这个位置已经被处理过了就直接返回了。
3、词库预load
在使用基于词库的方法时，我们必须要面临的一个问题是：必要将词库读到内存中，而这通常会耗费很长的时间，幸运的是这样的工作我们只需要做一次，当我们将词库load进来以后，所有的工作都会在内存中进行，分词的速度会得到极速提升。我们选择的词库预load
时机是我们第一次进行分词时，这相当于lazy load，只有用到的时候我们才去初始化。
讲完算法，我们来看看分词部分的实现代码，实际上这部分的内容实现起来远比想中简单。在处理的过程中，我们对给每个句子（实际是lucene里用SimpleAnalyzer分词后的一个个Token）都新建一个ChineseSplitter，这是更加面向对象的做法，使我们处理起来更加方便简洁，因为我们会发现如果用一个Singleton的ChineseSplitter时，它的变量无法共享会导致整个Splitter里的递归方法跟上一堆的参数，容易出错，而且无法调试。代码如下：
代码简单明了，只是做了词库预load的工作后就将实际的分词工作交给了ChineseSplitter。
ChineseSplitter的核心功能实际上将句子中词典中能找到的词放到一个队列中，这中队列里提供了分词以后的所有词的信息：
下面是分词的核心算法：
它是一个递归的过程，初始时我们调用的参数里pos为0，这样它就会一级一级递归下去并将所有可能的分词放入到tokenQueue里。
1.2.5 中文分词的实验结果
1、实验1——短文分词
在第一个实验中我们选了一篇2000字的文章（是关于中医药的专业论文）。然后用三种Analyzer对它进行处理，以下是实验结果：
我们没有找到最大匹配法分词可用的开源代码，因此只能用SimpleAnalyzer和StandardAnalyzer与之比较。这两种算法事实上是根本没有去查词库的，因此也不会按任何语义去分词，SimpleAnalyzer只是简单地将文章按标点符号隔开成句子，而StandardAnalyzer 则只是简单地将文章的中文字分成一个一个的单字。结果确实让人惊讶，当词库preload以后，我们的分词速度竟然远超不需要查任何词库的StandardAnalyzer算法！
2、实验2——建索引
这是将分词算法应用到我们的索引系统后的效果比较，我们的数据源是来自中医药数据库的几十张表，一共有九十万条记录：
由于建索引时数据库的查询操作会耗费很多的时间，因此两者的差别不是太明显，但结果至少说明了我们的分词效率确实是很高。
中文分词的几种算法
什么是中文分词？
众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子I am a student，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。上海SEO服务，分词的结果是：上海SEO服务
目前主流的中文分词算法有以下3种：
1、基于字符串匹配的分词方法
这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：
?1）正向最大匹配法（由左到右的方向）；
?2）逆向最大匹配法（由右到左的方向）；
?3）最少切分（使每一句中切出的词数最小）。
还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245.但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。
一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机械分词，从而减少匹配的错误率。另一种方法是将分词和词类标注结合起来，利用丰富的词类信息对分词决策提供帮助，并且在标注过程中又反过来对分词结果进行检验、调整，从而极大地提高切分的准确率。
对于机械分词方法，可以建立一个一般的模型，在这方面有专业的学术论文，这里不做详细论述。
2、基于理解的分词方法
这种分词方法是通过让计算机模拟人对句子的理解，达到识别词的效果。其基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。它通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息。由于汉语语言知识的笼统、复杂性，难以将各种语言信息组织成机器可直接读取的形式，因此目前基于理解的分词系统还处在试
验阶段。
3、基于统计的分词方法
从形式上看，词是稳定的字的组合，因此在上下文中，相邻的字同时出现的次数越多，就越有可能构成一个词。因此字与字相邻共现的频率或概率能够较好的反映成词的可信度。可以对语料中相邻共现的各个字的组合的频度进行统计，计算它们的互现信息。定义两个字的互现信息，计算两个汉字X、Y的相邻共现概率。互现信息体现了汉字之间结合关系的紧密程度。当紧密程度高于某一个阈值时，便可认为此字组可能构成了一个词。这种方法只需对语料中的字组频度进行统计，不需要切分词典，因而又叫做无词典分词法或统计取词方法。但这种方法也有一定的局限性，会经常抽出一些共现频度高、但并不是词的常用字组，例如“这一”、“之一”、“有的”、“我的”、“许多的”等，并且对常用词的识别精度差，时空开销大。实际应用的统计分词系统都要使用一部基本的分词词典（常用词词典）进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。
软件设计开发本栏目责任编辑：谢媛媛中文分词算法概述 龙树全,赵正文,唐华 （西南石油大学计算机科学学院，四川成都610500） 摘要：当前搜索引擎技术被广泛地应用，这使得全文检索技术和中文分词技术的研究逐渐深入。中文分词是中文信息的关键技术之一，其质量高低直接影响中文信息处理效率。文章致力于研究中文分词算法,对多种中文分词算法、自动分词系统的理论模型进行了详细的阐述和讨论，为中文分词的进一步发展提供基础和方向。 关键词：中文分词；全文检索；算法；搜索引擎；歧义切分 中图分类号：TP391.1文献标识码：A 文章编号：1009-3044(2009)10-2605-03 Overview on Chinese Segmentation Algorithm LONG Shu-quan,ZHAO Zheng-wen,TANG Hua (Department of Computer Science and Technology,Southwest Petroleum University,Chengdu 610500,China) Abstract:Currently,the search engine technology has been widely used,which brings in-depth researches to full-text search technology and Chinese segmentations;Chinese Segmentation is one of the key technologies of Chinese information,it directly affects the quality of Chinese information processing efficiency.This article dedicated to Research on Chinese Segmentation Algorithm,described in detail and discuss to some kinds of Chinese Segmentation Algorithms,Theoretical model of Auto-Segmentation system.Provide foundation and di -rection for the further development of Chinese segmentations. Key words:chinese segmentations;full-text search;algorithm;search engine;ambiguous word segmentation 1引言 自然语言处理是人工智能的一个重要分支。中文分词是中文自然语言处理的一项基础性工作，也是中文信息处理的一个重要问题。随着搜索引擎技术的广泛应用，全文检索技术和中文分词技术也逐步受到广泛的研究和应用，然而到目前为止，还没有完全成熟实用的中文分词系统面世，这成为严重制约中文信息处理发展的瓶颈之一。本文致力于研究中文分词算法，通过分词算法对分词的质量做出客观的判断和评估，从而为中文分词的进一步发展提供基础和方向。 2中文分词技术综述 2.1全文检索技术 所谓全文检索是指计算机索引程序通过扫描文章中的每一个词，对每一个词建立一个索引，指明该词在文章中出现的次数和位置，当用户查询时，检索程序就根据事先建立的索引进行查找，并将查找的结果反馈给用户的检索方式。在中文文档中根据是否采用分词技术，索引项可以是字、词或词组，由此可分为基于字的全文索引和基于词的全文索引。 基于字的全文索引是指对于文章中的每一个字都建立索引，检索时将词分解为字的组合。对于各种不同的语言而言，字有不同的含义，比如英文中字与词实际上是合一的，而中文中字和词有很大分别。此方法查全率较高，但查准率较低。有时会出现令人啼笑皆非的检索结果，如检索货币单位“马克”时，会把“马克思”检索出来。 基于词的全文索引是指对文章中的词，即语义单位建立索引，检索时按词检索，并且可以处理同义项等。英文等西方文字由于按照空白切分词，因此实现上与按字处理类似，添加同义处理也很容易。中文文字则需要切分字词，以达到按词索引的目的。对中文文档进行切词，提高分词的准确性，抽取关键词作为索引项，实现按词索引可以大大提高检索的准确率。 2.2中文分词技术 中文分词与英文分词有很大的不同，对英文而言，一个单词就是一个词，而汉语是以字为基本的书写单位，词语之间没有明显的区分标记，需要人为切分。中文分词系统是利用计算机对中文文本进行词语自动识别的系统，对其研究已经取得了很多成果，出现了众多的算法。根据其特点，可以将现有的分词算法分为四大类：基于字符串匹配的分词方法、基于理解的分词方法、基于统计的分词方法和基于语义的分词方法等。 3中文分词方法 中文分词方法的基本原理是针对输入文字串进行分词、过滤 处理，输出中文单词、英文单词和数字串等一系列分割好的字符 串。中文分词模块的输入输出如图1所示。3.1基于字符串匹配的分词方法 这种方法又叫作机械分词方法、基于字典的分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配。若在词典中找到某个字符串，则匹配成功(识别出一个词)。该方法有三个要素，即分词词典、文本扫描顺序和匹配原则。文本的扫描顺序有正向扫描、逆向扫描和双向扫描。匹配原则主要有最大匹配、最小匹配、逐词匹配和最佳匹配。 收稿日期：2009-02-11 图1中文分词原理图 ISSN 1009-3044 Computer Knowledge and Technology 电脑知识与技术 Vol.5,No.10,April 2009,pp.2605-2607E-mail:xsjl@https://www.doczj.com/doc/a75101831.html, https://www.doczj.com/doc/a75101831.html, Tel:+86-551-569096356909642605
前面我们讲个搜索引擎如何搜集网页,今天说下第二个过程网页预处理,其中中文分词就显得尤其重要,下面就详细讲解一下搜索引擎是怎么进行网页预处理的: 网页预处理的第一步就是为原始网页建立索引，有了索引就可以为搜索引擎提供网页快照功能;接下来针对索引网页库进行网页切分，将每一篇网页转化为一组词的集合;最后将网页到索引词的映射转化为索引词到网页的映射，形成倒排文件(包括倒排表和索引词表)，同时将网页中包含的不重复的索引词汇聚成索引词表。如下图所示: 一个原始网页库由若干个记录组成，每个记录包括记录头部信息(HEAD)和数据(DATA)，每个数据由网页头信息(header)，网页内容信息(content)组成。索引网页库的任务就是完成给定一个URL，在原始网页库中定位到该URL所指向的记录。 如下图所示:
对索引网页库信息进行预处理包括网页分析和建立倒排文件索引两个部分。中文自动分词是网页分析的前提。文档由被称作特征项的索引词(词或者字)组成，网页分析是将一个文档表示为特征项的过程。在对中文文本进行自动分析前，先将整句切割成小的词汇单元，即中文分词(或中文切词)。切词软件中使用的基本词典包括词条及其对应词频。 自动分词的基本方法有两种：基于字符串匹配的分词方法和基于统计的分词方法。 1) 基于字符串匹配的分词方法 这种方法又称为机械分词方法，它是按照一定的策略将待分析的汉字串与一个充分大的词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功(识别出一个词)。 按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配;按照不同长度优先匹配的情况，可以分为最大或最长匹配，和最小或最短匹配;按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下：
中文分词实验 一、实验目的： 目的：了解并掌握基于匹配的分词方法，以及分词效果的评价方法。 实验要求： 1、从互联网上查找并构建不低于10万词的词典，构建词典的存储结构； 2、选择实现一种机械分词方法（双向最大匹配、双向最小匹配、正向减字最大匹配法等）。 3、在不低于1000个文本文件，每个文件大于1000字的文档中进行中文分词测试，记录并分析所选分词算法的准确率、分词速度。 预期效果： 1、平均准确率达到85%以上 二、实验方案： 1.实验平台 系统：win10 软件平台：spyder 语言：python 2.算法选择 选择正向减字最大匹配法，参照《搜索引擎-原理、技术与系统》教材第62页的描述，使用python语言在spyder软件环境下完成代码的编辑。 算法流程图：
Figure Error! No sequence specified.. 正向减字最大匹配算法流程
Figure Error! No sequence specified.. 切词算法流程算法伪代码描述：
3.实验步骤 1)在网上查找语料和词典文本文件； 2)思考并编写代码构建词典存储结构； 3)编写代码将语料分割为1500个文本文件，每个文件的字数大于1000字； 4)编写分词代码； 5)思考并编写代码将语料标注为可计算准确率的文本； 6)对测试集和分词结果集进行合并； 7)对分词结果进行统计，计算准确率，召回率及F值（正确率和召回率的 调和平均值）； 8)思考总结，分析结论。 4.实验实施 我进行了两轮实验，第一轮实验效果比较差，于是仔细思考了原因，进行了第二轮实验，修改参数，代码，重新分词以及计算准确率，效果一下子提升了很多。 实验过程：
一种基于词典的中文分词法的设计与实 现 摘要：中文分词就是把没有明显分隔标志的中文字串切分为词串，它是其他中文信息处理的基础，广泛应用于搜索引擎、自动翻译、语音合成、自动分类、自动摘要、自动校对等领域。就中文分词的基本方法作了简单阐述，并介绍了一种基于词典采用最大匹配法实现中文分词的方法。 关键词：中文分词；词库索引；正向最大匹配法 1 中文分词 中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程就是分词算法。 1.1中文分词方法的种类 中文自动分词方法有多种，一般来说大致可归结为以下三大类：基于词典的分词方法、基于统计的分词方法、基于规则和基于统计相结合的分词方法[2]。1.1.1基于词典的分词方法。基于词典的分词方法，又叫做基于字符串匹配的分词方法。其基本思想是：事先建立词库，其中包含所有可能出现的词。对于给定的待分词的汉子串Str，按照某种确定的原则切取Str 的子串，若该子串与词库中的某词条相匹配，则该子串是就是词，继续分割其余的部分，直到剩余部分为空；否则，该子串不是词，转到上面重新切取Str的子串进行匹配。1.1.2基于统计的分词方法。基于词典分词方法要借助词典来进行，而中文的构词非常灵活，词的数目几乎是无限的，因此要构造完备的词典几乎是不可能的。鉴于上述分词方法存在的这些缺点，一种基于统计的分词方法应运而生。这种方法撇开词典，根据字串出现的频率来判断这个字串是否是词。该方法对于大的语料，分全率还可以，但是对于小的语料分全率就比较低。该方法的另一个缺点就是不够准确，有些经常一起出现的单字构成的字串其实不是词。但是由于出现的频率很高，就被分出来当作词处理了，而且这样的“词”还非常多, 例如“这一”、“之一”、“有的”、“我的”、“许多的”等。实际应用的统计分词系统都要使用一部基本的分词词典进行串匹配分词，同时使用统计方法识别一些新的词，即将串频统计和串匹配结合起来，既发挥匹配分词切分速度快、效率高的特点，又利用了无词典分词结合上下文识别生词、自动消除歧义的优点。1.1.3基于规则和基于统计相结合的分词方法。该方法首先运用最大匹配作初步切分，然后对切分的边界处进行歧义探测，发现歧义，最后运用统计和规则相结合的方法来判断正确的切分[4]。运用不同的规则解决人名、地名、机构名识别，运用词法结构规则来生成复合词和衍生词。日前这种方法可以解决汉语中最常见的歧义类型：单字交集型歧义。并对人名、地名、机构名、后缀、动词/形容词重叠、衍生词等词法结构进行识别处理，基本解决了分词所面临的最关键的问题。若词典结构和算法设计优秀，分词速度将非常快。 1.2分词中的难题 有了成熟的分词算法，是否就能容易的解决中文分词的问题呢？事实远非如此。中文是一种十分复杂的语言，让计算机理解中文语言更是困难。在中文分词过程中，有两大难题一直没有完全突破。1.2.1歧义识别。歧义是指同样的一句话，可能有两种或者更多的切分方法。例如：“表面的”，因为“表面”和“面的”都是词，那么这个短语就可以分成“表面的”和“表面的”，这种称为交叉歧义，像这种交叉歧义十分常见。“化妆和服装”可以分成“化妆和服装”或者“化妆和服装”。由于没有人的知识去理解，计算机很难知道到底哪个方案正确。交叉歧义
百度中文分词技巧 什么是中文分词？我们都知道，英文句子都是由一个一个单词按空格分开组成，所以在分词方面就方便多了，但我们中文是一个一个汉字连接而成，所以相对来说是比较复杂的。中文分词指的是将一个汉语句子切分成一个一个单独的词，按照一定的规则重新组合成词序列的过程。这个也称做“中文切词”。 分词对于搜索引擎有着很大的作用，是文本挖掘的基础，可以帮助程序自动识别语句的含义，以达到搜索结果的高度匹配，分词的质量直接影响了搜索结果的精确度。目前搜索引擎分词的方法主要通过字典匹配和统计学两种方法。 一、基于字典匹配的分词方法 这种方法首先得有一个超大的字典，也就是分词索引库，然后按照一定的规则将待分词的字符串与分词库中的词进行匹配，若找到某个词语，则匹配成功，这种匹配有分以下四种方式： 1、正向最大匹配法（由左到右的方向）； 2、逆向最大匹配法（由右到左的方向）； 3、最少切分（使每一句中切出的词数最小）； 4、双向最大匹配法（进行由左到右、由右到左两次扫描） 通常，搜索引擎会采用多种方式组合使用。但这种方式也同样给搜索引擎带来了难道，比如对于歧义的处理（关键是我们汉语的博大精深啊），为了提高匹配的准确率，搜索引擎还会模拟人对句子的理解，达到识别词语的效果。基本思想就是在分词的同时进行句法、语义分析，利用句法信息和语义信息来处理歧义现象。通常包括三个部分：分词子系统、句法语义子系统、总控部分。在总控部分的协调下，分词子系统可以获得有关词、句子等的句法和语义信息来对分词歧义进行判断，即它模拟了人对句子的理解过程。这种分词方法需要使用大量的语言知识和信息，当然我们的搜索引擎也在不断进步。 二、基于统计的分词方法 虽然分词字典解决了很多问题，但还是远远不够的，搜索引擎还要具备不断的发现新的词语的能力，通过计算词语相邻出现的概率来确定是否是一个单独的词语。所以，掌握的上下文越多，对句子的理解就越准确，分词也越精确。举个例子说，“搜索引擎优化”，在字典中匹配出来可能是：搜索/引擎/优化、搜/索引/擎/优化，但经过后期的概率计算，发现“搜索引擎优化”在上下文相邻出现的次数非常多，那么基于统计就会将这个词语也加入进分词索引库。关于这点我在《关于电商与圈的分词测试》就是同样的一个例子。 中文分词的应用分词准确性对搜索引擎来说十分重要，但如果分词速度太慢，即使准确性再高，对于搜索引擎来说也是不可用的，因为搜索引擎需要处理数以亿计的网页，如果分词耗用的时间过长，会严重影响搜索引擎内容更新的速度。因此对于搜索引擎来说，分词的准确性和速度，二者都需要达到很高的要求。 参考文档及网站: https://www.doczj.com/doc/a75101831.html, https://www.doczj.com/doc/a75101831.html, https://www.doczj.com/doc/a75101831.html, https://www.doczj.com/doc/a75101831.html,
Baidu查询分词算法 查询处理以及分词技术 如何设计一个高效的搜索引擎?我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎.搜索引擎涉及到许多技术点,比如查询处理,排序算法,页面抓取算法,CACHE机制,ANTI-SPAM等等.这些技术细节,作为商业公司的搜索引擎服务提供商比如百度,GOOGLE等是不会公之于众的.我们可以将现有的搜索引擎看作一个黑盒,通过向黑盒提交输入,判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节. 查询处理与分词是一个中文搜索引擎必不可少的工作,而百度作为一个典型的中文搜索引擎一直强调其”中文处理”方面具有其它搜索引擎所不具有的关键技术和优势.那么我们就来看看百度到底采用了哪些所谓的核心技术. 我们分两个部分来讲述:查询处理/中文分词. 一. 查询处理 用户向搜索引擎提交查询,搜索引擎一般在接受到用户查询后要做一些处理,然后在索引数据库里面提取相关的信息.那么百度在接受到用户查询后做了些什么工作呢? 1. 假设用户提交了不只一个查询串,比如”信息检索理论工具”.那么搜 索引擎首先做的是根据分隔符比如空格,标点符号,将查询串分割成若干子查询串,比如上面的查询就会被解析为:<信息检索,理论,工具>三个子字符串;这个道理 简单,我们接着往下看. 2. 假设提交的查询有重复的内容,搜索引擎怎么处理呢?比如查询”理论 工具理论”,百度是将重复的字符串当作只出现过一次,也就是处理成等价的”理论工具”,而GOOGLE显然是没有进行归并,而是将重复查询子串的权重增大进行处理.那么是如何得出这个结论的呢?我们可以将”理论工具”提交给百度,返回341,000篇文档,大致看看第一页的返回内容.OK.继续,我们提交查询”理论工具理论”,在看看返回结果,仍然是那么多返回文档,当然这个不能说明太多问题,那 看看第一页返回结果的排序,看出来了吗?顺序完全没有变化,而GOOGLE则排序有些变动,这说明百度是将重复的查询归并成一个处理的,而且字符串之间的先后出现顺序基本不予考虑(GOOGLE是考虑了这个顺序关系的). 3. 假设提交的中文查询包含英文单词,搜索引擎是怎么处理的?比如查询”电影BT下载”,百度的方法是将中文字符串中的英文当作一个整体保留,并以此为断点将中文切分开,这样上述的查询就切为<电影,BT,下载>,不论中间的英文是否一个字典里能查到的单词也好,还是随机的字符也好,都会当作一个整体来对待.
基于二级Hash的快速最长匹配分词算法 殷鹏程，谭献海 西南交通大学，四川成都（610031） E-mail：ypc_swjtu@https://www.doczj.com/doc/a75101831.html, 摘要：中文分词是中文信息处理的基础，在海量的中文信息处理中，分词速度至关重要。本文根据中文单词的特点，通过分析现有词典分词算法，提出了一种基于二级Hash的快速最长匹配分词算法。试验结果表明，该算法保证了分词的最长匹配，同时提高了分词的速度，适用于小型搜索引擎和自动文本分类等应用。 关键词：中文分词；Hash词典；最长匹配 1. 引言 在中文信息处理中, 如机器翻译、自动分类等等，词是最小的具有独立活动的有意义的语言成分。然而中文文本在计算机内部表示时，不像英文中词与词之间都有空格隔开，中文词与词之间没有明显的分隔标记, 而是连续的汉字串。因此, 自动识别词的边界, 将连续的汉字串切分为带有分割标记的词串将是实现中文信息处理的首要问题。 现有的分词算法可分为三大类：基于词典的分词方法、基于理解的分词方法和基于统计的分词方法。无论哪种分词方法都需要将大量时间用于将待切分语句的切分为可能的词，然后再依据统计或语法方面的规则对切分出的词进行处理，得到一种最有可能的切分结果。如果能加快初始切分的速度，对于提高整个分词算法的速度也会有很大帮助。由于词语信息都以词典的形式存储, 所以在整个汉语分词过程中, 都需要频繁地访问词典以获得词语信息。因此词典的查询速度是整个分词系统处理效率的关键所在。 现行常用的词典数据结构主要基于Hash方法和索引树方法，根据汉字编码的一对一映射关系，实现了词典的快速查询，但两种方法在构造词典时都没有考虑词语的长度这个关键信息，因此不适合最长匹配算法。本文在Hash方法的基础上，提出一种新的词典结构，不仅对词语的首字进行Hash，而且根据词语的长度进行二次Hash。实验证明，新的词典结构不仅提高了分词速度，而且满足最长匹配的分词需求。 2．二级Hash词典的设计 为了提高分词的准确度，基于词典的分词方法通常采用最长匹配算法。实验证明，如果分成的词语越长、分出的词语越少，分词的精确度就越高。通常基于Hash方法的词典只对词语的首字符进行了Hash，这样的词典虽然能实现快速查询，但是如果采用最长匹配算法，则需要对词典进行多次查询，影响算法速度。为了使词典更适合最长匹配算法，通过对对汉字编码体系、汉语词语特点的分析，针对传统Hash词典的缺点，本文设计了一种基于二级Hash的词典结构。 2.1 汉字编码体系 汉字在计算机内部是以内码的形式进行存储的，汉字内码是汉字在汉字信息处理系统中最基本的表达形式，它与汉字交换码、汉字区位码有一定的对应关系。由于自定义编码顺序的特殊性，因而，可通过计算偏移量的方法来定位该汉字在编码表中任意的位置。国标GB2312汉字编码表共收录了6763个汉字，汉字在编码表中的偏移量计算公式如下： offset = (ch1 – 0xB0) * 94 + (ch2 – 0xA1) (1) 其中，offset代表某汉字在编码表中的位置， ch1、ch2代表汉字的内部码。 2.2 汉语词的特点
一、为什么要进行中文分词？ 词是最小的能够独立活动的有意义的语言成分，英文单词之间是以空格作为自然分界符的，而汉语是以字为基本的书写单位，词语之间没有明显的区分标记，因此，中文词语分析是中文信息处理的基础与关键。 Lucene中对中文的处理是基于自动切分的单字切分，或者二元切分。除此之外，还有最大切分（包括向前、向后、以及前后相结合）、最少切分、全切分等等。 二、中文分词技术的分类 我们讨论的分词算法可分为三大类：基于字典、词库匹配的分词方法；基于词频度统计的分词方法和基于知识理解的分词方法。 第一类方法应用词典匹配、汉语词法或其它汉语语言知识进行分词，如：最大匹配法、最小分词方法等。这类方法简单、分词效率较高,但汉语语言现象复杂丰富，词典的完备性、规则的一致性等问题使其难以适应开放的大规模文本的分词处理。第二类基于统计的分词方法则基于字和词的统计信息，如把相邻字间的信息、词频及相应的共现信息等应用于分词，由于这些信息是通过调查真实语料而取得的，因而基于统计的分词方法具有较好的实用性。 下面简要介绍几种常用方法: 1）．逐词遍历法。 逐词遍历法将词典中的所有词按由长到短的顺序在文章中逐字搜索,直至文章结束。也就是说,不管文章有多短,词典有多大,都要将词典遍历一遍。这种方法效率比较低，大一点的系统一般都不使用。 2）．基于字典、词库匹配的分词方法（机械分词法） 这种方法按照一定策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行匹配，若在词典中找到某个字符串，则匹配成功。识别出一个词，根据扫描方向的不同分为正向匹配和逆向匹配。根据不同长度优先匹配的情况，分为最大（最长）匹配和最小（最短）匹配。根据与词性标注过程是否相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的方法如下： （一）最大正向匹配法 (ＭａｘｉｍｕｍＭａｔｃｈｉｎｇＭｅｔｈｏｄ)通常简称为ＭＭ法。其基本思想为：假定分词词典中的最长词有i个汉字字符，则用被处理文档的当前字串中的前i个字作为匹配字段，查找字典。若字典中存在这样的一个i字词，则匹配成功，匹配字段被作为一个词切分出来。如果词典中找不到这样的一个i字词，则匹配失败，将匹配字段中的最后一个字去掉，对剩下的字串重新进行匹配处理……如此进行下去，直到匹配成功，即切分出一个词或剩余字串的长度为零为止。这样就完成了一轮匹配，然后取下一个i字字串进行匹配处理，直到文档被扫描完为止。
一种中文分词算法 1.1.1 最大匹配法分词的缺陷 尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷，这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点： 一、长度限制 由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大匹配法在效率与词长之间的一种妥协。我们来看一下以下两种情况： （1）词长过短，长词就会被切错。例如当词长被设成5时，也就意味着它只能分出长度为5以下词，例如当这个词为“中华人民共和国”长度为7的词时，我们只能取出其中的5个字去词库里匹配，例如“中华人民共”，显然词库里是不可能有这样的词存在的。因此我们无法下确的划分出“中华人民共和国”这样的词长大于5的词。 （2）词长过长，效率就比较低。也许有人会认为既然5个字无法满足我们的分词要求，何不将词长加大，例如加到10或者100，毕竟这个世界超过100个字长的词还是很少见的，我们的词长问题不就解决了？然而当词长过长时，我们却要付出另一方面的代价：效率。效率是分词算法、甚至是整个算法理论体系的关键，毕竟算法书里所有的高深的查询或排序算法都是从效率出发的，否则任何笨办法都可以解决分词效率低的问题。设想到我们把字长设成100个词时，我们必须将词从100开始一直往下匹配直到找到要查的字为止，而我们大多数词的字长却只有两三个字，这意味着前97次的匹配算法是徒劳的。 因此我们必须要在词长与效率之间进行妥协，既要求分词尽量准确，又要求我们的词长不能太长。尽管我们可能找到这样一个比较优化的字长值使两者都达到比较满足的状态，但是毕竟不管我们怎么设定，总会有些太长词分出来，或者带来效率问题。 二、效率低 效率低是最大匹配法分词必然会来的问题。即使我们可以将字长设成相当短，例如5（注意，我们不能再缩短字长了，毕竟字长为5以上的词太多了，我们不能牺牲分词的准确），然而当我们的大数词长为2时，至少有3次的匹配算法是浪费掉的。回想一下算法书里提到
搜索引擎优化百度分词算法分析查询处理以及分词技术 随着搜索经济的崛起，人们开始越加关注全球各大搜索引擎的性能、技术和日流量。作为企业，会根据搜索引擎的知名度以及日流量来选择是否要投放丿告等； 作为普通网民，会根据搜索引擎的性能和技术来选择自己喜欢的引擎查找资料；作为技术人员，会把有代表性的搜索引擎作为研究对象。搜索引擎经济的崛起，又一次向人们证明了网络所蕴藏的巨大商机。网络离开了搜索将只剩下空洞杂乱的数据，以及大量等待去费力挖掘的金矿。 但是，如何设计一个高效的搜索引擎？我们可以以百度所采取的技术手段来探讨如何设计一个实用的搜索引擎。搜索引擎涉及到许多技术点，比如查询处理，排序算法，页面抓取算法，CACH机制，ANTI-SPAM等等。这些技术细节，作为商业公司的搜索引擎服务提供商比如百度，GOOGL等是不会公之于众的。 我们可以将现有的搜索引擎看作一个黑盒，通过向黑盒提交输入，判断黑盒返回的输出大致判断黑盒里面不为人知的技术细节。 查询处理与分词是一个中文搜索引擎必不可少的工作，而百度作为一个典型的中文搜索引擎一直强调其"中文处理"方面具有其它搜索引擎所不具有的关键技术和优势。那么我们就来看看百度到底采用了哪些所谓的核心技术。 我们分两个部分来讲述：查询处理/中文分词。 一、查询处理 用户向搜索引擎提交查询，搜索引擎一般在接受到用户查询后要做一些处理，然后在索引数据库里面提取相关的信息。那么百度在接受到用户查询后做了些什么工作呢？ 1、假设用户提交了不只一个查询串，比如"信息检索理论工具"。 那么搜索引擎首先做的是根据分隔符比如空格，标点符号，将查询串分割成若
干子查询串，比如上面的查询就会被解析为：信息检索，理论，工具三个子字符串；这个道理简单，我们接着往下看。 2、假设提交的查询有重复的内容，搜索引擎怎么处理呢？比如查询"理论工具理论"，百度是将重复的字符串当作只出现过一次，也就是处理成等价的"理 论工具"，而GOOGL显然是没有进行归并，而是将重复查询子串的权重增大进行处理。那么是如何得出这个结论的呢？我们可以将"理论工具"提交给百度，返回341,000篇文档，大致看看第一页的返回内容。 OK继续，我们提交查询"理论工具理论"，在看看返回结果，仍然是那么多返回文档，当然这个不能说明太多问题，那看看第一页返回结果的排序，看出来了吗？顺序完全没有变化，而GOOGL E排序有些变动，这说明百度是将重复的查询归并成一个处理的，而且字符串之间的先后出现顺序基本不予考虑（GOOGL是考虑了这个顺序关系的）。 3、假设提交的中文查询包含英文单词，搜索引擎是怎么处理的？比如查询" 电影BT下载"，百度的方法是将中文字符串中的英文当作一个整体保留，并以 此为断点将中文切分开，这样上述的查询就切为电影，BT,下载，不论中间的 英文是否一个字典里能查到的单词也好，还是随机的字符也好，都会当作一个整体来对待。至于为什么，你用查询"电影dfdfdf下载"看看结果就知道了。当然如果查询中包含数字，也是如此办理。 到目前为止，一切很简单，也很清楚，百度怎么处理用户查询的呢？归纳如下：首先根据分割符号将查询分开，然后看看是否有重复的字符串，如果有，就抛弃多余的，只保留一个，接着判断是否有英文或者数字，如果有的话，把英文或者数字当作一个整体保留并把前后的中文切开。 接着该干什么呢？该考虑分词的问题了。 二、中文分词 首先，讲讲百度的分词时机或者条件问题，是否是个中文字符串百度就拿来切一下呢？非也，要想被百度的分词程序荣幸的切割一下也是要讲条件的，哪能是个字符串就切割啊？你当百度是卖锯条的么？
中文分词 一、概述 什么是中文分词 众所周知，英文是以词为单位的，词和词之间是靠空格隔开，而中文是以字为单位，句子中所有的字连起来才能描述一个意思。例如，英文句子I am a student，用中文则为：“我是一个学生”。计算机可以很简单通过空格知道student是一个单词，但是不能很容易明白“学”、“生”两个字合起来才表示一个词。把中文的汉字序列切分成有意义的词，就是中文分词，有些人也称为切词。我是一个学生，分词的结果是：我是一个学生。 中文分词技术 中文分词技术属于自然语言处理技术范畴，对于一句话，人可以通过自己的知识来明白哪些是词，哪些不是词，但如何让计算机也能理解？其处理过程就是分词算法。 现有的分词算法可分为三大类：基于字符串匹配的分词方法、基于理解的分词方法和基于统计的分词方法。 1、基于字符串匹配的分词方法 这种方法又叫做机械分词方法，它是按照一定的策略将待分析的汉字串与一个“充分大的”机器词典中的词条进行配，若在词典中找到某个字符串，则匹配成功（识别出一个词）。按照扫描方向的不同，串匹配分词方法可以分为正向匹配和逆向匹配；按照不同长度优先匹配的情况，可以分为最大（最长）匹配和最小（最短）匹配；按照是否与词性标注过程相结合，又可以分为单纯分词方法和分词与标注相结合的一体化方法。常用的几种机械分词方法如下： 1）正向最大匹配法（由左到右的方向）； 2）逆向最大匹配法（由右到左的方向）； 3）最少切分（使每一句中切出的词数最小）。 还可以将上述各种方法相互组合，例如，可以将正向最大匹配方法和逆向最大匹配方法结合起来构成双向匹配法。由于汉语单字成词的特点，正向最小匹配和逆向最小匹配一般很少使用。一般说来，逆向匹配的切分精度略高于正向匹配，遇到的歧义现象也较少。统计结果表明，单纯使用正向最大匹配的错误率为1/169，单纯使用逆向最大匹配的错误率为1/245。但这种精度还远远不能满足实际的需要。实际使用的分词系统，都是把机械分词作为一种初分手段，还需通过利用各种其它的语言信息来进一步提高切分的准确率。 一种方法是改进扫描方式，称为特征扫描或标志切分，优先在待分析字符串中识别和切分出一些带有明显特征的词，以这些词作为断点，可将原字符串分为较小的串再来进机
中文搜索引擎的自动分词算法 !"#$%&’#(#($)!*+$’(#,-.$/#,01,()0.01,&’&2#0’30&’2,4)+()0 蒋 微5 西南财经大学成都 67889:; <摘要=提出了基于关键词搜索的两种自动分词算法>均以双词及三词作为搜索的最小单位5或基本单位;> 一种以栈实现?一种不借助栈且动态匹配实现>通过此两种算法均可进行发布网站@网页前网名入数据库的关键词标识提取及实现匹配后有效性的确认?以提高中文搜索引擎的搜索准确率及获得由网名入数据库前后同步性决定的快速响应>< 关键词=中文搜索引擎?自动分词?栈?非栈?关键词搜索 !A 3B C !1B D E FG H I F J G K I L I L F MG N O F K L I P Q RS G R T UF MV T W E F K UR T G K X P L M OG K TO L Y T ML MI P L RG K I L X N T ?L ME P L X PI E FE F K U RF K I P K T T E F K U R G K T H R T U G R I P T Q L M L Q H Q H M L I 5F K S G R L X H M L I ;L MR T G K X P L M O ?F M T L R L Q J N T Q T M I T U S W H R T F Z R I G X V ?G M U I P T F I P T K L R M F I S H I S W I P T E G W F Z U W M G Q L X Q G I X P L M O [\F I PG N O F K L I P Q R X G MT ]I K G X I I P T V T W E F K U L U T M I L Z L X G I L F MZ K F Q G M T I E F K VM G Q T T M I T K L M O I P T U G I G S G R T S T Z F K T S K F G U X G R I M T I M F U ?Z K F M I J G O T ?G M U X F M Z L K Q I P T Y G N L U L I W G Z I T K Q G I X P L M O R F G R I F L Q J K F Y T I P T P L O PG X X H K G X W F Z ^P L M T R T X P G K G X I T K R T G K X P T M O L M OG M UG X P L T Y T _H L X VK T R J F M R T U T I T K Q L M T US WR W M X P K F M L R Q S T Z F K T G M UG Z I T K M T I E F K VM G Q T T M I T K L M OI P T U G I G S G R T [‘4a bc C d 3^P L M T R T X P G K G X I T K R T G K X PT M O L M O ?G H I F J G K I L I L F M ?R I G X V ?M F M R I G X V ?V T W E F K UR T G K X P 自动分词系统是为中文搜索做预期和基础性的工作>通过常用词库的支持?它能在一定程度上智能地根据用户需要搜索到相关网站@网页及内容>本文将以类^语言描述两种不同的分词算法> e 算法的支撑 e [e 操作对象 定义75双词;f 存在于词库中以两个字构成的常用词> 定义g 5三词;f 存在于词库中以三个字构成的常用词> 算法的操作对象?即基本单位为双词或三词>范围缩小的依据为f h 单字词应以直接匹配的方式实现i j 四字或五字构成的词可用直接匹配的方式实现?其中可分解成若干双词或三词的词也可用逻辑组合的方式实现搜索> e [k 基本词词性针对网名?l 自动分词m 的分词范围缩小在动词和名词上? 其余为非重要成分>e [n 词库 作为自动分词系统的基础和载体?词库是必然的>要求对汉语常用词作穷举式的逐一调整录入?并以名词和动词进行分类得到词库>词库是本文算法的前提> k 算法的实现 k [e 算法 k [e [e 算法框架 此算法从左至右?以双词为基准?向右扩展>若发 现同一个字或一个词包含在左右相邻的两常用词内?则经判断分析?筛选出合乎逻辑的关键词入关键词组? 防止了l 断章取义m 的可能>特点为实现了无回溯的确定性算法> 注意f 此算法以双词为研究起点?同时进行关键词为三个字的词即三词的提取>前两字不为词?三个字才 为词的情况由子程序X P G K o p T ]I qF K U 5X F M R I X P G K o ;解决> k [e [k 算法的实现 变量说明f R H Q rr 关键词计数器> s \ rr 作为当前基准的双词对象>V T W t u rr 关键词组>v D r 当前双词向右扩展一位所得为三词> \ r 当前双词的右两个字组成双词>w r 当前双词的右字向右扩展一位成双词> D r 当前双词的右三个字组成三词> o g 88g 8789收到?g 88g 8x g y 改回 oo 蒋微?女?7y z 7年生?y y 级在读本科生? 攻读方向f 信息工程?信息管理>{6g {5 总g z z ;中文搜索引擎的自动分词算法 g 88g 年
分词算法设计中的几个基本原则： 1、颗粒度越大越好：用于进行语义分析的文本分词，要求分词结果的颗粒度越大，即单词的字数越多，所能表示的含义越确切，如：“公安局长”可以分为“公安局长”、“公安局长”、“公安局长”都算对，但是要用于语义分析，则“公安局长”的分词结果最好（当然前提是所使用的词典中有这个词） 2、切分结果中非词典词越少越好，单字字典词数越少越好，这里的“非词典词”就是不包含在词典中的单字，而“单字字典词”指的是可以独立运用的单字，如“的”、“了”、“和”、“你”、“我”、“他”。例如：“技术和服务”，可以分为“技术和服务”以及“技术和服务”，但“务”字无法独立成词（即词典中没有），但“和”字可以单独成词（词典中要包含），因此“技术和服务”有1个非词典词，而“技术和服务”有0个非词典词，因此选用后者。 3、总体词数越少越好，在相同字数的情况下，总词数越少，说明语义单元越少，那么相对的单个语义单元的权重会越大，因此准确性会越高。 下面详细说说正向最大匹配法、逆向最大匹配法和双向最大匹配法具体是如何进行的： 先说说什么是最大匹配法：最大匹配是指以词典为依据，取词典中最长单词为第一个次取字数量的扫描串，在词典中进行扫描（为提升扫描效率，还可以跟据字数多少设计多个字典，然后根据字数分别从不同字典中进行扫描）。例如：词典中最长词为“中华人民共和国”共7个汉字，则最大匹配起始字数为7个汉字。然后逐字递减，在对应的词典中进行查找。 下面以“我们在野生动物园玩”详细说明一下这几种匹配方法： 1、正向最大匹配法： 正向即从前往后取词，从7->1，每次减一个字，直到词典命中或剩下1个单字。 第1次：“我们在野生动物”，扫描7字词典，无
1 最大匹配法（Forward Maximum Matching method, FMM法）：选取包含6-8个汉字的符号串作为最大符号串，把最大符号串与词典中的单词条目相匹配，如果不能匹配，就削掉一个汉字继续匹配，直到在词典中找到相应的单词为止。匹配的方向是从右向左。 逆向最大匹配法（Backward Maximum Matching method, BMM法）：匹配方向与MM法相反，是从左向右。实验表明：对于汉语来说，逆向最大匹配法比最大匹配法更有效。 给定串：我是中国人 从左往右最长匹配优先： 读入‘我’，一个字当然是一个词 再读入‘是’，查表找‘我是’，不在表中，则‘我’是一个独立的词，‘是’还要下一步判断 读入‘中’‘是中’肯定不在表内，那‘是’也是一个独立的词，‘中’还要下一步判断 读入‘果’，‘中国’在表内 再读入‘人’，’中国人‘也在表内， 此时全部读完，’中国人‘是一个次 结果就是：我是中国人 从右往左也类似 最近折腾毕业论文，搞得人没心情写blog了。于是觉得不如把毕业论文里的东西贴出来当blog算了。这里主要介绍了我自己的中文分词算法，我觉得它比现在开源代码比较多的中文匹配法要好多了。这里的内容没有任何背景知识啥的，毕竟论文里的背景知道我也是从网上粘贴的，呵呵！因此这篇文章的内容可能适合做搜索引擎的人。如果要了解中文分词算法在搜索引擎中的重要性，或者最大匹配法的思想与过程，请去网上搜吧，资料还是蛮多的。 1.1.1 最大匹配法分词的缺陷 尽管最大匹配法分词是常用的解决的方案，但是无疑它存在很多明显的缺陷，这些缺陷也限制了最大匹配法在大型搜索系统中的使用频率。最大匹配法的问题有以下几点： 一、长度限制 由于最大匹配法必须首先设定一个匹配词长的初始值，这个长度限制是最大匹配法在效率与词长之间的一种妥协。我们来看一下以下两种情况：
中文分词入门之最大匹配法 发表于2009年01月12号由52nlp 中文分词在中文信息处理中是最最基础的，无论机器翻译亦或信息检索还是其他相关应用，如果涉及中文，都离不开中文分词，因此中文分词具有极高的地位。中文分词入门最简单应该是最大匹配法了，当年师兄布置给我的第一个学习任务就是实现最大匹配法的分词算法（正向、逆向）。记得当时对自己参考学习最有帮助的是北大詹卫东老师“中文信息处理基础”的课件和源程序，不过他实现的是mfc程序，词表存储在数据库里。自己实现时用纯c++实现，利用hash_map 存储词表。这里我介绍一下相关的知识和一个简单的程序示例，部分参考自詹老师的讲义。 正向最大匹配法算法如下所示： （注：以上最大匹配算法图来自于詹老师讲义） 逆向匹配法思想与正向一样，只是从右向左切分，这里举一个例子： 输入例句：S1=”计算语言学课程有意思” ； 定义：最大词长MaxLen = 5；S2= ” “；分隔符= “/”；
假设存在词表：…，计算语言学，课程，意思，…； 最大逆向匹配分词算法过程如下： （1）S2=”"；S1不为空，从S1右边取出候选子串W=”课程有意思”； （2）查词表，W不在词表中，将W最左边一个字去掉，得到W=”程有意思”； （3）查词表，W不在词表中，将W最左边一个字去掉，得到W=”有意思”； （4）查词表，W不在词表中，将W最左边一个字去掉，得到W=”意思” （5）查词表，“意思”在词表中，将W加入到S2中，S2=” 意思/”，并将W从S1中去掉，此时S1=”计算语言学课程有”； （6）S1不为空，于是从S1左边取出候选子串W=”言学课程有”； （7）查词表，W不在词表中，将W最左边一个字去掉，得到W=”学课程有”； （8）查词表，W不在词表中，将W最左边一个字去掉，得到W=”课程有”； （9）查词表，W不在词表中，将W最左边一个字去掉，得到W=”程有”； （10）查词表，W不在词表中，将W最左边一个字去掉，得到W=”有”，这W是单字，将W 加入到S2中，S2=“ /有/意思”，并将W从S1中去掉，此时S1=”计算语言学课程”； （11）S1不为空，于是从S1左边取出候选子串W=”语言学课程”； （12）查词表，W不在词表中，将W最左边一个字去掉，得到W=”言学课程”； （13）查词表，W不在词表中，将W最左边一个字去掉，得到W=”学课程”； （14）查词表，W不在词表中，将W最左边一个字去掉，得到W=”课程”； （15）查词表，“意思”在词表中，将W加入到S2中，S2=“课程/ 有/ 意思/”，并将W从S1中去掉，此时S1=”计算语言学”； （16）S1不为空，于是从S1左边取出候选子串W=”计算语言学”； （17）查词表，“计算语言学”在词表中，将W加入到S2中，S2=“计算语言学/ 课程/ 有/ 意思/”，并将W从S1中去掉，此时S1=”"； （18）S1为空，输出S2作为分词结果，分词过程结束。 相应程序示例： 准备文件：建立一个词表文件wordlexicon，格式如下 计算语言学 课程 意思 输入文件：test,格式如下 计算语言学课程有意思 编译后执行如下：SegWord.exe test 输出分词结果文件：SegmentResult.txt 源代码如下： // Dictionary.h #include