利用马尔可夫链生成随机文本
最后更新于：2022-04-01 21:40:38
### 问题描述
二阶马尔可夫链：**例如：of the people, by thepeople, for the people**
### 分析
Prefix(后缀数组) Suffix
of the people 比如 thepeople后面可以跟by for 空，可根据概率选择一个如果选择for，则过度到状态people for，从
the people by 而可以知道后续为the依次类推，给定一个前缀，可以一直往下找，直到”空”为止
people, by the **几种实现方法：(note:C++ stl中可用map>实现)**
by the people 1)普通的hash表，记录前缀与后缀(比如前缀thepeople的后缀包括by, for,空)，给定前缀可以通过hash
the people for 表很快查找到后缀，然后根据概率选择一个后缀(根据在后缀中出现次数)，过渡到下一个状态
people for the 2)使用后缀数组，数组中每个元素指向一个单词的开始的位置，**先对后缀数组排序**，然后**用二分查找**
for the people **得到prefix第一次出现的位置 ，**最后往后遍历根据概率选择一个后缀。
the people 空 3) hash表与后缀数组相结合，使用后缀数组构造hash表
**首先解决一个问题**
当有多个suffix时，如何按照概率选择一个，比如the people by for 空，
~~~
int nmatch=0;
for everyone in suffix
if( rand()%++nmatch==0 )
select=this_suffix;
~~~
对每一个后缀都执行上述的判断，可知第一个suffix一定被选中，第二个suffix以1/2的概率替换，第三个以1/3的概率替换
~~~
#include
#include
#include
#define NHASH 49979
#define MULT 31
#define MAXWORDS 80000
char inputchars[4300000];//存储输入数据
char *word[MAXWORDS];//后缀数组
int nword=0;//记录单词数
int k=2;//2阶
int next[MAXWORDS];//用于构建hash表
int bin[NHASH];
//以k个单词为单位，进行hash
unsigned int hash(char* str){
int n;
unsigned int h=0;
char* p=str;
for(n=k;n>0;++p){
h=MULT*h+*p;
if(*p=='\0')
--n;
}
return h%NHASH;
}
//比较前k个单词的大小
int wordncmp(char* p,char *q){
int n;
for(n=k;*p==*q;++p,++q){
if(*p=='\0'&&(--n)==0)
return 0;
}
return *p-*q;
}
//从当前单词出发，跳过前n个单词
char* skip(char* p,int n){
for(;n>0;++p){
if(*p=='\0')
--n;
}
return p;
}
int main(){
int i,j;
//步骤1：构建后缀数组
word[0]=inputchars;
//scanf以空格作为分隔符, 并且自动加上'\0'
while((scanf("%s",word[nword]))!=EOF){
word[nword+1]=word[nword]+strlen(word[nword])+1;
++nword;
}
//附加k个空字符,保证wordncmp()正确（感觉不需要这个）
for(i=0;inext[5](1)->next[1](0)->next[0](-1)
for(i=0;i<=nword-k;++i) {
j=hash(word[i]);
next[i]=bin[j];
bin[j]=i;
}
//步骤3：生成随机文本
int wordsleft;//生成单词数
int psofar;
char *phrase,*p;
phrase=inputchars;
for(wordsleft=10000;wordsleft>0;--wordsleft){
psofar=0;
for(j=bin[hash(phrase)];j>=0;j=next[j])
//在hash值相同的项中找出字符串值相同的后缀数组表项，根据概率选择一个
if(wordncmp(phrase,word[j])==0&&rand()%(++psofar)==0)
p=word[j];
//将phrase重新设置
phrase=skip(p,1);
//输出符合要求单词的后面第k个单词
if(strlen(skip(phrase,k-1))==0)
break;
printf("%s\n",skip(phrase,k-1));
}
return 0;
}
~~~
**转载请注明出处：**[http://blog.csdn.net/utimes/article/details/8864122](http://blog.csdn.net/utimes/article/details/8864122)
';