所謂海量數(shù)據(jù)處理，是指基于海量數(shù)據(jù)的存儲、處理或操作。因?yàn)閿?shù)據(jù)量太大，導(dǎo)致要么無法在較短時(shí)間內(nèi)迅速解決，要么無法一次性裝入內(nèi)存。

事實(shí)上，對于時(shí)間問題，可以采用巧妙的算法搭配合適的數(shù)據(jù)結(jié)構(gòu)（如布隆過濾器、散列、位圖、堆、數(shù)據(jù)庫、倒排索引、Trie 樹）來解決；對于空間問題，可以采取分而治之的方法（如利用散列映射），把規(guī)模大的數(shù)據(jù)轉(zhuǎn)化為規(guī)模小的，最終各個(gè)擊破。

處理海量數(shù)據(jù)問題有很多種方法，本文介紹5種典型方法：散列分治、多層劃分、位圖、布隆過濾器、Trie樹。

散列分治

方法介紹

對于海量數(shù)據(jù)而言，由于無法將其一次性裝進(jìn)內(nèi)存進(jìn)行處理，不得不將其通過散列映射的方法分割成相應(yīng)的小塊數(shù)據(jù)，然后再針對各個(gè)小塊數(shù)據(jù)通過hash_map進(jìn)行統(tǒng)計(jì)或其他操作。

那么什么是散列映射呢？簡單來說，為了方便計(jì)算機(jī)在有限的內(nèi)存中處理大量數(shù)據(jù)，通過映射的方式讓數(shù)據(jù)均勻分布在對應(yīng)的內(nèi)存位置上（例如，大數(shù)據(jù)通過取余的方式映射成小數(shù)據(jù)存放在內(nèi)存中，或把大文件映射成多個(gè)小文件），而這種映射的方式通常通過散列函數(shù)進(jìn)行映射，好的散列函數(shù)能讓數(shù)據(jù)均勻分布而減少沖突。

問題實(shí)例

尋找Top IP

從海量日志數(shù)據(jù)中提取出某日訪問百度（www.baidu.com）次數(shù)最多的那個(gè)IP。

分析： 百度作為國內(nèi)第一大搜索引擎，每天訪問它的IP數(shù)量巨大，如果想一次性把所有IP數(shù)據(jù)裝進(jìn)內(nèi)存處理，內(nèi)存容量通常不夠，故針對數(shù)據(jù)量太大、內(nèi)存受限的情況，可以把大文件轉(zhuǎn)化成（取模映射）小文件，從而大而化小，逐個(gè)處理。簡言之，先映射，而后統(tǒng)計(jì)，最后排序。

解法： 具體分為下述三個(gè)步驟。

（1）分而治之/散列映射。先將該日訪問百度的所有IP從訪問日志中提取出來，然后逐個(gè)寫入一個(gè)大文件中，接著采取散列映射的方法（如hash(IP) % 1000），把整個(gè)大文件的數(shù)據(jù)映射到1000個(gè)小文件中2。

（2）hash_map統(tǒng)計(jì)。大文件轉(zhuǎn)化成了小文件，便可以采用hash_map(ip, value)分別對1000個(gè)小文件的IP進(jìn)行頻率統(tǒng)計(jì)，找出每個(gè)小文件中出現(xiàn)頻率最高的IP，總共1000個(gè)IP。

（3）堆/快速排序。統(tǒng)計(jì)出1000個(gè)頻率最高的IP后，依據(jù)它們各自頻率的大小進(jìn)行排序（可采取堆排序），找出最終那個(gè)出現(xiàn)頻率最高的IP，即為所求。

尋找熱門查詢

搜索引擎會通過日志文件把用戶每次檢索所使用的所有查詢串都記錄下來，每個(gè)查詢串的長度為1～255字節(jié)。假設(shè)目前有1000萬條查詢記錄（但是，因?yàn)檫@些查詢串的重復(fù)度比較高，所以雖然總數(shù)是 1000 萬，但如果除去重復(fù)后，查詢串query不超過300萬個(gè)），請統(tǒng)計(jì)其中最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1 GB。

分析： 一個(gè)查詢串的重復(fù)度越高說明查詢它的用戶越多，也就是越熱門。如果是1億個(gè)IP求Top 10，可先%1000將IP分到1000個(gè)小文件中去，并保證一個(gè)IP只出現(xiàn)在一個(gè)文件中，再對每個(gè)小文件中的IP進(jìn)行hash_map統(tǒng)計(jì)并按數(shù)量排序，最后用歸并或者最小堆依次處理每個(gè)小文件中的Top 10以得到最后的結(jié)果。

但是對于本題，是否也需要先把大文件弄成小文件呢？根據(jù)題目描述，雖然有1000萬個(gè)查詢，但是因?yàn)橹貜?fù)度比較高，去除重復(fù)后，事實(shí)上只有300萬個(gè)查詢，每個(gè)查詢?yōu)?55字節(jié)，所以可以考慮把它們?nèi)糠胚M(jìn)內(nèi)存中去（假設(shè)300萬個(gè)字符串沒有重復(fù)，都是最大長度，那么最多占用內(nèi)存3000000 × 255 = 765MB=0.765GB，所以可以將所有字符串都存放在內(nèi)存中進(jìn)行處理）。

考慮到本題中的數(shù)據(jù)規(guī)模比較小，能一次性裝入內(nèi)存，因而放棄分而治之/散列映射的步驟，直接用hash_map統(tǒng)計(jì)，然后排序。事實(shí)上，針對此類典型的Top k問題，采取的對策一般都是“分而治之/散列映射（如有必要）+ hash_map+堆”。

解法：

（1）hash_map統(tǒng)計(jì)。對這批海量數(shù)據(jù)進(jìn)行預(yù)處理，用hash_map完成頻率統(tǒng)計(jì)。具體做法是：維護(hù)一個(gè)鍵為query、value為該query出現(xiàn)次數(shù)的hash_map，即hash_map(query, value)，每次讀取一個(gè)query，如果該query不在hash_map中，那么將該query放入hash_map中，并將它的value值設(shè)為1；如果該query在hash_map中，那么將該query的計(jì)數(shù)value加1即可。最終我們用hash_map在O(n)的時(shí)間復(fù)雜度內(nèi)完成了所有query的頻率統(tǒng)計(jì)。

（2）堆排序。借助堆這種數(shù)據(jù)結(jié)構(gòu)，找出Top k，時(shí)間復(fù)雜度為O(n'logk)。也就是說，借助堆可以在對數(shù)級的時(shí)間內(nèi)查找或調(diào)整移動。因此，維護(hù)一個(gè)k（該題目中是10）大小的最小堆，然后遍歷300萬個(gè)query，分別和根元素進(jìn)行比較，最終的時(shí)間復(fù)雜度是O(n) + O(n'logk)，其中n為1000萬，n'為300萬。

