搜索引擎索引与匹配

搜索引擎对网页分词后创建索引，查找时通过索引找出原网页。比如对于下面三个网页：

创建的索引如下：

当查找 dog in Title 时 ，首先查找 dog 索引项，检查索引命中，然后扫描 titleStart 和 titleEnd ，看 dog 是否在 Title 中。

最后第二页命中，而第三页虽然有 dog 但是没有在 Title 里。

搜索引擎排序之 PageRank

核心思想：权威网页通过超链接向其他网页传输权重

超链接：被链接越多的网页拥有更高的权重

权重：高权重网页拥有更高的排名，通过超链接自动计算网页权重

随机访问者：解决超链接计算权重会成环的问题

公钥加密

作者通过颜色混合来比喻通俗易懂：

  1. 双方要加密，但是要在公开场合传输密钥
  2. 假设 A 与 B 通信，A 创建一个私钥是红色 ，B 创建一个私钥是蓝色
  3. 约定一个公钥为黄色，公钥是暴露出去的，任何人都知道
  4. A 将红色和黄色混合发送给 B ，B 将蓝色和黄色混合发送给 A
  5. A 将 B 发送过来的颜色与自己的私钥混合组成加密密钥：红 + 黄 + 蓝
  6. B 将 A 发送过来的颜色与自己的私钥混合组成解密密钥：蓝 + 黄 + 红
  7. A 与 B 的密钥相同，就能够通过这个密钥通信

应用中的公钥加密原理和上面相同，只是用了数学的知识，而不是颜色的混合

纠错码

  • 使用重复传输纠正传输中的错误，如果错误率是 10% ，我们传输 100 次，收到 90 次相同的数据一定是正确的
  • 在传输中使用冗余，比如 5 用 five 传输，如果收到的是 fve, 我们就能够知道原数据是 five
  • 使用校验和判断数据是否出错，不同的校验和算法能保证出错数据的个数
  • 使用二维奇偶校验码能够定位出错的数据

图形识别

  • 最近邻分类：通过计算未知对象与已知对象的距离进行分类，距离最近的分为一类。这个算法不需要提前训练。
  • 决策树：决策树类似与通过问问题得到答案。需要通过训练得到一个决策树。
  • 神经网络

数据压缩

无损压缩：

  • 同前算法：比如 FGFGFGFG 这个数据可以压缩为 FG-b2c6 ，解压缩时 b2 表示向后退两个字符，=c6= 表示抄写 6 个字符
  • 更短符号：霍夫曼编码，用更短的符号表示出现频率更多的字符

有损压缩：

  • 抛弃数据

数据库

保证数据库一致性的方法：

  1. 预写日志记录：日志记录的每一项都必须幂等，方便恢复
  2. 两阶段提交

数字签名

有些程序不可能存在