计算机科学中伟大的算法

• 前言
• 搜索引擎的索引
• PageRank
• 公钥加密 --- 用明信片传输秘密
• 纠错码
• 数据压缩
• • 无损压缩
  • 有损压缩
• 数据库 --- 追求一致性的历程
• • 事务和待办事项（预写日志记录）
• 数字签名
• • 用挂锁签名
  • 用指数挂锁签名
  • RSA的安全性

前言

我肯定不是一位天文学专家——事实上，我在这个领域里相当无知，我想知道更多。但每当我注视夜空时，我知道的少量天文学知识增强了我此刻的享受。有时，我对所见事物的理解，让我产生了一种满足和惊奇的感觉。（这是在一本书中的一段话，或者这就是读书的一大乐趣之一吧）

目前，在我看来，公众对计算机科学认知（我就是学计算机科学与技术的）的不平衡：有一个广泛的观点认为，计算机科学基本上是编程（如“软件”）和设备设计（如“硬件”）。事实上，最美妙的计算机科学思想中有许多十分抽象的，并不属于以上任意一类。它们更强调的是计算机科学理论，有时候我们应该将计算机科学作为一门知识学科来理解。（可能是说要修好内功吧，理解好本质，因为太表面的，随便一个人学个几年也是可能操作的）。

搜索引擎的索引

搜索主要有两个阶段：匹配和排名。（在我的算法课设就是做一个小型搜索引擎，后悔没有先读到这本书，不然就可以实现功能更完善的搜索引擎了）。

1. 首先最基本的就是创建单词索引表了。也就是首先为出现在任一页面上的所有单词创建一份列表，然后按字母表的顺序整理这张列表。通过这种简单的方法，搜索引擎就可以答复许多简单的查询了。
2. 短语查询。指对于一个确切短语的查询，而非凑巧的一些单词出现在页面的某些地方。 比如 “cat sat”与 cat sat 两者的查询的意义是不同的。 那么如何进行有效的查询呢？那就是称之为“词位置”的索引方式。 也就是在上一遍索引的基础上，索引不仅应该存储页码，还要存储信息在页面内的位置。
3. 在上面基础上，还有一个就是“元词把戏”。 上边都是针对一些极其简单的网页实例。然而，绝大多数网页拥有众多结构，包括标题、标头、链接和图片。在HTML中，标头、标题、链接、图片等格式化结构是用被称为元词的特殊单词编写的。如<title> </title>.将出现的元词也像存储正常单词一样存储元词的位置来建立索引元词的简单把戏就是“元词把戏”。 该方式能让搜索引擎可以以极其高效的方式回应有关一个文件结构的查询。

搭建一个搜索引擎并不是一件容易的事情。单靠，前面提到的三个建立索引的方式并不能解决创建一个高效搜索引擎的问题。不过，这些无疑展现了真正的搜索引构建和使用索引的风格。（对于小型搜索引擎来说，如果能使用者三个引擎，可以说是能建立好一个较完善的搜索引擎的）

PageRank

可以说，搜索引擎的生死由其排名系统的质量来决定。这里就简单介绍一些，早起使得谷歌腾飞的一个网页排名算法。

1. 超链接。如果没有其他信息，那么一个网页的链入链接数可能成为该网页“有用性”或“权威性”的指标。虽然存在有的链入链接是差评之类的，但是，在实现生活中，超链接更多是用于推荐而不是批评。因此，尽管有这个明显的缺陷，借助超链接的方式仍然很有用。
2. 权重。来自高权重网页的链接排名要比来自低权重网页链接的排名高。那么如果进行判别呢？将超链接与权重结合起来。所有网页的初始权重都是1，但如果一个网页有链入链接，在计算该网页权重时就要加入指向其网页的权重。（但是这个方式有一个重大的缺陷就是遇到“循环”的时候，这样计算权重值，会产生“鸡生蛋还是蛋生鸡”的问题）。
3. 随机访问者。上边循环导致的问题，可以通过随机访问者来解决。 这个方式时假设一个随机访问互联网的人开始。确切地说，访问者随机从万维网上的一个网页开始访问，然后检查该网页上的所有超链接，之后随机挑选其中一个超链接进行点击。随后，用户再检查打开的新网页，并随机选择一个超链接打开。这个过程会持续进行。 该过程有一个关键要点是：每次访问一个网页时，都有一个固定的重新访问概率（15%），让访问者不从已有的超链接中挑选一个并点击。相反，访问者会重新开始这一过程，从互联网上随机选择一个网页点击。（也就是，访问者有15%的概率不想点击该网页中的超链接）。
4. 随机访问者模型和权重之间的联系是：从随机访问者模拟中计算得出的百分比，正好就可以当做我们权衡一个网页的权重。因此，基本用来进行网页排序的就是超链接数量与权重。而随机访问者模型解决了权重计算的问题。
5. 但是，有一个复杂因素直接PageRank算法的核心：超链接传输的合法权威性假设有时是存在争议的。