關(guān)于上述過程中的第2步（堆排序），進(jìn)一步講，可以維護(hù)k個(gè)元素的最小堆，即用容量為k的最小堆存儲最先遍歷到的k個(gè)數(shù)，并假設(shè)它們就是最大的k個(gè)數(shù)，建堆費(fèi)時(shí)O(k)，有k1 > k2 >…> kmin（設(shè)kmin為最小堆中最小元素）。繼續(xù)遍歷整個(gè)數(shù)列剩下的n?k個(gè)元素，每次遍歷一個(gè)元素x，將其與堆頂元素進(jìn)行比較，若x > kmin則更新堆（x入堆，每次調(diào)整堆費(fèi)時(shí)O(log k)），否則不更新堆。這樣下來，總費(fèi)時(shí)O(k + (n?k)log k ) = O(nlogk)。此方法得益于在堆中查找等各項(xiàng)操作的時(shí)間復(fù)雜度均為O(log k)。

當(dāng)然，也可以采用Trie樹，結(jié)點(diǎn)里存該查詢串出現(xiàn)的次數(shù)，沒有出現(xiàn)則為0，最后用10個(gè)元素的最小堆來對出現(xiàn)頻率進(jìn)行排序。

尋找出現(xiàn)頻率最高的100個(gè)詞

有一個(gè)1 GB大小的文件，里面每一行是一個(gè)詞，每個(gè)詞的大小不超過16字節(jié)，內(nèi)存大小限制是1 MB。請返回出現(xiàn)頻率最高的100個(gè)詞。

解法：

（1）分而治之/散列映射。按先后順序讀取文件，對于每個(gè)詞x，執(zhí)行hash(x)%5000，然后將該值存到5000個(gè)小文件（記為x0, x1,…, x4999）中。此時(shí)，每個(gè)小文件的大小大概是200 KB。當(dāng)然，如果其中有的小文件超過了1 MB，則可以按照類似的方法繼續(xù)往下分，直到分解得到的所有小文件都不超過1MB。

（2）hash_map統(tǒng)計(jì)。對每個(gè)小文件采用hash_map/Trie樹等數(shù)據(jù)結(jié)構(gòu)，統(tǒng)計(jì)每個(gè)小文件中出現(xiàn)的詞及其相應(yīng)的出現(xiàn)次數(shù)。

（3）堆排序或者歸并排序。取出出現(xiàn)次數(shù)最多的100個(gè)詞（可以用含100個(gè)結(jié)點(diǎn)的最小堆）后，再把100個(gè)詞及相應(yīng)的出現(xiàn)次數(shù)存入文件中，這樣又得到5000個(gè)文件。最后對這5000個(gè)文件進(jìn)行歸并（可以用歸并排序）。

尋找Top 10

有海量數(shù)據(jù)分布在100臺電腦中，請想個(gè)辦法高效統(tǒng)計(jì)出這批數(shù)據(jù)出現(xiàn)次數(shù)最多的Top 10。

解法一： 如果同一個(gè)數(shù)據(jù)元素只出現(xiàn)在某一臺機(jī)器中，那么可以采取以下步驟統(tǒng)計(jì)出現(xiàn)次數(shù)為Top 10的數(shù)據(jù)元素。

（1）堆排序。在每臺電腦上求出Top 10，可以采用包含10個(gè)元素的堆完成。（求Top 10小用最大堆，求Top 10大用最小堆。比如，求Top 10大，首先取前10個(gè)元素調(diào)整成最小堆，假設(shè)這10個(gè)元素就是Top 10大，然后掃描后面的數(shù)據(jù)，并與堆頂元素進(jìn)行比較，如果比堆頂元素大，那么用該元素替換堆頂，然后再調(diào)整為最小堆，否則不調(diào)整。最后堆中的元素就是Top 10大。）

（2）組合歸并。求出每臺電腦上的Top 10后，把這100臺電腦上的Top 10組合起來，共1000個(gè)數(shù)據(jù)，再根據(jù)這1000個(gè)數(shù)據(jù)求出Top 10就可以了。

解法二： 但是，如果同一個(gè)元素重復(fù)出現(xiàn)在不同的電腦中呢？舉個(gè)例子，給定兩臺機(jī)器，第一臺機(jī)器的數(shù)據(jù)及各自出現(xiàn)的次數(shù)為a（53）、b（52）、c（49）、d（49）、e（0）、f（0）（括號里的數(shù)字代表某個(gè)數(shù)據(jù)出現(xiàn)的次數(shù)），第二臺機(jī)器的數(shù)據(jù)及各自出現(xiàn)的次數(shù)為a（0）、b（0）、c（49）、d（49）、e（51）、f（50），求所有數(shù)據(jù)中出現(xiàn)次數(shù)最多的Top 2。

很明顯，如果先求出第一臺機(jī)器的Top 2——a（53）和b（52），然后再求出第二臺機(jī)器的Top 2——e（51）和f（50），最后歸并a（53）、b（52）、e（51）和f（50），得出最終的Top 2——a（53）和b（52）并非實(shí)際的Top 2，因?yàn)閷?shí)際的Top 2是c（49 + 49）和d（49 + 49）。

有兩種方法可以解決這個(gè)問題。

• 遍歷一遍所有數(shù)據(jù)，重新散列取模，使同一個(gè)元素只出現(xiàn)在單獨(dú)的一臺電腦中，然后采取上面所說的方法，統(tǒng)計(jì)每臺電腦中各個(gè)元素的出現(xiàn)次數(shù)，找出Top 10，繼而組合100臺電腦上的Top 10，找出最終的Top 10。

• 蠻力求解，直接統(tǒng)計(jì)每臺電腦中各個(gè)元素的出現(xiàn)次數(shù)，然后把同一個(gè)元素在不同機(jī)器中的出現(xiàn)次數(shù)相加，最終從所有數(shù)據(jù)中找出Top 10。

查詢串的重新排列

有10個(gè)文件，每個(gè)文件的大小是1 GB，每個(gè)文件的每一行存放的都是用戶的查詢串query，每個(gè)文件的query都可能重復(fù)。請按照query的頻度排序。

解法一： 分為以下三個(gè)步驟。

（1）散列映射。順序讀取10個(gè)文件，按照hash(query)%10的結(jié)果將query寫入另外10個(gè)文件（記為a0, a1,…, a9）中。這樣，新生成的每個(gè)文件的大小約為1 GB（假設(shè)散列函數(shù)是隨機(jī)的）。

（2）hash_map統(tǒng)計(jì)。找一臺內(nèi)存在2 GB左右的機(jī)器，依次用hash_map(query, query_count)來統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)。注意，hash_map(query, query_count)是用來統(tǒng)計(jì)每個(gè) query 的出現(xiàn)次數(shù)的，而不是存儲它們的值，query 出現(xiàn)一次則query_count+1。

