第一部分 模型简介

        隐马尔可夫模型是马尔可夫链的一种，它的状态不能直接观察到，但能通过观测向量序列观察到，每个观测向量都是通过某些概率密度分布表现为各种状态，每一个观测向量是由一个具有相应概率密度分布的状态序列产生。所以，隐马尔可夫模型是一个双重随机过程 ----具有一定状态数的隐马尔可夫链和显示随机函数集。自20 世纪80年代以来，HMM被应用于语音识别，取得重大成功。到了90年代，HMM还被引入计算机文字识别和移动通信核心技术“多用户的检测”。HMM在生物信息科学、故障诊断等领域也开始得到应用。

        1.隐马尔可夫模型（HMM）可以用一个五元组来描述，包括2个状态集合和3个概率矩阵：
        （1）隐含状态S集合
        这些状态之间满足马尔可夫性质，是马尔可夫模型中实际所隐含的状态。这些状态通常无法通过直接观测而得到。（例如S1、S2、S3等等)
        （2）可观测符号O集合
        在模型中与隐含状态相关联，可通过直接观测而得到。(例如O1、O2、O3等等，可观测状态的数目不一定要和隐含状态的数目一致。）
        （3）初始状态概率矩阵 π
        表示隐含状态在初始时刻t=1的概率矩阵，(例如t=1 时，P(S1)=p1、P(S2)=P2、P(S3)=p3，则初始状态概率矩阵 π=[ p1 p2 p3 ].
        （4）隐含状态转移概率矩阵 A。
        描述了HMM模型中各个状态之间的转移概率。其中Aij = P( Sj | Si ),1≤i,,j≤N。表示在 t 时刻、状态为 Si 的条件下，在 t+1 时刻状态是 Sj 的概率。
        （5）观测状态转移概率矩阵 B （英文名为Confusion Matrix，直译为混淆矩阵不太易于从字面理解）。
        令N代表隐含状态数目，M代表可观测状态数目，则：Bij = P( Oi | Sj ), 1≤i≤M,1≤j≤N.表示在 t 时刻、隐含状态是 Sj 条件下，观察状态为 Oi 的概率。

        总结：一般的，可以用λ=(A,B,π)三元组来简洁的表示一个隐马尔可夫模型。隐马尔可夫模型实际上是标准马尔可夫模型的扩展，添加了可观测状态集合和这些状态与隐含状态之间的概率关系。

第二部分 基本问题

        1. 评估问题。
        给定观测序列 O=O1O2O3…Ot和模型参数λ=(A,B,π)，怎样有效计算某一观测序列的概率，进而可对该HMM做出相关评估。例如，已有一些模型参数各异的HMM，给定观测序列O=O1O2O3…Ot，我们想知道哪个HMM模型最可能生成该观测序列。通常我们利用forward 算法分别计算每个HMM产生给定观测序列O的概率，然后从中选出最优的HMM模型。
        这类评估的问题的一个经典例子是语音识别。在描述语言识别的隐马尔科夫模型中，每个单词生成一个对应的HMM，每个观测序列由一个单词的语音构成，单词的识别是通过评估进而选出最有可能产生观测序列所代表的读音的HMM而实现的。

        2.解码问题
        给定观测序列 O=O1O2O3…Ot 和模型参数λ=(A,B,π)，怎样寻找某种意义上最优的隐状态序列。在这类问题中，我们感兴趣的是马尔科夫模型中隐含状态，这些状态不能直接观测但却更具有价值，通常利用Viterbi算法来寻找。
        这类问题的一个实际例子是中文分词，即把一个句子如何划分其构成才合适。例如，句子“发展中国家”是划分成“发展-中-国家”，还是“发展-中国-家”。这个问题可以用隐马尔科夫模型来解决。句子的分词方法可以看成是隐含状态，而句子则可以看成是给定的可观测状态，从而通过建HMM来寻找出最可能正确的分词方法。

        3. 学习问题。
        即HMM的模型参数λ=(A,B,π)未知，如何调整这些参数以使观测序列O=O1O2O3…Ot的概率尽可能的大。通常使用Baum- Welch算法以及Reversed Viterbi算法解决。
怎样调整模型参数λ=(A,B,π)，使观测序列 O=O1O2O3…Ot的概率最大？

        4.针对每个问题，人们提出了相应的算法：
        （1）评估问题： 前向算法
        （2）解码问题： Viterbi算法
        （3）学习问题： Baum-Welch算法(向前向后算法)

第三部分 实验结果

        对于二阶马尔科夫过程来说，由于训练语料的规模所限，符号发射矩阵会存在数据稀疏的问题，因此要在程序中进行数据平滑处理。实验选取了两种方式进行数据平滑，其一是Good-Turing（古德-图灵）平滑方法，其二为加一平滑方式。

        语料来源：《人民日报》1998年一月语料。

        下面是运用Good-Turing（古德-图灵）平滑方法处理数据，最终获得的结果为：

        下面是运用加一平滑方法（词频都加一）处理数据，最终获得的结果为：

        从上面的结果中看出，加一平滑方法结果更好一些。

第四部分 源代码

        （1）文件名：util.h。下面好几个文件都要用到该文件，如将测试文件中的/去掉。

#include <string>

using namespace std;

/*
 * 函数功能：将字符串中的所有特定子串置换为新的字符串
 * 函数输入：str     需要进行操作的字符串
 *         old_str 旧的字符串
 *         new_str 新的字符串
 * 函数输出：置换完毕的字符串
 */
string& replace_all(string &str, string old_str, string new_str){
	while(1){
		string::size_type pos(0);
		if((pos = str.find(old_str)) != string::npos){
			str.replace(pos, old_str.length(), new_str);
		}else{
			break;
		}
	}
	return str;
}

        （2）文件名：prehmm.cpp。对文件进行预处理工作，函数的功能请参见代码中的注释。

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <cstdlib>
#include <map>
#include "util.h"

using namespace std;


/*
 * 函数功能：将训练语料和测试语料中出现的汉字进行编码，将他们的对应关系存入文件
 *         格式为：汉字-编码，编码从0开始
 * 函数输入：infile_1 训练语料文件名
 *         infile_2 测试语料文件名
 *         outfile  指定的输出文件名
 * 函数输出：名为outfile的文件
 */
void makeDB(string infile_1, string infile_2, string outfile){
	//读取输入文件
	ifstream fin_1(infile_1.c_str());
	ifstream fin_2(infile_2.c_str());
	if(!(fin_1 && fin_2)){
		cerr << "makeDB : Open input file fail !" << endl;
		exit(-1);
	}
	//打开输出文件
	ofstream fout(outfile.c_str());
	if(!fout){
		cerr << "makeDB : Open output file fail !" << endl;
		exit(-1);
	}
	
	map<string, int> map_cchar;
	int id = -1;
	string line = "";
	string cchar = "";
	//读取输入文件内容
	while(getline(fin_1, line)){
		line = replace_all(line, "/", "");
		if(line.size() >= 2){
			//逐字读取
			for(int i = 0; i < line.size() - 1; i += 2){
				cchar = line.substr(i, 2);
				if(map_cchar.find(cchar) == map_cchar.end()){
					++id;
					map_cchar[cchar] = id;
				}
			}
		}
	}
	while(getline(fin_2, line)){
		line = replace_all(line, "/", "");
		if(line.size() >= 2){
			//逐字读取
			for(int i = 0; i < line.size() - 1; i += 2){
				cchar = line.substr(i, 2);
				if(map_cchar.find(cchar) == map_cchar.end()){
					++id;
					map_cchar[cchar] = id;
				}
			}
		}
	}
	
	//输出到文件
	map<string, int>::iterator iter;
	for(iter = map_cchar.begin(); iter != map_cchar.end(); ++iter){
		//cout << iter -> first << " " << iter -> second << endl;
		fout << iter -> first << " " << iter -> second << endl;
	}

	fin_1.close();
	fin_2.close();
	fout.close();
}


/*
 * 函数功能：将训练语料每个汉字后面加入对应的BMES状态
 * 函数输入：infile  训练语料文件名
 *         outfile 指定的输出文件名
 * 函数输出：名为outfile的文件
 */
void makeBMES(string infile, string outfile){

	ifstream fin(infile.c_str());
	ofstream fout(outfile.c_str());
	if(!(fin && fout)){
		cerr << "makeBMES : Open file failed !" << endl;
		exit(-1);
	}
	
	string word_in = "";
	string word_out = "";	
	string line_in = "";
	string line_out = "";

	while(getline(fin, line_in)){
		if(line_in.size() > 1){
			line_out.clear();
			line_in = replace_all(line_in, "/", " ");
			istringstream strstm(line_in);
			while(strstm >> word_in){
				word_out.clear();
				if(word_in.size()%2 != 0){
					cout << "单词不符合要求：" << word_in << endl;
					continue;
				}
				int num = word_in.size()/2;	//单词中包含多少个汉字
				if(num == 0){
					continue;
				}

				if(num == 1){
					word_out = word_in;
					word_out += "/S";
				}else{
					//复制单词中的第一个字
					word_out.insert(word_out.size(), word_in, 0, 2);
					word_out += "/B";
					//逐个复制单词中间的字
					for(int i = 1; i < num - 1; i++){
						word_out.insert(word_out.size(), word_in, 2*i, 2);
						word_out += "/M";
					}
					//复制单词中最后的汉字
					word_out.insert(word_out.size(), word_in, 2*num - 2, 2);
					word_out += "/E";
				}

				line_out += word_out;
			}
			
			//cout << line_out << endl;
			fout << line_out << endl;
		}
	}

}


/*
 * 主函数
 */
int main(int argc, char *argv[]){
	if(argc < 5){
		cout << "Usage: " << argv[0] << " train_file test_file db_file bmes_file" << endl;
		exit(-1);
	}
	//构造DB文件，输入训练语料、测试语料、输出文件名
	makeDB(argv[1], argv[2], argv[3]);

	//构造BMES文件，输入训练语料、输出文件名
	makeBMES(argv[1], argv[4]);

}

#include <iostream>
#include <fstream>
#include <map>
#include <cstdlib>

using namespace std;

/*
 * 转换类，获取编号
 */
class DB{
	private:
		map<string, int> cchar_map;	//汉字-编码映射
		map<int, string> index_map;	//编码-汉字映射
	public:
		DB();
		DB(string file);
		string getCchar(int id);		//根据编码获得汉字
		int getObservIndex(string cchar);	//根据汉字获得编码
		int getStateIndex(char state);		//根据状态获得状态编号
};

//无参构造函数
DB::DB(){

}

//有参构造函数
DB::DB(string file){
	ifstream fin(file.c_str());
	if(!fin){
		cout << "Open input file fail ! Can't init Trans !" << endl;
		exit(-1);
	}
	string line = "";
	string word = "";
	string cchar = "";
	int id = 0;
	while(getline(fin, line)){
		istringstream strstm(line);
		strstm >> word;
		cchar = word;
		strstm >> word;
		id = atoi(word.c_str());
		//加入map
		cchar_map[cchar] = id;
		index_map[id] = cchar;
	}
	cout << "cchar_map大小： " << cchar_map.size() << endl;
	cout << "index_map大小： " << index_map.size() << endl;
}

//将状态转换为数字编号
int DB::getStateIndex(char state){
	switch(state){
		case 'B' :
			return 0;
			break;
		case 'M' :
			return 1;
			break;
		case 'E' :
			return 2;
			break;
		case 'S' :
			return 3;
			break;
		default :
			return -1;
			break;
	}
}

//将汉字转换为数字编号
int DB::getObservIndex(string cchar){
	map<string, int>::iterator iter = cchar_map.find(cchar);
	if(iter != cchar_map.end()){
		return iter -> second;
	}else{
		return -1;
	}
}

//将数字编号转换为汉字
string DB::getCchar(int id){
	map<int, string>::iterator iter = index_map.find(id);
	if(iter != index_map.end()){
		return iter -> second;
	}else{
		return NULL;
	}
}

#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <iomanip>
#include <cmath>
#include <list>
#include "db.h"

using namespace std;

const int N = 4;		//隐藏状态的数目
const int M = 5236;		//汉字的个数
const double VALUE = http://www.mamicode.com/1.0;	//平滑算法增加的值>
        （5）文件名：hmm.h。将存储在文件中的HMM的模型参数读取到内存中，构造为一个HMM对象，供其他程序使用。
#include <fstream>
#include <sstream>
#include <string>
#include <cstdlib>

const int N = 4;
const int M = 5236;

//定义HMM模型
class HMM{

	public:
		int n;		//状态数目
		int m;		//可能的观察符号数目
		double A[N][N];	//状态转移概率矩阵
		double B[N][M];	//符号发射概率矩阵
		double Pi[N];	//初始状态概率
		HMM();
		HMM(string f1, string f2, string f3);
};

//无参构造函数
HMM::HMM(){

}

//有参构造函数
HMM::HMM(string f1, string f2, string f3){
	ifstream fin_1(f1.c_str());
	ifstream fin_2(f2.c_str());
	ifstream fin_3(f3.c_str());
	if(!(fin_1 && fin_2 && fin_3)){
		exit(-1);
	}

	string line = "";
	string word = "";

	//读取Pi
	getline(fin_1, line);
	istringstream strstm_1(line);
	for(int i = 0; i < N; i++){
		strstm_1 >> word;
		Pi[i] = atof(word.c_str());
	}
	
	//读取A
	for(int i = 0; i < N; i++){
		getline(fin_2, line);
		istringstream strstm_2(line);
		for(int j = 0; j < N; j++){
			strstm_2 >> word;
			A[i][j] = atof(word.c_str());
		}
	}

	//读取B
	for(int i = 0; i < N; i++){
		getline(fin_3, line);
		istringstream strstm_3(line);
		for(int j = 0; j < M; j++){
			strstm_3 >> word;
			B[i][j] = atof(word.c_str());
		}
	}
	
	fin_1.close();
	fin_2.close();
	fin_3.close();
}

        （6）文件名：viterbi.cpp。维特比算法，用于分词。
#include <iostream>
#include <fstream>
#include <sstream>
#include <string>
#include <stack>
#include "hmm.h"
#include "db.h"

using namespace std;

HMM hmm("Pi.mat", "A.mat", "B.mat");	//初始化HMM模型
DB db("db.txt");			//初始化字典

/*
 * Viterbi算法进行分词
 */
string viterbi(string str_in){
	string str_out = "";
	if(str_in.size() == 0){
		return str_out;
	}

	//分配矩阵空间
	int row = str_in.size() / 2;	//输入句子中的汉字个数

	double **delta = new double *[row];
	for(int i = 0; i < row; i++){
		delta[i] = new double[N]();
	}

	int **path = new int *[row];
	for(int i = 0; i < row; i++){
		path[i] = new int[N]();
	}

	//中间变量
	string cchar = "";	//存放汉字
	int max_path = -1;
	double val = 0.0;
	double max_val = 0.0;

	//初始化矩阵,给delta和path矩阵的第一行赋初值
	cchar = str_in.substr(0, 2);
	int cchar_num = db.getObservIndex(cchar);
	for(int i = 0; i < N; i++){
		delta[0][i] = hmm.Pi[i] + hmm.B[i][cchar_num];	//对数
		path[0][i] = -1;
	}

	//给delta和path的后续行赋值（对数）
	for(int t = 1; t < row; t++){
		cchar = str_in.substr(2*t, 2);
		cchar_num = db.getObservIndex(cchar);
		for(int j = 0; j < N; j++){
			max_val = 100000.0;
			//max_path = -1;
			max_path = 0;
			for(int i = 0; i < N; i++){
				val = delta[t-1][i] + hmm.A[i][j];
				if(val < max_val){
					max_val = val;
					max_path = i;
				}
			}

			delta[t][j] = max_val + hmm.B[j][cchar_num];
			path[t][j] = max_path;
		}
	}

	//找delta矩阵最后一行的最大值
	max_val = 100000.0;
	//max_path = -1;
	max_path = 0;
	for(int i = 0; i < N; i++){
		if(delta[row-1][i] < max_val){
			max_val = delta[row-1][i];
			max_path = i;
		}
	}

	//从max_path出发,回溯得到最可能的路径
	stack<int> path_st;
	path_st.push(max_path);
	for(int i = row - 1; i > 0; i--){
		max_path = path[i][max_path];
		path_st.push(max_path);
	}
	
	//释放二维数组
	for(int i = 0; i < row; i++){
		delete []delta[i];
		delete []path[i];
	}
	delete []delta;
	delete []path;

	//根据标记好的状态序列分词
	int pos = 0;
	int index = -1;
	while(!path_st.empty()){
		index = path_st.top();
		path_st.pop();
		str_out.insert(str_out.size(), str_in, pos, 2);
		if(index == 2 || index == 3){
			//状态为E或S
			str_out.append("/");
		}
		pos += 2;
	}
}


        （7）文件名：main.cpp。主函数，调用维特比算法进行分词工作，并对分词结果进行比对，统计后输出结果。
#include <cstdlib>
#include <vector>
#include <iomanip>
#include <map>
#include <algorithm>
#include <sys/time.h>
#include <sys/stat.h>
#include "util.h"
#include "viterbi.cpp"


const long MaxCount = 50000;	//需要切分的最大句子数量，若该值大于文件中
				//实际的句子数量，以实际句子数量为准。

//获取当前时间(ms)
long getCurrentTime(){
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec*1000 + tv.tv_usec/1000;
}

//获取文件大小
unsigned long getFileSize(string file_path){
	unsigned long filesize = -1;
	struct stat statbuff;
	if(stat(file_path.c_str(), &statbuff) < 0){
		return filesize;
	}else{
		filesize = statbuff.st_size;
	}
		return filesize;
}


/*
 * 函数功能：计算切分标记的位置
 * 函数输入：1.strline_in未进行切分的汉字字符串
           2.strline_right进行切分后的汉字字符串
 * 函数输出：vecetor，其中存放了strline_in中哪些位置放置了分词标记
 *         注意：vector中不包含最后标记的位置，但是包含位置0。
 */
vector<int> getPos(string strline_right, string strline_in){
	int pos_1 = 0;
	int pos_2 = -1;
	int pos_3 = 0;
	string word = "";
	vector<int> vec;

	int length = strline_right.length();
	while(pos_2 < length){
		//前面的分词标记
		pos_1 = pos_2;
		
		//后面的分词标记
		pos_2 = strline_right.find('/', pos_1 + 1);

		if(pos_2 > pos_1){
			//将两个分词标记之间的单词取出
			word  = strline_right.substr(pos_1 + 1, pos_2 - pos_1 - 1);
			//根据单词去输入序列中查出出现的位置
			pos_3 = strline_in.find(word, pos_3);
			//将位置存入数组
			vec.push_back(pos_3);
			pos_3 = pos_3 + word.size();
		}else{
			break;
		}
	}
	
	return vec;
}


/*
 * 获取标准切分和程序切分的结果
 */
string getString(string word, int pos, vector<int> vec_right){
	char ss[1000];
	int i = 0;
	int k = 0;
	if(vec_right.size() == 0){
		return word;
	}
	while(vec_right[i] < pos){
		i++;
	}
	for(int j = 0; j < word.size(); j++){
		if(j == vec_right[i] - pos){
			if(j != 0){
				ss[k] = '/';
				++k;
			}
			++i;
		}
		ss[k] = word[j];
		++k;
	}
	ss[k] = '\0';
	string word_str = ss;

	return word_str;
}

/*
 * 函数功能：获取单个句子切分的结果统计
 * 函数输入：1.vec_right 正确的分词标记位置集合
 *           2.vec_out   函数切分得到的分词标记位置集合
 * 函数输出：返回一个veceor，含有4个元素，分别为：
 *          切分正确、组合型歧义、未登录词、交集型歧义的数量
 *
 */
vector<int> getCount_2(string strline, vector<int> vec_right, vector<int> vec_out, vector<string> &vec_err){
	vector<int> vec(4, 0);	//存放计算结果
	//建立map
	map<int, int> map_result;
	for(int i = 0; i < vec_right.size(); i++){
		map_result[vec_right[i]] += 1;
	}
	for(int i = 0; i < vec_out.size(); i++){
		map_result[vec_out[i]] += 2;
	}

	//统计map中的信息
	//若value=http://www.mamicode.com/1，只在vec_right中>