用 Python 實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜索引擎

牛耳藪肓件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃用Python實(shí)現(xiàn)一個(gè)大數(shù)據(jù)搜素引擎搜索是大數(shù)據(jù)領(lǐng)域里常見(jiàn)的需求。Splunk和ELK分別是該領(lǐng)域在非開(kāi)源和開(kāi)源領(lǐng)域里的領(lǐng)導(dǎo)者。本文利用很少的Python代碼實(shí)現(xiàn)了一個(gè)基本的數(shù)據(jù)搜索功能，試圖讓大家理解大數(shù)據(jù)搜索的基本原理。布隆過(guò)濾器(BloomFilter)第一步我們先要實(shí)現(xiàn)一個(gè)布隆過(guò)濾器。布隆過(guò)濾器是大數(shù)據(jù)領(lǐng)域的一個(gè)常見(jiàn)算法，它的目的是過(guò)濾掉那些不是目標(biāo)的元素。也就是說(shuō)如果一個(gè)要搜索的詞并不存在與我的數(shù)據(jù)中，那么它可以以很快的速度返回目標(biāo)不存在。讓我們看看以下布隆過(guò)濾器的代碼:classBloomfilter(object):件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃ABloomfilterisaprobabilisticdata-structurethattradesspaceforaccuracywhendeterminingifavalueisinaset.Itcantellyouifavaluewaspossiblyadded,orifitwasdefinitelynotadded,butitcan'ttellyouforcertainthatitwasadded.def__init__(self,size):"SetuptheBFwiththeappropriatesize""”self.values=[False]*sizeself.size=sizedefhash_value(self,value):"""HashthevalueprovidedandscaleittofittheBFsize"""returnhash(value)%self.size件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃defadd_value(self,value):AddavaluetotheBF"h=self.hash_value(value)self.values[h]=Truedefmight_contain(self,value):"""CheckifthevaluemightbeintheBF""”h=self.hash_value(value)returnself.values[h]defprint_contents(self):"""DumpthecontentsoftheBFfordebuggingpurposes""”printself.values用國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃基本的數(shù)據(jù)結(jié)構(gòu)是個(gè)數(shù)組（實(shí)際上是個(gè)位圖，用1/0來(lái)記錄數(shù)據(jù)是否存在），初始化是沒(méi)有任何內(nèi)容，所以全部置False。實(shí)際的使用當(dāng)中，該數(shù)組的長(zhǎng)度是非常大的，以保證效率。利用哈希算法來(lái)決定數(shù)據(jù)應(yīng)該存在哪一位，也就是數(shù)組的索引當(dāng)一個(gè)數(shù)據(jù)被加入到布隆過(guò)濾器的時(shí)候，計(jì)算它的哈希值然后把相應(yīng)的位置為T(mén)rue當(dāng)檢查一個(gè)數(shù)據(jù)是否已經(jīng)存在或者說(shuō)被索引過(guò)的時(shí)候，只要檢查對(duì)應(yīng)的哈希值所在的位的True/Fasle件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃看到這里，大家應(yīng)該可以看出，如果布隆過(guò)濾器返回False,那么數(shù)據(jù)一定是沒(méi)有索引過(guò)的，然而如果返回True，那也不能說(shuō)數(shù)據(jù)一定就已經(jīng)被索引過(guò)。在搜索過(guò)程中使用布隆過(guò)濾器可以使得很多沒(méi)有命中的搜索提前返回來(lái)提高效率。我們看看這段code是如何運(yùn)行的:bf=Bloomfilter(10)bf.add_value('dog')bf.add_value('fish')bf.add_value('cat')bf.print_contents()bf.add_value('bird')bf.print_contents()#Note:contentsareunchangedafteraddingbird-itcollidesfortermin['dog','fish','cat','bird','duck','emu']:件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃print'{}:{}{}'.format(term,bf.hash_value(term),bf.might_contain(term))結(jié)果：[False,False,False,False,True,True,False,False,False,True][False,False,False,False,True,True,False,False,False,True]dog:5Truefish:4Truecat:9Truebird:9Trueduck:5Trueemu:8False首先創(chuàng)建了一個(gè)容量為10的的布隆過(guò)濾器用國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才摧籃牛耳我盲然后分別加入‘dog’，‘fish’，‘cat’三個(gè)對(duì)象，這時(shí)的布隆過(guò)濾器的內(nèi)容如下:用國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才摧籃牛耳我盲然后加入‘bird’對(duì)象，布隆過(guò)濾器的內(nèi)容并沒(méi)有改變，因?yàn)椤産ird’和‘fish’恰好擁有相同的哈希。