（3）堆排序、快速排序或者歸并排序。利用快速排序、堆排序或者歸并排序按照出現(xiàn)次數(shù)進(jìn)行排序，將排好序的query和對應(yīng)的query_cout輸出到文件中。這樣就得到了10個(gè)排好序的文件（記為b0, b1,…, b9）。最后，對這10個(gè)文件進(jìn)行歸并排序（內(nèi)排序與外排序相結(jié)合）。

解法二： 一般情況下，query的總量是有限的，只是重復(fù)的次數(shù)比較多而已，對于所有的query，可能一次性就可以加入內(nèi)存。這樣就可以采用Trie樹、hash_map等直接統(tǒng)計(jì)每個(gè)query出現(xiàn)的次數(shù)，然后按出現(xiàn)次數(shù)做快速排序、堆排序或者歸并排序就可以了。

解法三： 與解法一類似，但在做完散列，分成多個(gè)文件后，可以交給多個(gè)文件，采用分布式架構(gòu)來處理（如MapReduce），最后再進(jìn)行合并。

尋找共同的URL

給定a和b兩個(gè)文件，各存放50億個(gè)URL，每個(gè)URL占64字節(jié)，內(nèi)存限制是4 GB。請找出a和b文件中共同的URL。

解法： 可以估計(jì)出每個(gè)文件的大小為5000000000×64=320 GB，遠(yuǎn)遠(yuǎn)大于內(nèi)存限制的4 GB，所以不可能將其完全加載到內(nèi)存中處理。考慮采取分而治之的方法。

（1）分而治之/散列映射。遍歷文件a，對每個(gè)URL求取hash(URL)%1000，然后根據(jù)所取得的值將URL分別存儲到1000個(gè)小文件中（記為 a0, a1,…, a999）。這樣每個(gè)小文件大約為300 MB。遍歷文件b，采取和a相同的方式將URL分別存儲到1000小文件中（記為b0, b1,…, b999）。這樣處理后，所有可能相同的URL都在對應(yīng)的小文件中（a0對應(yīng)b0, a1對應(yīng)b1,…, a999對應(yīng)b999），不對應(yīng)的小文件不可能有相同的URL。然后只要求出1000對小文件中相同的URL即可。

（2）hash_set統(tǒng)計(jì)。求每對小文件中相同的URL時(shí)，可以把其中一個(gè)小文件的URL存儲到hash_set中，然后遍歷另一個(gè)小文件的每個(gè)URL，看其是否在剛才構(gòu)建的hash_set中，如果在，就是共同的URL，保存到文件里就可以了。

舉一反三

尋找最大的100個(gè)數(shù)

從100萬個(gè)數(shù)中找出最大的100個(gè)數(shù)。

提示：

選取前100個(gè)元素并排序，記為序列L。然后依次掃描剩余的元素x，與排好序的100個(gè)元素中最小的元素比較，如果比這個(gè)最小的元素大，就把這個(gè)最小的元素刪除，利用插入排序的思想將x插入到序列L中。依次循環(huán)，直到掃描完所有的元素。復(fù)雜度為O(108×100)。也可以利用快速排序的思想，每次分割之后只考慮比主元大的一部分，直到比主元大的一部分比100多的時(shí)候，采用傳統(tǒng)排序算法排序，取前100個(gè)。復(fù)雜度為O(108× 100)。此外，還可以用一個(gè)含100個(gè)元素的最小堆來完成，復(fù)雜度為O(108× log100)。

統(tǒng)計(jì)10個(gè)出現(xiàn)次數(shù)最多的詞

一個(gè)文本文件有上億行甚至10億行，每行中存放一個(gè)詞，要求統(tǒng)計(jì)出其中出現(xiàn)次數(shù)最多的前10個(gè)詞。

解法一： 如果文件比較大，無法一次性讀入內(nèi)存，可以采用散列取模的方法，將大文件分解為多個(gè)小文件，對單個(gè)小文件利用hash_map統(tǒng)計(jì)出每個(gè)小文件中10個(gè)出現(xiàn)次數(shù)最多的詞，然后再進(jìn)行歸并處理，找出最終的10個(gè)出現(xiàn)次數(shù)最多的詞。

解法二： 通過散列取模將大文件分解為多個(gè)小文件后，除了可以用hash_map統(tǒng)計(jì)出每個(gè)小文件中10個(gè)出現(xiàn)次數(shù)的詞，也可以用Trie樹統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，最終同樣找出出現(xiàn)次數(shù)最多的前10個(gè)詞（可用堆來實(shí)現(xiàn)）。

尋找出現(xiàn)次數(shù)最多的數(shù)

怎樣在海量數(shù)據(jù)中找出重復(fù)次數(shù)最多的一個(gè)？

提示：

先做散列，然后求模，映射為小文件，求出每個(gè)小文件中重復(fù)次數(shù)最多的一個(gè)數(shù)，并記錄重復(fù)次數(shù)，最后找出上一步求出的數(shù)據(jù)中重復(fù)次數(shù)最多的一個(gè)，即是所求。

統(tǒng)計(jì)出現(xiàn)次數(shù)最多的前n個(gè)數(shù)據(jù)

有上千萬或上億個(gè)數(shù)據(jù)（有重復(fù)），統(tǒng)計(jì)其中出現(xiàn)次數(shù)最多的前n個(gè)數(shù)據(jù)。

提示：

上千萬或上億個(gè)數(shù)據(jù)在現(xiàn)在的機(jī)器的內(nèi)存中應(yīng)該能存下，所以考慮采用hash_map、搜索二叉樹、紅黑樹等來進(jìn)行次數(shù)統(tǒng)計(jì)，然后取出前n個(gè)出現(xiàn)次數(shù)最多的數(shù)據(jù)，這一步可以用堆完成。

1000萬個(gè)字符串的去重

有1000萬個(gè)字符串，其中有些字符串是重復(fù)的，請把重復(fù)的字符串全部去掉，保留沒有重復(fù)的字符串。

提示：

本題用Trie樹比較合適，hash_map也行。當(dāng)然，也可以先散列成小文件分開處理再綜合。

多層劃分

方法介紹

多層劃分法本質(zhì)上還是遵循分而治之的思想。因?yàn)樵胤秶艽螅荒芾弥苯訉ぶ繁?，所以通過多次劃分，逐步確定范圍，然后在一個(gè)可以接受的范圍內(nèi)進(jìn)行查找。

問題實(shí)例

尋找不重復(fù)的數(shù)

在2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)的個(gè)數(shù)。注意，內(nèi)存空間不足以容納這2.5億個(gè)整數(shù)。

分析： 類似于鴿巢原理，因?yàn)檎麛?shù)個(gè)數(shù)為232，所以，可以將這232個(gè)數(shù)劃分為28個(gè)區(qū)域（比如，用一個(gè)文件代表一個(gè)區(qū)域），然后將數(shù)據(jù)分到不同的區(qū)域，最后不同的區(qū)域再利用位圖進(jìn)行統(tǒng)計(jì)就可以直接解決了。也就是說，只要有足夠的內(nèi)存空間，就可以很方便地解決。

