计算机程序编程课程设计报告(马尔可夫链算法生成随机可读文本)

计算机程序编程课程设计报告（马尔可夫链算法生成随机可读文本）一、引言：11、马尔可夫链的数学背景：马尔可夫链，因安德烈•马尔可夫（A.A.Markov，1856－1922）得名，是数学随机过程的一种。在20实际的初期，由于物理学、通讯与控制、生物学、管理科学等领域的需要，随机过程的理论逐步产生和发展起来。随机过程理论为诸多领域的随机现象提供了数学模型。随机过程的数学定义：设试验E的样本空间为Ω，T是一个数集（T⊆（-∞，+∞）），如果对于每一个t∈T，都有一个定义在样本空间Ω上的随机变量X（ω，t），ω∈Ω，则称依赖于t的一族随机变量{X（ω，t），t∈T}为随机过程。马尔可夫链是一种特殊随机过程。马尔可夫链的数学定义：设随机序列{X（n），n=0,1,2,……}满足如下条件：（1）对于每一个n（n=0,1,2,……），X（n）取整数或它的子集（记为I）；（2）对于任意r+1个非负整数n1，n2，…，nr，m（0≤n1＜n2＜…＜nr＜m）和任意正整数k，以及状态i1，i2，ir，i，j∈I，有P{X（n1）=i1，X（n2）=i2，…，X（nr）=ir，X（m）=i}＞0，且P{X(m+k)=j│X(n1)=i1,X(n2)=i2,…,X(nr)=ir,X(m)=i}=P{X(m+p)=j│X(m)=i}，则随机序列{X(n),n=0,1,2,…}为马尔可夫链。条件概率P{X(m+k)=j│X(m)=i}称为马尔可夫链{X(n),n=0,1,2,…}在时刻m从状态i出发，在时刻m+k转移到状态j的k步转移概率，记作pij(m,m+k),即Pij(m,m+k)=P{X(m+k)=j│X(m)=i}.马尔可夫链的性质：对于齐次的马尔可夫链有C-K方程成立，这一方程表明“从状态i出发经k+l步转移到达状态j”这一事件，可以分解为“从状态i出发经k步转移到达中间状态s（s∈I），再从s出发经l步转移到达状态j”这样一些事件的并。对于不同的中间状态s（s∈I），这样的事件是互不相容的。如果马尔可夫链具有遍历性，那么它的直观意义是：不论质点从哪一个状态i出发，当转移步数k充分大时，到达状态j的概率近似于常数πj。如果已求出πj值，则当k充分大时πj可以作为pij（k）（i,j∈I）的近似值。2如果马尔可夫链具有平稳分布，并取初试概率分布为平稳分布，则它在任意时刻m的概率分布都相同，都等于初始概率分布。2、马尔可夫链的典型应用：物理马尔可夫链通常用来建模排队理论和统计学中的建模，还可作为信号模型用于熵编码技术，如算术编码（著名的LZMA数据压缩算法就使用了马尔可夫链与类似于算术编码的区间编码）。马尔可夫链也有众多的生物学应用，特别是人口过程，可以帮助模拟生物人口过程的建模。隐蔽马尔可夫模型还被用于生物信息学，用以编码区域或基因预测。马尔可夫链最近的应用是在地理统计学（geostatistics）中。其中，马尔可夫链用在基于观察数据的二到三维离散变量的随机模拟。这一应用类似于“克里金”地理统计学（Kriginggeostatistics），被称为是“马尔可夫链地理统计学”。3、相关图书介绍：《马尔可夫决策过程引论》（作者：胡奇英/刘建庸）简介:马尔可夫决策过程是研究马氏型序贯(动态)决策问题的工具。本书提供了处理离散时间、连续时间、半马氏等三类基本马氏决策过程模型的一般化方法。在此基础上，本书研究了状态部分可观察、多目标、带约束条件等一般化马氏决策过程以及处于随机变化环境中的马氏决策过程。《生灭过程与马尔可夫链》（作者：王梓坤）简介：本书叙述生灭过程与马尔可夫链的基本理论并介绍近年来的一些研究进展第一章概述随机过程的一般概念：第二章至第四章讲述马尔可夫链；第五、六章研究生灭过程的基本理论和构造，主要是用概率方法；第七、八章研究生灭过程和双边生灭过程构造论，主要是用分析的方法。同时还讨论了用两种方法所得结论之间的联系。二、数据结构设计：本程序的数据结构在用哈希表设计。1、哈希表介绍：哈希表是一种散列结果，它只通过关键字的特征便可以查找出所需结果，是一种十分便捷的用于查找的数据结构。在记录的存储地址和它的关键字之间建立一个确定的对应关系H，使每个关键字和结构中唯一的一个存3储位置相对应。因而在查找时，只要根据这个对应关系H找到给定关键字值K的像H（K），即对应的存储位置。若结构中存在关键字和K相等的记录，则必定在H（K）的存储位置上，因此，不需要进行比较便可直接取得所查记录。2、哈希表的设计：前缀表设计：structqianzhuib{char*phrase[N];structhouzhuib*houzhui;structqianzhuib*next;};structqianzhuib*qianzhuitable[HASH];phrase[2]用于存储前缀structhouzhuib*houzhui用于指向该前缀所跟随的后缀structqianzhuib*next用于指向具有相同关键字的同义词前缀前缀表是一个很长（长度为HASH）的结构体数组后缀表设计：structhouzhuib{char*word;structhouzhuib*next;};char*word用于指向后缀词structhouzhuib*next用于指向同一前缀所跟随的不同后缀对应关系H的设计：对应关系用于确定一个前缀具体存放在前缀表哪一个下标所对应的空间中。我们将前缀词组中每个字母的ACSII值乘以37后作和当作对应关系。之所以选择37，是因为这可以将前缀较均匀的分布在散列表上。三、程序架构介绍：4对算法的思考：这个程序运用了马尔可夫链算法。因为文章的结尾两个词是没有后缀的，所以当以这两个词为前缀时文章的输出一定可以结束。如果把这两个词看作一个吸收壁，那么根据数学理论这个马尔可夫链一定是具有遍历性的，也就是说这个输出是可以结束的。这就是马尔可夫链算法的可行性。inthash(char*c[N])该函数表示哈希表的对应关系，它可以计算出前缀在哈希表中的对应位置。调用它时需要输入一个指针数组，这个数组分别指向前缀词组的两个词；它返回的整数值就是前缀在哈希表中的位置。structqianzhuib*lookout(char*phrase[N],intcreate)该函数用于查找、添加一个前缀。调用它时第一个参数为指向需要添加前缀的指针数组，的二个参数为创建标识符（当create为0时之查找，当create为1时将前缀添加进前缀表）；它返回为一个指向所查找或创建的前缀结构体的指针。voidadd(char*phrase[N],char*houzhui)该函数用于向指定前缀添加后缀。调用它时第一个参数为需添加后缀的前缀，第二个参数为指向需要添加的后缀的指针。该函数没有返回值。voidaddhouzhui(structqianzhuib*p,char*houzhui)该函数是上一函数内部的函数，它用特定的方法添加后缀。intshuchu(char*phrase[N])该函数用于输出。调用该函数时参数为指向前缀的指针，函数随机选择一个对应的后缀并将其输出；函数返回一个整型变量，返回1表示继续输出，返回0表示输出结束。在编写C#语言时运用了许多模板库：四、程序调试：1、编译错误：由于本程序涉及函数、变量很多，所以在编写阶段经常把名字打错，导致编译过程中出现众多错误。经过多次修改后这些错误被排除。2、运行错误：（1）文章不能成功输入：使用for(x=0;a!=13;x++)导致文章不能不能5输入，正确应为for(x=0;a!='\n';x++)。13不是换行符的ASCII码。由于在装入单词时没有在末尾添加‘\0’导致文章输入不正确。添加语句wzzc[x][y]='\0';后输入正确。（2）查询函数lookout中遇到问题：lookout函数中有一语句错误for(i=0;i=N;i++)它导致程序无法为同一个前缀建立不同的后缀，改为for(i=0;iN;i++)后问题解决。(3)关于函数中的return：在函数中如果执行了return语句，那么函数便就此结束，不会再执行下面的语句。在lookout函数的编写中曾经出现了这种错误，即函数执行了return后不再向下执行。五、程序测试：输入文本：abcabdabeabfabgabh.输入前缀：ab输出文本：abeabgabcabeabeabh.输入文本：showyourflowcharsandconcealyourtablesandiwillbemystified.showyourtablesandyourflowchartswillbeobvious.输入前缀：showyour输出文本：showyourtablesandyourflowchartswillbemystified.showyourflowcharsandconcealyourtablesandiwillbeobvious.六、语言对比：从代码结构来看，C语言代码长度大结构较为复杂，需要编写者考虑每一个细节。由于长度大结构复杂，C语言程序在编译期和运行期都出现了很多错误，花费了大量时间调试修改。而C#语言采用面向对象设计的方法，编写中运用了大量的类和模板，因此代码紧凑、数据结构清晰，算法使人一目了然。即使发生错误，调试修改也比较容易。从运行时间来看，运用C语言编写的程序效率较高，运行时间较短；C#程序效率没有C语言程序高。七、程序代码：C语言代码：#defineN2/*前缀长度*/6#defineHASH4093/*散列长度*/#defineLONG30/*单词长度*/#defineNULL0#defineLENQsizeof(structqianzhuib)#defineLENHsizeof(structhouzhuib)#includestdio.h#includemalloc.h#includestring.h#includestdlib.h/*后缀表结构*/structhouzhuib{char*word;structhouzhuib*next;};/*前缀散列表*/structqianzhuib{char*phrase[N];/*装前缀单词*/structhouzhuib*houzhui;structqianzhuib*next;};structqianzhuib*qianzhuitable[HASH];/*计算哈希值*/inthash(char*c[N]){inth;inti;char*p;7h=0;for(i=0;iN;i++){for(p=(char*)c[i];*p!='\0';p++)h=37*h+*p;}returnh%HASH;}/*查找并建立散列,create为1则创建前缀*//*输出前缀表单元的值*/structqianzhuib*lookout(char*phrase[N],intcreate){inti,h;structqianzhuib*p;h=hash(phrase);for(p=qianzhuitable[h];p!=NULL;p=p-next){for(i=0;iN;i++){if(strcmp(phrase[i],p-phrase[i])!=0)break;}if(N==i)return(p);}if(1==create){p=(structqianzhuib*)malloc(LENQ);for(i=0;iN;i++)p-phrase[i]=phrase[i];8p-houzhui=NULL;p-next=qianzhuitable[h];/*往前插入*/qianzhuitable[h]=p;}return(p);}/*添加后缀*/voidaddhouzhui(structqianzhuib*p,char*houzhui){structhouzhuib*pp;pp=(structhouzhuib*)malloc(LENH);pp-word=houzhui;pp-next=p-houz