公钥加密 — 用明信片传输秘密

之所以计算机传递的数据需要加密，是因为互联网上的所有信息都会通过无数被称为路由器的计算机，信息的内容可以为任何访问路由器的人所见。因此，每一条离开你的计算机并进入互联网的数据，就好像写在明信片上一样！（为什么？可以查阅我写的网络是如何进行的博客了解详情）

1. 首先我们的想法或许是，我们直接对每条信息加密不就好了？如果每一次通信我们都知道通信的对象是谁，那么这个方法还是可行的。但是问题是，计算机在和不“认识”的接收方进行通信。（比如，在第一次通信的时候，你的计算机之前从未和那个服务器联系过，那么就没有机会对密码达成一致）。
2. 之后的一个想法是，借用两者都知道的一件事，但是第三者不知道来进行计算。比如我和通信对象因为从小到大一起长大，互相知道对方的年龄，但是第三者不知道。那么我就可以传达，用我的年龄加上一个数，就会得到30.假设通信对象知道你的年龄是20，那么就可以知道这个数为10.因此，我们就对10进行了加密传输。这就是共享密钥的思想。
3. 上边提到的就是 一个“加法把戏”。在实际中，共享秘钥的数值会大很多。同时，由于加法得出的结果能用于统计分析，因此在这个相加把戏的基础上，出现了称之为“分块密码”的机密技术。目前，较为流行的分块密码是高级加密标准（AES），其标准配置是使用16个字母的“块”，配备128位秘钥，进行10轮混合操作。
4. 上边提到的思想的一个难点就是如何公开建立一个共享密钥。乍一想，感觉可能无解，因为传递的信息是公开的。但是聪明的计算机科学家们解决了这一个问题。被称之为迪菲-赫尔曼密钥交换。（俗称为颜料混合把戏）。也就是说，我和通信对象都有一个私有的颜料，之后两者公开选出一个公开颜料。之后各自将这个公开颜料与自己的私有颜料进行混合。之后，各自将混合之后的颜料公开，之后双方各自取到对方混合后的颜料，之后再加入自己的私有颜料，这个时候，两者最后颜料的颜色是一样的。但是，第三者很难知道，因为第三者只能知道，公开的一种颜料和两种混合之后的颜料。
5. 上边能实现的一个基础是一个被称之为单向操作的东西。也就是可以做一些事情，但不能取消做过的事。上边的例子就是，将一些颜料混合起来形成一种新颜色很容易，但是“分开”它们并获得原来的颜料则不可能。
6. 在现实生活中，我们就需要一个在现实生活中容易做到，但是实际中又不可能取消的数学操作。在计算机中，混合操作就是离散指数，而分离操作则被称为离散对数。（由于还没有一种方法能让计算机高效地计算离散对数，因此可以将认为离散指数就称为了我们寻找的那类单向操作）
7. 上边6中所提到的，在实际中，双方各自有一个私钥，公开的信息，也就是公钥（共享密钥）指的是幂和钟算的数字。这种计算机在互联网建立共享密钥的实践方法被称为迪菲-赫尔曼密钥交换机制。 常用于 https开头的网站。
8. 目前最著名的公钥加密系统是RSA。RSA与迪菲-赫尔曼方法（目前称之为DH密钥协商）都是非对称加密。两者最大的区别就是：①应用的场景不同。RSA常用于gitlab、github或者码云上，DH密钥协商则是带有https的网站的交互。②前者的数学原理是大叔分解质因数难和欧拉定理，后者则是离散对数。

