数学建模社区-数学中国

标题: 2015数学中国认证杯赛题点评 B题 [打印本页]

作者: magic2728 时间: 2015-4-19 18:41
标题: 2015数学中国认证杯赛题点评 B题

大家好，我是magic2728，欢迎来到B题，这题也是我在本次挑战赛四个题目中比较欣赏的，题目思路清晰，既考功底，也需要源于技能积累的创新能力，能反映水平，也能拉开差距，望大家认真品评。

（文章中用到我在数学中国课程中常用的信息标注法和函数建模法，不影响阅读，也欢迎同学们关注magic2728在数学中国开设的课程，助各位在建模学习之路上一臂之力。）

历史上有许多密码的编制方法。较为简单的是替换式密码,也就是将文中出现的字符一对一地替换成其它的符号。对拼音文字而言,最简单的形式是单字母替换加密,也就是以每个字母为一个单位,将每个字母替换成另外的字母或者另外的符号。较为复杂的形式是以多个字母为一个单元,整体替换成其它的字符。这个映射方法被称为密码表,拿到密码表的人就能够将密文破译成明文。单字母替换加密是在古代就使用过的一种加密方法,但由于其容易被破解,所以在现代需要加密的场合已经很少使用。（bk1）

单字母替换加密的破译方法有频率分析等。这种密码和破译方法在小说中也经常提到,例如爱伦·坡的«金甲虫»和柯南·道尔在福尔摩斯系列故事«归来记»中的“跳舞小人”。但当获取的密文篇幅不是很大时,光凭借频率分析是不足以破译全部密文的。往往还要熟知该种语言的人,经过对可能出现的词汇及字母组合进行分析,才能完整地破译密码。（bk2）

第一阶段问题:假设明文是由现代通常使用的英语写成的。（rsc1）现在我们获取了一些由单字母加密方法加密的密文。请你建立合理的数学模型,设计一个算法,来自动化地破译密文。并设计一个衡量破译能力的标准,来评价破译算法的破译能力。（spm1）为了问题简单起见,我们假设密码表仅是针对26 个字母的,每个单词之间的空格,以及标点符号仍然会保留。（rsc2）在设计算法时,如果需要,可以参考英文语料库的数据,例如免费的COCA1等相关资料。（imp1）

密码学背景，实际是一个自然语言处理问题，让我回忆起了一些这个领域用以数学建模，尤其是统计建模为核心设计的优美解决方案：机器翻译，语音识别，拼音输入法，当然还包括此处的加密，再一次赞叹数学建模在现代科学技术引领的社会里的伟大作用！

回到此题，前第一段背景介绍了替换式密码，用数学语言描述就是，对于字母表全集A，由以其为象和原象的一一映射C，使得b = C(a),a,b 均含于A，C就是所谓的替换式密码。后一段介绍频率破译法，模型本质是，每一个字母表的字母映射到一个属性出现频率，这一频率也是该字母对应象值的频率值，根据这种穿透力，破译原来的映射。

按照函数建模法的思路，我们挖掘出本题的函数关系：

自变量：破译算法

因变量：破译算法的破译能力，比如量化为期望错误率；

参数：语料库大小，加密方式，语种等等；

函数关系：依据统计模型推断在给定样本容量的情况下期望错误率的大小。

本题表面上是评价模型评价算法好坏，单一评价指标错误率就足矣（算法的复杂度，语言什么的显然不在评价范围之内），没什么难度，又好像是优化模型，而求解更没有难度，无非是对方案的评价结果值比较大小而已，因此，本题重点在于自变量的找寻（即算法设计），辅之以基于统计学的函数关系表达式建立，就像眼科病床问题重点在于设计出安排方案作为自变量，而方案比较绝非难事一样。

下面简单谈谈破译算法设计：

可以看作破译是对应映射C的获得，等价于字母表的一个特定排列，我们要做的就是把排列当做参数，估计最优者。估计参数必然要找损失函数，比如频率法中，损失函数可以是各自变量字母频率与对应因变量频率的残差平方和最小，或推导下似然性的最大，即：

C = arg min sum（S）（loss（Q（s， cp） - Q（C（s）， cp）））

s为某语言结构S（字母表A集合的函数）中的元素（比如字母S = A，A ^ 2等），Q为所选择的性质的基于语料cp的估计，则为整个训练语料库，而除了字母频率这一性质，基于语料库还有多该信息的种理解方式以挖掘出一些性质来作为破译的标的，下面简述之。

基本语料库给出了按国家，风格划分的文章的内容，如果不利用任何周边信息，假设每一个有序出现的字母都是独立重复事件，S = A, Q(s，cp) = p(s)est，此即为频率破译法的本质。

这里，可以提几个其他的几个简单想法：

1. A ^ n, A的n阶笛卡尔积，这样，元素个数会迅速指数式扩展，在语料库里也可以直接理解为有序的横向排列。在保证每个元素样本数量仍然足够的情况下，可以挖掘出更高层次的信息；当然也可以是其他模糊匹配模式。

