数据结构课设（二）
设计并实现一个基于马尔可夫链的写作机器人软件。
软件通过对素材文本的学习，建立词库以及单词的马尔可夫链，然后使用所建立的单词马尔可夫链配合随机数选择，自动生成一段文字。
由于不太清楚老师的具体要求，所以在网上找了个马尔可夫链的简单教程，基于的是一阶马尔可夫链，只往前看一个词，所以比较简单，就决定做这个了，虽然感觉和马尔可夫链没多大关系。
具体原理不太懂，就不多说了，只能根据前一个字推测出下一个字，所以关联度很低，比较简单的句子效果更好，学习多的句子就不太顺了。
比如：
根据这个例子，来讲解一下我的程序。
首先，用了一个vector来存储每句话的第一个字，这样子我们生成句子的时候，生成的第一个字就从这个vector里面随机选取。
vector<string> Start;//开始token
然后用了一个map存储所有的字
map<string,int> T;//Token序列
接着就是这个map和一个二维的vector存储着所有的“词典”，这个Co结构体里的weight可能是整个算法和马尔可夫有一点关系的东西…
struct Co
{
string name;//字
int weight;//出现次数
Co(string n)
{
name=n;
weight=1;
}
};
vector<vector<Co> > Token;//词典
最后存储的效果大概是这样子的
前面的是所有的字，后面的是就是类似于组词一样，在样本中出现的临近字。从这里就可以看出关联性是比较弱的，两个毫无关系的词也会组在一起，比如“好-朋，明-是”，如果是英文的应该会好一点，中文的许多单个字是不成意思的。
read函数
int Read(vector<string> &Start,map<string,int> &T,vector<vector<Co> > &Token)//训练马可夫链，得到词典
{
ifstream fin("test2.txt");
if(!fin)
{
cout<<"can't find your file"<<endl;
return 0;
}
char p;
string s;
bool finish=1;//判断是否为开始Token
int val=0;//计算Token序列个数
int fir=0;
Token.resize(1000);
//这一步有点傻，因为不清楚有多少个字，所以用resize申请了1000的空间，这样子的做的后果是如果你字少的话会出现资源浪费，如果字多的话，内存不够程序就会报错，所以这一步可以改进。
while(fin.get(p))
{
if(p=='\n'||p=='\0'||p=='\t') continue;
if(s.size()==2) //一个汉字或符号
{
if(s=="（"||s=="）"||s=="”"||s=="“"||s=="、"||s=="；") continue;//大部分符号都被抛弃了，只是为了偷懒，不要学我
int lo=0;
//pari<string,string>中的第一个
int sec=0;//pari<string,string>中的第二个
if(Charjudge(s)==0) {
if(T.count(s)==0)//判断Token序列里有没有s,没有就加入
{
lo=val;
T[s]=val;
val++;
}
else lo=T[s];
}
if(finish==1)//开始
{
AddStart(s,Start);
finish=0;
//AddToken(s,Token,lo);
}
else
{
if(Charjudge(s)==1)//结束
{
finish=1;
//AddToken(s,Token,lo);
}
AddToken(s,Token,fir);
//AddToken(s,Token,lo);
}
fir=lo;
s.clear();
}
s+=p;
}
fin.close();
return 0;
}
然后就是生成一段文字了。
在这里我规定遇到句号问号这种符号算一句话结束，生成一段100字以内的句子。
int n=100;
while(Charjudge(s==0)&&n--)
首先，第一个字用随机函数来选取；
srand((unsigned)time(NULL));
int r=rand()%(Start.size());
string first=Start[r];
然后就可以在“词典”中一个个生成后面的字了。在这里需要注意一个循环的情况，比如“我-和-你”三者循环，“我”之后跟着“和”，“和”之后跟着“你”，“你”之后跟着“我”，这样子输出会一直在这个圈子里循环下去，一直到100字为止。
所以我用了一个map记录一个字输出次数，如果出现两次之后就更换字。
函数Max（）是找下一个字最有可能的字是哪个，Rand（）就是解决可能的循环情况。
int Write(vector<string> Start,map<string,int> T,vector<vector<Co> > Token)
{
srand((unsigned)time(NULL));
int r=rand()%(Start.size());
string first=Start[r];
string sen=Max(Token,T[first]);
map<string,int> xxx;
cout<<first;
xxx[first]++;
int n=200;
while(n>0)
{
cout<<sen;
xxx[sen]++;
if(sen=="，")
{
int t=rand()%(Start.size());
sen=Max(Token,T[Start[t]]);
xxx[Start[t]]++;
cout<<Start[t];
}
else if(Charjudge(sen)) break;
else
{
if(xxx[sen]>0)
sen=Rand(Token,T[sen]);
else sen=Max(Token,T[sen]);
}
n--;
}
cout<<endl;
return 0;
}
这是学习了三体部分内容之后生成的句子。
这个算法不足之处挺多的，首先一开始选择中文文本就感觉有点不太对劲了。需要考虑编码问题和中文分词的问题，在这里我都没有解决，所以读的文本只能是GB格式的汉字，一个字占两个字节，并且是单个字的形式。然后里面造句的话都是根据前一个字来组词的，最后凑成一个句子，关联性基本没有。此外，由于我没有存训练好的文件，所以每次使用前都要重新训练一次。
这个算法是一天写完的，写的很简陋，就是为了交作业。如果最开始选择用英文并且前缀词用两个词会比较好，这样子和马克尔夫链的算法关联也大一些，不过难度也会相应大一点，所以就这样吧，以后有时间再来改吧。终于还差最后一个课设就可以开始期末复习了。
源码上传在我的GitHub上。