来到实验室正好有一个月了，趁着端午假期稍微轻松一些，在大改程序体系之前，想将自己在这30天中工作之一Markov回顾一下，将从真实的写程序中学习到的知识、思想记录下来。希望能和大家积极讨论！
本文会以用C#实现Markov Model为主线，分享自己的感悟。
一、简介Markov
Markov是一种概率模型，最简单的理解是通过大量数据的学习后，可以通过个数为n的词推断出第n+1个词的出现可能。能理解Markov整体思想就可以了。
所以通常将Markov Model的实现分为两个部分：
1、Markov Model数据学习部分
2、根据Markov Model生成部分
二、Markov数据学习
很多人说，当Markov的阶数（Order）变高的时候，如order=5，数据学习部分根本跑不动，为什么？因为Markov要求的是全排列。举个例子，如果学习数据中有5000种词，阶数为5，那么我们有5000的5次方种全排列可能。在存储过程中，因为数据量过大，对内存的一种挑战；在搜索并累积的过程中，如果采用不适当的数据结构，将会消耗大量，超大量时间在搜索中。而这点也就是程序跑不动的原因。
功能的需求就只是个需求，怎么写程序根本是另一回事。很多程序不会按那个需求那么直接的实现，比如说我们现在要全排列，那我们就把全排列的结果全部都存在计算机中吗？我们做不到。我们得通过其他方法来实现这个需求，这就可能会稍微拐点弯啦，但能否灵巧地解决编程难点，看的就是不同程序员的能力高低了。
统计可以得到，全排列中有大量组合是没有值的，会是个稀疏矩阵。所以我只将学习数据中出现的词组合记录下来，这个数据量将远远小于应有的全排列，内存将会有足够的空间存放。在这样的前提下，我第一次使用的List做数据结构来存储，发现程序依然跑的很慢很慢，30mins才跑了50W数据；后来灵机一动用了Dictionary（hash）做数据结构，2mins就跑了300W数据……这真是天壤之别啊！！！这就说明数据结构真是太重要了！！！千万不要小看数据结构啊！！！一定要重视！！！以前学的时候只知道哈希查询效率是O(1)，但从没有这么震撼的感触。
话又说回来，为什么Markov要求是全排列，像我这样只把出现的学习一样不可以吗？生成的时候只生成我们学到的内容不可以吗？不可以！因为Markov需要平滑，因为Markov需要考虑所有可能的情况，虽然没学习到的内容出现可能会非常低罢了！
既然有这样的需求，，那我们依然需要稀疏矩阵中稀疏部分的值呀，所以我们在生成部分直接求呗，很快的。这也说明了一句古话，“逃得了初一,逃不过十五”，是在一开始我们就将所有稀疏部分的值求好呢，还是需要的时候临时再求呢？这有点像ECC和RSA，一个加密快一个解密快，那就合理使用嘛！服务器若需要做大量解密工作的话，就用RSA做公钥加密算法呗，因为解密快，就会少用点资源。要灵活地看程序真正使用场景的需求，是动态还是静态？是牺牲空间还是牺牲时间？哪有谁就比谁好呢？
这算是Markov学习数据过程中，最大的感触了，其他的就不说了。
三、根据Markov生成数据
这部分给我带来的最大的感触就是，代码要一定要和执行环境挂钩！不要想当然！一切要以程序真正实现为主！必须考虑计算机内存资源的合理分配！！！（这点大家可能都没有遇到过，就不和大家解释了）
为了能让程序正常运行，我们必须合理使用内存，内存的占用、内存的释放、一次使用多大的内存、用什么数据结构存放？我们都要去考虑！
长度太长的时候，内存经常到4个G，程序就报错了。在没有找到简单解决方案后，自己写了一个内存硬盘动态交换数据并支持断续执行的代码，而这个代码也是我非常想逼逼的哈哈。这个环节我直接上代码了，由于是代码片段，所以不是很好理解= =。
//通过循环来生成长度为0-maxlength的数据 for (int i = 0; i < maxlength; i++) { //fragnum数决定着长度相同数据 “分存” 在几个txt中 //随着长度的增大数据数量会非常非常大 //故我们通过存储在多个txt中，可以保证txt文件的正常生成，可以做到 “分段” 跑数据！ int fragnum = 0; for (int j = 0; ; j++) { //读取Length为i，Part为j的文件，即长度为i的第j个存储数据的txt文件 string inpath = FileDirectory + "Markov_Length_" + i.ToString() + "_Part_" + j.ToString() + ".txt"; //ListofBase用来临时存放从上面文件中读取到的length-1的pre数据 //在循环内初始化List，可控制内存开销，保证可持续发展 List<string> ListofBase = new List<string>(); Console.WriteLine(i + " " + j); try { //将inpath文件中的basic数据读进ListofBase StreamReader sr = new StreamReader(inpath, Encoding.Default); String line; while ((line = sr.ReadLine()) != null) { Console.WriteLine(line); ListofBase.Add(line); } Console.WriteLine("------------------------------"); //准备将生成的数据存储在长度为length为i+1的数据txt中 //part值由fragnum决定，fragnum在length层面上初始化为0，随后的值将一直伴随 string outpath = FileDirectory + "Markov_Length_" + (i + 1).ToString() + "_Part_" + fragnum.ToString() + ".txt"; FileStream fs = new FileStream(outpath, FileMode.Create); StreamWriter sw = new StreamWriter(fs); //modcount的大小决定从ListofBase中抽取多少个用来生成数据 //同一批数据生成的新数据存放在一个part中，用这个来具体实现对同一长度数据的 “碎片化” 存储 int modcount = 0; //遍历整个ListofBase foreach (var element in ListofBase) { //将modcount控制在（0，499999）之间 modcount = (modcount + 1) % 500000; //若modcount等于499999，则说明foreach循环已经执行了500000次 //通过更改输出txt文件名来分开存储 if (modcount == 499999) { //文件后续处理 sw.Flush(); sw.Close(); fs.Close(); //修改文件名，++fragnum outpath = FileDirectory + "Markov_Length_" + (i + 1).ToString() + "_Part_" + (++fragnum).ToString() + ".txt"; fs = new FileStream(outpath, FileMode.Create); sw = new StreamWriter(fs); } //temp用来存储ListofBase生成的数据 List<string> temp = new List<string>(); //调用ExtendPassword方法，element生成的数据存放在temp中 temp = ExtendPassword(element); //并将temp中数据存放在文件中 foreach (var every in temp) { sw.WriteLine(every); } } //文件后续处理 sw.Flush(); sw.Close(); fs.Close(); } //如果没有读到（i，j）文件，那么判断Length为i的第j+1个部分是不存在的 //跳出循环，读Length为i+1，Part为0的txt文件 catch { break; } } }