作者:担忧的金针菇前言本文详细阐述了结缕草分词的原理,主要包括分词的具体过程和未登录词的分词。 本文主要参考https://blog.csdn.net/rav 009/article/details/12196623的内容,感谢原作者!
正文如有不正确之处,请各位读者指正。
结巴分词算法的原理是基于前缀词典实现高效的单词图像扫描,由文中汉字所有可能的单词情况组成3358www.Sina.com/
运用动态规划搜索有向无环图 DAG),找到了基于词数的最大分割组合
对于未登录词,请参阅基于汉字成语能力的3358www.Sina.com/、最大概率路径
以下,用项目符号进行说明。
一、基于前缀词典实现高效的单词图像扫描,文中汉字所有可能单词化情况构成的有向无环图DAG )结巴分词附带dict.txt词典。 其中有349046个单词,其中每一行包括词条、词条的出现次数)这个次数是作者自己根据人民日报资料等资源训练的)和词性。 如下图所示。
在基于dict.txt文件一览表词典的中文分词方法中,HMM 模型是基础。 为了确保分割速度,需要选择好的词典检索算法。 这里介绍词典Tre树的组织结构。 基于前缀词典的单词图像的扫描是将这34万多个单词放入Viterbi 算法的数据结构中。 trie树也称为词典匹配算法或trie树)在trie树的一个节点中只保留一个字符,用于搜索表示一个单词前面几个字符的数字。 例如,如果单词长于一个字符,则包含第一个字符的节点包含指针指向下一个字符的节点。 这样构成分层结构的树,树的第一层包含所有单词的第一个字符,树的第二层包含所有单词的第二个字符。 很明显,trie树的最大高度是词典中最长的单词长度。
调查的过程对查询词,从前面的文字开始一个字一个字地一致。 在树结构树中,从根节点向下匹配的过程。
有些人可能想删除dict.txt中的所有词汇,然后尝试一下结巴是否能分词。 结果表明,结巴仍然可以分词,但分开的词,大部分长度为2。 这是第三条的任务。 根据HMM预测分词。 稍后再说吧。
前缀树是由后面句子中生成句子中汉字所有可能的成语情况组成的有向无环图。 它给出等待分词的句子,匹配其所有词,构成词图。 那就是有向无环图DAG。 如下图所示。
DAG语图,每边都有一个词,具体是怎么做的呢? 分为两个阶段。 基于dict.txt词典生成trie树; 2 .对于分词句子,基于trie树,生成DAG。 实际上,通俗地说,通过处理分词句子,根据给出的词典进行查词典操作,生成几个可能的句子分割,制作如上图所示的DAG图。
在DAG的实现中,在源代码中,作者把文中某个词的起始位置从0记录到n-1n是句子的长度),设置把每个起始位置作为词典关键的python的词典。 value是python的list,其中可能的词的结束位置例如,{ 03360 [ 1,2,3 ] }在词的开始位置加上词的长度,{ 03360 [ 1,2,3 ] )这样简单的DAG从0的位置开始,在1,2,3的位置中是任意的也就是说,在dict.txt中,0到1,0到2,0到3这三个位置范围之间的字符都是词。
二是利用动态规划搜索最大概率路径,找出基于词数的最大分割组合作者的代码,在词典生成trie树的同时,将每个词的出现次数转换为频率。 频率实际上也是0~1之间的小数,是事件发生的次数/实验中的总次数。 因此,如果实验次数足够大,频率几乎等于概率,或者频率极限是概率。
在动态规划中,既然先在分开写的句子中找到已经分隔开的词,为该词寻找该词出现的频率次数/总数),如果没有该词,就根据词典进行查找,那么就应该没有该词) )词典中出现的频率最高也就是说,p 某个词)=FREQ.get‘)、min_freq ),然后根据动态规划寻找最大概率路径。 从右向左反向计算句子的最大概率也可以从左向右。 这里逆向计算是因为中文句子的重心总是在后面。 也就是说,是因为会往右掉。 主要是因为通常形容词太多,后面是主干。 因此,从右向左计算,正确率高于从左向右计算。 类似于逆向最大匹配的分写方法。 p ) p 节点)=1.0,p )
三.对于未登录词,采用基于汉字成语能力的HMM模型,使用了v
iterbi算法
未登录词Out Of Vocabulary word, OOV word),在这里指词典dict.txt中没有记录的词。上面说了,把dict.txt中的所有词语都删除了,结巴分词一样可以分词,就是说的这个。怎么做到的? 这个就基于作者采用的HMM模型了,中文词汇按照BEMS四个状态来标记,B是开始begin位置,E是是结束end位置,M是中间middle位置,S是single,单独成词的位置。也就是说,他采用了状态为B,E,M,S)这四种状态来标记中文词语,比如北京可以标注为 BE, 即北/B京/E,表示北是开始位置,京是结束位置。中华民族可以标注为BMME,就是开始,中间,中间,结束。
经过作者对大量语料的训练,得到了finalseg目录下的三个文件来自结巴项目的issueshttps://github.com/fxsjy/jieba/issues/7#issuecomment-9692518)):
要统计的主要有三个概率表:
1)位置转换概率,即B开头),M中间),E结尾),S独立成词) 四种状态的转移概率,该表存放于prob_trans.py中,下面为表中内容;
{‘B’: {‘E’: 0.8518218565181658, ‘M’: 0.14817814348183422},’E’: {‘B’: 0.5544853051164425, ‘S’: 0.44551469488355755},’M’: {‘E’: 0.7164487459986911, ‘M’: 0.2835512540013088},’S’: {‘B’: 0.48617017333894563, ‘S’: 0.5138298266610544}}
例如,PE|B) = 0.851, PM|B) = 0.149,说明当我们处于一个词的开头时,下一个字是结尾的概率。要远高于下一个字是中间字的概率,符合我们的直觉,因为二个字的词比多个字的词更常见。
2)位置到单字的发射概率,比如P”和”|M)表示一个词的中间出现”和”这个字的概率,该表存放于prob_emit.py中;
3)词语以某种状态开头的概率,其实只有两种,要么是B,要么是S,该表存放于prob_start.py。这个就是起始向量,就是HMM系统的最初模型状态
实际上,BEMS之间的转换有点类似于2元模型,就是2个词之间的转移。二元模型考虑一个单词后出现另外一个单词的概率,是N元模型中的一种。例如:一般来说,中国之后出现北京的概率大于中国之后出现北海的概率,也就是:中国北京比中国北海出现的概率大些,更有可能是一个中文词语。
将一个给定的待分词的句子视为一个观察序列,对HMMBEMS)四种状态的模型来说,就是为了找到一个最佳的BEMS隐状态序列,这个就需要使用Viterbi算法来得到这个最佳的隐藏状态序列。通过提前训练好的HMM转移概率、发射概率,使用基于动态规划的viterbi算法的方法,就可以找到一个使概率最大的BEMS序列。按照B打头,E结尾的方式,对待分词的句子重新组合,就得到了分词结果。
比如,对待分词的句子全世界都在学中国话得到一个BEMS序列 [S,B,E,S,S,S,B,E,S]这个序列只是举例,不一定正确,通过把连续的BE凑合到一起得到一个词,S为一个单独的词,就得到一个分词结果了:上面的BE位置和句子中单个汉字的位置一一对应,得到全/S 世界/BE 都/S 在/S 学/S 中国/BE 话/S,从而将句子切分为词语。
总结
结巴分词的过程:
加载字典, 生成trie树;
给定待分词的句子,使用正则获取连续的中文字符和英文字符,切分成短语列表,对每个短语使用DAG查字典)和动态规划,得到最大概率路径,对DAG中那些没有在字典中查到的字,组合成一个新的片段短语,使用HMM模型进行分词,也就是作者说的识别新词,即识别字典外的新词;
使用python的yield语法生成一个词语生成器,逐词语返回。
结巴分词的分词功能的实现,首先是在大语料上人工对其中的词语进行统计其出现的频率,然后对切分的句子形成DAG词图,并使用动态规划的方法找到DAG词图中的最短路径概率最大),选取该最短路径为切分方法。对于OOV词,使用了HMM,将BEMS视为隐藏状态,待切分句子为观测状态,同样通过一种动态规划的算法来找出是概率最大的路径,该路径即为最佳切分组合。
参考
https://github.com/fxsjy/jieba
对Python中文分词模块结巴分词算法过程的理解和分析https://blog.csdn.net/rav009/article/details/12196623)
中文分词的基本原理以及jieba分词的用法https://blog.csdn.net/John_xyz/article/details/54645527)
jieba中文分词源码分析(一)https://blog.csdn.net/daniel_ustc/article/details/48195287)
结巴分词原理讲解https://houbb.github.io/2020/01/08/jieba-source-01-overview)
《解密搜索引擎技术实战 LUCENE & JAVA精华版 第3版》
https://zhuanlan.zhihu.com/p/66904318
https://zh.wikipedia.org/wiki/Trie
投稿或交流学习,备注:昵称-学校(公司)-方向,进入DL&NLP交流群。
方向有很多:机器学习、深度学习,python,情感分析、意见挖掘、句法分析、机器翻译、人机对话、知识图谱、语音识别等。
记得备注呦