尋找中位數(shù)

找出5億個(gè)int型數(shù)的中位數(shù)。

分析： 首先將這5億個(gè)int型數(shù)劃分為216個(gè)區(qū)域，然后讀取數(shù)據(jù)統(tǒng)計(jì)落到各個(gè)區(qū)域里的數(shù)的個(gè)數(shù)，根據(jù)統(tǒng)計(jì)結(jié)果就可以判斷中位數(shù)落到哪個(gè)區(qū)域，并知道這個(gè)區(qū)域中的第幾大數(shù)剛好是中位數(shù)。然后，第二次掃描只統(tǒng)計(jì)落在這個(gè)區(qū)域中的那些數(shù)就可以了。

實(shí)際上，如果不是int型而是int64型，經(jīng)過3次這樣的劃分即可降低到能夠接受的程度。也就是說，可以先將5億個(gè)int64型數(shù)劃分為224個(gè)區(qū)域，確定每個(gè)數(shù)是其所在區(qū)域的第幾大數(shù)，然后再將該區(qū)域分成220個(gè)子區(qū)域，確定是子區(qū)域的第幾大數(shù)，最后當(dāng)子區(qū)域里的數(shù)的個(gè)數(shù)只有220個(gè)時(shí)，就可以利用直接尋址表進(jìn)行統(tǒng)計(jì)。

6.4　MapReduce

方法介紹

MapReduce是一種計(jì)算模型，簡單地說就是將大批量的工作或數(shù)據(jù)分解執(zhí)行（稱之為Map），然后再將結(jié)果合并成最終結(jié)果（稱之為Reduce）。這樣做的好處是，可以在任務(wù)被分解后通過大量機(jī)器進(jìn)行分布式并行計(jì)算，減少整個(gè)操作的時(shí)間?？梢哉f，MapReduce的原理就是一個(gè)歸并排序，它的適用范圍為數(shù)據(jù)量大而數(shù)據(jù)種類少以致可以放入內(nèi)存的場景。MapReduce模式的主要思想是將要執(zhí)行的問題（如程序）自動拆分成Map和Reduce的方式，其流程如圖6-2所示。

在數(shù)據(jù)被分割后，通過Map函數(shù)將數(shù)據(jù)映射到不同的區(qū)塊，分配給計(jì)算機(jī)集群處理，以達(dá)到分布式計(jì)算的效果，再通過Reduce函數(shù)的程序?qū)⒔Y(jié)果匯總，從而輸出需要的結(jié)果。

MapReduce 借鑒了函數(shù)式程序設(shè)計(jì)語言的設(shè)計(jì)思想，其軟件實(shí)現(xiàn)是指定一個(gè)Map函數(shù)，把鍵值對映射成新的鍵值對，形成一系列中間結(jié)果構(gòu)成的鍵值對，然后把它們傳給 Reduce 函數(shù)，把具有相同中間形式的鍵值對合并在一起。Map 函數(shù)和Reduce函數(shù)具有一定的關(guān)聯(lián)性。

問題實(shí)例

尋找n2個(gè)數(shù)的中數(shù)

一共有n臺機(jī)器，每臺機(jī)器上有n個(gè)數(shù)，每臺機(jī)器最多存O(n)個(gè)數(shù)并對它們進(jìn)行操作。如何找到n2個(gè)數(shù)的中數(shù)（median）？

6.5　外排序

方法介紹

顧名思義，所謂外排序就是在內(nèi)存外面的排序。當(dāng)要處理的數(shù)據(jù)量很大而不能一次性裝入內(nèi)存時(shí)，只能將數(shù)據(jù)放在讀寫較慢的外存儲器（通常是硬盤）上。

外排序通常采用的是一種“排序-歸并”的策略。在排序階段，先讀入能放在內(nèi)存中的數(shù)據(jù)，將其排序后輸出到一個(gè)臨時(shí)文件，依次進(jìn)行，將待排序數(shù)據(jù)組織為多個(gè)有序的臨時(shí)文件，而后在歸并階段將這些臨時(shí)文件組合為一個(gè)大的有序文件，即為排序結(jié)果。

舉個(gè)例子。假定現(xiàn)在有一個(gè)含有20個(gè)數(shù)據(jù){5, 11, 0, 18, 4, 14, 9, 7, 6, 8, 12, 17, 16, 13, 19, 10, 2, 1, 3, 15}的文件A，但使用的是一次只能裝4個(gè)數(shù)據(jù)的內(nèi)存，所以可以每趟對4個(gè)數(shù)據(jù)進(jìn)行排序，即5路歸并，具體方法如下述步驟所示。

首先把“大”文件A分割為a1、a2、a3、a4、a5這5個(gè)小文件，每個(gè)小文件包含4個(gè)數(shù)據(jù)：

• a1文件的內(nèi)容為{5, 11, 0, 18}；

• a2文件的內(nèi)容為{4, 14, 9, 7}；

• a3文件的內(nèi)容為{6, 8, 12, 17}；

• a4文件的內(nèi)容為{16, 13, 19, 10}；

• a5文件的內(nèi)容為{2, 1, 3, 15}。

然后依次對5個(gè)小文件進(jìn)行排序：

• a1文件完成排序后的內(nèi)容為{0, 5, 11, 18}；

• a2文件完成排序后的內(nèi)容為{4, 7, 9, 14}；

• a3文件完成排序后的內(nèi)容為{6, 8, 12, 17}；

• a4文件完成排序后的內(nèi)容為{10, 13, 16, 19}；

• a5文件完成排序后的內(nèi)容為{1, 2, 3, 15}。

最終進(jìn)行多路歸并，完成整個(gè)排序。最后，整個(gè)大文件A文件完成排序后變?yōu)閧0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19}。

問題實(shí)例

給107個(gè)數(shù)據(jù)的磁盤文件排序

給定一個(gè)文件，里面最多含有n個(gè)不重復(fù)的正整數(shù)（也就是說可能含有少于n個(gè)不重復(fù)的正整數(shù)），且其中每個(gè)數(shù)都小于等于n（n = 107）。請輸出一個(gè)按從小到大升序排列的包含所有輸入整數(shù)的列表。假設(shè)最多有大約1 MB的內(nèi)存空間可用，但磁盤空間足夠。要求運(yùn)行時(shí)間在5分鐘以內(nèi)，10秒為最佳結(jié)果。

解法一：位圖方案

你可能會想到把磁盤文件進(jìn)行歸并排序，但題目假設(shè)只有1 MB的內(nèi)存空間可用，所以歸并排序這種方法不行。

熟悉位圖的人可能會想到用位圖來表示這個(gè)文件集合3。比如，用一個(gè)20位長的字符串來表示一個(gè)所有元素都小于20的簡單的非負(fù)整數(shù)集合，如集合{1, 2, 3, 5, 8, 13}，在字符串中將集合中各個(gè)數(shù)對應(yīng)的位置置為1，沒有對應(yīng)的數(shù)的位置置為0，用字符串表示為01110100100001000000。