纠错码

没有纠错码，我们的计算机和通信系统就会比现在慢很多，功能弱许多，可靠性也会差很多。为了使得计算机必须能在存储和传输数十亿“块”信息的情况下，不犯任何一个错误。大致思路如下：

1. 重复把戏。要确保一些信息被正确地传输，你只需要重复几次该信息。我们只需要增加重新传输的次数，那么总会使得可靠性达到我们的满意程度为止。 但是，重要操作对于小数据还行，但是对于大数据，很明显，重复传输的代价太大了。
2. 冗余把戏。这条基本原则是，你不能只发送原始消息，还要发送一些多余的东西以增加可靠性。在重复把戏中，可以认为发送的额外信息就是更多份原始消息。重复把戏和冗余把戏，都是可以同时侦测和纠正数据中错误的方法。
3. 校验和把戏。现如今，对许多软件而言，只侦测到一个错误，之后再请求发送一份数据即可。而且你可以一些请求新拷贝，知道得到完全无误的拷贝。这是最常用的策略了。①最原始的校验和就是将每个数据相加的结果就是用来检验的值。很明显这个方法只能检验出有一个错误的情况，因为如果有两个数据同时变化了，但是相加的和还是有相等的可能的。②阶梯校验和。如原始数据为 5 7 8，那么阶梯校验和为 15+27+3*8 ，使用简单校验和与阶梯校验和一起，就可以检验有三个错误一下的信息了。
4. 定位把戏。学名为 二维奇偶校验码。使用该校验码可以快速定位到错误的位置。
5. 目前较为使用的有 Reed-Solomon代码、以及在计算机网络中使用的CRC检验、MD5检验和SHA-1检验。

数据压缩

计算机文件和其他种类的数据，通常被压缩成更小的体积，以方便存储或传输。然后，它们会被解压并以原始形式被使用。
事实上，计算机系统背后经常用到压缩。比如，许多通过互联网发送的消息都经过了压缩，用户甚至不知道这一点，几乎所有软件都是以压缩格式被下载的——这意味着你下载和转移文件的速度要比不压缩时快数倍。甚至当你对着电话讲话时，你的声音也经过了压缩：如果电话公司能在传输语音数据前进行压缩，它们就能对自己的资源实现超高利用率。

无损压缩

虽然压损压缩算法并不能为所有文件节省大量空间。但是，一种好的压缩算法能为特定大类的文件节省大量空间。无损压缩算法主要是运用 “同前原则”和“更短符号原则”.

1. 同前原则。简单来说，就是将一些重复的数据通过更加简单的方式进行表示。
2. 更短符号原则。将数据中重复次数较多的用更短的代码形式来表示。
3. 计算机标准压缩ZIP文件背后的基本具体实施步骤为：①计算机使用“同前原则”传输未经压缩的原文件，让文件中绝大多数重复数据由段得多的指令取代，这些指令会返回并拷贝其他地方的数据。② 计算机会检查传输后的文件，选出经常出现的符号。比如，原文件以英语为书写语言，那么计算机就很有可能会发现“e”和“t”是最常出现的两个符号。随后，计算机会创建一张如下页的表格（该表格也会被存储在ZIP文件中，否则在后面就无法解压了），用短数字码代表经常用到的符号，用更长的数字码代表极少用到的符号。③计算机会通过直接将文件翻译为步骤二中的数字码来在次传输文件。

有损压缩

有损压缩常用于图片、音乐和视频的压缩。

1. 抛弃把戏。有损压缩的一个简单且有效的方法就是直接“抛弃”一些数据。 如在图片的有损压缩中，就可以每两行像素就抛弃一行，之后再解压的时候，消失的像素就可能选择任一相邻的像素的颜色。
2. 上边简单的抛弃我们是很少使用的。现实中，计算机的确会“抛弃”信息以实现有损压缩，但它们对抛弃哪些信息却要小心得多。其中一个常见的就是JPEG图像压缩技术了（简单来说，jpeg是把图像分割为很多小块分别压缩，每个小块就可能用很少的字符表示）。
3. 音、视频的压缩则是根据人耳或视觉的特性抛弃那些不敏感的部分。

