<改变未来的九大算法>读书笔记一

                                                             算法原理        

                                                             数据压缩

    1.无损压缩：替换，短信息替代长信息，如USA替代United States Of America.

     两种方式：1.同前把戏，对于重复出现的字段，在后面出现的位置用同前面的xx表示。2.更短符号把戏，把出现的频繁的字段用短的符号来表示，虽然为了能够识别，其他一些只能设计得更长，但由于出现频率分布的极端不平衡，也能极大地实现压缩。

     解压缩时，只需根据符号替换表和压缩之后的文件就可以还原。

     2.有损压缩：牺牲精度来压缩

     抛弃把戏：图片：每两行或每两列像素就抛弃一行或一列。解压时，被抛弃的部分有计算机推测补上，最简单的措施是从相邻的像素任取一补上。而jpeg是分块，按块压缩，若某一块内的像素相同，则该块可以统一表示。音频文件和音乐文件同样奉行抛弃对成品影响很小的信息。它除了分块压缩外还可以抛弃那些对人影响小的或没影响的声音。

 

 

                                                                纠错码

    重复把戏：多次重复，每个位置上出现次数最多的最可能是真实值。即用多次重复消除偶然误差。

    校检和把戏：信息尾部添上校检和，供接受方校检信息是否出错。实际使用的是加密哈希函数校检和

    简单校验和：把各项相加所得之和取个位数作为校检和添加在末尾，只能检验单项出错

    阶梯校检和：把每项乘上不同不同权值之后再相加，即使有项一加一减因为权值不同也不会抵消偏差。 

    冗余把戏 ：把信息替换成更长的冗余值，冗长信息即使出现错误，也更容易根据对应模式匹配出原信息，如用five表示5，即使变成fife或fivg也可以知道要传递的是5.实际使用的是（7，4）汉明代码。

    定位把戏：把信息排成矩阵，通过计算各行各列校检和，然后可以通过校检和知道错误在那行和那列，两个一结合便可完成定位，甚至可以根据校检和纠错。

 

 

                                                                  公钥加密

     依赖单向加密，就像颜料一样，可以混合但之后不能再分开。基于计算复杂度上的难题。

     常用的是用对方公布的公钥把要发给对方的信息加密，发送给对方，只能用对方的私钥来解密。

     用颜料来形容就是：每人都有自己选定的私人颜色，在和公共的基准颜色混合形成自己的公开混合颜料，要交换信息的双方交换各自的公开混合颜色再和各自的私有颜色换个那么最后双方得到的是完全一样的，都有双方的私有颜色和基准颜色。但其他人得到那两份公开的混合颜色并没有用，因为无法还原。

 

 

                                                                  数字签名

       因为加密解密的唯一性，所以能用私钥解的一定是用对应的公钥加密的，所以当证明了其中一方自然另一方不证自明。而数字签名正是网上的签名认证。把钥匙交给受信任的第三方，用自己保存的锁来加密的信息相当于给该信息签上自己的名。其他人去受信任的第三方取得他的钥匙来解密该加密的信息能解的开的话证明是他加的密，就相当于是他签的名。

 

                                                                   搜索引擎

      遍历所有网页建立索引表，根据用户的输入根据算法按照语义分析切分得到用户所想表达的，再跟索引表匹配从而得到匹配的页面。

      词位置把戏：短语查询要求词必须连在一起，此时可以通过在索引表中分别找到他们的位置，通过比较他们的位置来确定，完成短语查询。

      短语查询中词离得更近相关度更大。

      元词把戏：同样出现查询的短语，在主题中出现的相关度更大。通过标签元素的位置可以知道词语在页面出现的位置。从而知道该词语在此页面的重要程度。

                   

 

                                                                 页面排名

      对于匹配到的页面把人们搜索时越想得到的排在越前面。基本的评价标准是以指向该页面的链接的数目。不同的链接权重值不同，链接的权重值取决于所在页面有多少链接指向它。

      权重把戏:所有的页面初始权值为1，任选一个一个页面开始沿链接出发，下一个页面有多少链接指向它就是它的权重值，该页面的所有链接指向的页面在计算权重值时，那个链接的权重值就是该页面的权重值。然后那个页面计算了所有指向它的链接的权值得到它的权重值后又通过它上面的链接带向下个页面。

     随机访问者模式：因为存在着回路，所以到达每个页面时采取随机选择一个链接继续访问，这样便不会因为循环而使页面权重值一直增加。

     权值把戏主要思想：和来自低权重值相比，一个来自高权重网页的链入链接应该更能证明一个页面的排名。而在随机访问者模式也包含了这一点：因为和一个来自不知名网页的链接相比，访问者更可能继续点击一个来自知名网页的链入链接。