2021SC@SDUSC
我们组软件工程应用与实践的选题为jieba分词。
在网上搜集相关项目资料，对题目进行研读和总结，做出初步工作流程分析并分工：
jieba分词包整体的工作流程如下图所示：
在本项目中相关的算法知识，主要包括用于新词发现的隐马尔科夫模型和维特比算法、用于关键词提取的TextRank和TF-IDF算法。
根据组内分工，我将对维特比算法相关内容进行学习介绍和代码分析。
Viterbi算法
维特比算法是一个特殊但应用最广的动态规划算法，它是针对篱笆网络的有向图（Lattice）的最短路径问题而提出的。凡是使用隐含马尔可夫模型描述的问题都可以用维特比算法来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等。
算法概述图
Viterbi算法的基本思想是：如果最佳路径经过一个点，那么起始点到这个点的路径一定是最短路径，否则用起始点到这点更短的一条路径代替这段，就会得到更短的路径，这显然是矛盾的；从起始点到结束点的路径，必然要经过第n个时刻，假如第n个时刻有k个状态，那么最终路径一定经过起始点到时刻n中k个状态里最短路径的点。
将时刻t隐藏状态为i所有可能的状态转移路径i1到i2的状态最大值记为：
我们可以据此由初始时刻依次向后推出每一个时刻的最大概率隐藏状态。
维特比算法的基础1.如果概率最大的路径p(或者说最短路径)经过某个点，比如途中的X22，那么这条路径上的起始点S到X22的这段子路径Q，一定是S到X22之间的最短路径。否则，用S到X22的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优性原理。
2.从S到E的路径必定经过第i个时刻的某个状态，假定第i个时刻有k个状态，那么如果记录了从S到第i个状态的所有k个节点的最短路径，最终的最短路径必经过其中一条，这样，在任意时刻，只要考虑非常有限的最短路即可。
3. 结合以上两点，假定当我们从状态i进入状态i+1时，从S到状态i上各个节的最短路径已经找到，并且记录在这些节点上，那么在计算从起点S到第i+1状态的某个节点Xi+1的最短路径时，只要考虑从S到前一个状态i所有的k个节点的最短路径，以及从这个节点到Xi+1，j的距离即可。
用Viterbi算法进行的工作
在jieba分词中，采用了HMM进行新词发现，它将每一个字表示为B/M/E/S分别代表出现在词头、词中、词尾以及单字成词。将B/M/E/S作为HMM的隐藏状态，而连续的各个单字作为观测状态，其任务即为利用观测状态预测隐藏状态，并且其模型的A,B,π概率已经给出在文件中，所以这是一个标准的解码问题。在jieba分词中采用了Viterbi算法来进行求解。
词性分析部分与分词模块用了同一个基础的分词器，对于词典词的词性，将直接从词典中提取，但是对于新词，词性分析部分有一个专属的新词及其词性的发现模块。
用于词性标注的HMM模型与用于分词的HMM模型相似，同样将文字序列视为可见状态，但是隐藏状态不再是单单的词的位置（B/E/M/S），而变成了词的位置与词性的组合，如(B,v)(B,n)(S,n)等等。因此其初始概率向量、转移概率矩阵和表现概率矩阵和上一节中所用的相比都要庞大的多，但是其本质以及运算步骤都没有变化。
安装说明代码对 Python 2/3 均兼容，使用PyCharm 编辑代码。
- 全自动安装：easy_install jieba 或者 pip install jieba / pip3 install jieba
- 半自动安装：先下载 jieba · PyPI ，解压后运行 python setup.py install
- 手动安装：将 jieba 目录放置于当前目录或者 site-packages 目录
- 通过 import jieba 来引用
- 如果需要使用paddle模式下的分词和词性标注功能，请先安装paddlepaddle-tiny，pip install paddlepaddle-tiny==1.6.1。
