海量数据处理：算法
海量信息即大規(guī)模數(shù)據(jù)，隨著互聯(lián)網(wǎng)技術(shù)的發(fā)展，互聯(lián)網(wǎng)上的信息越來越多，如何從海量信息中提取有用信息成為當(dāng)前互聯(lián)網(wǎng)技術(shù)發(fā)展必須面對的問題。
在海量數(shù)據(jù)中提取信息，不同于常規(guī)量級數(shù)據(jù)中提取信息，在海量信息中提取有用數(shù)據(jù)，會存在以下幾個方面的問題：
（1）數(shù)據(jù)量過大，數(shù)據(jù)中什么情況都可能存在，如果信息數(shù)量只有20條，人工可以逐條進(jìn)行查找、比對，可是當(dāng)數(shù)據(jù)規(guī)模擴(kuò)展到上百條、數(shù)千條、數(shù)億條，甚至更多時，僅僅只通過手工已經(jīng)無法解決存在的問題，必須通過工具或者程序進(jìn)行處理。
（2）對海量數(shù)據(jù)信息處理，還需要有良好的軟硬件配置，合理使用工具，合理分配系統(tǒng)資源。通常情況下，如果需要處理的數(shù)據(jù)量非常大，超過了TB級，小型機(jī)、大型工作站是要考慮的，普通計算機(jī)如果有好的方法也可以考慮，如通過聯(lián)機(jī)做成工作集群。
（3）對海量信息處理時，要求很高的處理方法和技巧，如何進(jìn)行數(shù)據(jù)挖掘算法的設(shè)計以及如何進(jìn)行數(shù)據(jù)的存儲訪問等都是研究的難點。
針對海量數(shù)據(jù)的處理，可以使用的方法非常多，常見的方法有Hash法、Bit-map法、Bloom filter法、數(shù)據(jù)庫優(yōu)化法、倒排索引法、外排序法、Trie樹、堆、雙層桶法以及MapReduce法。
Hash法
Hash 一般被翻譯為哈希，也被稱為散列，它是一種映射關(guān)系，即給定一個數(shù)據(jù)元素，其關(guān)鍵字為key，按一個確定的哈希函數(shù)Hash計算出hash（key），把hash（key）作為關(guān)鍵字key對應(yīng)元素的存儲地址（或稱哈希地址），再進(jìn)行數(shù)據(jù)元素的插入和檢索操作。簡而言之，哈希函數(shù)就是一種將任意長度的消息壓縮到某一固定長度的消息摘要的函數(shù)。
哈希表是具有固定大小的數(shù)組，其中，表長（即數(shù)組的大小）應(yīng)該為質(zhì)數(shù)。哈希函數(shù)是用于關(guān)鍵字與存儲地址之間的一種映射關(guān)系，但是不能保證每個元素的關(guān)鍵字與函數(shù)值是一一對應(yīng)的，因為極有可能出現(xiàn)對應(yīng)于不同的元素，卻計算出了相同的函數(shù)值。沖突是指兩個關(guān)鍵字映射到同一個存儲地址的情況，即對不同的關(guān)鍵字可能得到同一散列地址，即key1！=key2，而 f(key1) = f(key2)
哈希函數(shù)的特點
哈希函數(shù)一般應(yīng)具備以下幾個方面的特點：
（1）運算應(yīng)該盡可能簡單
（2）函數(shù)的值域必須在散列表的范圍內(nèi)
（3）盡可能的減少沖突
哈希函數(shù)的構(gòu)建方法
哈希函數(shù)的構(gòu)建方法一般有以下幾種：
（1）直接尋址法
取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為散列地址。即h(key)=key或h(key)=a*key+b,其中a和b均為整型常數(shù)，這種散列函數(shù)叫做自身函數(shù)。例如，有一個人口數(shù)字統(tǒng)計表，人的年齡取值范圍為1~100歲，其中，年齡作為關(guān)鍵字，哈希函數(shù)取關(guān)鍵字自身，但這種方法效率比較低，時間復(fù)雜度O(1)，空間復(fù)雜度為O(n)，n為關(guān)鍵字的個數(shù)。
直接尋址法不會產(chǎn)生沖突，但由于它沒有壓縮映像，因此當(dāng)關(guān)鍵字集合很大時，使用這種Hash函數(shù)是不可能實現(xiàn)地址編碼的散列的。
（2）取模法
選擇一個合適的正整數(shù)p，令hash（Key） = key mod p。p如果選擇的是比較大的素數(shù)，則效果比較好，一般選取p為TableSize，即哈希表的長度。
（3）數(shù)字分析法
設(shè)關(guān)鍵字是d位的以r為基的數(shù)（如以10為基的十進(jìn)制數(shù)），且共有n個關(guān)鍵字。則關(guān)鍵字的每個位可能有r個不同的數(shù)符出現(xiàn)（即0,1,2，。。。，9），但這r個數(shù)符在各個位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，即每個數(shù)符出現(xiàn)的次數(shù)接近于n/r，而在另一些位上分布不均勻。因此可選取其中分布較均勻的，重新組成新的數(shù)，用其作為哈希地址。
這種方法簡單、直觀，但是需要預(yù)先知道每個關(guān)鍵字的情況，這就限制了它的使用范圍。
（4）折疊法
將關(guān)鍵字分成位數(shù)為t的幾個部分（最后一部分的位數(shù)可能小于t），然后把各部分按位對齊進(jìn)行相加，將所得的和舍棄進(jìn)位，留下t位作為哈希地址。當(dāng)關(guān)鍵字位數(shù)很多，而且關(guān)鍵字中每位上數(shù)字分布比較均勻時，采用折疊法比較合適。
（5）平方取中法
這是一種較常用的方法，將關(guān)鍵字進(jìn)行平方運算，然后從結(jié)果的中間取出若干位（位數(shù)與散列地址的位數(shù)相同），將其作為散列地址，具體取幾位由哈希表的表長決定。
（6）除留余數(shù)法
除留余數(shù)法是一種比較常用的哈希函數(shù)，它的主要原理是取關(guān)鍵字除以某個數(shù)p（p不大于哈希表的長度TableSize）的余數(shù)作為哈希地址，即Hash（key）=key%p
使用除留余數(shù)法時，選取合適的p值很重要，一般要求p<=TableSize，且接近TableSize，p一般選取質(zhì)數(shù)，也可以是不包含小于20質(zhì)因子的合數(shù)
（7）隨機(jī)數(shù)法
選擇一個隨機(jī)函數(shù)，然后用關(guān)鍵字key的隨機(jī)函數(shù)值作為哈希地址，即Hash（key）=random（key）
解決沖突的方法
解決沖突的主要途徑是當(dāng)一個關(guān)鍵字映射到哈希表中的某一個地址且該地址上已有關(guān)鍵字時，再為該關(guān)鍵字尋找新的存儲地址。
（1）開放地址法
基本思想是當(dāng)發(fā)生地址沖突時，在哈希表中再按照某種方法繼續(xù)探測其他的存儲地址，直到找到空閑的地址為止
Hi(key)=(H(key)+di)mod m(i = 1,2,...，k（k<=m-1）)其中H(key)為關(guān)鍵字key的直接哈希地址，m為哈希表的長度，di為每次再探測時的地址增量。
采用這種方法時，首先計算出關(guān)鍵字的直接哈希地址，即H（key），如果該直接哈希地址上已有其他的關(guān)鍵字，則繼續(xù)查看地址為[H(key)+di]的存儲地址，判斷其是否為空。如此反復(fù)直至找到空閑的存儲地址為止，然后將關(guān)鍵字key存放到該地址。
（2）鏈地址法
鏈地址法解決沖突的主要思想是：如果哈希表空間為[0,m-1]，則設(shè)置一個由m個指針組成的一維數(shù)組CH[m]，然后在尋找關(guān)鍵字哈希地址的過程中，所有哈希地址為i的數(shù)據(jù)元素都插入到頭指針為CH[i]的鏈表中。這種方法比較適合于沖突比較嚴(yán)重的情況下使用
（3）再散列法
當(dāng)發(fā)生沖突時，使用第二個、第三個哈希函數(shù)計算地址，直到無沖突時。但這種方法的缺點是計算時間會大幅增加。
（4）建立一個公共溢出區(qū)。
假設(shè)哈希函數(shù)的值域為[0,m-1]，則設(shè)向量HashTable[0,…,m-1]為基本表，另外設(shè)立存儲空間向量OverTable[0,…,v]用以存儲發(fā)生沖突的記錄。
Hash主要用來進(jìn)行“快速存取”，在O(1)時間復(fù)雜度里就可以查找到目標(biāo)元素，或者判斷其是否存在。Hash數(shù)據(jù)結(jié)構(gòu)里的數(shù)據(jù)對外是雜亂無序的，無法得知其具體存儲位置，也不知道各個存儲元素位置之間的相互關(guān)系，但是卻可以在常數(shù)時間里判斷元素位置及存在與否。
在海量數(shù)據(jù)處理中，使用hash方法一般可以快速存取、統(tǒng)計某些數(shù)據(jù)，將大量數(shù)據(jù)進(jìn)行分類。例如，提取某日訪問網(wǎng)站次數(shù)最多的IP地址等。
Bit-map法
Bit-map（位圖）法的基本原理是使用位數(shù)組來表示某些元素是否存在，如8位電話號碼中查重復(fù)號碼，它適用于海量數(shù)據(jù)的快速查找、判重、刪除等。
如，1101001011 表示的集合為{ 1,2,4,7,9,10 }
位圖排序的時間復(fù)雜度是O(n)的，比一般的排序都快，但它以空間換時間（需要一個N位別的串）的，而且有些限制，即數(shù)據(jù)狀態(tài)不是很多。例如，排序前集合大小最好已知，而且集合中元素的最大重復(fù)次數(shù)必須已知，最好是惆集數(shù)據(jù)（不然空間浪費很大）
位圖法適用于判斷數(shù)據(jù)是否重復(fù)，也使用位圖法判斷某個數(shù)據(jù)是否存在。（需要兩次遍歷數(shù)據(jù)）
Bloom filter法
遇到問題：程序中判斷一個元素是否在一個集合中
最直接解決方法是將集合中全部的元素都存儲在計算機(jī)中，每當(dāng)遇到一個新元素時，就將它和集合中的元素直接進(jìn)行比較即可。這種做法雖然能夠準(zhǔn)確無誤地完成任務(wù)，但是比較次數(shù)太多，效率比較低下。
Bloom filter正是解決這一問題的有效方法，它是一種空間效率和時間效率很高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，它用來檢測一個元素是否屬于一個集合。但是它犧牲了正確率，Bloom filter以犧牲正確率為前提，來換取空間效率與時間效率的提高。當(dāng)它判斷某元素不屬于這個集合時，該元素一定不屬于這個集合；當(dāng)它判斷某元素屬于這個集合時，該元素不一定屬于這個集合。具體而言，查詢結(jié)果由兩種可能，即“不屬于這個集合（絕對正確）”和”屬于這個集合（可能錯誤）“。所以，Bloom filter適合應(yīng)用在對于低錯誤率可以容忍的場合。
So，使用Bloom filter的難點是如何根據(jù)輸入元素個數(shù)n，來確定位數(shù)組m的大小以及hash函數(shù)。當(dāng)hash函數(shù)個數(shù) k=(ln2)*(m/n)時錯誤率最小，在錯誤率不大于E的情況下，m至少要等于n*lg(1/E)才能表示任意n個元素的集合。但m還應(yīng)該更大些，因為還要保證位數(shù)組里至少一半為0，則m應(yīng)該>=nlg(1/E)*lge,大概就是nlg(1/E)的1.44倍（lg表示以2為底的對數(shù)）。
例如，假設(shè)E為0.01，即錯誤率為0.01，則此時m應(yīng)該大約為n的13倍。這樣k大約是8個（注意，m與n的單位不同，m的單位是bit，而n則是以元素個數(shù)為單位）。通常單個元素的長度都是有很多bit的，所以使用bloom filter內(nèi)存上通常都是節(jié)省的。
Bloom filter的優(yōu)點是具有很好的空間效率和時間效率。它的插入和查詢時間都是常數(shù)，另外它不保存元素本身，具有良好的安全性。然而，這些優(yōu)點都是以犧牲正確率為代價的。當(dāng)插入的元素越多，錯判“元素屬于這個集合”的概率就越大。另外，Bloom filter只能插入元素，卻不能刪除元素，因為多個元素的哈希結(jié)果可能共用了Bloom filter結(jié)構(gòu)中的同一個位，如果刪除元素，就可能會影響多個元素的檢測。所以，Bloom filter可以用來實現(xiàn)數(shù)據(jù)字典、進(jìn)行數(shù)據(jù)的判重或者集合求交集。
CBF與SBF是BF的擴(kuò)展，Counting Bloom Filter（CBF）將位數(shù)組中的每一位擴(kuò)展為一個counter，從而支持了元素的刪除操作。Spectral Bloom Filter（SBF）將其余集合元素的出現(xiàn)次數(shù)關(guān)聯(lián)，SBF采用counter中的最小值來近似表示元素的出現(xiàn)頻率。
數(shù)據(jù)庫優(yōu)化法
互聯(lián)網(wǎng)上的數(shù)據(jù)一般都被存儲在數(shù)據(jù)庫中，很多情況下，人們并非對這些海量數(shù)據(jù)本身感興趣，而是需要從這些海量數(shù)據(jù)中提取出對自己有用的信息。例如，從數(shù)據(jù)中獲取訪問最多的頁面信息等，這就涉及數(shù)據(jù)的查詢技術(shù)等相關(guān)內(nèi)容。
數(shù)據(jù)庫管理軟件選擇是否合理、表結(jié)構(gòu)涉及是否規(guī)范、索引創(chuàng)建是否恰當(dāng)都是影響數(shù)據(jù)庫性能的重要因素。所以，對數(shù)據(jù)庫進(jìn)行優(yōu)化，是實現(xiàn)海量數(shù)據(jù)高效處理的有效方法之一。常見的數(shù)據(jù)庫優(yōu)化方法有以下幾種：
（1）優(yōu)秀的數(shù)據(jù)庫管理工具
選擇一款優(yōu)秀的數(shù)據(jù)庫管理工具非常重要。現(xiàn)在的數(shù)據(jù)庫一般使用Oracle、DB2、MySQL等。
（2）數(shù)據(jù)分區(qū)
進(jìn)行海量數(shù)據(jù)的查詢優(yōu)化，一種重要方式就是如何有效地存儲并降低需要處理的數(shù)據(jù)規(guī)模，所以可以對海量數(shù)據(jù)進(jìn)行分區(qū)操作提高效率。例如，針對按年份存取的數(shù)據(jù)，可以按年進(jìn)行分區(qū)，不同的數(shù)據(jù)庫有不同的分區(qū)方式，不過處理機(jī)制卻大體相同。例如，SQL Server的數(shù)據(jù)庫分區(qū)是將不同的數(shù)據(jù)存于不同的文件組下，而不同的文件組存于不同的磁盤分區(qū)下，這樣將數(shù)據(jù)分散開，減小磁盤I/O，減小了系統(tǒng)負(fù)荷，而且還可以將日志、索引等放于不同的分區(qū)下。
（3）索引
索引一般可以加速數(shù)據(jù)的檢索速度，加速表與表之間的鏈接，提高性能，所以在對海量數(shù)據(jù)進(jìn)行處理時，考慮到信息量比較大，應(yīng)該對表建立索引，包括在主鍵上建立聚簇索引，將聚合索引建立在日期列上等。
索引優(yōu)點很多，但是對于索引的建立，還需要考慮到實際情況，而不是對每一個列建立一個索引。例如，針對大表的分組、排序等字段，都要建立相應(yīng)的索引，同時還應(yīng)該考慮建立復(fù)合索引。增加索引同時也有很多不利的方面：
- 創(chuàng)建索引和維護(hù)索引要耗費時間，這種時間隨著數(shù)據(jù)量的增加而增加
- 索引需要占物理空間，除了數(shù)據(jù)表占數(shù)據(jù)空間之外，每一個索引還要占一定的物理空間。如果要建立聚簇索引，那么需要的空間就會更大。
- 當(dāng)對表中的數(shù)據(jù)進(jìn)行增加、刪除和修改的時候，索引也要動態(tài)地維護(hù)，這樣就降低了數(shù)據(jù)的維護(hù)速度。
所以索引要用到好的時機(jī)，索引的填充因子和聚集、非聚集索引都要考慮。
（4）緩存機(jī)制
當(dāng)數(shù)據(jù)量增加時，一般的處理工具都要考慮到緩存問題。緩存大小設(shè)置的好差也關(guān)系到數(shù)據(jù)處理的成敗。例如，在處理2億條數(shù)據(jù)聚合操作時，緩存設(shè)置為10萬條/Buffer可行。
（5）加大虛存
由于系統(tǒng)資源有限，而需要處理的數(shù)據(jù)量非常大，所以當(dāng)內(nèi)存不足時，可以通過增加虛擬內(nèi)存來解決
（6）分批處理
由于需要處理的信息量巨大，可以對海量數(shù)據(jù)進(jìn)行分批處理（類似于云計算中的MapReduce思想），然后再對處理后的數(shù)據(jù)進(jìn)行合并操作，分而治之，有利于小數(shù)據(jù)量的處理，不至于面對大數(shù)據(jù)量帶來的問題。
（7）使用臨時表和中間表
數(shù)據(jù)量增加時，處理中要考慮提前匯總。這樣做的目的是化整為零，大表變小表，分塊處理完成后，再利用一定的規(guī)則進(jìn)行合并，處理過程中的臨時表的使用和中間結(jié)果的保存都非常重要。如果對于超海量的數(shù)據(jù)，大表處理不了，只能拆分為多個小表。如果處理過程中需要多步匯總操作，可按匯總步驟一步步來。
（8）優(yōu)化查詢語句
查詢語句的性能對查詢效率的影響是非常大的。編寫高效優(yōu)良的SQL腳本和存儲過程是數(shù)據(jù)庫工作人員的職責(zé)，也是檢驗數(shù)據(jù)庫工作人員水平的一個標(biāo)準(zhǔn)。
（9）使用視圖
視圖中的數(shù)據(jù)來源于基本表，對海量數(shù)據(jù)的處理，可以將數(shù)據(jù)按一定的規(guī)則分散到各個基本表中，查詢或處理過程中可以基于視圖進(jìn)行。
（10）使用存儲過程
在存儲過程中盡量使用SQL自帶的返回參數(shù)，而非自定義的返回參數(shù)，減少不必要的參數(shù)，避免數(shù)據(jù)冗余。
（11）用排序來取代非順序存取
磁盤存取臂的來回移動使得非順序磁盤存取變成了最慢的操作，但是在SQL語句中這個現(xiàn)象被隱藏了，這樣就使得查詢中進(jìn)行了大量的非順序頁查詢，降低了查詢速度。
（12）使用采樣數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘
基于海量數(shù)據(jù)的數(shù)據(jù)挖掘正在逐步興起，面對著超海量的數(shù)據(jù)，一般的挖掘軟件或算法往往采用數(shù)據(jù)抽樣的方式進(jìn)行處理，這樣的誤差不會很高，大大提高了處理效率和處理的成功率。一般采樣時要注意數(shù)據(jù)的完整性，防止過大的偏差。
倒排索引法
倒排索引是目前搜素引擎公司對搜索引擎最常用的存儲方式，也是搜索引擎的核心內(nèi)容。在搜索引擎實際的引用之中，有時需要按照關(guān)鍵字的某些值查找記錄，所以是按照關(guān)鍵字建立索引，這個索引就被稱為倒排索引。
倒排索引也常被稱為反向索引、置入檔案或反向檔案，它本質(zhì)上是一種索引方法，被用來存儲在全文搜索下某個單詞在一個文檔或者一組文檔中的存儲位置的映射。它是文檔檢索系統(tǒng)中最常用的數(shù)據(jù)結(jié)構(gòu)，有兩種不同的反向索引形式：
（1）一條記錄的水平反向索引（或者反向檔案索引）包含每個引用單詞的文檔的列表
（2）一個單詞的水平反向索引（或者完全反向索引）又包含每個單詞在一個文檔中的位置。
第二種形式提供了更多的兼容性（如短語搜索），但是需要更多的時間和空間來創(chuàng)建。
一般情況下可以采用矩陣的方式來存儲，但會浪費大量的空間。例如，對于如下的內(nèi)容，
D1:The GDP increased.
D2:The text is this.
D3:My name is.
如果采用矩陣的方式存儲，見表14-1.其中，行表示關(guān)鍵字，列表示所有的文件。
通過比較發(fā)現(xiàn)，采用倒排索引比采用矩陣的方式節(jié)省很多的空間。
正向索引開發(fā)出來用來存儲每個文檔的單詞的列表。正向索引的查詢往往滿足每個文檔有序頻繁的全文查詢和每個單詞在校驗文檔中的驗證查詢。在正向索引中，文檔占據(jù)了中心的位置，每個文檔指向了一個它所包含的索引項的序列。也就是說，文檔指向了它包含的那些單詞，而反向索引則是單詞指向了包含它的文檔，很容易看到這個反向的關(guān)系。而與正向索引相比，倒排索引的優(yōu)點是在處理復(fù)雜的多關(guān)鍵字查詢時，可在倒排表中先完成查詢的并、交等邏輯運算，得到結(jié)果后再對記錄進(jìn)行存取，這樣不必對每個記錄隨機(jī)存取，把對記錄的查詢轉(zhuǎn)換為地址集合的運算，從而提高查找速度。所以，倒排索引一般被應(yīng)用于文檔檢索系統(tǒng)，查詢哪些文件包含了某個單詞，比如常見的學(xué)術(shù)論文的關(guān)鍵字搜索
外排序法
外排序，即當(dāng)待排序的對象數(shù)目特別多時，在內(nèi)存中不能一次處理，必須把它們以文件的形式存放于外存，排序時再把它們一部分一部分調(diào)入內(nèi)存進(jìn)行處理。
外排序是相對內(nèi)排序而言的，它是大文件的排序，待排序的記錄存儲在外存儲器上，待排序的文件無法一次裝入內(nèi)存，需要在內(nèi)存和外部存儲器之間進(jìn)行多次數(shù)據(jù)交換，以達(dá)到排序整個文件的目的。一般采用歸并排序等方式實現(xiàn)外排序，主要分為兩個步驟
（1）生成若干初始?xì)w并段（順串），也被稱為文件預(yù)處理，把含有n個記錄的文件，按內(nèi)存大小劃分為若干長度為L的子文件，然后分別將子文件調(diào)入內(nèi)存，采用有效的內(nèi)排序方法排序后送回外存
（2）進(jìn)行多路歸并，即對這些初始?xì)w并段進(jìn)行歸并，使得有序的歸并段逐漸擴(kuò)大，最后再外存上形成整個文件的單一歸并段，此時就完成了文件的外排序。
外排序的適用范圍是大數(shù)據(jù)的排序以及去重復(fù)。但外排序也存在著很大的缺陷，就是它會消耗大量的IO，效率不會很高。
Trie樹
Trie 這個單詞來自于“retrieve”，Trie樹又稱字典樹或鍵樹。是一種用于快速字符串檢索的多叉樹結(jié)構(gòu)，其原理是利用字符串的公共前綴來降低時空開銷，即以空間換時間，從而達(dá)到提高程序效率的目的。Trie樹的典型應(yīng)用是用于統(tǒng)計和排序大量的字符串（但不僅限于字符串），所以經(jīng)常被搜索引擎系統(tǒng)用于文本詞頻統(tǒng)計。它的優(yōu)點是：最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
Trie樹一般具有以下3個基本特性：
（1）根結(jié)點不包含字符，除根結(jié)點外每一個結(jié)點都只包含一個字符
（2）從根結(jié)點到某一結(jié)點，路徑上經(jīng)過的字符連接起來，為該結(jié)點對應(yīng)的字符串
（3）每個結(jié)點的所有子結(jié)點包含的字符都不相同。
Trie樹可以利用字符串的公共前綴來節(jié)約存儲空間。 如圖14-4所示，該Trie樹用10個結(jié)點保存了5個字符串 amy、aan、em、rob、rg
在該Trie樹中，字符串“amy”和“aan”有公共前綴“a”。當(dāng)然，如果系統(tǒng)中存在大量字符串且這些字符串基本沒有公共前綴，則相應(yīng)的Trie樹將非常消耗內(nèi)存，這也是Trie樹的一個缺點。
給一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么稱b是a的兄弟單詞。例如，單詞army和mary互為兄弟單詞。現(xiàn)在要給出一種解決方案，對于用戶輸入的單詞，根據(jù)給定的字典找出輸入單詞有哪些兄弟單詞。
一般情況下，Trie樹的結(jié)構(gòu)都是采用26叉樹進(jìn)行組織的，每個結(jié)點對應(yīng)一個字母，查找的時候，就是一個字母一個字母地進(jìn)行匹配，算法的時間復(fù)雜度就是單詞的長度n，效率很高。本例子可以定義一個Trie樹作為數(shù)據(jù)結(jié)構(gòu)來查詢，此時就轉(zhuǎn)化為在一棵Trie樹中查找兄弟單詞，只要在Trie樹中的前綴中再存儲一個vector結(jié)構(gòu)的容器，就可以大大降低時間復(fù)雜度。
上例中，Trie樹的構(gòu)建是在預(yù)處理階段完成的，首先根據(jù)字典中的單詞來建立字典樹，當(dāng)建立完字典樹后，查詢兄弟單詞的效率就會提高很多，比hash法效率還要高。
Trie樹適用數(shù)據(jù)量大、重復(fù)多，但是數(shù)據(jù)種類小可以放入內(nèi)存的情況。例如，已知n（n很大）個由小寫字母構(gòu)成的平均長度為10的單詞，判斷其中是否存在某個字符串是另一個字符串的前綴子串。針對這種問題，一般可以采用以下3種方法。
（1）迭代法
對于每一個單詞，都要去查找它前面的單詞中是否包含它，看每個字符串是否為字符串集中某個字符串的前綴，由于需要不停地進(jìn)行迭代比較，所以此時的時間復(fù)雜度為O(n^2)
（2）Hash法
使用Hash方法存儲所有字符串的所有前綴子串。而建立存有子串Hash的時間復(fù)雜度為O(n*len)，查詢的復(fù)雜度為O(n)*O(1)=O(n)
（3）Trie樹
假設(shè)要查詢的單詞是abcd，那么在它前面的單詞中，以b、c、d、f之類開頭的單詞則不必考慮，而只要找以a開頭的單詞中是否存在abcd就可以了。同樣，在以a開頭的單詞中，只要考慮以b作為第二個字母的單詞即可，所以建立Trie樹的復(fù)雜度為O(n*len)，而建立操作與查詢操作在trie樹中是可以同時執(zhí)行的。所以，總的時間復(fù)雜度為O(n*len)，實際查詢的復(fù)雜度只是O(len)。
例如，有串911,911456輸入，如果要同時執(zhí)行建立與查詢，過程如下：首先查詢911，沒有；然后存入9、91、911，再查詢911456，沒有；然后存入9114、91145、911456，而程序沒有記憶功能，并不知道911在輸入數(shù)據(jù)中出現(xiàn)過，所以使用Hash必須先存入所有子串，然后for循環(huán)查詢。而trie樹則可以，存入911后，已經(jīng)記錄911為出現(xiàn)的字符串，在存入911456的過程中就能發(fā)現(xiàn)而輸出答案。反過來也可以，縣存入911456，再存入911時，當(dāng)指針指向最后一個1時，程序會發(fā)現(xiàn)這個1已經(jīng)存在，說明911必定是某個字符串的前綴
堆
堆是一種樹形數(shù)據(jù)結(jié)構(gòu)，每個結(jié)點都有一個值，而通常所說的堆，一般是指二叉堆。在堆中，以大頂堆為例，堆的根結(jié)點的值最大，且根結(jié)點的兩個子樹也是一個大頂堆，基于以上特點，堆適用于海量數(shù)據(jù)求前N大（用小頂堆）或者前N小（用大頂堆）數(shù)問題，其中N一般比較小。例如，當(dāng)求海量數(shù)據(jù)前N小的數(shù)據(jù)時，使用大頂堆，比較當(dāng)前元素與大頂堆的最大元素（即堆頂元素），如果該元素小于最大元素，則應(yīng)該替換該最大元素，并調(diào)整堆的結(jié)構(gòu)。當(dāng)求海量數(shù)據(jù)前N大的數(shù)據(jù)時，思路一樣。由于采用堆，只需要掃描一遍即可得到所有的前n元素，所以在海量信息處理中，效率非常高。
雙層桶法
雙層桶不是一種數(shù)據(jù)結(jié)構(gòu)，而是一種算法思想，類似于分治思想。因為元素范圍很大，不能利用直接尋址表，所以通過多次劃分，逐步確定范圍，最后在一個可以接受的范圍內(nèi)進(jìn)行。
本文以桶排序進(jìn)行分析，桶排序的基本思想是把[ 0,1）劃分為n個大小相同的子區(qū)間，每一子區(qū)間是一個桶，然后將n個記錄分配到各個桶中。因為關(guān)鍵字序列是均勻分布在 [ 0,1）上的，所以必須采用關(guān)鍵字比較的排序方法（通常用插入排序）對各個桶進(jìn)行排序，然后依次將各非空桶中的記錄連接（收集）起來即可。這種排序思想的前提是假設(shè)輸入的n個關(guān)鍵字序列隨機(jī)分布在區(qū)間 [ 0,1）之上，若關(guān)鍵字序列的取值范圍不是該區(qū)間，只要其取值均非負(fù)，總能將所有關(guān)鍵字除以某一合適的數(shù)，將關(guān)鍵字映射到該區(qū)間上，但要保證映射后的關(guān)鍵字是均勻分布在 [ 0,1）上的。
桶排序的平均時間復(fù)雜度是O(n)，最壞情況仍有可能是O(n^2)，一般只適用于關(guān)鍵字取值范圍較小的情況，否則所需桶的數(shù)目m太多導(dǎo)致浪費存儲空間和計算時間。例如，n=10，被排序的記錄關(guān)鍵字ki取值范圍是0~99之間的整數(shù)（36,5,16,98,95,47,32,36,48）時，要用100個箱子來做一趟排序。
桶排序一般適用于尋找第k大的數(shù)、尋找中位數(shù)、尋找不重復(fù)或重復(fù)的數(shù)字等情況。例如：
（1）在一個文件中有10億個整數(shù)，亂序排列，要求找出中位數(shù)，內(nèi)存限制2GB
（2）現(xiàn)在有一個0~30000的隨機(jī)數(shù)生成器。請根據(jù)這個隨機(jī)數(shù)生成器，設(shè)計一個抽獎范圍是0~350000彩票中獎號碼列表，其中要包含20000個中獎號碼。
MapReduce
MapReduce是云計算的核心技術(shù)之一，是一種簡化并行計算的分布式編程模型。它為并行系統(tǒng)的數(shù)據(jù)處理提供了一個簡單、高效的解決方案，其主要目的是為了大型集群的系統(tǒng)能在大數(shù)據(jù)集上進(jìn)行并行工作，并用于大規(guī)模數(shù)據(jù)的并行運算。
MapReduce適用于大規(guī)模數(shù)據(jù)集（通常大于1TB）的并行運算，它的核心操作是Map和Reduce，即MapReduce拆開為 “Map（映射）”和“Reduce（化簡）”。其中，Map函數(shù)獨立地對每個元素進(jìn)行操作，它用于把一組鍵值對映射成一組新的鍵值對，即先通過Map程序?qū)?shù)據(jù)切割成不相關(guān)的區(qū)塊，分配（調(diào)度）給大量計算機(jī)處理達(dá)到分布計算的效果，然后通過指定并發(fā)的Reduce函數(shù)來將結(jié)果匯總，保證所有映射鍵值對中的每一個共享相同的鍵組。
簡而言之，一個映射函數(shù)就是對一些獨立元素組成的概念上的列表（如一個測試成績的列表）的每一個元素進(jìn)行指定的操作（例如，有人發(fā)現(xiàn)所有學(xué)生的成績都被低估了一分，它可以定義一個“加1”的映射函數(shù)，用來修正這個錯誤）。而Map操作與Reduce操作都可以高度并行運行，Map是把一組數(shù)據(jù)一對一地映射為另外的一組數(shù)據(jù)，其映射的規(guī)則由一個函數(shù)來指定。例如，對 [ 1,2,4,8 ] 進(jìn)行乘 2 的映射就變?yōu)?[ 2,4,8,16 ] ，Reduce是對一組數(shù)據(jù)進(jìn)行規(guī)約，這個規(guī)約的規(guī)則是由另外一個函數(shù)指定的。例如，對 [ 1,2,4,8 ] 進(jìn)行求和規(guī)約得到的結(jié)果是 15，而對它進(jìn)行求積的規(guī)約是 64。
通過MapReduce，不會分布式并行編程的程序員也能很容易地將自己的程序運行在分布式系統(tǒng)上。同時，通過該模型，能夠充分高效地利用集群中每個機(jī)器的資源，適合在集群中處理大規(guī)模數(shù)據(jù)的計算任務(wù)，這些優(yōu)點使得其已成為云計算平臺的主流編程模型。
總結(jié)
- 上一篇： 关于SAP云平台的Identity Au
- 下一篇： 舞蹈训练教学计划