針對本題的107個(gè)數(shù)據(jù)的磁盤文件排序問題，可以這么考慮：由于每個(gè)7位十進(jìn)制整數(shù)表示一個(gè)小于1000萬的整數(shù)，所以可以使用一個(gè)具有1000萬個(gè)位的字符串來表示這個(gè)文件，當(dāng)且僅當(dāng)整數(shù)i在文件中存在時(shí)，字符串中的第i位置為1。

采取這個(gè)位圖的方案是因?yàn)榭紤]到本問題的特殊性：

• 輸入數(shù)據(jù)限制在相對較小的范圍內(nèi)；

• 數(shù)據(jù)沒有重復(fù)；

• 其中的每條記錄都是單一的整數(shù)，沒有任何其他與之關(guān)聯(lián)的數(shù)據(jù)。

所以，此問題用位圖的方案可以分為以下三步進(jìn)行解決。

（1）將所有的位都初始化為0。

（2）通過讀入文件中的每個(gè)整數(shù)來建立集合，將每個(gè)整數(shù)對應(yīng)的位都置為1。

（3）檢驗(yàn)每一位，如果該位為1，就輸出對應(yīng)的整數(shù)。

經(jīng)過以上三步后，就產(chǎn)生了一個(gè)有序的輸出文件。令n為位圖向量中的位數(shù)（本例中為10 000 000），偽代碼表示如下：

// 磁盤文件排序位圖方案的偽代碼 // 第一步：將所有的位都初始化為0  for i ={0,....n}　　  
　　 bit[i]=0;  
// 第二步：通過讀入文件中的每個(gè)整數(shù)來建立集合，將每個(gè)整數(shù)對應(yīng)的位都置為1for each i in the input file　　 
　　 bit[i]=1;  
// 第三步：檢驗(yàn)每一位，如果該位為1，就輸出對應(yīng)的整數(shù)  for i={0...n}　　  
　　 if bit[i]==1　　　　
　　　　 write i on the output file

上述的位圖方案共需要掃描輸入數(shù)據(jù)兩次，具體執(zhí)行步驟如下。

（1）第一次只處理1～5 000 000的數(shù)據(jù)，這些數(shù)都是小于5 000 000的。對這些數(shù)進(jìn)行位圖排序，只需要約5 000 000/8=625 000字節(jié)，即0.625 MB，排序后輸出。

（2）第二次掃描輸入文件時(shí)，只處理5 000 001～10 000 000的數(shù)據(jù)，也只需要0.625 MB（可以使用第一次處理申請的內(nèi)存）。因此，這種位圖的方法總共只需要0.625 MB。

但是，很快我們就意識到，用位圖方案的話，需要約1.2 MB（若每條記錄是8位的正整數(shù)，則空間消耗約等于107/(102410248)≈ 192 MB）的空間，而現(xiàn)在只有1 MB的可用存儲空間，所以嚴(yán)格來說，用位圖方法還是不行4。那么究竟該如何處理呢？

解法二：多路歸并

誠然，在面對本題時(shí)，通過計(jì)算分析出可以用上述解法一這樣的位圖法解決。但實(shí)際上，很多時(shí)候我們都面臨著這樣一個(gè)問題：文件太大，無法一次性放入內(nèi)存中計(jì)算處理。這時(shí)候應(yīng)該怎么辦呢？分而治之，大而化小，也就是把整個(gè)大文件分為若干大小的幾塊，然后分別對每一塊進(jìn)行排序，最后完成整個(gè)過程的排序。k趟算法可以在O(kn)的時(shí)間開銷內(nèi)和O(n/k)的空間開銷內(nèi)完成對最多n個(gè)小于n的無重復(fù)正整數(shù)的排序。比如，可分為2塊（k=2時(shí)，一趟反正占用的內(nèi)存只有1.25/2 MB），即1～5 000 000和5 000 001～10 000 000。先遍歷一趟，排序處理1～5 000 000的整數(shù)（用5 000 000/8=625 000字節(jié)的存儲空間來排序1～5 000 000的整數(shù)），然后再第二趟，對5 000 001～1 000 000的整數(shù)進(jìn)行排序處理。

解法總結(jié)

本節(jié)中位圖和多路歸并兩種方案的時(shí)間復(fù)雜度及空間復(fù)雜度的比較如表6-1所示。

表6-1

多路歸并的時(shí)間復(fù)雜度為O(k × n/k × log n/k) = O(nlogn)5。但嚴(yán)格來說，還要加上讀寫磁盤的時(shí)間，而此算法的絕大部分時(shí)間也正是浪費(fèi)在讀寫磁盤的步驟上。

位圖

方法介紹

什么是位圖

所謂位圖，就是用一個(gè)位（bit）來標(biāo)記某個(gè)元素對應(yīng)的值，而鍵就是該元素。由于采用了位為單位來存儲數(shù)據(jù)，因此可以大大節(jié)省存儲空間。

位圖通過使用位數(shù)組來表示某些元素是否存在，可進(jìn)行數(shù)據(jù)的快速查找、判重、刪除。

來看一個(gè)具體的例子。假設(shè)我們要對0～7中的5個(gè)元素（4, 7, 2, 5, 3）進(jìn)行排序（假設(shè)這些元素沒有重復(fù)），此時(shí)就可以采用位圖的方法來達(dá)到排序的目的。因?yàn)橐硎?個(gè)數(shù)，所以只需要8位，由于8位等于1字節(jié)，所以開辟1字節(jié)的空間，并將這個(gè)空間的所有位都置為0，如圖6-3所示。

然后遍歷這5個(gè)元素。因?yàn)榇判蛐蛄械牡谝粋€(gè)元素是4，所以把4對應(yīng)的位重置為1（可以這樣操作：p + (i/8) | (001 << (i % 8)) 。當(dāng)然，這里的操作涉及big-endian和little-endian6的情況，這里默認(rèn)為big-endian），又由于是從0開始計(jì)數(shù)的，所以把第5位重置為1，如圖6-4所示。

然后再處理待排序序列的第二個(gè)元素7，將第8個(gè)位重置為1。接著再處理待排序序列的第三個(gè)元素2，一直到處理完所有的元素。將相應(yīng)的位置為1后，這時(shí)候內(nèi)存的位的狀態(tài)如圖6-5所示。

現(xiàn)在遍歷一遍這個(gè)位區(qū)域，將某位是1的位的編號（2, 3, 4, 5, 7）輸出，這樣就達(dá)到了排序的目的。

問題實(shí)例

電話號碼的統(tǒng)計(jì)

已知某個(gè)文件內(nèi)包含一些電話號碼，每個(gè)號碼為8位數(shù)字，統(tǒng)計(jì)不同號碼的個(gè)數(shù)。8位數(shù)字最多組成99 999 999個(gè)號碼，大概需要99兆位，大概十幾兆字節(jié)的內(nèi)存即可。

