Persi Diaconis(2)

本篇将给出上次提出的解码问题的一个可能的解(建议大家阅读Persi Diaconis写的原文，可以很容易在谷歌中找到，文章名字见上一篇)。

假设我们已经知道该密码文件中所有字符对应的实际中的符号集(如26个英文字母以及0-9的阿拉伯数字等)。

我们将这些字符随机地对应到我们已知的符号，看看结果是否合理(即解码后是否有意义)，如此遍历所有可能的对应关系，就可以了。这是一个办法，但显然不是一个好的办法。

我们知道实际中每个字母的出现频率是有高低的，而字符表中每个字符的出现频率也是有高低的，并且，二者应该是有这样的倾向性的，即高频率的字符应该对应着高频率的字母。那我们就可以按照这样的频率对应关系，将其对应过去即可。

我们如此估计是因为我们觉得某个字符高频率地出现正是由于它对应了高频率出现的字母的可能性“忒”(东北人)大了。但这个策略不佳，一方面在于除了一部分字母出现频率显著地高或者低以外，其他很多字母出现的频率是差不多的，另一方面是由于该策略考虑到是一个局部最优或者说是贪心策略，而没有整体上考虑。下面给出Persi Diaconis的策略，来解释整体考虑的含义。

他(实际上是他的学生Marc做的)找来一个标准的文本(战争与和平，因为足够厚)，统计从字母x到字母y的一步转移概率(即当字母x出现后，下一个字母是y的频率)。

这样，他利用前后字母的依赖关系，来描述整个密码文本中出现这些字符的概率模型，即如果给出每个字符所对应的字母，我们实际上是利用一步转移概率的模型而并非之前(策略二)字符彼此独立的模型来描述文本出现的可能，这一点非常重要！)。这就是为什么我们说(我说)策略二给出的是局部的，贪心的，因为真正的情况，这些字符出现彼此是有关联的，而并非完全独立，举一个例子，当前一个字母为辅音时，后一个字母出现元音的概率更大，进一步，连续几个辅音出现之后再出现辅音的概率将非常低。

在这里，我们只考虑了当下字母的出现只依赖于上一个字母，即一步转移概率。

在给出具体的算法前，我们现在应该了解到，为什么Persi Diaconis 给出的策略是好的，因为他更为准确地描述了这一密码文档的概率模型，我们还应该了解到，我们是如何定义什么情况下找到的字符与字母对应关系是好的，即这种对应关系在我们给出的概率模型中使其概率最大的那种对应关系。

如果能够知道我上述所说的含义，那么即使你不能够了解下面给出的算法也没关系，因为下面给出的只是为了解决如何能够更快地计算出这种概率模型概率最大时的字符与字母对应关系。

======================MCMC=======================

1. 随机给出字符与字母的一个对应关系。

2. 利用已经获得的一步转移概率，以及我们建立的概率模型，计算这种对应关系出现的可能性大小(概率)P1。

3.  随机抽取两个字符，互换它们的对应关系。

4.  计算新的对应关系下，该模型的概率P2。

5.  如果P2>P1，接受新的对应关系；否则，抛一枚以P2/P1的概率出现正面的硬币，如果出现正面，则接受新的对应关系，否则依然保持旧有的对应关系。

6.  如此重复上述操作2-5，不断更新这种对应关系，直至对应关系确定(收敛)。

================================================================

这里利用的MCMC策略中的Metropolis-Hastings 算法(MCMC策略还包括Gibbs Sampling等)。在假设所有对应关系出现的可能性相等的前提下(了解贝叶斯统计的知道，这是说一个uniform prior)，我们考虑从该对应关系在给定密码文件的情况的下的条件分布(后验分布)中抽样，由于该分布是尖锐的(真实的对应关系对应的概率相当大，其他情形都比较小)，这样，我们当MCMC算法抽样稳定时，基本上会抽到真实的对应关系了。

实际情况下，程序大概跑了200多步（相当快），得到的信息就已经有意义了，下图给出翻译出来的结果：

从这里，我们看到的是混合有英语，西班牙语等信息的文件。而算法本身的可行性，涉及到了MCMC算法的理论，我们后续给出。