7.1 访问：顺序 vs. 随机

错误做法：

    1）直接定义一个二位大数组，存储每一个二元组的出现次数（20万x20万），差不多需要160GB内存，不现实，如果用硬盘存，速度太慢

    2）矩阵压缩存储，利用二元组矩阵稀疏特点，但不利于统计。因为在统计完所有二元组之前，并不清楚每一行有多少非零元素，虽然可以预留空间，但一旦预留被填满又要动态调整前后几行非零元素，十分麻烦

    3）哈希表顺序扫描，仍然是存储问题

    4）利用堆建立“优先队列”，比如找最高频100万个二元组，建有100万个元素的空堆，然后扫描文本，然后根据统计动态更新。该方法只能统计出前100万个二元组的次数，而不是最高频的100万（虽然可能有重叠），因为根据上述过程，任何新二元组第一次出现时肯定是1，竞争不过已在优先队列中的二元组，即便该二元组之后出现巨多，也无法统计进去

Zipf's Law（齐普夫定律）：

    在自然语言中，如果原始文本占用空间为1TB，把二元组统计一遍，则大概需要耗费1/4~1/2TB，因为大部分二元组只出现一两次，还有1/4左右只出现小几次。即自然语言的语料库里一个单词出现的频率与它在频率表里的排名大致成反比。并且无论是单词词频，还是二元组、三元组的频率都符合这个统计规律

正确做法：

    1）随机抽样（1%数据，即1GB），然后统计该1GB中二元组的出现次数，保留频率最高的1000万个二元组作为候选。之后假定1TB中频率最高的100万个就在这1000万里，其他略过不统计

    2）利用齐普夫定律限定范围，近似估算。先统计每个词本身出现的词频，排序。由于词频分布符合Zipf's Law，若某单词只出现两次，那么与之相关的二元组肯定不会出现超过两次，因此任何含有低频词的二元组都不用考虑

    3）分治算法（略）

7.2 层次：容量 vs. 速度

衡量存储器的性能的三个指标：

    1）大量顺序访问（读/写）数据时的速率，这在通信上被称为传输的带宽

    2）访问一个存储单元的时间

    3）一次访问的准备时间

7.3 索引：地址 vs. 内容

    对顺序存储的数据实现随机访问常用的方法就是建立索引：

附录：

    第一种方法第一次遇到的话基本无法想到，第二种方法则非常精妙，本质上是用空间换时间，即将二进制数B以8位为一个单位：即B=B1B2B3...，由于8位二进制数只有256种可能，可以将每一种对应的1的个数存储起来：i[0]=0, i[1]=1, i[2]=1, i[3]=2, ... i[255]=8，这样相当于打表，如果查表的次数很多的话，O(1)的时间就很快。