2. 构成以空格或者标点分割的单词，其实可以发现，单词的频率在某类文章才会更体现其特点，也会越不一样，因为我们是先想到要表达的意思，再想到逻辑结构，再想到要填的单词，最后才把字母拼上去，所以单词的特性更能够有区分力，信息熵更大；（当然以句号分割的句子，以逗号分割的单句，或者意群（能充当句子成分的多个单词）等等也可以作为S，但那要大量语料库才行）；当然，一个词以不同词性出现时归为一个词考虑，还是有所区分，建立更高阶网络，也是需要考量的问题，题目网站里前两个数据库结论就是给的以词为独立元素和词性划分的信息的。

Q：

我们很难去想清楚一个句子的生成有什么物理机理，而且我们对推断出一个特定的结果也没有兴趣，做解密不需要深入到这个层次。我们写出一个领域的文章，段落，句子，单词，字母，难以象F = ma那样挖掘出精确的等式关系，因为那需要知道该事件发生的一切信息，而这更像我们研究一个性质稳定的色子，大概不可能去获得所有信息，然后计算数值，找阈值判别最后的点数结果（虽然理想地来看这个结果是个确定的数），而应当是做些实验去得到一个稳定的统计规律即可，这就是统计建模相比于机理建模的优势，一方面便于实践操作，另一方面抓住本质而不浪费更多资源地解决了要解决的问题，难怪统计学“难度不大，应用甚广”的特点。

这里提几个简单的统计模型。

1. p（s）est = freq(s)，不考虑上下文对s出现的影响（或假设没有影响），把s的出现看作是独立重复事件，直接用频率作为估计概率的极大似然估计值，当S = A, 此即频率分析法；

2. p(s1 | s2)est = freq(s1s2) / freq(s2),假设仅上文的一个s2对下一个s1有影响而构成有用的先验知识，估计一组条件概率的值（｜S｜ ^2 个参数），这就是马尔可夫链了。

3. p(s1 | s2, s3)est = freq(s1, s2, s3) / freq(s2, s3),假设上文的两个元素s2，s3有影响，没错，这是二阶马尔可夫链！

（也可以注意，p(s1, s2 | s2, s3) = p(s1 | s2, s3),二阶马尔可夫链等价于一阶链但是对应字母集变成自身平方。）

当前大部分对序列的建模方式就是这些了，包括提到的机器翻译，语音识别，手写识别，染色体拷贝数判别，拼音输入识别等方法大部分都是基于马尔可夫链或隐含马尔可夫链，其它或许还有更好的分词方式和统计模型，但就抓住模型本质来说，马尔可夫链无疑是当前广为接受的最佳的一个了。

好了好了，不影响大家自己的思路了，就说到这里，各位加油！

作者: 阿远2014 时间: 2015-4-22 14:24
写得真好，不错啊

作者: 湮栎 时间: 2015-4-26 14:07
可以，感觉自己做得不怎么好

作者: 2278287706 时间: 2015-4-29 16:32
感觉自己只做了个皮毛！

作者: 1345389794 时间: 2015-6-3 23:06
不错~~~~~~~~~~~~~~~~~~~~

作者: wlz123 时间: 2015-7-10 09:25
不错给楼主赞。。。。。。。

作者: 843134767 时间: 2015-7-31 08:17
上次发挥的不好争取下次考出好成绩！

作者: 383250890 时间: 2015-8-4 09:19
写得真好，不错啊写得真好，不错啊写得真好，不错啊写得真好，不错啊

作者: miss张 时间: 2015-8-27 08:38
写得真好，不错啊写得真好，不错啊写得真好，不错啊写得真好，不错啊

作者: 刘永强 时间: 2016-3-26 22:00
写的很好很认真，对建模初学者有很大的帮助。。

作者: lshqcable605 时间: 2016-4-11 09:34
excellent

作者: 王== 时间: 2016-7-30 17:53
写的很好

作者: jiquan 时间: 2016-10-19 13:20
写得真好，不错啊

作者: jiquan 时间: 2016-10-19 13:21
写得真好，不错啊

作者: jiquan 时间: 2016-10-19 13:21
写得真好

作者: jiquan 时间: 2016-10-19 13:22
不错啊……

作者: jiquan 时间: 2016-11-6 09:24
感谢分享~

作者: jiquan 时间: 2016-11-6 09:25
感谢分享~

作者: jiquan 时间: 2016-11-6 09:26
感谢分享~

作者: jiquan 时间: 2016-11-29 08:29
谢谢分享

作者: jiquan 时间: 2016-11-29 08:30
谢谢分享

作者: jiquan 时间: 2016-11-29 08:31
谢谢分享

作者: jiquan 时间: 2016-11-29 08:32
谢谢分享

作者: jiquan 时间: 2016-11-30 08:01
感谢分享~

作者: jiquan 时间: 2016-11-30 08:02
感谢分享~

作者: jiquan 时间: 2016-11-30 08:03
感谢分享~

作者: 荒野孤狼 时间: 2017-4-12 11:27
写的真好不错，就是有点看不懂

作者: 605444314 时间: 2018-4-7 16:23
6666666666666666666666

作者: 442757975 时间: 2019-9-21 20:38
感谢分享，大爱！

欢迎光临数学建模社区-数学中国 (http://www.madio.net/)