2.5億個(gè)整數(shù)的去重

在2.5億個(gè)整數(shù)中找出不重復(fù)的整數(shù)。注意，內(nèi)存不足以容納這2.5億個(gè)整數(shù)。

分析： 采用2位圖（每個(gè)數(shù)分配2位，00表示不存在，01表示出現(xiàn)一次，10表示出現(xiàn)多次，11無意義），共需內(nèi)存232 × 2=1 GB內(nèi)存，可以接受。然后掃描這2.5億個(gè)整數(shù)，查看位圖中相對應(yīng)的位，如果是00就變?yōu)?1，如果是01就變?yōu)?0，如果是10就保持不變。掃描完之后，查看位圖，把對應(yīng)位是01的整數(shù)輸出即可。也可以先劃分成小文件，然后在小文件中找出不重復(fù)的整數(shù)，并排序，最后歸并，歸并的同時(shí)去除重復(fù)的數(shù)。

整數(shù)的快速查詢

給定40億個(gè)不重復(fù)的沒排過序的unsigned int型整數(shù)，然后再給定一個(gè)數(shù)，如何快速判斷這個(gè)數(shù)是否在這40億個(gè)整數(shù)當(dāng)中？

分析： 可以用位圖的方法，申請512 MB的內(nèi)存，一個(gè)位代表一個(gè)unsigned int型的值。讀入40億個(gè)數(shù)，設(shè)置相應(yīng)的位，讀入要查詢的數(shù)，查看相應(yīng)位是否為1，如果為1表示存在，如果為0表示不存在。

布隆過濾器

方法介紹

我們經(jīng)常會遇到這樣的問題：判斷一個(gè)元素是否在一個(gè)集合中。常見的做法是用散列表實(shí)現(xiàn)集合，然后遇到一個(gè)新的元素時(shí)，在散列表中查找：如果能找到則意味著存在于集合中，反之不存在。但是散列表有一個(gè)弊端，它耗費(fèi)的空間太大。本節(jié)來看一種新的方法，即布隆過濾器（Bloom filter）。

布隆過濾器是一種空間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它可以看成是對位圖的擴(kuò)展。其結(jié)構(gòu)是長度為n（如何計(jì)算最優(yōu)n，后面會給出）的位數(shù)組，初始化為全0。當(dāng)一個(gè)元素被加入集合中時(shí)，通過k個(gè)散列函數(shù)將這個(gè)元素映射成一個(gè)位數(shù)組中的k個(gè)點(diǎn)，并將這k個(gè)點(diǎn)全部置為1。

在檢索一個(gè)元素是否在一個(gè)集合中時(shí)，我們只要看看這個(gè)元素被映射成位陣列的k個(gè)點(diǎn)是不是都是1，就能大致判斷出集合中有沒有那個(gè)元素：如果這k個(gè)點(diǎn)中有任何一個(gè)點(diǎn)為0，則被檢索元素在集合中一定不存在；如果這k個(gè)點(diǎn)都是1，則被檢索元素很可能在集合中。

但是，布隆過濾器也有它的缺點(diǎn)或不足，即它有一定的誤判率——在判斷一個(gè)元素是否屬于某個(gè)集合時(shí)，有可能會把不屬于這個(gè)集合的元素誤判為屬于這個(gè)集合。因此，它不適合那些“零誤判”的應(yīng)用場合。而在能容忍低誤判率的應(yīng)用場合下，布隆過濾器通過極少的誤判換取了存儲空間的極大節(jié)省。

集合表示和元素查詢

下面我們來具體看看布隆過濾器是如何用位數(shù)組表示集合的。如圖6-6所示，初始狀態(tài)時(shí)，布隆過濾器是一個(gè)包含m位的位數(shù)組，每一位都置為0。

對于S={x1, x2,…, xn}這樣一個(gè)n個(gè)元素的集合，布隆過濾器使用k個(gè)互相獨(dú)立的散列函數(shù)分別將集合S={x1, x2,…, xn}中的每個(gè)元素映射到{1,…, m}的范圍中。對于任意一個(gè)元素x，第i個(gè)散列函數(shù)映射的位置hi(x)就會被置為1（1≤i≤k）。

注意，如果一個(gè)位置多次被置為1，那么只有第一次會起作用，后面幾次將沒有任何效果。在圖6-7中，k=3且有兩個(gè)散列函數(shù)選中同一個(gè)位置（從左邊數(shù)第五位，即第二個(gè)1處）。

于此，在判斷y是否屬于圖6-6所示的集合S={x1, x2, …, xn}時(shí)，對y應(yīng)用k次散列函數(shù)，如果所有hi(y)的位置都是1（1≤i≤k），那么就認(rèn)為y是集合S={x1, x2, …, xn}中的元素，否則就認(rèn)為y不是集合中的元素。

例如，圖6-8中的y1可以確定不是集合S={x1, x2, …, xn}中的元素，因?yàn)閥1有兩處指向了0位，而y2可能屬于這個(gè)集合，也可能剛好是一個(gè)誤判。

誤判率估計(jì)

前面已經(jīng)提到，布隆過濾器在判斷一個(gè)元素是否屬于它表示的集合時(shí)會有一定的誤判率（false positive rate），下面就來估計(jì)一下這個(gè)誤判率的大小。

為了簡化模型，假設(shè)kn < m且各個(gè)散列函數(shù)是完全隨機(jī)的。每插入一個(gè)新元素第一個(gè)散列函數(shù)就會把過濾器中的某個(gè)位置為1，因此任意一個(gè)位被置成1的概率為1/m，反之，它沒被置為1（依然是0）的概率為1?1/m。如果這個(gè)元素的k個(gè)散列函數(shù)都沒有把某個(gè)位置為1，即在做完k次散列后，某個(gè)位還是0（意味著k次散列都沒有選中它）的概率就是(1?1/m)k。如果插入第二個(gè)元素，某個(gè)位依然沒有被置為1的概率為(1?1/m)2k，所以如果插入n個(gè)元素都還沒有把某個(gè)位置為1的概率為(1?1/m)kn。

也就是說，當(dāng)集合S = {x1, x2, …, xn}中的所有元素都被k個(gè)散列函數(shù)映射到m位的位數(shù)組中時(shí)，這個(gè)位數(shù)組中某一位還是0的概率是

為了簡化運(yùn)算，可以令

，則有

如果令

為位數(shù)組中0的比例，則

的數(shù)學(xué)期望

。

在

已知的情況下，誤判率為

為位數(shù)組中1的比例，

表示k次散列都剛好選中1的區(qū)域，即誤判率。上式中的第二步近似在前面已經(jīng)提到了，現(xiàn)在來看第一步近似。p'只是

的數(shù)學(xué)期望，在實(shí)際中

的值有可能偏離它的數(shù)學(xué)期望值。M. Mitzenmacher已經(jīng)證明，位數(shù)組中0的比例非常集中地分布在它的數(shù)學(xué)期望值的附近。因此，第一步近似得以成立。分別將p和p'代入上式中，得

