package algorithm;
public class Viterbi {
/**
* 维特比算法(Viterbi algorithm)是一种动态规划算法。它用于寻找最有可能产生观测事件序列的-维特比路径-隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。
术语“维特比路径”和“维特比算法”也被用于寻找观察结果最有可能解释相关的动态规划算法。例如在统计句法分析中动态规划算法可以被用于发现最可能的上下文无关的派生(解析)的字符串,有时被称为“维特比分析”。
* @param args
*/
public static void main(String[] args) {
// 用分词举例有如下结构.采用少词方式
// 0 中 中国 中国人
// 1 国 国人
// 2 人 人民
// 构建一个数组将如上结构放入数组中
Node begin = new Node("B", 0);
begin.score = 1 ;
Node end = new Node("END", 5);
Node[][] graph = new Node[6][0];
graph[0] = new Node[] { begin };
graph[1] = new Node[] { new Node("中", 1), new Node("中国", 1), new Node("中国人", 1) };
graph[2] = new Node[] { new Node("国", 2), new Node("国人", 2) };
graph[3] = new Node[] { new Node("人", 3), new Node("人民", 3) };
graph[4] = new Node[] { new Node("民", 4) };
graph[5] = new Node[] { end };
int to = 0;
Node node = null;
// viterbi寻找最优路径
for (int i = 0; i < graph.length - 1; i++) {
for (int j = 0; j < graph[i].length; j++) {
node = graph[i][j];
to = node.getTo();
for (int k = 0; k < graph[to].length; k++) {
graph[to][k].setFrom(node);
}
}
}
// 反向遍历寻找结果
node = graph[5][0];
while ((node = node.getFrom()) != null) {
System.out.println(node.getName());
}
}
static class Node {
private String name;
private Node from;
private int offe;
private Integer score;
public Node(String name, int offe) {
this.name = name;
this.offe = offe;
}
public Node(Node node, Node node2, Node node3) {
// TODO Auto-generated constructor stub
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getFrom() {
return from;
}
public void setFrom(Node from) {
if (this.score == null) {
this.score = from.score + 1;
this.from = from;
} else if (this.score > from.score + 1) {
this.score = from.score + 1;
this.from = from;
}
}
public int getTo() {
return this.offe + name.length();
}
}
}
分享到:
相关推荐
用Java实现了HMM中的前/后向算法、Viterbi算法。测试的内容参照了《统计学习方法》例10.2和例10.3
Viterbi译码算法在55系列DSP上的C语言实现.pdf
viterbi算法linux下C++实现.docx
采用(2,1,8)卷积码编码,采用viterbi译码算法进行解码
算法解决的问题:通过观察序列来猜测背后最有可能的隐藏序列。viterbi译码算法是一种卷积码的解码算法。优点不说了。缺点就是随着约束长度的增加算法的复杂度增加很快。
载波相位估计算法,补偿相位偏移。
卷积码译码之维特比译码算法(Viterbi decoding algorithm).docx
基于FPGA的Viterbi算法改进及其实现.pdf
Viterbi译码器回溯算法实现研究
MATLAB 实现的 viterbi算法
举一例用Java实现Viterbi算法 适合隐马尔科夫初学者
使用C语音编写的viterbi编码和解码算法,里面包含了1.编解码的速度测试2.在高斯白噪声下的误码率效果测试
基于Python的一些常用的机器学习算法实现.zip 1. 概率统计中常见概念总结 总体均值、总体方差 样本均值、样本方差 无偏估计、有偏估计 样本标准差 样本协方差、协方差矩阵 2. 一些常用的机器学习算法理论及实现...
c++实现viterbi算法的一般方法!!!
Viterbi算法详解,用于信号检测与估计的研究,详细讲述了算法的过程,希望给大家有用武之地!
viterbi算法通俗讲解
matlab实现简单的hmm算法,包括前向算法、后向算法以及viterbi算法
本部分主要是详细介绍viterbi算法,这是信号与信息处理课程的重要知识模块,对该部分的研究与分析有较高的参考价值