中文分词基本算法介绍
本文内容框架:
1、基于词典的方法(字符串匹配,机械分词方法)
2基于统计的分词(无字典分词)
3基于规则的分词(基于语义)
4基于字标注的中文分词方法
5基于人工智能技术的中文分词方法
6中文分词的难点
7小结
基于词典的方法、基于统计的方法、基于规则的方法等
1、基于词典的方法(字符串匹配,机械分词方法)
定义:按照一定策略将待分析的汉字串与一个“大机器词典”中的词条进行匹配,若在词典中找到某个字符串,则匹配成功。
按照扫描方向的不同:正向匹配和逆向匹配
按照长度的不同:最大匹配和最小匹配
1.1正向最大匹配思想MM
1》从左向右取待切分汉语句的m个字符作为匹配字段,m为大机器词典中最长词条个数。
2》查找大机器词典并进行匹配。若匹配成功,则将这个匹配字段作为一个词切分出来。
若匹配不成功,则将这个匹配字段的最后一个字去掉,剩下的字符串作为新的匹配字段,进行再次匹配,重复以上过程,直到切分出所有词为止。
1.2邻近匹配算法
邻近匹配算法是正向最大匹配算法的改进,因为正向正向最大匹配算法对每个不存在的长字符串都要进行一次二分搜索,算法复杂度太高,可以利用同一个首字符下的词条按升序排列这一条件,在找到某个字符串后,在其后增加一个字得到一个新字串,如果新字串在词典中出现,那么新词一定在原字串的后面,且相隔位置不会太远。这样就可以加快匹配进程。
1.3逆向最大匹配算法RMM
该算法是正向最大匹配的逆向思维(最大匹配的顺序不是从首字母开始,而是从末尾开始),匹配不成功,将匹配字段的最前一个字去掉,实验表明,逆向最大匹配算法要优于正向最大匹配算法。
1.4双向最大匹配法(Bi-directction Matching method,BM)
双向最大匹配法是将正向最大匹配法得到的分词结果和逆向最大匹配法的到的结果进行比较,从而决定正确的分词方法。据SunM.S. 和 Benjamin K.T.(1995)的研究表明,中文中90.0%左右的句子,正向最大匹配法和逆向最大匹配法完全重合且正确,只有大概9.0%的句子两种切分方法得到的结果不一样,但其中必有一个是正确的(歧义检测成功),只有不到1.0%的句子,或者正向最大匹配法和逆向最大匹配法的切分虽重合却是错的,或者正向最大匹配法和逆向最大匹配法切分不同但两个都不对(歧义检测失败)。这正是双向最大匹配法在实用中文信息处理系统中得以广泛使用的原因所在。
1.5最短路径匹配算法(Shortest path match)
最短路径匹配算法是根据词典,找出字串中所有可能的词(也称全分词),然后构造词语切分有向无环图。这样,每一个词对应图中的一条有向边。若赋给相应的边长一个权值(该权值可以是常数,也可以是构成的词的属性值),然后针对该切分图,在起点到终点的所有路径中,求出最短路径,该最短路径上包含的词就是该句子的切分结果。最短路径匹配算法的规则是使切分处理的词数最少,符合汉语自身的语言规律。但是,同样发现在实际应用中,同样不能正确切分出许多不完全符合规则的句子。如果有多条最短路径,往往只能保留其中一个结果,这样对其他同样符合要求的结果是不公平的,也缺乏理论依据。
1.6基于统计的最短路径分词算法
为进一步提供切分精度,可以在词表中增加词的属性值,即为每一个词给出一个权重,这样每个词在字符串的权重就不同。最简单的词权重可以用词的词频表示,具体权重值可以通过该规模语料库获得。
2基于统计的分词(无字典分词)
主要思想:上下文中,相邻的字同时出现的次数越多,就越可能构成一个词。因此字与字相邻出现的概率或频率能较好的反映词的可信度。
主要统计模型为:N元文法模型(N-gram)、隐马尔科夫模型(Hidden Markov Model, HMM)
2.1N-gram模型思想
模型基于这样一种假设,第n个词的出现只与前面N-1个词相关,而与其它任何词都不相关,整句的概率就是各个词出现概率的乘积 .我们给定一个词,然后猜测下一个词是什么。当我说“艳照门”这个词时,你想到下一个词是什么呢?我想大家很有可能会想到“***”,基本上不会有人会想到“陈志杰”吧。N-gram模型的主要思想就是这样的。
对于一个句子T,我们怎么算它出现的概率呢?假设T是由词序列W1,W2,W3,…Wn组成的,那么P(T)=P(W1W2W3…Wn)=P(W1)P(W2|W1)P(W3|W1W2)…P(Wn|W1W2…Wn-1)
但是这种方法存在两个致命的缺陷:一个缺陷是参数空间过大,不可能实用化;另外一个缺陷是数据稀疏严重。
为了解决这个问题,我们引入了马尔科夫假设:一个词的出现仅仅依赖于它前面出现的有限的一个或者几个词。
如果一个词的出现仅依赖于它前面出现的一个词,那么我们就称之为bigram。即
P(T) = P(W1W2W3…Wn)=P(W1)P(W2|W1)P(W3|W1W2)…P(Wn|W1W2…Wn-1)
≈P(W1)P(W2|W1)P(W3|W2)…P(Wn|Wn-1)
如果一个词的出现仅依赖于它前面出现的两个词,那么我们就称之为trigram。
在实践中用的最多的就是bigram和trigram了,而且效果很不错。高于四元的用的很少,因为训练它需要更庞大的语料,而且数据稀疏严重,时间复杂度高,精度却提高的不多。设w1,w2,w3,...,wn是长度为n的字符串,规定任意词wi 只与它的前两个相关,得到三元概率模型,以此类推,N元模型就是假设当前词的出现概率只同它前面的N-1个词有关。
2.2隐马尔科夫模型思想
3基于规则的分词(基于语义)
通过模拟人对句子的理解,达到识别词的效果,基本思想是语义分析,句法分析,利用句法信息和语义信息对文本进行分词。自动推理,并完成对未登录词的补充是其优点。不成熟.
具体概念:有限状态机\语法约束矩阵\特征词库
4基于字标注的中文分词方法
以往的分词方法,无论是基于规则的还是基于统计的,一般都依赖于一个事先编制的词表(词典)。自动分词过程就是通过词表和相关信息来做出词语切分的决策。与此相反,基于字标注的分词方法实际上是构词方法。即把分词过程视为字在字串中的标注问题。由于每个字在构造一个特定的词语时都占据着一个确定的构词位置(即词位),假如规定每个字最多只有四个构词位置:即B(词首),M (词中),E(词尾)和S(单独成词),那么下面句子(甲)的分词结果就可以直接表示成如(乙)所示的逐字标注形式:
(甲)分词结果:/上海/计划/N/本/世纪/末/实现/人均/国内/生产/总值/五千美元/
(乙)字标注形式:上/B海/E计/B划/E N/S 本/s世/B 纪/E 末/S 实/B 现/E 人/B 均/E 国/B 内/E生/B产/E总/B值/E 五/B千/M 美/M 元/E 。/S
首先需要说明,这里说到的“字”不只限于汉字。考虑到中文真实文本中不可避免地会包含一定数量的非汉字字符,本文所说的“字”,也包括外文字母、阿拉伯数字和标点符号等字符。所有这些字符都是构词的基本单元。当然,汉字依然是这个单元集合中数量最多的一类字符。
把分词过程视为字的标注问题的一个重要优势在于,它能够平衡地看待词表词和未登录词的识别问题。在这种分词技术中,文本中的词表词和未登录词都是用统一的字标注过程来实现的。在学习架构上,既可以不必专门强调词表词信息,也不用专门设计特定的未登录词(如人名、地名、机构名)识别模块。这使得分词系统的设计大大简化。在字标注过程中,所有的字根据预定义的特征进行词位特性的学习,获得一个概率模型。然后,在待分字串上,根据字与字之间的结合紧密程度,得到一个词位的标注结果。最后,根据词位定义直接获得最终的分词结果。总而言之,在这样一个分词过程中,分词成为字重组的简单过程。然而这一简单处理带来的分词结果却是令人满意的。
5基于人工智能技术的中文分词方法
5.1神经网络分词算法
词算法该类分词算法是以模拟人脑运行,分布处理和简历数值计算模型工作的。它将分词知识的隐式方法存入神经网内部,通过自学习和训练内部权值,以达到正确的分词结果。
神经网络分词法的关键在于知识库(权重链表)的组织和网络推理机制的建立。算法的分词过程是一个生成分词动态网的过程,该过程是分步进行的:首先以确定待处理语句的权字串为基础,来确定网络处理单元;然后根据链接权重表激活输入/输出单元之间的链接,该过程可以采用某种激活方式,取一个汉字作为关键字,确定其链接表,不断匹配。神经网络分词法具有自学习、自组织功能,可以进行并行、非线性处理,并且反应迅速、对外界变换敏感;但是目前的基于神经网络的分词算法存在着网络模型表达复杂,学习算法收敛速度较慢,训练时间长,并且对已有的知识维护更新困难等不足。
5.2专家系统分词算法
专家系统分词算法从模拟人脑功能出发,构造推理网络,将分词过程看做是知识推理过程。该方法将分词所需要的语法、语意以及句法知识从系统的结构和功能上分离处理,将知识的表示、知识库的逻辑结构与维护作为首要考虑的问题。知识库按常识性知识与启发性知识分别进行组织。知识库是专家系统具有“智能”的关键行部件。
专家系统分词算法是一种统一的分词算法,不仅使整个分词处理过程简明,也使整个系统的运行效率提高。
6设立切分标志法这种方法
首先要收集那些标点符号(称为自然切分标志)以外的众多非自然切分标志,例如,只充当词首字或词尾的子,对这些非自然切分标志进行搜索,根据这些标志,把句子切分为若干较短的字段,然后在使用MM或者RMM等方法进一步切分。准确的说,这种方法并不是一种真正意义上的分词方法,只不过是自动分词的前处理而已。
6中文分词的难点
6.1歧义问题
最困难\最核心的问题:只用机械匹配进行分词,其精度不可能高,不能满足高标准要求.分为不同类型:交集型歧义\组合型歧义\真歧义,主要依靠上下文\语义来解决.
6.2未登录词识别
7小结
这篇文章讲的比较简单,其实就是要么太难(还不成熟),要么太简单(不够理想),但实际应用只要稍加改进就可以,日后再有收获,定来补充。如果你有任何建议或者批评和补充,请不吝留言指出,不胜感激,更多参考请移步互联网。
参考:
①abstractwind: http://www.cnblogs.com/lvpei/archive/2010/08/04/1792409.html
②朱巧明,李培峰等: 中文信息处理技术教程
③尹炳龙: 消除交叉歧义中文分词算法的研究与应用
分享到:
相关推荐
该算法的基本思想是从待分词文本的末尾开始,向前寻找最长的已存在于词典中的词语,以此达到最佳的分词效果。 在中文分词中,由于汉字组成的词语具有多样性,分词结果的准确性直接影响到后续的语义分析和信息提取。...
中文不同于英文,单词之间没有明显的分隔符,因此在处理中文文本时,我们需要先进行分词,即将连续的汉字序列切分成有意义的词汇单元。Sanford中文分词库是一种常用的分词工具,它基于统计模型,能够根据语料库学习...
中文自动分词算法是自然语言处理中的一项基本技术,旨在将中文文本切分成单个词语,以便更好地进行信息检索、自动标引、自动文摘、机器翻译、语言学研究、搜索引擎研究和自然语言理解等领域的应用。 分词的基本知识...
分词匹配算法有多种类型,其中机械分词方法是最基本的一种,机械分词方法可以分为正向最大匹配和反向最大匹配两种。 正向最大匹配 正向最大匹配是机械分词方法中的一种,它的工作原理是从左到右扫描汉字串,从左到...
这里介绍的是一种基于动态规划的算法,其基本思路是从输入的字符串(str)中逐个取出字符(currentchar),并尝试将当前字符与已构建的词(currentword)一起在词库中进行匹配。如果匹配成功,会根据匹配到的词的类型进行...
中文分词是中文信息处理的基础步骤,其目的是将连续的汉字序列切分成具有语义的词汇单元,对于后续的词性标注、句法分析、情感分析等任务至关重要。 首先,我们要理解贝叶斯网络(Bayesian Network)的基本概念。...
在这个"word分词算法(demo)"中,我们将探讨分词算法的基本原理、常见方法以及如何通过DEMO来理解和应用这些概念。 分词是NLP的第一步,它的目标是将句子拆分成一系列独立的词汇元素,这些元素称为“词元”(Token...
在中文文本处理中,由于汉字不带有明显的边界标识,因此需要借助特定的算法来将连续的汉字序列切分成有意义的词汇,这个过程就称为分词。正向最大匹配算法就是其中一种有效且应用广泛的策略。 正向最大匹配算法的...
总结起来,KNN中文分词算法是一种基于机器学习的文本处理技术,通过C++实现,利用基本词典和敏感词词典,并结合距离度量和空间索引结构进行高效分词。这个项目提供了实现这一算法的源代码,对于理解和研究中文分词有...
本文将详细探讨几种常见的中文分词算法,包括最大匹配法及其变体。 最大匹配法(FMM法)是一种广泛应用的分词策略,其基本思想是从文本中选取一个最大长度的候选词,然后与词典进行匹配。如果匹配失败,则逐渐减少...
自然语言处理(NLP)中的分词算法是处理文本数据的关键步骤,它的目的是将连续的汉字序列分割成具有独立意义的词语。在这个场景中,我们关注的是基于最大概率的汉语切分方法,它利用统计学原理来确定最可能的分词...
基于C语言文本文件的中文分词程序,可实现基本功能,还有待完善
### 基于改进最大匹配快速...通过以上介绍可以看出,基于改进的最大匹配快速中文分词算法不仅考虑了中文分词的基本需求,还针对实际应用场景进行了优化,特别是在处理混合文本、特殊词汇识别等方面表现出了较好的性能。
### 一种改进的中文分词歧义消除算法研究 #### 关键知识点概述 本文主要讨论了一种改进的中文分词歧义消除算法的研究。中文分词是自然语言处理(NLP)的重要组成部分,对于后续的语义分析、机器翻译等任务至关重要。...
综上所述,该文献提出的中文自动分词算法,通过改进的分词词典机制和结合最大匹配算法与概率算法的方式,有效地解决了中文分词中存在的问题,提高了分词的效率和准确性。这对于推动中文信息处理技术的发展具有重要...
#### 基本分词算法介绍与特点分析 根据余战秋在《中文分词技术及其应用初探》中的研究,主要介绍了三种基本的中文分词算法:基于字典和词库匹配的分词方法、基于词频统计的分词方法以及基于知识理解的分词方法。...
在IT领域,中文分词是自然语言处理(NLP)中的关键步骤,它涉及到将连续的汉字序列分割成有意义的词语单元,以便计算机能够理解和分析文本。本项目以"matlab中文分词——最大正向匹配法.rar"为主题,重点讨论了如何...
在自然语言处理(NLP)领域,中文分词是一项基础且关键的任务,它涉及到将连续的汉字序列分割成有意义的词汇单元。在这个“HMM实现中文分词python实现作业”中,我们关注的是如何利用隐马尔可夫模型(HMM)来解决这...