與p'和f ' 相比，使用p 和f 通常在分析中更為方便。

最優(yōu)的散列函數(shù)個(gè)數(shù)

既然布隆過濾器要靠多個(gè)散列函數(shù)將集合映射到位數(shù)組中，那么應(yīng)該選擇幾個(gè)散列函數(shù)才能使元素查詢時(shí)的誤判率降到最低呢？這里有兩個(gè)互斥的理由：如果散列函數(shù)的個(gè)數(shù)多，那么在對一個(gè)不屬于集合的元素進(jìn)行查詢時(shí)得到0的概率就大；但是，如果散列函數(shù)的個(gè)數(shù)少，那么位數(shù)組中的0就多。為了得到最優(yōu)的散列函數(shù)個(gè)數(shù)，我們需要根據(jù)上一節(jié)中的誤判率公式進(jìn)行計(jì)算。

先用p 和f 進(jìn)行計(jì)算。注意到f = exp(k ln(1?ekn/m))，我們令g = k ln(1?ekn/m)，只要讓g取到最小，f 自然也取到最小。由于p = e?kn/m，可以將g寫成

根據(jù)對稱性法則可以很容易看出：當(dāng)p = 1/2，也就是k = (m/n)ln2≈0.693m/n時(shí)，g取得最小值。在這種情況下，最小誤判率f等于(1/2)k≈(0.6185)m/n。另外，注意到p是位數(shù)組中某一位仍是0的概率，所以p = 1/2對應(yīng)著位數(shù)組中0和1各一半。換句話說，要想保持誤判率低，最好讓位數(shù)組有一半還空著。

需要強(qiáng)調(diào)的一點(diǎn)是，p = 1/2時(shí)誤判率最小這個(gè)結(jié)果并不依賴于近似值p和f。同樣，對于f' = exp(k ln(1?(1?1/m)kn))，g' = k ln(1?(1?1/m)kn)，p' = (1?1/m)kn，可以將g'寫成

同樣，根據(jù)對稱性法則可以得到當(dāng)p' = 1/2時(shí)，g'取得最小值。

位數(shù)組的大小

下面來看看在不超過一定誤判率的情況下，布隆過濾器至少需要多少位才能表示全集中任意n個(gè)元素的集合。假設(shè)全集中共有u個(gè)元素，允許的最大誤判率為?，下面來求位數(shù)組的位數(shù)m。

假設(shè)X為全集中任取n個(gè)元素的集合，F(xiàn)(X)是表示X的位數(shù)組。那么，對于集合X中任意一個(gè)元素x，在s = F(X)中查詢x都能得到肯定的結(jié)果，即s能夠接受x。顯然，由于布隆過濾器引入了誤判，s能夠接受的不僅僅是X中的元素，它還能夠接受?(u?n)個(gè)誤判。因此，對于一個(gè)確定的位數(shù)組來說，它能夠接受總共n +? (u?n)個(gè)元素。在n +? (u?n)個(gè)元素中，s真正表示的只有其中n個(gè)，所以一個(gè)確定的位數(shù)組可以表示

個(gè)集合。m位的位數(shù)組共有2m個(gè)不同的組合，進(jìn)而可以推出，m位的位數(shù)組可以表示

個(gè)集合。全集中n個(gè)元素的集合總共有

個(gè)，因此要讓m位的位數(shù)組能夠表示所有n個(gè)元素的集合，必須有

即

上式中的近似前提是n和?u相比很小，這也是實(shí)際情況中常常發(fā)生的。根據(jù)上式，我們得出結(jié)論：在誤判率不大于?的情況下，m至少要等于n log2(1/?)才能表示任意n個(gè)元素的集合。

上一節(jié)中我們曾算出當(dāng)k = m/n ln2時(shí)誤判率f最小，這時(shí)f = (1/2)k= (1/2)mln2 / n?，F(xiàn)在令f ≤?，可以推出

這個(gè)結(jié)果比前面算得的下界n log2(1/)大了log2≈1.44倍。這說明，在散列函數(shù)的個(gè)數(shù)取到最優(yōu)時(shí)，要讓誤判率不超過?，m至少需要取到最小值的1.44倍。

布隆過濾器可以用來實(shí)現(xiàn)數(shù)據(jù)字典，進(jìn)行數(shù)據(jù)的判重或者集合求交集。

問題實(shí)例

尋找通過URL

給定A和B兩個(gè)文件，各存放50億條URL，每條URL占用64字節(jié)，內(nèi)存限制是4 GB，請找出A和B兩個(gè)文件中共同的URL。

分析： 如果允許有一定的誤判率，可以使用布隆過濾器，4 GB內(nèi)存大概可以表示340億位。將其中一個(gè)文件中的URL使用布隆過濾器映射到這340億位，然后挨個(gè)讀取另外一個(gè)文件中的URL，檢查這兩個(gè)URL是否相同，如果是，那么該URL應(yīng)該是共同的URL。如果是3個(gè)乃至n個(gè)文件呢？讀者可以繼續(xù)獨(dú)立思考。

垃圾郵件過濾

用過電子郵箱的朋友都知道，經(jīng)常會收到各種垃圾郵件，可能是廣告，可能是病毒，所以郵件提供商每天都需要過濾數(shù)以幾十億計(jì)的垃圾郵件，請想一個(gè)辦法過濾這些垃圾郵件。

分析： 比較直觀的想法是把常見的垃圾郵件地址存到一個(gè)巨大的集合中，然后遇到某個(gè)新郵件就將它的地址和集合中的全部垃圾郵件地址一一進(jìn)行比較，如果有元素與之匹配，則判定新郵件為垃圾郵件。

雖然本節(jié)開始部分提到集合可以用散列表實(shí)現(xiàn)，但它太占空間。例如，存儲1億個(gè)電子郵件地址就需要1.6 GB內(nèi)存，存儲幾十億個(gè)電子郵件地址就需要上百GB的內(nèi)存，雖然現(xiàn)在有的機(jī)器內(nèi)存達(dá)到了上百GB，但終究是少數(shù)。

事實(shí)上，如果允許一定的誤判率的話，可以使用布隆過濾器。解決了存儲的問題后，可以利用貝葉斯分類鑒別一份郵件是否為垃圾郵件，減少誤判率。

Trie樹

方法介紹

什么是Trie樹

Trie樹，即字典樹，又稱單詞查找樹或鍵樹，是一種樹形結(jié)構(gòu)，常用于統(tǒng)計(jì)和排序大量字符串等場景中（但不僅限于字符串），且經(jīng)常被搜索引擎用于文本詞頻統(tǒng)計(jì)。它的優(yōu)點(diǎn)是最大限度地減少無謂的字符串比較，查詢效率比較高。

Trie樹的核心思想是以空間換時(shí)間，利用字符串的公共前綴來降低查詢時(shí)間的開銷，以達(dá)到提高效率的目的。