数据库 — 追求一致性的历程

互联网交易中，一项关键技术就是公钥加密（上班已经提到了）。另外一种至关重要的技术就是数据库。 数据库针对交易处理的两个问题：高效性和可靠性。

事务和待办事项（预写日志记录）

事务（Transaction）极有可能是数据库世界中最重要的思想。但要理解它们的含义和必要性，我们就需要接受有关计算机的两个事实。你也许非常熟悉第一个事实：计算机程序会崩溃——当一个程序崩溃时，它会丢掉所有正在处理的东西。只有安放在计算机文件系统中的信息会得到保存。我们要知道的第二个事实不太为人所知，但它极其重要：硬盘和闪存条等计算机存储设备一次只能写入少量数据——基本上在500个字符左右。

1. 通常来说，对任何一个大小合理的数据库而言，更改两行的确需要两次单独的磁盘操作。 那么，许多对数据库看似简单的变更，要求更改两行或更多，我们知道这时无法一次性完成的，因此数据库更新会导致多次的磁盘操作。但计算机可能在某个时间崩溃。当计算机重启的时候，它会忘掉之前计划执行的操作。也就是说，数据库可能处于不一致的状态。
2. 首先，不一致不能通过在特定时刻检查数据库被侦测到。 为了解决这一问题，就提出了“事务”的概念----如果想让数据库最后保持一致性，就必须在数据库上完成一系列更改。
3. 待办事项的基本思想是，维护一个数据库计划采取的动作日志。日志被存储在硬盘或其他一些永久性存储介质中，这样，日志中的信息就能幸免与崩溃或重启。在一项事务的任何动作得到执行前，它们都被记录在日志中，然后再被保存到磁盘里。如果事务成功完成，我们就能删除日志中的待办事项列表，进而节省一些空间。（所以，当计算机崩溃的时候，检查日志中如果有记录，说明之前存在崩溃的情况）。在确保日志项被保存到了某种永久性存储介质上后，我们就可以按照表来按计划进行变更了。

由于这部分的内容，稍微学过数据库原理的都大致了解了，因此，就不再用太多的文字进行描述了。

数字签名

数字签名在实际生活中有哪些用途呢？答案可能和你一开始的想法相反：与你签署发送给其他人的材料不同，基本上是其他人先签署材料再发送给你。你很有可能并未意识到这一点的原因是，数字签名由计算机自动验证。比如，不管你何时想下载并运行程序，网络浏览器都会检查程序是否有数字签名以及数字签名是否有效。然后浏览器再显示一个合适的警告。
这里有两种可能性。如果软件拥有有效签名，计算机能完全肯定地告诉你编写该软件的公司名。当然，这并不能保证软件安全，但至少你能基于对该公司的信任程度做出充分了解后再做决定。反之，如果签名失效或缺失，你绝不会得到软件来自哪里的保证。即便你认为自己下载的软件来自一家信誉良好的公司，也有可能被黑客用一些恶意软件替换了真正的软件。软件也有可能由业余人士编写，他们没有时间或动力去创造一个有效的数字签名。在这些情况下，是否安装取决于用户是否信任软件。

尽管软件签名是数字签名最明显的应用，但这绝不是仅有的一种应用。事实上，计算机接收和验证数字签名的频率非常高，因为一些经常使用的互联网协议也使用数字签名，以验证与你进行交互的计算机的身份。比如，网络地址以“https”开头的安全服务器在建立一段安全对话前，通常会向你的计算机发送一个数字签名证书。数字签名还应用于验证许多软件组件的真实性，比如浏览器插件。你在浏览网页时很有可能已经见过这样的警告消息。

用挂锁签名

通过这个例子可以了解数字签名的理论原理。

