064 | 计算机科学中的随机化 —— Bitcoin的基础之一

我们通常比较喜欢确定性，不喜欢随机性。但是在计算机科学中，很多时候我们故意要把确定性变成随机的，这种思维显然和我们人类的思维不同。我们前几天提到了查到和搜索需要用到这种方法，今天我们填上这个坑。另外，每个人都不知不觉地使用信息加密，也离不开随机化。我们今天说比特币是安全的，其实也是靠随机化来做保障。当然，我们还是从查找信息这件事说起。

之前几次讲到有效查找信息可以借助搜索这个工具。比如说我们要找李强的信息，有了索引之后，计算机可以先在索引中找到李强的信息所存放的位置，然后才是进一步获取所要的信息。有了索引之后，计算机可以先在索引中找到李强的信息所存放的位置，然后才是进一步获取所要的信息。但是在前几天的课中，我们忽略了一个问题，就是在索引中，我们怎么找到李强的位置？如果我们的索引包含北京市户籍中所有的人名，这个索引本身就很大，可能有几百万，或者上千万。虽然在索引中找到李强比在数据库中找到他容易，但毕竟是件不小的事情。类似地，在搜索引擎中，虽然我们根据每一个词把所有的文档建立了索引，但是在Google的词表中，全世界有千万个不同的词，要在索引中找到“得到”这个词，也不容易。（是啊，感觉是之前做过的爬虫逻辑有点像。）

解决办法是，把索引排个序，用二分查找即可。没错，这确实是一个好方法。对于规模不大的数据库，索引也是这么建立的。这种方法最大的好处是不会浪费任何空间，储存的效率比较高。那么用二分查找，在索引中找到“李强”要查找多少次呢？假设北京市人名索引中有800万个不同的人名，或者Google的词表中有800万个单词，通过二分查找需要23次可以找到“李强”，或者”得到”，也就是Log(8,000,000)。23次算不算多呢？（为什么我得出的是6.9呢？）这对计算机科学家来讲不算一件了不得的事情，但是在工程上这个次数算不算多，得看具体的应用了。对于查户籍这件事，23次查找真算不上什么，但是对于语音识别或者机器翻译，识别或者翻译一句需要查找上万次词语，如果每一个词都要先在索引查23次才能找到，就是一个大负担了。我们希望最好有一个办法，能否三下两下就找到“李强”或者“得到”在索引中的位置，这样可以节省十倍的时间了。

上面这样的想法现实不现实呢？事实上是可以做大的，但是要付出一点代价，它就需要用到我所说的随机化了。下面我就来讲讲随机化是怎么样进行的。

#方法一
首先，我们来看一个笨办法，有些时候，笨办法是好办法的基础。我们知道，汉字大约有两万多个，我们就放大一下，假设是3万个吧。这样每个汉字就对应了一个从0~29999的数字。加入“李”这个字对应3500，“强”这个字对应“4003”（哇，那英语怎么办呀？俄语呢？其他特别的语言呢？比如阿拉伯语？），那么，“李强”就对应就对应一个数字组3500和4003。注意这个对应是唯一的，没有歧义性。

接下来，我们做一个简单的数学变换，把上面两个数字变成一个，方法是：30000 * 3500 + 4003 = 105,004,003，也就是说拿105,004,003这个数字作为“李强”这个名字的编号。注意，这个数字和“李强”这个名字的对应关系也是唯一的。类似地，我们假设“得”对应509，“到”对应10032，作为“得到”这个词的编号。这样以一来，每一个中国人的名字，或者汉语的词都可以对应一个数字。

再接下来就简单了，我们建立索引的时候，直接把“李强”存放到第105,004,003个储存单元，把“得到”存放到第15,280,032个储存单元，将来查找时，无论是看到一个词，还是看到一个名字，只要用上面的公式做一次计算，就能直接找到“李强”，或者“得到”在索引中的位置了。这个方法确实快，把原来23次查找变成了一次，但是什么事情都是有成本的，这个方法有两个大问题：

• 其一，非常浪费。不会有人起名为“猪狗”后者类似的名字，于是对应数字所占据的单元就被浪费掉了（原来如此啊！）。大约会浪费掉多少呢？如果汉字是3万个，每个人都是两字的名字，一共有9亿个不同的编号。再假如北京市不重复的人名是800万个，大约浪费了99%以上的编号（以及对应的内存单元）（99%是怎么算出来的呢？）。这显然不是一个好办法。
• 其二，也是更糟糕的，当大家齐了三字名，甚至是四字名后，名字对应的编号就可能非常大，以至于超出计算机的存储范围。

所以，问题一方面是浪费，另一方面是空间不够用。为了解决问题，我们就要用到第二个方法了。方法二，只保留编号的尾数。

#方法二
我们注意到无论是“李强”的编号，还是“得到”的编号，都特别长，这么长的编号是不太会重复的，那么稍微短一点行不行？比如我们不管编号多少位，只保留最后的7位数字，也就是说将编号的范围从9亿缩小到1000万。由于北京市只有800万不同的人名，照理说准备1000万个代号是够用的，之所以不够用是因为不同的人名计算出的编号，位数可能恰巧重复，这种情况并不少见。那么接下来怎么办?这其实也是我给你的问题。通常这时候人会有两种态度，一种是退回来，另一个种是遇到问题，解决问题。

