姓名：苗春雨? ? 學(xué)號：16019110036
轉(zhuǎn)載自：http://blog.csdn.net/dev_csdn/article/details/78533168
【嵌牛導(dǎo)讀】：摘要：為了高效地分析海量的數(shù)據(jù)甫窟，科學(xué)家首先要將大數(shù)打破成碎片叙淌。作者循序漸進(jìn)地闡述了一個處理海量數(shù)據(jù)流的最佳流式算法侥加，算法經(jīng)過不斷改進(jìn)跑芳，是超大規(guī)模數(shù)據(jù)流高性能分析的新算法岸晦，以下是譯文三热。
【嵌牛鼻子】：海量數(shù)據(jù)流的最佳算法
【嵌牛提問】：建立算法所需的策略？
【嵌牛正文】：
原文：Best-Ever Algorithm Found for Huge Streams of Data
翻譯：無阻我飛揚(yáng)
當(dāng)從消防水帶出來的水沖擊你的臉部時脯爪，很難計量水则北。從某種意義上說矿微，這正是分析數(shù)據(jù)流所面臨的挑戰(zhàn)，數(shù)據(jù)源源不斷地向我們奔流而來尚揣，永不停息涌矢。如果在Twitter上看一篇篇推文不停閃過，你可能想要暫停一下快骗，以便弄清楚時下的流行話題是什么娜庇。話雖這么說，但這行不通方篮，所以需要找到一種方法名秀，以便實時記錄主題標(biāo)簽。
執(zhí)行這種實時計算的計算機(jī)程序稱為流式算法藕溅。因為數(shù)據(jù)以龐大的量持續(xù)不斷地出現(xiàn)匕得，流式算法試圖記錄下重要的數(shù)據(jù)，同時戰(zhàn)略性遺忘其余數(shù)據(jù)巾表。30多年來汁掠，計算機(jī)科學(xué)家一直致力于構(gòu)建更好的流式算法。去年秋天集币，一個研究小組發(fā)明了一種近乎完美的算法考阱。
哈佛大學(xué)的計算機(jī)科學(xué)家杰拉尼·尼爾森（Jelani Nelson）表示：“我們開發(fā)了一種新算法，從各個標(biāo)準(zhǔn)維度來看惠猿，也是最好的算法”羔砾，他與丹麥奧胡斯大學(xué)的卡斯珀·格林·拉森（Kasper Green Larsen）、哥本哈根大學(xué)的邁克爾·托魯普（Mikkel Thorup）以及東北大學(xué)的阮惠（Huy Nguyen）一起提出了這個新算法偶妖。
哈佛大學(xué)的理論計算機(jī)科學(xué)家杰拉尼·尼爾森與別人共同開發(fā)出了新算法姜凄。
圖片來源：Yaphet Teklu
這種一流的流式算法的工作原理是，通過記住足夠多的數(shù)據(jù)來告訴你它最持悍茫看到的是什么态秧。這表明在數(shù)據(jù)流分析中固有的折衷實際上似乎并不必要。這也為戰(zhàn)略性遺忘的新紀(jì)元指明了前進(jìn)的道路扼鞋。
流式算法在監(jiān)視連續(xù)不斷更新的數(shù)據(jù)庫的任何情況下都是有幫助的申鱼。這可能是AT&T持續(xù)不斷的選項卡數(shù)據(jù)包或者Google繪制永無止境的搜索查詢流程。在這些情況下云头，流式算法是非常有用的捐友，甚至是必要的，即使沒有重新檢查或甚至記住你所見過的每一段數(shù)據(jù)溃槐，都有一種方法來回答數(shù)據(jù)方面的實時問題匣砖。
這里有一個簡單的例子。假設(shè)有一連串的數(shù)字，想知道目前為止你所看到的所有數(shù)字的總和猴鲫。這種情況下对人，很顯然不是記住每一個數(shù)字，只需要記住一個數(shù)字：累計總數(shù)拂共。
然而牺弄，當(dāng)想問的關(guān)于數(shù)據(jù)的問題變得更復(fù)雜時，這個挑戰(zhàn)就更難了宜狐。想象一下势告，假設(shè)不是想計算總和，而是想回答以下問題：哪些數(shù)字最常出現(xiàn)抚恒？看不太出來有什么捷徑可以快速給出正確的答案培慌。
這個特殊的謎題被稱為“頻繁項”（frequent item，或heavy hitter）問題柑爸。解決這個難題的第一個算法是在20世紀(jì)80年代初由康奈爾大學(xué)的大衛(wèi)·格里斯（David Gries）和得克薩斯大學(xué)奧斯汀分校的賈亞德夫·米斯拉（Jayadev Misra）開發(fā)的。他們的算法在許多方面是有效的盒音，但卻不能處理所謂的“變化檢測”表鳍。它可以告訴你最常搜索的詞語，但是無法告訴哪些詞語很流行祥诽。以Google為例譬圣，它可以將“維基百科”視為一個受歡迎的搜索詞語，卻發(fā)現(xiàn)不了與艾爾瑪颶風(fēng)等重大事件相伴隨的熱搜雄坪。
沃里克大學(xué)的計算機(jī)科學(xué)家格雷厄姆·科爾莫德（Graham Cormode）說：“這是一個編碼問題 ——你將信息編碼為簡潔的摘要厘熟，并嘗試提取信息，讓你恢復(fù)最初的內(nèi)容维哈∩蹋”
在接下來的30多年里，科爾莫德和其他計算機(jī)科學(xué)家改進(jìn)了Gries和Misra的算法阔挠。比如說飘庄，一些新的算法能夠檢測出流行詞語，另一些算法能夠更精細(xì)地定義某個詞語怎樣才算是頻繁詞語购撼。所有這些算法都有其弊端跪削，比如犧牲速度以換去準(zhǔn)確性，或者犧牲內(nèi)存消耗來保證可靠性迂求。
這方面的工作大多數(shù)依賴索引（index）碾盐。想象一下，設(shè)若你試圖識別頻繁的搜索字詞揩局。一個辦法就是為英語中的每個單詞分配一個編號毫玖，然后將該編號與跟蹤該詞搜索了多少次的第二個編號配對起來。也許“aardvark” 以單詞編號17被編入索引，并在數(shù)據(jù)庫中顯示為（17孕豹，9）涩盾，意思是單詞編號為17的單詞已被搜索9次。這種方法離將最頻繁的項放在手邊更近了一步励背，因為在任何特定時刻春霍，你知道每個單詞到底被搜索了多少次。
盡管如此叶眉，它還是有缺點的址儒，那就是要花很多的時間用一個算法來梳理英語中成千上萬的單詞。
但要是字典里只有100個單詞衅疙，將會怎么樣莲趣？羅伊·尼爾森說：“遍歷字典中的每個單詞花不了太長時間”ヒ纾”
可惜喧伞，字典里的單詞數(shù)量實在是太多了。正如新算法的作者發(fā)現(xiàn)的那樣绩郎，除非你可以把大字典分解成更小的字典潘鲫，并找到一種巧妙的方法把它重新組合起來，否則無計可施肋杖。
小數(shù)字比大數(shù)字容易跟蹤溉仑。
想象一下，假如你正在監(jiān)視0到50000000之間的一個數(shù)字流（這項任務(wù)類似于按照IP地址來記錄互聯(lián)網(wǎng)用戶）状植∽蔷梗可以使用50000000項索引來跟蹤這些數(shù)字，但是很難處理這么龐大的索引。更好的方法是把每個八位數(shù)字視為連接在一起的四個兩位數(shù)字。
設(shè)若看到數(shù)字12345678垃瞧。一種高效記憶的方法是將其分解成四個兩位數(shù)塊：12,34,56,78吨娜。然后，可以將每個塊發(fā)送給計算項目頻率的子算法：12發(fā)給子算法一，34發(fā)給子算法二，56發(fā)給子算法三，78發(fā)給子算法四徘郭。
每個子算法都為它看到的內(nèi)容建有各自的索引，但由于每個版本都不會看到比兩位數(shù)大的索引丧肴，所以每個索引只是從0到99残揉。
這種分拆的一個重要特點是，如果大數(shù)字——12345678 在整個數(shù)據(jù)流中頻繁出現(xiàn)芋浮，其兩位數(shù)字塊部分也將頻繁出現(xiàn)抱环。如果要求每個子算法識別出最晨强欤看到的數(shù)字，子算法一會給出12镇草，子算法二將給出34眶痰，依此類推。只要在四個短得多的列表中查找頻繁項梯啤，就能夠找到龐大列表中最常見的內(nèi)容竖伯。
圖片來源：Lucy Reading-Ikkanda/《Quanta》雜志
尼爾森說：“不是花5000萬個時間單位遍歷整個宇宙，只是四個算法因宇，花了100個時間單位七婴。”
這種分而治之策略存在的主要問題是察滑，雖然很容易把一個大數(shù)字分解成小的數(shù)字打厘，但將小數(shù)重新組合成大數(shù)比較棘手— 很難找出正確的小數(shù)來重新組合，從而獲得正確的大數(shù)贺辰。
想象一下户盯，你的數(shù)據(jù)流通常包含幾個數(shù)字相同的兩個數(shù)：12,345,678和12,999,999。兩者都從12開始饲化。你的算法將每個大數(shù)字分成四個較小的數(shù)字先舷，然后將每個小數(shù)字發(fā)送給子算法。然后你問每個子算法滓侍，“哪些數(shù)最常看到牲芋？”子算法1將會說：“我經(jīng)沉冒剩看到數(shù)字12.” 一種算法試圖識別是哪個八位數(shù)字，在這種情況下缸浦，經(jīng)常不知道這些12是屬于其中某一個八位數(shù)的夕冲，還是屬于該例中兩個不同的八位數(shù)的。
尼爾森說：“難就難在搞清楚哪些兩位數(shù)塊與另外哪些兩位數(shù)塊連在一起裂逐〈跤悖”
新算法的作者通過將每個兩位數(shù)塊封裝成一個不占用大量內(nèi)存的小標(biāo)簽來解決這個困境，但是仍然允許算法將兩位數(shù)的塊以正確的方式重新組合在一起卜高。
要查看標(biāo)簽如何工作的簡單方法弥姻，不妨從12,345,678開始，并將其拆分成兩位數(shù)塊掺涛。但這一次庭敦，在將每個塊發(fā)送到其各自的子算法之前，使用一對唯一的標(biāo)識號封裝塊薪缆，標(biāo)識號可以將塊重新組合在一起秧廉。這些標(biāo)簽中的第一個用作塊的名稱，第二個標(biāo)簽作為環(huán)。這樣一來疼电，12345678成為：
12, 0, 134, 1, 256, 2, 378, 3, 4
這里嚼锄，數(shù)字12的名稱為“0”，并鏈接到名為“1”的數(shù)字蔽豺。數(shù)字34的名稱為“1”区丑，并鏈接到名為“2”的數(shù)字，依此類推茫虽。
現(xiàn)在刊苍，當(dāng)子算法返回最常見的兩位數(shù)字塊時，12找尋一個標(biāo)有“1”的數(shù)字濒析，從而找到34正什，然后34找尋一個標(biāo)有“2”的數(shù)字，從而找到56号杏， 56找尋一個標(biāo)有“3”的數(shù)字婴氮，從而找到78。
這么一來盾致，可以把兩位數(shù)字塊視為鏈中的環(huán)主经，并通過這些額外的標(biāo)記號將這些環(huán)連接在一起。
當(dāng)然許多鏈的問題在于庭惜，其牢固性完全取決于最薄弱的那一環(huán)罩驻。而這些鏈幾乎可以保證會斷掉。
沒有一種算法能在每次運(yùn)行時都完美地運(yùn)行——即使最好的算法也會在很小的一段時間內(nèi)失效护赊。在上述的例子中惠遏，一個失效可能意味著第二個兩位數(shù)的塊，34骏啰，被分配了一個不正確的標(biāo)簽节吮，結(jié)果就是當(dāng)它去找尋它應(yīng)該連接的塊時，它沒有找到56所需要的信息判耕。一旦鏈中的一個環(huán)節(jié)失敗透绩，整個工作就土崩瓦解了。
哥本哈根大學(xué)的計算機(jī)科學(xué)家邁克爾·托魯普幫助開發(fā)了一種防止錯誤的方法來記住數(shù)據(jù)壁熄。
圖片來源：UNIAVISEN.DK
為了避免這個問題帚豪，研究人員使用所謂的“擴(kuò)展圖”。在擴(kuò)展圖中草丧，每兩個數(shù)字塊形成一個點志鞍。這些點按線連接（遵循上述的標(biāo)記過程）形成一個聚類。擴(kuò)展圖的一個重要特點是方仿，不只是將每個點與其相鄰的塊連接起來固棚，而是將每個兩個數(shù)字塊與多個其它塊連接起來统翩。以12345678為例，不僅將12與34連接此洲，也與56連接厂汗，這樣即使12和34之間的鏈接失敗，仍然可以知道12和56屬于同一個數(shù)字呜师。
擴(kuò)展圖的結(jié)果并不總是完美的娶桦。有時它無法鏈接本該鏈接的兩個塊，或者會鏈接不屬于一起的兩個塊汁汗。為了克服這個不足衷畦，研究人員開發(fā)了其算法的最后環(huán)節(jié)：“聚類保留”子算法，它可以調(diào)查擴(kuò)展圖知牌，準(zhǔn)確地確定哪些點旨在聚合起來祈争、哪些點不是，即使某幾條線丟失角寸、虛假線添加上去也沒關(guān)系菩混。
托魯普說：“這確保我可以恢復(fù)看起來酷似原始聚類的內(nèi)容”馀海”
雖然Twitter不會明天就使用這個擴(kuò)展圖沮峡，但其底層技術(shù)適用于解決極其廣泛的計算機(jī)科學(xué)問題，而不是僅僅用來統(tǒng)計推文亿柑。該算法還證明了不需要作出某些犧牲邢疙，也即以前在回答頻繁項目問題的時候似乎非常必要的犧牲。以前的算法總是放棄一些東西——準(zhǔn)確性很高望薄，但很費內(nèi)存疟游，或者速度很快，但是無法確定哪些頻繁項很流行式矫。這個新的算法表明，若有正確的方法來編碼大量信息役耕，你最后能夠集眾者之所長：不僅可以存儲頻繁項采转，還可以取回頻繁項。