它有以下三個(gè)基本性質(zhì)。

（1）根結(jié)點(diǎn)不包含字符，除根結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都只包含一個(gè)字符。

（2）從根結(jié)點(diǎn)到某一結(jié)點(diǎn)的路徑上經(jīng)過的字符連接起來，即為該結(jié)點(diǎn)對應(yīng)的字符串。

（3）每個(gè)結(jié)點(diǎn)的所有子結(jié)點(diǎn)包含的字符都不相同。

Trie樹的構(gòu)建

先來看一個(gè)問題：假如現(xiàn)在給定10萬個(gè)長度不超過10個(gè)字母的單詞，對于每一個(gè)單詞，要判斷它出沒出現(xiàn)過，如果出現(xiàn)了，求第一次出現(xiàn)在第幾個(gè)位置。這個(gè)問題該怎么解決呢？

如果采取最笨拙的方法，對每一個(gè)單詞都去查找它前面的單詞中是否有它，那么這個(gè)算法的復(fù)雜度就是O(n2)。顯然對于10萬的范圍難以接受。

換個(gè)思路想：假設(shè)要查詢的單詞是abcd，那么在它前面的單詞中，以b，c，d，f之類開頭的顯然就不必考慮了，而只要找以a開頭的單詞中是否存在abcd就可以了。同樣，在以a開頭的單詞中，只要考慮以b作為第二個(gè)字母的，一次次縮小范圍和提高針對性，這樣一個(gè)樹的模型就漸漸清晰了。

因此，如果現(xiàn)在有b、abc、abd、bcd、abcd、efg和hii這6個(gè)單詞，可以構(gòu)建一棵圖6-9所示的Trie樹。

如圖6-9所示，從根結(jié)點(diǎn)遍歷到每一個(gè)結(jié)點(diǎn)的路徑就是一個(gè)單詞，如果某個(gè)結(jié)點(diǎn)被標(biāo)記為紅色（如圖中加黑點(diǎn)的節(jié)點(diǎn)），就表示這個(gè)單詞存在，否則不存在。那么，對于一個(gè)單詞，只要順著它從根結(jié)點(diǎn)走到對應(yīng)的結(jié)點(diǎn)，再看這個(gè)結(jié)點(diǎn)是否被標(biāo)記為紅色就可以知道它是否出現(xiàn)過了。把這個(gè)結(jié)點(diǎn)標(biāo)記為紅色，就相當(dāng)于插入了這個(gè)單詞。這樣一來，查詢和插入可以一起完成，所用時(shí)間僅僅為單詞長度（在這個(gè)例子中，便是10）。這就是一棵Trie樹。

我們可以看到，Trie樹每一層的結(jié)點(diǎn)數(shù)是26i級別的。所以，為了節(jié)省空間，還可以用動態(tài)鏈表，或者用數(shù)組來模擬動態(tài)，而空間的花費(fèi)不會超過單詞數(shù)乘以單詞長度。

查詢

Trie 樹是簡單且實(shí)用的數(shù)據(jù)結(jié)構(gòu)，通常用于實(shí)現(xiàn)字典查詢。我們做即時(shí)響應(yīng)用戶輸入的Ajax搜索框時(shí)，就是以Trie樹為基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)的。本質(zhì)上，Trie樹是一棵存儲多個(gè)字符串的樹。相鄰結(jié)點(diǎn)間的邊代表一個(gè)字符，這樣樹的每條分支代表一個(gè)子串，而樹的葉結(jié)點(diǎn)則代表完整的字符串。和普通樹不同的地方是，相同的字符串前綴共享同一條分支。

下面再舉一個(gè)例子。給出一組單詞inn、int、ate、age、adv、ant，可以得到圖6-10所示的Trie樹。

可以看出以下幾條。

• 每條邊對應(yīng)一個(gè)字母。

• 每個(gè)結(jié)點(diǎn)對應(yīng)一項(xiàng)前綴。葉結(jié)點(diǎn)對應(yīng)最長前綴，即單詞本身。

• 單詞inn與單詞int有共同的前綴'in'，所以它們共享左邊的一條分支（根結(jié)點(diǎn)→i→in）。同理，ate、age、adv和ant共享前綴'a'，所以它們共享從根結(jié)點(diǎn)到結(jié)點(diǎn)a的邊。

查詢操縱非常簡單。例如，要查找int，順著路徑i→ in→int就找到了。

搭建Trie的基本算法也很簡單，無非是逐一把每個(gè)單詞的每個(gè)字母插入Trie樹。插入前先看前綴是否存在：如果存在，就共享，否則創(chuàng)建對應(yīng)的結(jié)點(diǎn)和邊。例如，要插入單詞add，就有下面幾步。

（1）考察前綴'a'，發(fā)現(xiàn)邊a已經(jīng)存在。于是順著邊a走到結(jié)點(diǎn)a。

（2）考察剩下的字符串'dd'的前綴'd'，發(fā)現(xiàn)從結(jié)點(diǎn)a出發(fā)，已經(jīng)有邊d存在。于是順著邊d走到結(jié)點(diǎn)ad。

（3）考察最后一個(gè)字符'd'，這次從結(jié)點(diǎn)ad出發(fā)沒有邊d了，于是創(chuàng)建結(jié)點(diǎn)ad的子結(jié)點(diǎn)add，并把邊ad→add標(biāo)記為d。

問題實(shí)例

10個(gè)頻繁出現(xiàn)的詞

在一個(gè)文本文件中大約有1萬行，每行1個(gè)詞，要求統(tǒng)計(jì)出其中出現(xiàn)次數(shù)最頻繁的10個(gè)詞。

分析： 用Trie樹統(tǒng)計(jì)每個(gè)詞出現(xiàn)的次數(shù)，時(shí)間復(fù)雜度是O(nl)（l表示單詞的平均長度），最終找出出現(xiàn)最頻繁的前10個(gè)詞（可用堆來實(shí)現(xiàn)，時(shí)間復(fù)雜度是O(nlog10)。

尋找熱門查詢

搜索引擎會通過日志文件把用戶每次檢索使用的所有查詢串都記錄下來，每個(gè)查詢串的長度為1～255字節(jié)。假設(shè)目前有1000萬條記錄（因?yàn)椴樵兇闹貜?fù)度比較高，雖然總數(shù)是1000萬，但是如果去除重復(fù)，不超過300萬個(gè)）。請統(tǒng)計(jì)最熱門的10個(gè)查詢串，要求使用的內(nèi)存不能超過1 GB。（一個(gè)查詢串的重復(fù)度越高，說明查詢它的用戶越多，也就越熱門。）

分析： 可以利用Trie樹，觀察關(guān)鍵字在該查詢串出現(xiàn)的次數(shù)，若沒有出現(xiàn)則為0。最后用10個(gè)元素的最小堆來對出現(xiàn)頻率進(jìn)行排序。