7.1 訪問：順序 vs. 隨機(jī)

錯(cuò)誤做法：

????1）直接定義一個(gè)二位大數(shù)組，存儲每一個(gè)二元組的出現(xiàn)次數(shù)（20萬x20萬），差不多需要160GB內(nèi)存，不現(xiàn)實(shí)，如果用硬盤存，速度太慢

????2）矩陣壓縮存儲，利用二元組矩陣稀疏特點(diǎn)，但不利于統(tǒng)計(jì)。因?yàn)樵诮y(tǒng)計(jì)完所有二元組之前，并不清楚每一行有多少非零元素，雖然可以預(yù)留空間，但一旦預(yù)留被填滿又要?jiǎng)討B(tài)調(diào)整前后幾行非零元素，十分麻煩

????3）哈希表順序掃描，仍然是存儲問題

????4）利用堆建立“優(yōu)先隊(duì)列”，比如找最高頻100萬個(gè)二元組，建有100萬個(gè)元素的空堆，然后掃描文本，然后根據(jù)統(tǒng)計(jì)動(dòng)態(tài)更新。該方法只能統(tǒng)計(jì)出前100萬個(gè)二元組的次數(shù)，而不是最高頻的100萬（雖然可能有重疊），因?yàn)楦鶕?jù)上述過程，任何新二元組第一次出現(xiàn)時(shí)肯定是1，競爭不過已在優(yōu)先隊(duì)列中的二元組，即便該二元組之后出現(xiàn)巨多，也無法統(tǒng)計(jì)進(jìn)去

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

????在自然語言中，如果原始文本占用空間為1TB，把二元組統(tǒng)計(jì)一遍，則大概需要耗費(fèi)1/4~1/2TB，因?yàn)榇蟛糠侄M只出現(xiàn)一兩次，還有1/4左右只出現(xiàn)小幾次。即自然語言的語料庫里一個(gè)單詞出現(xiàn)的頻率與它在頻率表里的排名大致成反比。并且無論是單詞詞頻，還是二元組、三元組的頻率都符合這個(gè)統(tǒng)計(jì)規(guī)律

正確做法：

????1）隨機(jī)抽樣（1%數(shù)據(jù)，即1GB），然后統(tǒng)計(jì)該1GB中二元組的出現(xiàn)次數(shù)，保留頻率最高的1000萬個(gè)二元組作為候選。之后假定1TB中頻率最高的100萬個(gè)就在這1000萬里，其他略過不統(tǒng)計(jì)

????2）利用齊普夫定律限定范圍，近似估算。先統(tǒng)計(jì)每個(gè)詞本身出現(xiàn)的詞頻，排序。由于詞頻分布符合Zipf's Law，若某單詞只出現(xiàn)兩次，那么與之相關(guān)的二元組肯定不會(huì)出現(xiàn)超過兩次，因此任何含有低頻詞的二元組都不用考慮

????3）分治算法（略）

7.2 層次：容量 vs. 速度

衡量存儲器的性能的三個(gè)指標(biāo)：

????1）大量順序訪問（讀/寫）數(shù)據(jù)時(shí)的速率，這在通信上被稱為傳輸?shù)膸?br>

????2）訪問一個(gè)存儲單元的時(shí)間

????3）一次訪問的準(zhǔn)備時(shí)間

7.3 索引：地址 vs. 內(nèi)容

????對順序存儲的數(shù)據(jù)實(shí)現(xiàn)隨機(jī)訪問常用的方法就是建立索引：

附錄：

????第一種方法第一次遇到的話基本無法想到，第二種方法則非常精妙，本質(zhì)上是用空間換時(shí)間，即將二進(jìn)制數(shù)B以8位為一個(gè)單位：即B=B1B2B3...，由于8位二進(jìn)制數(shù)只有256種可能，可以將每一種對應(yīng)的1的個(gè)數(shù)存儲起來：i[0]=0, i[1]=1, i[2]=1, i[3]=2, ... i[255]=8，這樣相當(dāng)于打表，如果查表的次數(shù)很多的話，O(1)的時(shí)間就很快。