chanong 中文分词算法是指将汉字序列分割成单独的单词。 与英语使用空格作为自然分隔符不同，汉字在语义识别时需要将多个字符组合成单词才能表达真正的含义。 。 分词算法是文本挖掘的基础，通常应用于自然语言处理、搜索引擎、智能推荐等领域。
1.分词算法的分类
中文分词算法大致分为三类。 第一类是基于字符串匹配，即扫描字符串。 如果发现字符串的子串与字典中的单词相同，则认为匹配，例如机械分词方法。 这类分词通常会添加一些启发式规则，如“正向/反向最大匹配”、“长词优先”等。第二类是基于统计和机器学习的分词方法。 他们基于手动标记的词性和统计特征对中文进行建模，即根据观察到的数据（标记语料库）训练模型参数。 在分词阶段 然后利用模型计算各种分词出现的概率，将概率最大的分词结果作为最终结果。 常见的序列注释模型包括HMM和CRF。 这类分词算法可以很好地处理歧义和未记词问题，效果比前一类要好，但需要大量的人工标注数据，分词速度较慢。 第三类是通过让计算机模拟人类对句子的理解来达到单词识别的效果。 由于中文语义的复杂性，很难将各种语言信息组织成机器可以识别的形式。 目前，该分词系统还处于实验阶段。 。
2.机械分词算法
机械分词方法也称为基于字符串匹配的分词方法。 它将待分析的字符串按照一定的策略与“足够大”的机器字典中的条目进行匹配。 如果在字典中找到字符串，则匹配成功（识别出单词）。 这是最简单的分词方法，但是非常高效且常用。
(1) 匹配方法
机械分词方法根据扫描方向不同可分为正向匹配和反向匹配； 根据不同长度的优先级匹配，可以分为最大（最长）匹配和最小（最短）匹配； 常用的几种机械分词方法如下：
l 前向最大匹配法（从左到右的方向）； 例如，例句“大观数据是一家大数据公司”，采用前向最大匹配法分词的结果是“大观/数据/是一家/家/大数据/公司”
l 反向最大匹配法（从右到左的方向）； 同样，用例句“大观数据是一家大数据公司”，使用反向最大匹配法分词的结果是“大观/data/is/a/big data/”
l 最小分词（最小化每句话的词数）。 例句“大观数据是一家大数据公司”分为“大观数据/is/a/大数据公司”。
(2)消除歧义
由于机械分词中同一个句子往往包含多种分词组合，因此需要消除歧义才能得到最优的分词结果。
以非常常见的MMSEG机械分词算法为例。 MMSEG常用于搜索引擎Solr中，是一种非常可靠且高效的分词算法。 MMSEG 有四个消歧规则。 它按顺序使用这四个规则进行过滤，直到只有一个结果或使用第四个规则。 这四个规则是：
l 为了最大匹配，选择“短语长度最大”的短语，然后选择该短语的第一个单词作为第一个分词。 例如“中国人民万岁”，匹配结果为：
中国人
中国人
中国/人民/万岁
中国人民万岁/人民/
本例中，“最长短语长度”短语为后两个，因此选择“中国人/人民/万岁”中的“中国人”或“中国/人民/万岁”中的“中国”。
l 最大平均字长。 按规则1过滤后，如果剩余短语多于1个，则选择平均词长最大的一个（平均词长=短语总单词数/单词数）。 例如，“生活水平”可能会导致以下短语：
生命/活水/水位（4/3=1.33）
生命/水/等级（4/3=1.33）
生活/标准(4/2=2)
根据这个规则，你绝对可以选择“居住/级别”这个词组
l 最小字长变化率。 这个变化率一般可以通过标准差来确定。 例如，对于“中国人民万岁”这句话，我们可以计算：
中国/人民/万岁（标准差=sqrt(((2-2)^2+(2-2)^2+(2-2^2))/3)=0)
中国人民/人民万岁（标准差=sqrt(((2-3)^2+(2-1)^2+(2-2)^2)/3)=0.8165)
所以我选择了“中国/人民/万岁”这句话。
计算短语中所有单词词出现频率的自然对数，然后将结果值相加，取总和最大的短语。 例如：
设施/服务/服务
设施/和/服务
这两个短语中分别有两个单字词“吾”和“和”。 假设“无”作为单字词的出现频率为5，“和”作为单字词的出现频率为10。对5取和10的自然对数，然后取最大值，所以就拿“和”字所在的短语来说，即“/and/”。
(3)机械分词的缺陷
机械分词方法是一种非常简单、高效的分词方法。 速度非常快，时间复杂度为O(n)，效果也不错。 但缺点是它不能很好地处理歧义和生词，不能处理字典中没有出现的单词。 因此往往需要其他分词方法的配合。
3、基于n-gram的分词算法
(一)概念
基于词的n-gram模型是一种典型的生成模型。 许多早期的统计分词都以它为基础模型，然后用其他未注册词识别模块对其进行扩展。 基本思想是：首先根据字典（可以从训练语料库或外部字典中提取）简单地匹配句子，找到所有可能的字典单词，然后将它们和所有单个单词作为结果。 点，构造一个n元分段词图。 图中的节点表示可能的候选单词，边表示路径，边上的 n 元概率表示成本。 最后，使用相关搜索算法（动态规划）从图中找到最小成本。 该路径作为最终的分词结果。
图1：n-gram分词算法图解
(2)解决方法
假设随机变量S是汉字序列，W是S上所有可能可以分词的词序列。分词过程应该是找到条件概率P(W|S)最大的分词词序列W* ）， 那是：
根据贝叶斯公式，可以改写为：
由于分母为归一化因子，P(S|W)为固定值，因此求解公式变为：
如果使用单变量模型，则公式变为：
使用二元模型，公式成为解决方案
以二元模型为例，求解示例图中的短语“ into ”时，分词序列为“//sub”和“/into/”的概率分别为：
这里P(组合|开始)、P(成分|组合)、P(子|成分)、P(结束|子)都是通过大量语料统计得到的，所以可以通过概率相乘来判断是哪个分词顺序比较好。 示例图中，可以通过动态划分算法计算出最终的最优分词序列。
n-gram的分词方法是一种统计分词算法，比简单的机械分词算法更加准确。 但该算法基于现有词典，因此很难发现新词。
4.基于隐马尔可夫模型的分词算法
(1)隐马尔可夫模型
隐马尔可夫模型（Model，简称HMM）是最简单的动态贝叶斯网络（ ）。 是一个特别著名的有向图模型。 它主要用于时间序列数据建模，并用于语音识别和自然语言。 广泛应用于加工等领域。 在分词算法中，经常使用隐马尔可夫作为可以发现新词的算法。 通过海量数据学习，可以一一识别人名、地名、网络生词等，应用场景广泛。 （大观数据蒋永清）
隐马尔可夫模型是马尔可夫链的一种。 它的状态不能直接观察到，但可以通过一系列观察向量来观察。 每个观测向量由具有相应概率密度分布的状态序列生成。 如图所示，隐马尔可夫模型中的变量可以分为两组。 第一组是状态变量{y1,y2,…,yn}，其中yi表示第i时刻的系统状态。 通常假设状态变量是隐藏的且不可观察的，因此状态变量也称为隐藏变量。 第二组是观测变量{x1,x2,…,xn}，其中xi表示第i时刻的观测值。 在隐马尔可夫模型中，系统通常在多个状态之间转换，因此状态变量yi的取值范围通常是具有N个可能值的离散空间。
图 2：隐马尔可夫模型图示
图中的箭头表示变量之间的依赖关系。 任何时刻，观测变量的值只取决于状态变量，即xi由yi决定，与其他状态变量和观测变量的值无关。 同时，i时刻的状态yi只依赖于i-1时刻的状态yi-1，与其他n-2个状态无关。 这就是所谓的“马尔可夫链”，即系统下一时刻的状态仅由当前状态决定，不依赖于之前的任何状态。
(2)隐马尔可夫的求解
一般来说，HMM可以记为五元组u=(S,K,A,B,π)，其中S是状态集，K是输出符号，即观察集，A是状态转移概率，B 为符号。 发射概率 π 是初始状态的概率分布。 HMM主要解决三个基本问题：
估计问题，给定一个观测序列O=O1,O2,O3,...,Ot，模型u=(A,B,π)，计算观测序列的概率；
序列问题，给定一个观测序列O=O1,O2,O3...Ot，模型μ=(A,B,π)，计算最优状态序列Q=q1,q2,q3...qt；
参数估计问题，给定一个观测序列O=O1,O2,O3...Ot，如何调整模型的参数μ=(A,B,π)使得P(O|μ)最大化。
隐马尔可夫估计问题可以通过前向/后向动态规划算法解决； 序列问题可以通过算法解决； 参数估计问题可以通过EM算法来解决。 通过海量语料数据，可以轻松快速地学习HMM图模型。
(3)HMM分词方法
隐马尔可夫的三大问题分别对应分词的几个步骤。 参数估计问题是分词的学习阶段。 分词模型的各种参数是通过海量语料数据学习和总结的。 状态序列问题是分词的执行阶段。 通过观察变量（即待分词的句子序列）来预测最优状态序列（分词结构）。
我们设置状态值集合S = (B,M,E,S)，表示每个状态代表该单词在单词中的位置，B代表该单词是单词中的起始单词，M代表该单词在单词中的起始单词。单词。 中间词中，E代表词中的结束词，S代表单字词； 观测值集合K=（均为汉字）； 那么中文分词的问题就是通过观察序列来预测最优状态序列。
例如，观察序列为：
O = 小红在大观数据工作
预测的状态序列为：
Q=
根据这个状态序列我们可以进行分词：
BE/BE/S/BMME/
所以分词结果如下：
晓红/Job/余/大观数据/
由于HMM分词算法是基于词状态（BEMS）的，因此非常适合新词发现。 只要一个新词被标记为“BMME”，即使它没有出现在历史词典中，HMM分词算法也可以识别它。
5、基于条件随机场的分词算法
(1)条件随机场模型
条件随机场（Field，简称CRF）是一种判别性无向图模型。 它是一种随机场，通常用于标记或分析序列语料库，例如自然语言文本或生物序列。 与通过联合分布建模的隐马尔可夫模型不同，条件随机场尝试对给定观测值的多个变量的条件概率进行建模。 （大观数据蒋永清）
具体来说，如果 x = {x1, x2, …, xn} 是观测序列，y = {y1, y2, …, yn} 是相应的标记序列，那么条件随机场的目标就是构造条件随机场概率模型 P(y|x)。 设图G = 表示一个无向图，节点与标签变量y中的元素一一对应，yv表示节点v对应的标签变量，n(v)表示节点v的相邻节点.如果图G中的每个变量yv满足马尔可夫性质，即：
那么(y,x)就构成了一个条件随机场。 也就是说，条件概率只与x、y的相邻节点有关，与其他y节点无关。
图 3：条件随机场模型图示
理论上，图G可以具有任何结构，只要它能够表达标记变量之间的条件独立关系即可。 但在实际应用中，尤其是在对标记序列进行建模时，最常用的仍然是上图所示的链式结构，即“链式条件随机场”。
(2)条件随机场的求解方法
条件随机场使用图结构上的势函数和团来定义条件概率 P(y|x)。 给定一个观测序列x，链式条件随机场主要包含两种关于标签变量的派系，即单个标签变量{yi}和相邻标签变量{yi-1，yi}。 在条件随机场中，通过选择适当的势函数并引入特征函数，可以得到条件概率的定义：
在：
其中，tk(yi - 1, yi, x, i)是在观测序列的两个相邻标记位置处定义的传递特征函数，用于描述相邻标记变量之间的相关性以及观测序列对他们。 ,(yi,x,i)是在观测序列的标记位置i处定义的状态特征函数，用于描述观测序列对标记变量的影响。 λk 和 是参数，Z 是归一化因子。
两个特征函数tk(yi - 1, yi, x, i)和sl(yi, x, i)可以统一为：fk(yi-1, yi, x, i)，则有：
在：
给定训练数据集，经验概率分布是已知的，并且可以通过最大化训练数据的对数似然函数来找到模型参数。 添加惩罚项后，训练数据的对数似然函数为：
其中 σ 是可调整的惩罚权重。 求似然函数 L(w) 中 w 的偏导数，令：
Wi可以按顺序找到。
(3)条件随机场分词方法
条件随机场，如隐马尔可夫，也使用BMES的四个状态位进行分词。 以下面的句子为例：
中国是一个伟大的国家
嗯嗯嗯
条件随机场解码就是在上述由标记组成的数组中寻找一条最优路径。
我们需要找出每个词（即观察变量）对应的每个状态BMES（即标签变量）的概率。 例如，对于观测变量“国家”，当前标记变量为E，上一个观测变量为“中”，上一个标记变量为B，则：
t(B, E, '国') 对应于条件随机场中相邻标记变量{yi-1, yi}的势函数：
s(E, '国') 对应于条件随机场中单个标记变量 {yi} 对应的势函数 sl(yi, x, i)：
t(B, E, '') 和 s(E, '') 对应的权重 λk 都是使用大量带注释的语料库通过条件随机场训练的。 因此，分词的标记识别就是针对每个观察变量求标记变量（BMES）的状态序列的最大概率值，即求：
概率组合的最大值。 该解决方案类似于隐马尔可夫，可以使用算法来求解。
(4)条件随机场分割的优缺点
条件随机场分词是一种高精度的分词方法。 它比隐马尔可夫更准确，因为隐马尔可夫假设观测变量xi只与当前状态yi有关，而与其他状态yi-1无关。 yi+1 无关； 条件随机场假设当前观测变量xi与上下文相关。 例如，当前标记状态为E，前一个单词标记状态为B时，输出“国”字的概率。因此，通过上下文分析，条件随机场分词将提高到更高的准确率。 然而，由于其复杂度较高，条件随机场一般具有较高的训练成本。
6、大观数据分词算法应用
大观数据是一家新兴的高科技大数据公司。 其创始人来自腾讯、百度、盛大、搜狗等知名公司，拥有非常深厚的技术实力。 在分词技术领域，大观数据借鉴国内外优秀项目，升级了多项分词算法，积累了大量分词词典。 此外，大观文本挖掘集成了全套自然语言处理技术和机器学习技术。 它在分词的基本文本处理功能上集成了词性标注、句法分析、命名实体识别、文本标签提取等功能模块。 在此基础上，与SVM和GBRT相结合。 等机器学习算法，实现认知层面的自动文本分类、涉黄政治分析、垃圾评论识别等功能。
总结
本文介绍了几种常见的分词算法及其原理，并分析了它们相应的优缺点。在文本挖掘、搜索引擎等领域使用时，需要根据不同的场景使用不同的分词算法和词典来实现最有效、最准确的分词效果。
微信扫一扫打赏
支付宝扫一扫打赏
