引言：
我们现在准备做的就是给定一个由不同的单词组成的句子，由这个句子产生一些随机的可以读的英语文本。
马尔可夫链可以比较好的完成这个任务！
描述：
该算法把每个短语分割为两个部分：一部分是由多个词构成的前缀，另一部分是只包含一个词的后缀。马尔可夫链算法能够
生成输出短语的序列，其方法是依据 原文本的统计性质，随机性地选择跟在前缀后面的特定后缀。采用三个词的短语就能够工作
得很好——利用连续两个词构成的前缀来选择作为后缀的一个词：
设置w1和w2为文本的前两个词
输出w1和w2
循环：
随机地选出w3，它是文本中w1w2的后缀中的一个
打印w3
把w1和w2分别换成w2和w3
重复循环
马尔可夫的数据结构简单一点说就是：以NPREF个单词做为前缀，前缀可以用一个大小为NPREF的一维数组表示（键），
后缀可以用一个链表或者一个动态数组表示（值），看起来就像是一个映射，
用C++的语法表示可以是：
map<vector<string> key[NPREF],vector<string> value>
图示：
如果用纯C来设计数据结构的话，看起来像是这样：
数据结构部分代码：
typedef struct State State;typedef struct Suffix Suffix;struct State{char *pref[NPREF];Suffix *suf;State *next;};struct Suffix{char *word;Suffix *next;};State *statetab[NHASH];
那么生成前缀后缀的算法应该是这样:
循环
在哈希表中查找到前缀的位置(指针)，这一步需要用到hash函数，并返回指针.
用返回的State指针的suf指针指向后缀.
前缀向前移动一位,并将suf指针填充末位,循环第1步.
重复循环
#include <string>#include <time.h>#include <iostream>using namespace std;const int MULTIPLIER = 1 << 5;//自定义一个数值enum{NPREF = 2,NHASH = 4093,MAXGEN = 10000};enum { BUFSIZE = 0 };typedef struct State State;typedef struct Suffix Suffix;struct State{char *pref[NPREF];Suffix *suf;State *next;};struct Suffix{char *word;Suffix *next;};State *statetab[NHASH];unsigned int hash(char *s[NPREF])//哈希函数:将前缀散列到哈希表某一位置{unsigned int h = 0;unsigned char *p = NULL;for (int i=0; i < NPREF; ++i)for (p=(unsigned char*)s[i]; *p != '\0'; ++p)h = MULTIPLIER *h + *p;return h % NHASH;}State* lookup(char *prefix[NPREF],int create)//查找前缀数组prefix[NPREF]是否在哈希表中出现，如果未出现，就插入{int i,h;State *sp;h = hash(prefix);for (sp = statetab[h]; sp != NULL; sp = sp->next){for (i=0; i < NPREF; ++i){if (strcmp(prefix[i],sp->pref[i]))break;}if (i == NPREF)//找到就返回return sp;}if (create){sp = new State;for (i = 0; i < NPREF; ++i){sp->pref[i] = prefix[i];}sp->suf = NULL;sp->next = statetab[h];//头插法statetab[h] = sp;}return sp;}void addsuffix(State *sp,char *suffix)//在后缀链表中插入一个结点{Suffix *suf = new Suffix;suf->word = suffix;suf->next = sp->suf;sp->suf = suf;}void add(char *prefix[NPREF], char *suffix)//往数据结构中插入一个项{State *sp = NULL;sp = lookup(prefix,1);addsuffix(sp,suffix);memmove(prefix,prefix+1,(NPREF-1)*sizeof(prefix[0]));prefix[NPREF-1] = suffix;}void build(char * prefix[NPREF], FILE *f){char buf[100], fmt[10];sprintf(fmt,"%%%ds",sizeof(buf)-1);//这个调用很奇妙!while (fscanf(f,fmt,buf)!=EOF)add(prefix,strdup(buf));}void generate(int nwords){State *sp;Suffix * suf;char *prefix[NPREF], *w;int i,nmatch;for (i = 0; i < NPREF; ++i)prefix[i] = "\0";for (i = 0; i < nwords; ++i){sp = lookup(prefix,0);nmatch = 0;for (suf = sp->suf; suf != NULL; suf = suf->next)if (rand() % ++nmatch == 0)w = suf->word;if (strcmp(w,"\0")==0)break;printf("%s\n",w);memmove(prefix,prefix+1,(NPREF-1)*sizeof(Suffix));prefix[NPREF-1] = w;}}int main(){#ifndef ONLINE_JUDGEfreopen("2.txt","r",stdin);#endifint i,nwords = MAXGEN;char *prefix[NPREF];srand((unsigned int)time(0));//随机种子for (i=0; i < NPREF; ++i)prefix[i] = "\0";build(prefix,stdin);add(prefix,"\0");generate(nwords);return 0;}
上面的代码可以增长不少见识：
1.函数原型：void *memmove(void *dest, const void *source, size_t count)
返回值说明：返回指向dest的void *指针
参数说明：dest,source分别为目标串和源串的首地址。count为要移动的字符的个数
函数说明：memmove用于从source拷贝count个字符到dest，如果目标区域和源区域有重叠的话，memmove能够保证源串在被覆盖
之前将重叠区域的字节拷贝到目标区域中。
2.
void build(char * prefix[NPREF], FILE *f){char buf[100], fmt[10];sprintf(fmt,"%%%ds",sizeof(buf)-1);//这个调用很奇妙!while (fscanf(f,fmt,buf)!=EOF)add(prefix,strdup(buf));}
这一段
定义函数：int sprintf(char *str, const char * format, ...);
函数说明：sprintf()会根据参数format 字符串来转换并格式化数据, 然后将结果复制到参数str 所指的字符串数组,
直到出现字符串结束('\0')为止
sprintf函数和我们常见的printf函数十分类似，只不过printf打印到标准输出流，而sprintf打印到字符串中。
sprintf(fmt,"%%%ds",sizeof(buf)-1)等价于sprintf(fmt,"%%%ds",99)，则运行后,fmt的结果为"%99s",所以下一句实质上为：
while (fscanf(f,"%99s",buf)!=EOF)，就很好理解了，意思为从文件中至多读99个字符到buf中。
3.strdup()复制给定字符串的一个副本。
C++ STL版本的实现（结构紧凑，思路清晰，效率比C低不少）
#include <map>#include <queue>#include <time.h>#include <vector>#include <string>#include <iostream>using namespace std;map<deque<string>,vector<string> > statetab;void add(deque<string>& prefix,const string& s){if (prefix.size() == 2){statetab[prefix].push_back(s);//增加后缀prefix.pop_front();//删除队列头}prefix.push_back(s);//入队，构成新的prefix}void build(deque<string>& prefix,istream& in){string buf;while (in >> buf)add(prefix,buf);}void generate(int nwords){deque<string> prefix;int i;for (i=0; i < 2; ++i)add(prefix,"\0");for (i=0; i < nwords; ++i){vector<string>& suf = statetab[prefix];const string& w = suf[rand() % suf.size()];if (w=="\0")break;cout << w << ' ';prefix.pop_front();prefix.push_back(w);}}int main(){#ifndef ONLINE_JUDGEfreopen("2.txt","r",stdin);#endifsrand(time(0));int nwords = 10000;deque<string> prefix;for (int i = 0; i < 2; ++i)add(prefix,"\0");build(prefix,cin);add(prefix,"\0");generate(nwords);return 0;}