件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃最后我們檢查一堆對(duì)象(’dog’,‘fish’,‘cat’,‘bird’,‘duck’,’emu’)是不是已經(jīng)被索引了。結(jié)果發(fā)現(xiàn)’duck’返回True,2而’emu’返回False。因?yàn)椤痙uck’的哈希恰好和‘dog’是一樣的。用國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃分詞下面一步我們要實(shí)現(xiàn)分詞。分詞的目的是要把我們的文本數(shù)據(jù)分割成可搜索的最小單元，也就是詞。這里我們主要針對(duì)英語(yǔ)，因?yàn)橹形牡姆衷~涉及到自然語(yǔ)言處理，比較復(fù)雜，而英文基本只要用標(biāo)點(diǎn)符號(hào)就好了。下面我們看看分詞的代碼:defmajor_segments(s):件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃Performmajorsegmentingonastring.Splitthestringbyallofthemajorbreaks,andreturnthesetofeverythingfound.Thebreaksinthisimplementationaresinglecharacters,butinSplunkpropertheycanbemultiplecharacters.Asetisusedbecauseorderingdoesn'tmatter,andduplicatesarebad.major_breaks=''last=-1results=set()#enumerate()willgiveus(0,s[0]),(1,s[1]),...foridx,chinenumerate(s):ifchinmajor_breaks:件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃segment=s[last+1:idx]results.add(segment)last=idx#Thelastcharactermaynotbeabreaksoalwayscapture#thelastsegment(whichmayendupbeing"",butyolo)segment=s[last+1:]results.add(segment)returnresults主要分割主要分割使用空格來(lái)分詞，實(shí)際的分詞邏輯中，還會(huì)有其它的分隔符。例如Splunk的缺省分割符包括以下這些，用戶(hù)也可以定義自己的分割符。件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃]<>(){}|!;,‘"*s&?+%21%26%2526%3B%7C%20%2B%3D—%2520%5D%5B%3A%0A%2C%28%29defminor_segments(s):"""Performminorsegmentingonastring.Thisislikemajorsegmenting,exceptitalsocapturesfromthestartoftheinputtoeachbreak."""minor_breaks='_.'last=-1results=set()foridx,chinenumerate(s):ifchinminorbreaks:件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃segment=s[last+1:idx]results.add(segment)segment=s[:idx]results.add(segment)last=idxsegment=s[last+1:]results.add(segment)results.add(s)returnresults次要分割件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃次要分割和主要分割的邏輯類(lèi)似，只是還會(huì)把從開(kāi)始部分到當(dāng)前分割的結(jié)果加入。例如""的次要分割會(huì)有1，2，3，4，1.2，1.2.3defsegments(event):Simplewrapperaroundmajor_segments/minor_segmentsresults=set()formajorinmajor_segments(event):forminorinminor_segments(major):results.add(minor)returnresults分詞的邏輯就是對(duì)文本先進(jìn)行主要分割，對(duì)每一個(gè)主要分割在進(jìn)行次要分割。然后把所有分出來(lái)的詞返回。我們看看這段code是如何運(yùn)行的:件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃forterminsegments('src_ip='):printtermsrc.4src_ip1.2.3ip件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃搜索好了，有個(gè)分詞和布隆過(guò)濾器這兩個(gè)利器的支撐后，我們就可以來(lái)實(shí)現(xiàn)搜索的功能了。上代碼：classSplunk(object):def__init__(self):self.bf=Bloomfilter(64)self.terms=(}#Dictionaryoftermtosetofeventsself.events=[]defadd_event(self,event):Addsaneventtothisobject件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃#GenerateauniqueIDfortheevent,andsaveitevent_id=len(self.events)self.events.append(event)#Addeachtermtothebloomfilter,andtracktheeventbyeachtermforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term]=set()self.terms[term].add(event_id)defsearch(self,term):件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃Searchforasingleterm,andyieldalltheeventsthatcontainit"""InSplunkthisrunsinO(1),andislikelytobeinfilesystemcache(memory)ifnotself.bf.might_contain(term):returnInSplunkthisprobablyrunsinO(logN)whereNisthenumberoftermsinthetsidxiftermnotinself.terms:returnforevent_idinsorted(self.terms[term]):yieldself.events[event_id]用國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃Splunk代表一個(gè)擁有搜索功能的索引集合每一個(gè)集合中包含一個(gè)布隆過(guò)濾器，一個(gè)倒排詞表（字典），和一個(gè)存儲(chǔ)所有事件的數(shù)組當(dāng)一個(gè)事件被加入到索引的時(shí)候，會(huì)做以下的邏輯為每一個(gè)事件生成一個(gè)unqieid，這里就是序號(hào)對(duì)事件進(jìn)行分詞，把每一個(gè)詞加入到倒排詞表，也就是每一個(gè)詞對(duì)應(yīng)的事件的id的映射結(jié)構(gòu)，注意，一個(gè)詞可能對(duì)應(yīng)多個(gè)事件，所以倒排表的的值是一個(gè)Set。倒排表是絕大部分搜索引擎的核心功能。當(dāng)一個(gè)詞被搜索的時(shí)候，會(huì)做以下的邏輯用國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃檢查布隆過(guò)濾器，如果為假，直接返回檢查詞表，如果被搜索單詞不在詞表中，直接返回在倒排表中找到所有對(duì)應(yīng)的事件id，然后返回事件的內(nèi)容我們運(yùn)行下看看把：s=Splunk()s.add_event('src_ip=')s.add_event('src_ip=')s.add_event('dst_ip=')foreventins.search(''):件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃printeventprint'-foreventins.search('src_ip'):printeventprint'-foreventins.search('ip'):printeventsrc_ip=dst_ip=-src_ip=src_ip=src_ip=用國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃src_ip=dst_ip=是不是很贊！更復(fù)雜的搜索更進(jìn)一步，在搜索過(guò)程中，我們想用And和Or來(lái)實(shí)現(xiàn)更復(fù)雜的搜索邏輯。上代碼：classSplunkM(object):def__init__(self):self.bf=Bloomfilter(64)self.terms=(}#Dictionaryoftermtosetofeventsself.events=[]defadd_event(self,event):件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃"""Addsaneventtothisobject""”#GenerateauniqueIDfortheevent,andsaveitevent_id=len(self.events)self.events.append(event)#Addeachtermtothebloomfilter,andtracktheeventbyeachtermforterminsegments(event):self.bf.add_value(term)iftermnotinself.terms:self.terms[term]=set()self.terms[term].add(event_id)defsearch_all(self,terms):件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃"""SearchforanANDofallterms"""#Startwiththeuniverseofallevents...results=set(range(len(self.events)))forterminterms:#Ifatermisn'tpresentatallthenwecanstoplookingifnotself.bf.might_contain(term):returniftermnotinself.terms:return#Dropeventsthatdon'tmatchfromourresultsresults=ersection(self.terms[term])件■國(guó)互聯(lián)網(wǎng)前沿技術(shù)人才搖籃forevent_idinsorted(results):yieldself.events[event_id]defsearch_any(s