计算机程序编程课程设计 马尔可夫链.doc

计算机程序编程课程设计(2009-2010-3) 题 目：马尔可夫链算法生成随机可读的文本 学 号： 姓 名： 计算机程序编程课程设计报告引言马尔可夫链，因安德烈马尔可夫得名，是数学中具有马尔可夫性质的离散时间随机过程。该过程中，在给定当前知识或信息的情况下，只有当前的状态用来预测将来，过去（即当前以前的历史状态）对于预测将来（即当前以后的未来状态）是无关的。在马尔可夫链的每一步，系统根据概率分布，可以从一个状态变到另一个状态,也可以保持当前状态。状态的改变叫做过渡，与不同的状态改变相关的概率叫做过渡概率。随机漫步就是马尔可夫链的例子。随机漫步中每一步的状态是在图形中的点，每一步可以移动到任何一个相邻的点，在这里移动到每一个点的概率都是相同的(无论之前漫步路径是如何的)。马尔可夫在1906年首先做出了这类过程。而将此一般化到可数无限状态空间是由柯尔莫果洛夫在1936年给出的。马尔可夫链与布朗运动以及遍历假说这两个二十世纪初期物理学重要课题是相联系的，但马尔可夫寻求的似乎不仅于数学动机，名义上是对于纵属事件大数法则的扩张。物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）。马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。 马尔可夫链最近的应用是在地理统计学（geostatistics）中。其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟。这一应用类似于“克里金”地理统计学（Kriging geostatistics），被称为是“马尔可夫链地理统计学”。这一马尔可夫链地理统计学方法仍在发展过程中。马尔可夫链模型的性质：马尔可夫链是由一个条件分布来表示的P(Xn + 1 | Xn) 这被称为是随机过程中的“转移概率”。这有时也被称作是“一步转移概率”。二、三，以及更多步的转移概率可以导自一步转移概率和马尔可夫性质：同样： 这些式子可以通过乘以转移概率并求k1次积分来一般化到任意的将来时间n+k。边际分布P(Xn)是在时间为n时的状态的分布。初始分布为P(X0)。该过程的变化可以用以下的一个时间步幅来描述：这是Frobenius-Perron equation的一个版本。这时可能存在一个或多个状态分布满足：其中Y只是为了便于对变量积分的一个名义。这样的分布被称作是“平稳分布”（Stationary Distribution）或者“稳态分布”（Steady-state Distribution）。一个平稳分布是一个对应于特征根为1的条件分布函数的特征方程。平稳分布是否存在，以及如果存在是否唯一，这是由过程的特定性质决定的。“不可约”是指每一个状态都可来自任意的其它状态。当存在至少一个状态经过一个固定的时间段后连续返回，则这个过程被称为是“周期的”。离散状态空间中的马尔可夫链模型：如果状态空间是有限的，则转移概率分布可以表示为一个具有(i,j)元素的矩阵，称之为“转移矩阵”：Pij = P(Xn + 1 = i | Xn = j) 对于一个离散状态空间，k步转移概率的积分即为求和，可以对转移矩阵求k次幂来求得。就是说，如果是一步转移矩阵，就是k步转移后的转移矩阵。 平稳分布是一个满足以下方程的向量：在此情况下，稳态分布*是一个对应于特征根为1的、该转移矩阵的特征向量。如果转移矩阵不可约，并且是非周期的，则收敛到一个每一列都是不同的平稳分布*，并且独立于初始分布。这是由Perron-Frobenius theorem所指出的。正的转移矩阵（即矩阵的每一个元素都是正的）是不可约和非周期的。矩阵被称为是一个随机矩阵，当且仅当这是某个马尔可夫链中转移概率的矩阵。注意：在上面的定式化中，元素(i,j)是由j转移到i的概率。有时候一个由元素(i,j)给出的等价的定式化等于由i转移到j的概率。在此情况下，转移矩阵仅是这里所给出的转移矩阵的转置。另外，一个系统的平稳分布是由该转移矩阵的左特征向量给出的，而不是右特征向量。转移概率独立于过去的特殊况为熟知的Bernoulli scheme。仅有两个可能状态的Bernoulli scheme被熟知为贝努利过程。现实应用：马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算法编码。马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。 马尔可夫链最近的应用是在地理统计学（geostatistics）中。其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟。这一应用类似于“克里金”地理统计学（Kriging geostatistics），被称为是“马尔可夫链地理统计学”。这一马尔可夫链地理统计学方法仍在发展过程中。人力资源中的应用：马尔可夫链模型主要是分析一个人在某一阶段内由一个职位调到另一个职位的可能性，即调动的概率。该模型的一个基本假设就是，过去的内部人事变动的模式和概率与未来的趋势大体相一致。实际上，这种方法是要分析企业内部人力资源的流动趋势和概率，如升迁、转职、调配或离职等方面的情况，以便为内部的人力资源的调配提供依据。 它的基本思想是：通过发现过去组织人事变动的规律，以推测组织在未来人员的供给情况。马尔可夫链模型通常是分几个时期收集数据，然后再得出平均值，用这些数据代表每一种职位中人员变动的频率，就可以推测出人员变动情况。具体做法是：将计划初期每一种工作的人数量与每一种工作的人员变动概率相乘，然后纵向相加，即得到组织内部未来劳动力的净供给量。其基本表达式为：Ni(t)：t时间内I类人员数量； Pji：人员从j类向I类转移的转移率；Vi(t)：在时间（t-1,t）I类所补充的人员数。 企业人员的变动有调出、调入、平调、晋升与降级五种。表3 假设一家零售公司在1999至2000年间各类人员的变动情况。年初商店经理有12人，在当年期间平均90的商店经理仍在商店内，10的商店经理离职，期初36位经理助理有 11晋升到经理，83留在原来的职务，6离职；如果人员的变动频率是相对稳定的，那么在2000年留在经理职位上有11人（1290），另外，经理助理中有4人（3683）晋升到经理职位，最后经理的总数是15人（114）。可以根据这一矩阵得到其他人员的供给情况，也可以计算出其后各个时期的预测结果。主要参考文献：A.A. Markov. Rasprostranenie zakona bolshih chisel na velichiny, zavisyaschie drug ot druga. Izvestiya Fiziko-matematicheskogo obschestva pri Kazanskom universitete, 2-ya seriya, tom 15, pp 135-156, 1906.A.A. Markov. Extension of the limit theorems of probability theory to a sum of variables connected in a chain. reprinted in Appendix B of: R. Howard. Dynamic Probabilistic Systems, volume 1: Markov Chains. John Wiley and Sons, 1971.Leo Breiman. Probability. Original edition published by Addison-Wesley, 1968; reprinted by Society for Industrial and Applied Mathematics, 1992. ISBN 0-89871-296-3. (See Chapter 7.)J.L. Doob. Stochastic Processes. New York: John Wiley and Sons, 1953. ISBN 0-471-52369-0.数据结构设计这里的数据结构主要是处理每次查找字符串的过程，在C程序中采用了hashtable，在C+中采用了C+的map容器，即RB-TREE（因为SGI-STL的map底层实现是RB-TREE）。Hashtable是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。Knuth在TAOCP第三卷查找与排序中专门对其数学性能做了大量的分析。基本概念： 若结构中存在关键字和K相等的记录，则必定在f(K)的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系f为散列函数(Hash function)，按这个思想建立的表为散列表。 对不同的关键字可能得到同一散列地址，即key1key2，而f(key1)=f(key2)，这种现象称冲突。具有相同函数值的关键字对该散列函数来说称做同义词。综上所述，根据散列函数H(key)和处理冲突的方法将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表便称为散列表，这一映象过程称为散列造表或散列，所得的存储位置称散列地址。 若对于关键字集合中的任一个关键字，经散列函数映象到地址集合中任何一个地址的概率是相等的，则称此类散列函数为均匀散列函数(Uniform Hash function)，这就是使关键字经过散列函数得到一个“随机的地址”，从而减少冲突。常用的构造散列函数的方法：散列函数能使对一个数据序列的访问过程更加迅速有效，通过散列函数，数据元素将被更快地定位1. 直接定址法：取关键字或关键字的某个线性函数值为散列地址。即H(key)=key或H(key) = akey + b，其中a和b为常数（这种散列函数叫做自身函数）2. 数字分析法3. 平方取中法4. 折叠法5. 随机数法6. 除留余数法：取关键字被某个不大于散列表表长m的数p除后所得的余数为散列地址。即 H(key) = key MOD p, p=m。不仅可以对关键字直接取模，也可在折叠、平方取中等运算之后取模。对p的选择很重要，一般取素数或m，若p选的不好，容易产生同义词。处理冲突的方法1. 开放定址法；Hi=(H(key) + di) MOD m, i=1,2, k(k=m-1)，其中H(key)为散列函数，m为散列表长，di为增量序列，可有下列三种取法： 1. di=1,2,3, m-1，称线性探测再散列；2. di=12, (-1)2, 22,(-2)2, (3)2, , (k)2,(k=m/2)称二次探测再散列;3. di=伪随机数序列，称伪随机探测再散列。 =2. 再散列法：Hi=RHi(key), i=1,2,k RHi均是不同的散列函数，即在同义词产生地址冲突时计算另一个散列函数地址，直到冲突不再发生，这种方法不易产生“聚集”，但增加了计算时间。3. 链地址法（拉链法）4. 建立一个公共溢出区查找的性能分析散列表的查找过程基本上和造表过程相同。一些关键码可通过散列函数转换的地址直接找到，另一些关键码在散列函数得到的地址上产生了冲突，需要按处理冲突的方法进行查找。在介绍的三种处理冲突的方法中，产生冲突后的查找仍然是给定值与关键码进行比较的过程。所以，对散列表查找效率的量度，依然用平均查找长度来衡量。查找过程中，关键码的比较次数，取决于产生冲突的多少，产生的冲突少，查找效率就高，产生的冲突多，查找效率就低。因此，影响产生冲突多少的因素，也就是影响查找效率的因素。影响产生冲突多少有以下三个因素：1. 散列函数是否均匀；2. 处理冲突的方法；3. 散列表的装填因子。散列表的装填因子定义为：= 填入表中的元素个数 / 散列表的长度，是散列表装满程度的标志因子。由于表长是定值，与“填入表中的元素个数”成正比，所以，越大，填入表中的元素较多，产生冲突的可能性就越大；越小，填入表中的元素较少，产生冲突的可能性就越小。实际上，散列表的平均查找长度是装填因子的函数，只是不同处理冲突的方法有不同的函数。有关hashtable的经典参考文献：1.Charles E. Leiserson, Amortized Algorithms, Table Doubling, Potential Method Lecture 13, course MIT 6.046J/18.410J Introduction to Algorithms - Fall 20052. Donald Knuth (1998). The Art of Computer Programming. 3: Sorting and Searching (2nd ed.). Addison-Wesley. pp. 513558. ISBN 0-201-89685-0. 3. Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (second ed.). MIT Press and McGraw-Hill. 221252. ISBN 978-0-262-53196-2. 4. Bret Mulvey, Hash Functions. Accessed April 11, 20095. Thomas Wang (1997), Prime Double Hash Table. Accessed April 11, 20096. Askitis, Nikolas; Zobel, Justin (2005). Cache-conscious Collision Resolution in String Hash Tables. 3772. 91102. doi:10.1007/11575832_11. ISBN 1721172558. /content/b61721172558qt03/. 7. Askitis, Nikolas; Sinha, Ranjan (2010). Engineering scalable, cache and space efficient tries for strings. doi:10.1007/s00778-010-0183-9. ISBN 1066-8888 (Print) 0949-877X (Online). /content/86574173183j6565/. 8. Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys. 91. 113122. ISBN 978-1-920682-72-9. /confpapers/CRPITV91Askitis.pdf. 9.Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. /6.897/spring03/scribe_notes/L2/lecture2.pdf10. Tenenbaum, Aaron M.; Langsam, Yedidyah; Augenstein, Moshe J. (1990). Data Structures Using C. Prentice Hall. pp. 456461, pp. 472. ISBN 0-13-199746-7. 11.Celis, Pedro (1986). Robin Hood hashing. Technical Report Computer Science Department, University of Waterloo CS-86-14.12. Viola, Alfredo (October 2005). Exact distribution of individual displacements in linear probing hashing. Transactions on Algorithms (TALG) (ACM) 1 (2,): 214242. doi:10.1145/1103963.1103965. ISSN:1549-6325. 13. Celis, Pedro (March, 1988). External Robin Hood Hashing. Technical Report Computer Science Department, Indiana University TR246.14. Herlihy, Maurice and Shavit, Nir and Tzafrir, Moran (2008). Hopscotch Hashing. DISC 08: Proceedings of the 22nd international symposium on Distributed Computing. Arcachon, France: Springer-Verlag. pp. 350364. 15. Litwin, Witold (1980). Linear hashing: A new tool for file and table addressing. Proc. 6th Conference on Very Large Databases. pp. 212223. 16. Doug Dunham. CS 4521 Lecture Notes. University of Minnesota Duluth. Theorems 11.2, 11.6. Last modified 21 April 2009.17. Crosby and Wallachs Denial of Service via Algorithmic Complexity Attacks.18. Mehta, Dinesh P.; Sahni, Sartaj. Handbook of Datastructures and Applications. pp. 915. ISBN 1584884355.RB-TREE（又叫红黑树）红黑树是一种自平衡二叉查找树，是在计算器科学中用到的一种数据结构，典型的用途是实现关联数组。它是在1972年由鲁道夫贝尔发明的，他称之为对称二叉B树，它现代的名字是在 Leo J. Guibas 和 Robert Sedgewick 于1978年写的一篇论文中获得的。它是复杂的，但它的操作有着良好的最坏情况运行时间，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n是树中元素的数目。红黑树和AVL树一样都对插入时间、删除时间和查找时间提供了最好可能的最坏情况担保。这不只是使它们在时间敏感的应用如实时应用(real time application)中有价值，而且使它们有在提供最坏情况担保的其他数据结构中作为建造板块的价值；例如，在计算几何中使用的很多数据结构都可以基于红黑树。红黑树在函数式编程中也特别有用，在这里它们是最常用的持久数据结构之一，它们用来构造关联数组和集合，在突变之后它们能保持为以前的版本。除了O(log n)的时间之外，红黑树的持久版本对每次插入或删除需要O(log n)的空间。红黑树是 2-3-4树的一种等同。换句话说，对于每个 2-3-4 树，都存在至少一个数据元素是同样次序的红黑树。在 2-3-4 树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得 2-3-4 树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍 2-3-4 树的原因，尽管 2-3-4 树在实践中不经常使用。RB-TREE的主要参看文献（最好的是Princeton的pdf课件）：1. Rudolf Bayer (1972). Symmetric binary B-Trees: Data structure and maintenance algorithms. Acta Informatica 1 (4): 290-306. doi:10.1007/BF00289509. /content/qh51m2014673513j/. 2. Leonidas J. Guibas and Robert Sedgewick (1978). A Dichromatic Framework for Balanced Trees. Proceedings of the 19th Annual Symposium on Foundations of Computer Science. pp. 8-21. doi:10.1109/SFCS.1978.3. /10.1109/SFCS.1978.3. 3. /rs/talks/LLRB/RedBlack.pdf4. /courses/archive/fall08/cos226/lectures/10BalancedTrees-2x2.pdf5. /rs/talks/LLRB/RedBlack.pdf程序框架介绍基本上是一个框架，都是统计文本中的单词，然后根据连续的单词生成其前缀，然后用红黑树或者哈希表来存储获得的前缀，然后再根据文本的开始两个单词组成其前缀，随机生成的文本，整体来说效率还可以，具体的内容见程序。这里介绍一下C+程序的几个函数：C+程序中主要采用了C+的STL库中的map容器，还有C+中的string类，所以写起来比较简单，而C程序中则有很多函数是实现string的拼接和哈希表的具体实现的。C+程序中主要有三个函数：void build_prefix(void);void get_full_text(void);int main(void);第一个函数主要是提取文本的前缀的对应关系，第二个则是随机生成一个完整的文本，main函数则是驱动整个程序，这里有个要求就是一定要在输入的文本中加入特殊的标记。随机数的生成则使用C语言stdlib库中的rand函数，在main函数中使用srand(time(NULL);初始化随机数的种子。程序调试主要是C语言中的变量定义必须在函数的初始位置，因为习惯了写C+程序而C+可以在任何使用的地方定义变量，所以这个错误好大，修改了好久，而且Visual Studio因为这种错误给出的提示一般也不够准确，所以这个真的恨令人头疼，还有就是if中的判断NULL错误的地方有些还是少些了一个=号，所以有些地方还是采用了建议的那种if(NULL = variable)，不过这种都是在修改程序bug的时候才改的。程序测试输入文本还是用老师给的那个人月神话（话说这本书真的很经典，不幸的是作者后来去搞学术了）中的例子，结果各种各样的，直接给截图，可以看到每次运行都会产生出新的结果文本，说明还是好使的。两种语言对比代码行显然是C语言多，运行速度其实差不多，因为没有运行大的文本，如果运行大的文本C的效率应该更高点，因为使用了经典的哈希函数：1/字符串哈希函数2/（著名的ELFhash算法）3intELFhash(char*key)45unsignedlongh=0;6unsignedlongg =0;7while(*key) 8h=(h24;11h&=g;1213returnh%NUMBER;14据说这个哈希函数是C语言编译器的词法分析中使用的，用在这里应该不为过。完整程序源代码：C+程序：1#include2#include3#include4#include5#include6#include7#include8#include9usingnamespacestd;10string sentence =Show your flowchars and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious. (end);11mapstring, vector prefix_set;12typedefmapstring, vector :iterator map_iter;13string begin_prefix;14string first_word;15string second_word;16voidbuild_prefix() 17istringstream get_words_stream(sentence);18string w1;19string w2;20string w3;21get_words_stream w1;22get_words_stream w2;23first_word = w1;24second_word = w2;25begin_prefix = w1 + + w2;26string last_prefix = begin_prefix;27while(get_words_stream w3) 28map_iter iter = prefix_set.find(last_prefix);29if(iter = prefix_set.end() 30vector map_inner;31map_inner.push_back(w3);32prefix_set.insert(make_pair(last_prefix, map_inner);33else34iter-second.push_back(w3);3536w1 = w2;37w2 = w3;38last_prefix = w1 + + w2;394041voidget_full_text() 42string w1 = first_word;43string w2 = second_word;44string w3;45string past_prefix;46string result = w1 + + w2 + ;47while(true) 48past_prefix = w1 + + w2;49map_iter iter = prefix_set.find(past_prefix);50if(iter = prefix_set.end() 51break;52else53intsize = iter-second.size();54intindex = rand() % size;55w3 = iter-second.at(index);56result = result + w3 + ;57w1 = w2;58w2 = w3;596061cout result endl;626364intmain() 65srand(time(NULL);66build_prefix();67get_full_text();68 -程序分割线-C程序：1#include2#include3#include4#include5intELFhash(char*key);6#define NUMBER7197#define INNERN158typedefstruct9char*prefix;10char*lastINNERN;11intn;12data_type;13data_type* hash_locNUMBER;14char* sentence =Show your flowchars and conceal your tables and I will be mystified. Show your tables and your flowcharts will be obvious. (end);15char* begin_prefix;16char* first_word;17char* second_word;18voidinit_hash_loc(data_type* item) 19inti =0;20if(item) 21item-prefix =NULL;22item-n =0;23for(i =0; i != INNERN; i+) 24item-lasti =NULL;25262728voidinit_hash(void) 29inti =0;30for(i =0; i != NUMBER; i+) 31hash_loci =NULL;323334data_type* search(char* key) 3536inti = ELFhash(key);37while(NULL!= hash_loci) & strcmp(key, hash_loci-prefix) 38i = i +5;39i %= NUMBER;4041if(NULL= hash_loci) 42returnNULL;4344returnhash_loci;4546voidinsert(char* prefix,char* w3) 47data_type* iter = search(prefix);48if(iter =NULL) 49/自己插入一遍50inti = ELFhash(prefix);51while(NULL!=hash_loci) 52i = i +5;53i %= NUMBER;5455iter = hash_loci = malloc(sizeof(data_type);56init_hash_loc(iter);57iter-prefix = prefix;58iter-la