数学之美

2000多年前，古埃及人在罗塞塔石碑上，用三种文字记录了托勒密五世登基的诏书，这帮助后人破解了古埃及的象形文字，让我们了解了5000年前古埃及的历史。可见信息冗余是信息安全的保障，这对于信息编码具有重要指导意义。

犹太人为了避免抄错《圣经》，发明了一种校验码的方法，他们把每一个希伯来字母对应于一个数字，这样每行文字加起来便得到一个特殊的数字，这样的数字变成为了这一行的校验码。

隐含马尔可夫链成功应用在机器翻译、拼写纠错、手写体识别、图像处理、基因序列分析、股票预测和投资等方面。

如何准确的识别出一个快递地址，写一个分析器去分析这些描述恐怕是不行的，因为地址是比较复杂的上下文有关的文法。答案是使用有限状态机。当用户输入的地址不太标准或有错别字的时候，有限状态机会束手无措，因为有限状态机是严格匹配的，所以科学家提出了基于概率的有限状态机。

2002 年，Google 想要做一个全新的中、日、韩搜索算法，吴军写的算法比较简单，但是占用内存比较多，Google 服务器数量还没有那么多。辛格提出，用一个拟合函数替换很耗内存的语言模型，无需增加任何服务器，但是搜索质量会降到 80%。辛格指出，这样可以提早两个月将这个新算法提供给中国的用户，用户体验会有质的提高。辛格做事情的哲学，先帮助用户解决 80% 的问题，再慢慢解决剩下的 20% 的问题，是在工业界成功的秘诀之一。

新闻分类的关键在于计算出两篇新闻的相似度，每篇新闻变成一个向量，最后余弦定理可以计算出来相似度。但两两计算的迭代次数太多，如何一次性就把所有新闻的相关性计算出来呢？答案是矩阵运算中的奇异值分解。

如何判断两个集合是否相同？一种答案是双层 for 循环一一比较，复杂度 O(N^2)；稍好一点的办法是对集合进行排序，然后顺序比较，时间复杂度 O(NlogN)；还可以将一个集合的元素放到散列表里面，另外一个与之一一对比，时间复杂度 O(N)，但是额外使用了 O(N) 的空间，不完美；最完美的是计算这两个集合的指纹，对一个集合中的元素分别计算指纹，然后一一相加。

如何判断两个集合基本相同？答案是 Simhash。判断两个网页是否重复，也没有必要完全从头比到尾，只需要每个网页挑选出几个词 (IDF 最大的几个词)，构成特征词，然后计算信息指纹即可。判断一篇文章是否抄袭另外一篇文章，每篇文章切成小的片段，挑选特征词，并计算指纹。YouTuBe 如何从上百万视频中找出一个视频是否另外一个视频的盗版？其核心在于关键帧的提取和特征的提取。关键帧对于视频的重要性，就如同主题词对于新闻的重要性一样。

最大熵原理指出，对一个随机事件的概率分布进行预测时，我们的预测应当满足全部已知的条件，而对未知的情况不要做任何主观假设，这种情况下，概率分布最均匀，预测的风险最小。例如拼音输入法，Wang-Xiao-Bo 转换为王晓波和王小波，唯一确定用户需要的是哪一个，非常难。