1625-5 王子昂 总结《2017年6月6日》 【连续第248天总结】
A.计算理论第二章 数据压缩和错误纠正
B.
数据压缩分为有损和无损两种
有损常应用于多媒体之中 编码分为固定长度和不等长两种 固定长度编码可以用log2n的编码长度来编码n个不同的字符 在所有字符出现频率相同的情况下，固定长度的编码的空间效率是最高的 eg:ASCII 而由于在实际应用中，字符出现的频率总是不同的 因此可以进行优化，使得出现频率高的字符用短的编码，能够显著提升压缩率 eg:霍夫曼编码 如果有编码是其他编码的前缀，就有导致二义性 任何一个字符的编码都不是其他编码的前缀，叫做前缀编码 霍夫曼编码的原理是二叉树，因为每一个叶节点的路径都一定不是其他节点的路径的前缀 首先将所有字母按照频率进行排序，然后将最小的两个字母打包作为一个节点，放回后重复以上过程，就生成了一课霍夫曼树 游程压缩 将大量重复的数据，例如大片的黑色，缩减为特征+长度的形式 Ziv-Lempel压缩算法 基于文字和数据中的大量重复，用指针的方式（指示位置和长度）来代替，从而达到压缩的目的 有损压缩 人类对图像、声波中的某些频率成分不敏感的特性，允许损失一定的信息 预测编码 根据离散信号的关联性，利用前面一个或多个信号来预测下一个信号 例如黑色的附近一般也常常是黑色的 变换编码 对信号进行某种函数变换。例如将时域信号变换到频域信号。保留低频信号，去掉高频信号 基于模型的编码 首先分析图像建立模型，然后就可以只保留模型参数 分形编码 挖掘自然物体（天空、云雾、森林等），找到其中的相似性 用仿射变换进行描述，利用变幻的参数进行编码 奇偶校验 通过添加一个校验位来保证原数据的每行数据的0或1的个数都是偶数/奇数，这称为偶校验/奇校验。发生一个错误则可以发现错误并纠正，而同时两个错误则可以发现，但可能无法纠正；同时四个错误则可能无法发现。但由于发生多个错误的可能性较低，因此可以忽略。 RAID-独立冗余磁盘阵列 由于数据较大需要用到多个磁盘存储时，为了提升稳定性而设计出的技术 RAID有多个级别，分别使用了不同的纠错方式，具有不同的效果 基于奇偶校验的RAID5： 假设有8块硬盘，每个字节的8个比特依次存储在8块硬盘上，这样读取数据时可以同时进行，比较高效。 添加第九块硬盘存储奇偶校验位。这样当某一块硬盘损毁时，都可以由奇偶校验位反推出损毁的数据。 ISBN检测 ISBN分为两种，10位和13位。 对于10位的ISBN是9位数据，最后一位是纠错信息 第一位*10，第二位*9，... 和除以11 纠错数据=除数-余数 这样当任何一位出错时，都可以反应在它的和上。并且由于乘数的设定，无论错误是什么都不可能使累加和的变化正好是11的倍数，即余数一定会改变。从而得知出现了错误。 对于13位的ISBN 第一位*1，第二位*3，第三位*1，第四位*3，... 和除以10 其他相同 不过如果第一位和第三位颠倒次序，将会导致无法发现错误 这种纠错方法在很多地方使用，例如商品条码和身份证号 纠错编码 使用了一种称为汉明距离的距离计算公式 汉明距离指两个数据之间不同的位的数量可以通过编码的设计，来自行查错并纠错
C. 明日计划
CrackMe(16)