1. 首先，每个人都会有很多挂锁（都是一样的，且假设挂锁无法破坏且没有钥匙无法打开），同时也会有对应的钥匙。 同时挂锁还有生物识别功能，也就是别人无法使用自己的挂锁去锁其余的东西。
2. 之后进行的数字签名过程是，自己向对方一份数字签名，之后为了能证明这份数字签名有效，将数字签名放入自己的挂锁中。并将这个装有数字签名的挂锁交给对方。（准确的说，上锁的箱子就是文件的签名）。
3. 如果对方像验证签名的有效性，只需要使用发送方的钥匙来尝试打开锁。如果能打开，那么发送发就需要对其中的数字签名负责。
4. 这一过程是真的巧妙，但是有一个缺点就是，它需要发送发的配合，如果发送方在开锁的时候，使用的不是自己的钥匙，那么就可以否认是自己的。因此为了防止这种欺骗行为，我们仍需要一个收信任的第三方，这个第三方有着发送发的钥匙，
5. 那么我们检验的时候，只需要通过这个第三方进行检验即可。
6. 上边提到地过程就是一个理论的步骤。实际生活中，我们不能在必须进行电子转换的签名上使用实体挂锁和实体钥匙。因此，下一步就是用类似的能数字化的数学对象取代挂锁和钥匙。、
7. 具体来说，挂锁和钥匙将用数字代表，上锁或开锁的动作将由钟算乘法代表。（也就是取余乘法）。

用指数挂锁签名

也就是在现实中运用的著名数字签名机制RSA。

1. 首先，我们会选择公开钟大小。之后，选自一个密码挂锁值（这个值可以是钟大小之外的任意数）。然后，我们用计算机算出挂锁和钟大小的钥匙值。（这一步可以轻易计算出）
2. 之后，如果对消息进行以挂锁值为幂的计算。如消息为4，挂锁值为3，钟大小为22 ，那么签名就为$4^{3}mod22=20$. 之后，对方如果想验证签名，就需要去权威的第三方得到我们算的钟的大小和钥匙的权威值。然后，对方借助这个钥匙对签名进行验证（如果结果与原消息匹配则认为签名是有效的）
3. 使用这一数学机制后，一旦选定挂锁值，参与者就能轻易计算出合适的钥匙值。但其他任何人想要逆转这一过程基本是不可能的。（如果你知道某人正在用的钥匙和钟的大小，你也不能算出对应的挂锁值）

事实上，RSA既是一种公钥加密机制，又是一种数字签名机制。RSA加密算法包含公钥和私钥。用于信息加密时是：公钥加密，私钥解密；用于数字签名时是：私钥加密，公钥解密。

RSA的安全性

对于RSA而言，这个问题可以转化为“别人能根据我的公开钟大小和钥匙值能计算出我的私人挂锁值吗”。
这个问题的答案是肯定的。

1. 暴力求解。我们已经知道了钟的大小和钥匙值，我们就可以枚举出所有可能的挂锁值。但是这个钟的大小在实现中是很大的，因此，我们对使用这种方法计算出挂锁值是不感兴趣的。相反，我们是想知道对方是否能足够高效地来计算出挂锁值。
2. 这个问题又可以转化为因式分解问题。在实际中，公开的钟的大小是由两个素数相乘得到的。因此，只要我们根据钟的大小，通过因式分解的方式得到两个因子，那么我们就可以轻易通过另外两个信息----钟大小和钥匙值来计算出挂锁值。
3. 事实上，尽管所谓的“整数分解”问题被研究了数个世纪，但是还没人能找到一个足够高效的通用方法解决它。因此，尽管专家们认为破译的可能性非常低，但原则上任何时候的任何一种加密或数字签名机制都由可能被攻破的。

数字签名的主要用途是验证下载后的内容。一个明显的例子就是，当你下载一份新软件时候，如果软件有签名，计算机就会使用签名者的公钥“解开”签名，并将结果和签名者的“消息”—软件本身—对比（实际中，软件会在签名之前被缩减成一条小得多的名为安全哈希的消息）。如果解开的签名与软件不匹配，则会收到一个警告。

参考文献：《改变未来的九大算法》