在Google时，每当下属对我讲什么事情有苦难时，我一般会先判断一下能解决的可能性有多大，如果我觉得还是能解决的，就会对他们说，“遇到问题，解决问题，这时候正是显示你们科班出身的工程师水平的时候，否则你和半路出家的人有什么区别？”几乎所有的时候，他们发挥主动性，问题还真就解决了。对于上述问题，当年研究算法的科学家们也是本着这个态度解决问题的。具体讲，就是在尾号出现相同的情况时，想办法找到一个没有那个词或者名字对应的尾号，作为备选方案。我们既然有1000万个代号，只有800万个名字，这个备选的号码，一定是能够找到的。

为了便于你理解其中的原理，我们不妨看这样一个例子。假如火车站买票时是随机安排座位的，到了火车上，一定有一些人拿到相同的座号。但是，但是如果火车能载1000人，只卖了800张票，一定有办法安排每一个人就座的。具体的做法是，先来的先坐下，如果后来的发现自己的票上的座位已经被占据了，那么没关系，找最近的坐下即可（不是等到所有人都坐下，被占座的被统一安排到空余座位上）。如果火车上真的有20%的空座，大家其实都能在附近找到一个空座。在计算机中，安排这种相同位数的编号的方法和火车上安排座位的原理是一样的。当然，对于任何事情，我们都应该问问，是否还有更好的方法。对于这个问题也是有的，那么就要讲到方法三了。

#方法三
方法三，随机指定一个名字或者词语的编号。我们在方法一和方法二中，其实是按照一个公式，将人的名字或者一个词，变成一个编号的，然后再取它的尾数。这时，两个不同的名字有可能得到相同的编号尾数。后来计算机科学家们发现，如果随机地给每个名字，后者词语进行编号，重复的可能性最小（hmmmm，为什么呢？）。于是，计算机科学又有了一个小分支，如何产生伪随机数(Pseduo-Random Nubmers)。为什么说是伪随机数呢？因为它们并非真的随机，只是看上去非常像随机产生的。至于为什么随机的比确定性的好，我们这里就省略了，大家记住这个结论就好。伪随机数想要像真的随机数，就需要懂得很多数学原理，于是很多数学家也就加入了这方面的研究。后来，数学家和计算机科学家们发现，如果一个信息（比如名字或者词语），对应的伪随机数足够长，别人是无法通过这个数字还原出来原来的信息的，但是产生这个伪随机数的人却可以（Jezz，这个好有意思啊）。于是，这个方法就能用来进行数据加密。当然，这里面还有一个问题，如果加密的人和接受到信息后解密的人不是一个人，解密的人需要知道加密的方法。如果这个方法给了对方，万一泄露了出去，就麻烦了。后来，数学家们想出了一个不让对方知道自己怎么加密，却能够让某个信息解密的方法。这种方法在密码学上被称为公开密匙，今天大部分加密算法都采用这种技术。

比特币产生的算法，外面的人是不知道的，即使挖币的矿工也不知道，否则你就自己能制造比特币了。产生比特币的过程，和我们说的将“李强”对应一个数字类似，它要产生一个比特币对应的随机数，也被称为私钥（不公开的），谁拿到它，就拥有了比特币。这个随机数不能丢，否则比特币就不是你的了。那么大家怎么知道你的比特币是真的呢？比特币协议还会产生一个公开的秘钥，它可以用来验证比特币的真假。你可以把比特币产生的协议看成印钞机，它怎么印钞，不能让你知道。而比特币的公开秘钥，则相当于验钞机，你可以拿它验证比特币的真伪。如果验证完了确认为真，你瘦了那个比特币，私钥就归你了（哎，怎么保证不泄密啊），当然，比特币的所有权和使用权就给了你了。

​
我们从今天查找讲到比特币，内容跨度很大，我把他们总结如下：

• 1. 从查找到比特币，很多技术背后的道理是相同的，这也就是我喜欢讲原理，不喜欢讲具体的实战技术的原因，原理搞懂了，一通百通。一些朋友讲，能不能将一些我明天就用得上的内容。非常抱歉，我只能说他们找错人了。我希望我的读者朋友都是能举一反十的，不是死记硬背方法的。
• 2. 我们今天的内容是一层层递进的，这样讲的目的是要强调一种做事情的方法，就是遇到问题解决问题。（层层递进 —》 等于遇到问题解决问题。）
• 3. 今天我们队对急性和随机化开了一个头，今后我们还会讲到相关的内容。从随机性在一些领域比确定性的好处，我们应该了解，世界上很多时候，好和坏和我们想象的不一样，而且这种客观性不随我们的好恶改变。
• 4. 回顾这一周的内容，我们讲查找信息的成本从几千万次，甚至十多亿次降到了几十次，又通过随机化降到了几次，甚至是一次直接成功，这也说明了技术无止境，我们队自己的要求也不该有止境。

有了这些铺垫，接下来可以讨论一些技术性较强的Google面试题了。