Repository navigation
Expand file tree
/
Copy pathViterbi.java
More file actions
69 lines (62 loc) · 1.86 KB
/
Copy pathViterbi.java
File metadata and controls
69 lines (62 loc) · 1.86 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
package com.HMM.example;
/**
* 维特比算法
* @author hankcs
*/
public class Viterbi
{
/**
* 求解HMM模型
* @param obs 观测序列
* @param states 隐状态
* @param start_p 初始概率（隐状态）
* @param trans_p 转移概率（隐状态）
* @param emit_p 发射概率 （隐状态表现为显状态的概率）
* @return 最可能的序列
*/
public static int[] compute(int[] obs, int[] states, double[] start_p, double[][] trans_p, double[][] emit_p)
{
double[][] V = new double[obs.length][states.length];
int[][] path = new int[states.length][obs.length];
for (int y : states)
{
V[0][y] = start_p[y] * emit_p[y][obs[0]];
path[y][0] = y;
}
for (int t = 1; t < obs.length; ++t)
{
int[][] newpath = new int[states.length][obs.length];
for (int y : states)
{
double prob = -1;
int state;
for (int y0 : states)
{
double nprob = V[t - 1][y0] * trans_p[y0][y] * emit_p[y][obs[t]];
if (nprob > prob)
{
prob = nprob;
state = y0;
// 记录最大概率
V[t][y] = prob;
// 记录路径
System.arraycopy(path[state], 0, newpath[y], 0, t);
newpath[y][t] = y;
}
}
}
path = newpath;
}
double prob = -1;
int state = 0;
for (int y : states)
{
if (V[obs.length - 1][y] > prob)
{
prob = V[obs.length - 1][y];
state = y;
}
}
return path[state];
}
}