维特比算法解决隐马尔可夫模型解码问题（中文句法标注）

圆圈：隐藏状态            方框：观察状态 
虚线圆圈：非法转移      虚线：计算路径  
q：隐藏空间状态              o：观察时间序列状态

String observationStr="病有发热恶寒者；发于阳也，无热恶寒者；发于阴也。";//观察序列
String[] states={"B","I","O"};//状态序列
double start_probability=0.3333;//初始状态概率
String str="书名：伤寒论。作者：张仲景。朝代：东汉。";
String stateStr=MethodUilt.Vitrerbi(str, start_probability, Amatrixpath, Bmatrixpath);//隐藏状态序列，即隐含马尔科夫模型的词类标注
System.out.println("观察序列：\t"+str.replaceAll("", "\t")+"\n标注序列：\t\t"+stateStr);
		

	/**
	 * 针对马尔科夫模型中第二个问题，采用维特比算法进行句子标注，其中主要还是动态规划思想
	 * @param observationStr 观察序列
	 * @param states         状态序列
	 * @param start_probability  初始化状态,即π
	 * @param Amatrixpath    发射矩阵路径
	 * @param Bmatrixpath    转移矩阵路径
	 * start_probability, transititon_probability, emission_probability
	 * @return
	 */
	public static String Vitrerbi(String observationStr,double start_probability,String Amatrixpath,String Bmatrixpath){
		//将观察序列切词存储在数组里面
		String[] ObserArr=observationStr.split("");
		//将发射矩阵放入数组中
		String[] emissionArrs=HeplerUilt.readStrFile(Amatrixpath, "\n").split("\n");//文本中发射矩阵逐次切割放于一位数组中
		Map<String,BIOEntity> countMap=new HashMap<String,BIOEntity>();//实例化map，存储：词+实体（二维数组）
		for(int i=0;i<emissionArrs.length;i++){
			String[] rowdata = emissionArrs[i].split("\t");
			countMap.put(rowdata[0], new BIOEntity(rowdata[0],Double.parseDouble(rowdata[1]), Double.parseDouble(rowdata[2]), Double.parseDouble(rowdata[3])));
		}
		//转移概率矩阵放入数组中
		String[] transititonArr=HeplerUilt.readStrFile(Bmatrixpath, "\t").split("\t");
		double[][] transArr=new double[3][3];//存放转移矩阵
		int k=0;
		for(int i=0;i<transArr.length;i++){
			for(int j=0;j<transArr[i].length;j++){
				transArr[i][j]=Double.parseDouble(transititonArr[k]);
				k++;
			}
		}
		//隐含的标注序列
		String stateStr="";
		double V=0;//每步V*P(q_i|q_i-1)*P(w|q_i)
		List list = new LinkedList();//存放路径
		//初始状态V的值
		String tarWord=ObserArr[1];//首个字母
		for(Map.Entry<String, BIOEntity> entry : countMap.entrySet()){
			if(entry.getKey().equals(tarWord)){
				double emission_probability=HeplerUilt.getMax(entry.getValue().getXb(), entry.getValue().getXi(), entry.getValue().getXo());
				String prior=HeplerUilt.compareMark(entry.getValue().getXb(), entry.getValue().getXi(), entry.getValue().getXo());
				list.add(prior);
				V=start_probability*emission_probability;
				//System.out.println(tarWord+":"+start_probability+":"+emission_probability+":"+prior+":"+HeplerUilt.DecFormat(4,V));
			}
		}
		//观察序列O，第二个状态到结束
		for(int i=2;i<ObserArr.length;i++){//由初始状态生成V，接着后面遍历观察序列进行
			for(Map.Entry<String, BIOEntity> entry : countMap.entrySet()){
				String q=list.get(list.size()-1).toString();//获取前一个标注
				if(entry.getKey().equals(ObserArr[i])){     //获取观察序列的发射概率
					double max_probability=HeplerUilt.getMax(entry.getValue().getXb(), entry.getValue().getXi(), entry.getValue().getXo());//得到最大发射概率值
					double transititon_probability=HeplerUilt.getMaxTrans(q,transArr);                                                     //获取最大的转移概率
					String prior=HeplerUilt.compareMark(entry.getValue().getXb(), entry.getValue().getXi(), entry.getValue().getXo());//得到最大发射概率的标注
					list.add(prior);//将最大发射概率进行保存
					V=V*max_probability*transititon_probability;//得到下一步的V值
					//测试数据
					//System.out.println(ObserArr[i]+":"+max_probability+":"+transititon_probability+":"+prior+":"+HeplerUilt.DecFormat(4,V));
				}
			}
		}
		//System.out.println(observationStr.length()+":"+list.size());
		for(int i=0;i<list.size();i++){
			stateStr+=list.get(i)+"\t";//记录路径
		}
		return stateStr;
	}
	//单元测试
	public static void main(String[] args) {
		//维特比解码算法找出观察序列O的最后的隐藏状态序列Q
				System.out.println("***************************隐马尔可夫模型中维特比解码算法序列标注****************************");
				String observationStr="病有发热恶寒者；发于阳也，无热恶寒者；发于阴也。";//观察序列
				String str="书名：伤寒论。作者：张仲景。朝代：东汉。";
				String stateStr=MethodUilt.Vitrerbi(str, 0.3333, "./targetFile/Amatrix.txt", "./targetFile/Bmatrix.txt");//隐藏状态序列，即隐含马尔科夫模型的词类标注
				System.out.println("观察序列：\t"+str.replaceAll("", "\t")+"\n标注序列：\t\t"+stateStr);
	}