Category: Algorithm

有趣的排序视频 2

有趣的排序视频

转载自:http://www.matrix67.com/blog/archives/1942 [fla­shvi­deo file=/wp-content/uploads/2009/06/sort.flv /]

HMM学习笔记:初识隐马尔科夫模型 0

HMM学习笔记:初识隐马尔科夫模型

HMM是Hi­dden Mar­kov Model的缩写,是马尔科夫模型的过程概率函数。这种模型在现在语音识别系统构建中起到了十分重要的作用。 最近通过学习HMM,基本上理解了这种算法模型。感谢公司同事William和Yong的精彩课程,让我能够很快地理解。 ====================================== 关于HMM的入门,有一些网上的作品写的很好,值得借鉴: http://hi.baidu.com/myqa/blog/item/1882224f026c4535aec3abe3.html http://life.tongji.edu.cn/biforum/viewthread.php?tid=296&extra=page%3D1%26amp%3Bfilter%3Ddigest http://www.comp.leeds.ac.uk/roger/HiddenMarkovModels/html_dev/main.html ======================================= 马尔科夫模型是一种基于预测的概率模型。在语言学的实践中,甚至在一般数理统计中,我们经常会考虑这样一种情况序列,这组序列由并不相互独立的随机变量组成,序列中的每个元素的变量值依赖于它前面的元素。给定了一个元素,为了能够预测到它的继任(successor),我们会分析这个序列中相关元素与其继任出现的概率,并最终给出一个下一个最有可能出现的情况。而马尔科夫模型就是解决完成这样的问题而出现的。 在马尔科夫模型中,我们根据已知的整个序列,加上出现的这个元素,来预测即将出现的元素的可能性。而在大多数情况中,我们无法得知整个序列,只能得到序列中的一部分,一个片段。这个时候用马尔科夫模型就不够了,要使用隐马尔科夫模型。隐马尔科夫模型可以根据表层事件中的一些现象来分析判断底层中事件的情况,反之亦然。即,当系统中出现表层事件是由底层事件所引发相关的问题时,HMM便可以派上用场了。 利用HMM,我们可以由表层事件的发生和模型来判断底层事件的发生;可以根据底层事件和模型来预测表层事件的发生;还可以根据表层事件和底层事件,来估计整个模型(参数估计)。这是HMM的三大作用,三个基本问题。 ======================================= 参考书: http://www.china-pub.com/22710 http://club.book.csdn.net/book/28296.html 接下来的一段时间里,我想将自己对于整个HMM模型的理解和演算过程加以记录和整理,方便大家一起学习。也加深一下印象。

最大子序列算法 0

最大子序列算法

周日的软件技术实现课上,Xin Zou 老师给我们出了一道题。在一个数字数组里面,求一个连续数字之和的最大值子序列,返回最大的值,以及这个子序列的起始位置、终止位置。 我们小组使用了动态规划算法实现,实现方法如下(用C++实现,关键代码): /* 问题描述: 有一串数字(可正可负的int,放在数组Num里),要求找到起始位置start和终止位置end,使得从start位置到end位置的所有数字之和最大,返回这个最大值max。 算法阐述: 最简单的方法是用动态规划算法实现: 设 f[x] 为以 a[x] 终止且包含 a[x] 的最大序列的和,有:    f[1] = a[1];    f[x+1] = f[x] > 0 ? f[x] + a[x+1] : a[x+1] 那么最大子序列的和就是 f[1]…