/**
 * Created by ganjun on 2017/7/19.
 */
/*
states = ('Rainy', 'Sunny')
observations = ('walk', 'shop', 'clean')
start_probability = {'Rainy': 0.6, 'Sunny': 0.4}
transition_probability = {
    'Rainy' : {'Rainy': 0.7, 'Sunny': 0.3},
    'Sunny' : {'Rainy': 0.4, 'Sunny': 0.6},
    }
emission_probability = {
    'Rainy' : {'walk': 0.1, 'shop': 0.4, 'clean': 0.5},
    'Sunny' : {'walk': 0.6, 'shop': 0.3, 'clean': 0.1},
}
*/
import sun.tools.tree.DoubleExpression;
import java.util.*;
public class Viterbi {
//    public static final String [] hiddenStates = {"Rainy" , "Sunny"};
//    public static final String [] observeStates = {"walk" , "shop" ,  "clean"};
//
//    public static final double startProbability[] = {0.6, 0.4};
//    public static final double [][] emissionProbability = {{0.1 , 0.4 , 0.5} , {0.6 , 0.3 , 0.1}};
//    public static final double [][] transitionProbability = {{0.7 , 0.3} , {0.4 , 0.6}};
    public static final String [] hiddenStates = {"1" , "2" , "3"};
    public static final String [] observeStates = {"1" , "2"};
    public static final double startProbability[] = {0.333, 0.333 , 0.333};
    public static final double [][] emissionProbability = {{0.5 , 0.5} , {0.75 , 0.25} , {0.25 , 0.75}};
    public static final double [][] transitionProbability = {{0.333, 0.333 , 0.333} , {0.333, 0.333 , 0.333} , {0.333, 0.333 , 0.333}};
    public static void readData(){
    }
    public Vector<Integer> getWeatherState(String [] hiddenStates ,
                                String [] observeStates ,
                                double [] startProbability ,
                                double [][] transitionProbability ,
                                double [][] emissionProbability ,
                                int [] observations){
        int [][] recall = new int [observations.length][hiddenStates.length];
        double [][] pro = new double [observations.length][hiddenStates.length];
        for(int i=0 ; i<hiddenStates.length ; i++){
            pro[0][i] = startProbability[i] * emissionProbability[i][observations[0]] ;
        }
        double maxV = -1.0d;
        int maxI = -1;
        for(int i=1 ; i<observations.length ; i++){
            //当前隐藏状态为j，有上一次的k状态转移过来
            for(int j=0 ; j<hiddenStates.length ; j++){
                maxV = -1.0d;
                maxI = -1;
                for(int k=0 ; k<hiddenStates.length ; k++){
                    double tmp = pro[i-1][k] * transitionProbability[k][j];
                    if(tmp > maxV){
                        maxV = tmp;
                        maxI = k;
                    }
                }
                recall[i][j] = maxI;
                //下方这一步中 * emissionProbability[j][observations[i]]个人觉得放在上一个循环中的tmp计算也是可以的
                //但是根据http://www.52nlp.cn/hmm-learn-best-practices-six-viterbi-algorithm-5所描述的就应该是这样的步骤
                pro[i][j] = maxV * emissionProbability[j][observations[i]];
            }
        }
        Vector<Integer> res = new Vector<Integer>();
        //找到当前概率最高的结束点
        maxV = -1.0d;
        maxI = -1;
        for(int i=0 ; i<hiddenStates.length ; i++){
            if(pro[observations.length-1][i] > maxV){
                maxV = pro[observations.length-1][i];
                maxI = i;
            }
        }
        for(int i=observations.length-1 ; i>0 ; i--){
            res.add(maxI);
            maxI = recall[i][maxI];
        }
        res.add(maxI);
        Vector<Integer> reverseRes = new Vector<Integer>();
        for(int i=0 ; i<res.size() ; i++){
            reverseRes.add(res.get(res.size()-i-1));
        }
        return reverseRes;
    }
    public static void main(String [] args){
        Viterbi vit = new Viterbi();
        int [] observations = {0,0,0,0,1,0,1,1,1,1};
        Vector<Integer> vec = vit.getWeatherState(hiddenStates ,
                observeStates , startProbability , transitionProbability , emissionProbability , observations);
        for(int i=0 ; i<vec.size() ; i++){
            System.out.print(hiddenStates[vec.get(i)]+" ");
        }
    }
}