丨面向?qū)ο笙氯绾螌?shí)現(xiàn)一個(gè)搜索引擎

對(duì)象的建模思搜索引擎極大地方便了互聯(lián)網(wǎng)生活，也成為上網(wǎng)必不可少的剛需工具。依托搜索引擎發(fā)展起來(lái)的互聯(lián)網(wǎng)，則成了硅谷和中國(guó)巨頭的商業(yè)模式；而搜索本身，也在持續(xù)進(jìn)步著， 也一直有意向在自家社交產(chǎn)品架設(shè)搜索平臺(tái)關(guān)于搜索引擎的價(jià)值我不必多說(shuō)了，今天我們主要來(lái)看一下搜索引擎的構(gòu)成聽(tīng)的朋友說(shuō)，他們?nèi)肼毰嘤?xùn)的時(shí)候，有一門課程叫做Thelifeofaquery，內(nèi)容我們知道，一個(gè)搜索引擎由搜索器、索引器、檢索器和用戶接口四個(gè)部分組成搜索器，通俗來(lái)講就是我們常提到的爬蟲（srar），（index），于內(nèi)部的數(shù)據(jù)庫(kù)等待檢索最后的用戶接口很好理解，是指網(wǎng)頁(yè)和App端界面，例如和谷歌的搜索頁(yè)面。用通過(guò)用戶接口，向搜索引擎發(fā)出詢問(wèn)（query），后，再將結(jié)果返回給用戶。為了方便，我們只提供五個(gè)文件的檢索，內(nèi)容我放在了下面這段代碼代碼#Ihaveadreamthatmyfourlittlechildrenwillonedayliveinanationwherethey3#IhaveadreamthatonedaydowninAlabama,withitsviciousracists,...oneday6#Ihaveadreamthatonedayeveryvalleyshallbeexalted,everyhillandmountain9#Thisisourhope...Withthisfaithwewillbeabletohewoutofthemountainof#Andwhenthishappens,andwhenweallowdomring,whenweletitringfromevery我們先來(lái)定義SearchEngineBase類。這里我先給出了具體的代碼，你不必著急操作，代碼class34

init(self):defadd_corpus(self,withopen(file_path,'r')astext=cess_corpus(file_pah,9defprocess_corpu(self,id,raisException('process_corpusnotdefseach(selfqraseException('searchnotdefforfile_pathin['1.txt','2.txt','3.txt','4.txt',whilequery=results=print('found{}forresultinSearchEngineBase可以被繼承，繼承的類分別代表不同的算法引擎。每一個(gè)引擎都應(yīng)該實(shí)現(xiàn)process_corpus()和search()兩個(gè)函數(shù)，對(duì)應(yīng)我們剛剛提到的索引器和檢索器。函數(shù)提供搜索器和用戶接口，于是一個(gè)簡(jiǎn)單的包裝界面就有了具體來(lái)看這段代碼，其中add_corpus()函數(shù)負(fù)責(zé)文件內(nèi)容，將文件路徑作為ID，連同內(nèi)容一起送到process_corpus中。process_corpus要對(duì)內(nèi)容進(jìn)行處理，然后文件路徑為ID將處理后的內(nèi)容存下來(lái)。search則給定一個(gè)詢問(wèn)，處理詢問(wèn)，再通過(guò)索引檢索，然后返回好，理解這些概念后，接下來(lái)，我們實(shí)現(xiàn)一個(gè)最基本的可以工作的搜索引擎，代代碼1class2init3super(SimpleEngine,self).init4self.id_to_texts=56process_corpus(self,id,7self.id_to_texts[id]=89search(self,results=forid,textinself.ifqueryinreturn16search_engine=1720##########輸出found0found2你可能很驚訝，只需要短短十來(lái)行代碼居然就可以了沒(méi)錯(cuò)，正是如此，這段代碼我們拆開(kāi)來(lái)看一SimpleEngine實(shí)現(xiàn)了一個(gè)繼承SearchEngineBase的子類，繼承并實(shí)現(xiàn)了process_corpussearch口，同時(shí)，也順手繼承了add_corpus數(shù)（當(dāng)然你想重寫也是可行的），因此我們可以在main()函數(shù)中直接調(diào)取。 id_to_texts={}初始化了自己的私有變量，也就process_corpus()數(shù)則非常直白地將文件內(nèi)容插入到字典中。這里注意，ID要是唯一的，不然相同ID的新內(nèi)容會(huì)覆蓋掉舊的內(nèi)容。search接枚舉字典，從中找到要搜索的字符串。如果能夠找到，則將ID到結(jié)果列表基類是如何充當(dāng)接口作用的（參數(shù)，看一下會(huì)報(bào)什么錯(cuò)）？好的，我們重新回到搜索引擎這個(gè)話題相信你也能看得出來(lái)，這種實(shí)現(xiàn)方式簡(jiǎn)單，但顯然是一種很低效的方式：每次索引后需要占用大量空間，因?yàn)樗饕瘮?shù)并沒(méi)有做任何事情；每次檢索需要占用大量時(shí)間，因?yàn)樗兴饕龓?kù)的文件都要被重新搜索一遍。如果把語(yǔ)料的信息量視為n，復(fù)雜度都應(yīng)該是O(n)而且，還有一個(gè)問(wèn)題：這query能是一個(gè)詞，或者是連起來(lái)的幾個(gè)詞。如果你想要這時(shí)應(yīng)該怎么優(yōu)化呢所有詞匯的set即可。根據(jù)齊夫定律（Zipf’slaw，），在自然語(yǔ)言的語(yǔ)料庫(kù)里，一個(gè)單詞出現(xiàn)率與頻率的反比現(xiàn)冪布。，語(yǔ)詞的可以提升我們的和搜索效率。那具體該如何實(shí)現(xiàn)呢BagofWords和Inverted我們先來(lái)實(shí)現(xiàn)一個(gè)名叫BagofWords的搜索模型。請(qǐng)看下面的代碼代碼import2class567

init(self):super(BOWEngine,self).init()self.ido_words={}efprocess_corpus(self,id,self.id_to_words[id]=defsearch(self,query_words=results=forid,wordsinself.ifself.query_match(query_words,returndefquery_match(query_words,forquery_wordinifquery_wordnotinreturnreturndef#使用正則表達(dá)式去除標(biāo)點(diǎn)符號(hào)和換text=re.sub(r'[^\w]','',#轉(zhuǎn)為小text=#生成所有單詞的列word_list=#去除空白word_list=#返回單詞的returnsearch_engine=輸出ihaveafound3domfound1你應(yīng)該發(fā)現(xiàn)，代碼開(kāi)始變得稍微復(fù)這里我們先來(lái)理解一個(gè)概念，BOWModel，即BagofWordsModel，中文叫做詞袋模型。這是NLP領(lǐng)域最常見(jiàn)最簡(jiǎn)單的模型之一。假設(shè)一個(gè)文本，不考慮語(yǔ)法、句法、段落，也不考慮詞匯出現(xiàn)的順序，只將這個(gè)文本看成這些詞匯的集合。于是相應(yīng)的，我們把dtottsdto_word，這樣就只需要存這些單詞，而不是全部文章，也不需要考慮順序。其中，process_corpus(數(shù)調(diào)用類靜態(tài)函數(shù)parse_text_to_words，將文章打碎形成詞袋，放入set之后再放到字典中。ser)函數(shù)則稍微復(fù)雜一些。這里我們假設(shè)，想得到的結(jié)果，是所有的搜索都要出現(xiàn)在同一篇文章中。那么，我們需要同樣打碎querysttquery_math及對(duì)象的私有變量（沒(méi)有self作為參數(shù)），相同的輸入能夠得到完全相同的輸出結(jié)果。因可是，即使這樣做，每次查詢時(shí)依然需要遍歷所有ID，雖然比起Simple模型已經(jīng)節(jié)約了你可能想到了，我們每次查詢的query單詞量不會(huì)很多，一般也就幾個(gè)、最多十幾個(gè)的針對(duì)這兩點(diǎn)，我們還能做得更好嗎？顯然是可以的，請(qǐng)看接下來(lái)的這段代碼1import2class567

init(self):super(BOWInvertedIndexEngine,self).init()self.inverted_index={}defprocess_corpus(self,id,words=forwordinifwordnotinself.inverted_index[word]=defsearch(self,query_words=query_words_index=forquery_wordin#如果某一個(gè)查詢單詞的倒序索引為空，我們就立刻forquery_wordinifquery_wordnotinreturnresult=while#首先，獲得當(dāng)前狀態(tài)下所有倒序索引的current_ids=foridx,query_wordincurrent_index=current_inverted_list= #已經(jīng)遍歷到了某一個(gè)倒序索引的末尾，結(jié)束 ifcurrent_index>= return #然后，如果current_ids的所有元素都一樣，那么表明這個(gè)單詞在這個(gè)元素對(duì)應(yīng)的文ifall(x==current_ids[0]forxinquery_words_index=[x+1forxin#如果不是，我們就把最小的元素min_val=min_val_pos=query_words_index[min_val_pos]+=def#使用正則表達(dá)式去除標(biāo)點(diǎn)符號(hào)和換text=re.sub(r'[^\w]','',#轉(zhuǎn)為小text=#生成所有單詞的列word_list=text.split('#去除空白word_list=filter(None,#返回單詞的returnsearch_engine=70##########輸出found2littlefound1首先我要強(qiáng)調(diào)一下，這次的算法并不需要你完全理解，這里的實(shí)現(xiàn)有一些超出了本章知識(shí)但希不要退縮個(gè)例告訴面向編程何把復(fù)雜開(kāi)來(lái)，而保留接口和其他的代碼不變。我們接著來(lái)看這段代碼。你可以看到，新模型繼續(xù)使用之前的接口，仍init()、process_corpus()和search()三個(gè)函數(shù)進(jìn)行修改這其實(shí)也是大公司里團(tuán)隊(duì)協(xié)作的式，在合理的分層設(shè)計(jì)后，每一層的邏輯只需要處好分內(nèi)的事情即可。在迭代升級(jí)我們的搜索引擎內(nèi)核時(shí)，main變。當(dāng)然，如果公司招了新的前端工程師，要對(duì)用戶接口部分進(jìn)行修改，新人也不需要過(guò)分擔(dān)心的事情，只要做好數(shù)據(jù)交互就可以了。繼續(xù)看代碼，你可能注意到了開(kāi)頭的InvertedIndex。InvertedIndexModel，即倒序索倒序索引，一如其名，也就是說(shuō)這次反過(guò)來(lái)，我們保留的是word->dsh時(shí)，我們只需要把想要的query_ordID，就是我們想要的查詢結(jié)果。這樣，我們就避免了將所有的x過(guò)一遍的尷尬。process_corpus立倒序索引。注意，這里的代碼都是非常精簡(jiǎn)的。在工業(yè)界領(lǐng)域，需要一個(gè)uniqueID，來(lái)對(duì)每一篇文章標(biāo)記上不同的ID，倒序索引也應(yīng)該按照這個(gè)unique_id來(lái)進(jìn)行排序。至于search()函數(shù)，你大概了解它做的事情即可。它會(huì)根據(jù)query_words拿到所有的倒序索引，如果拿不到，就表示有的queryword不存在于任何文章中，直接返回空；拿到之后，運(yùn)行一個(gè)“合并K個(gè)有序數(shù)組”的算法，從中拿到我們想要的ID，并返回。注意，這里用到的算法并不是最優(yōu)的，最優(yōu)的寫法需要用最小堆index。這是一道有名的leetcodehard題，有請(qǐng)參考）我們需InvertedIndex對(duì)于每篇文章也保留單詞的位置信息，這樣一來(lái)，在合并LRU到這一步，終于，你的搜索引擎上線了，有了越來(lái)越多的量（QP）。欣喜驕傲的同你卻服務(wù)“重。經(jīng)段時(shí)調(diào)研發(fā)現(xiàn)重復(fù)索占%所以，最后這部分，我就來(lái)講講緩存和多重繼承的內(nèi)代碼import2class56

init(self,size=32):self.cache=pylru.lrucache(size)defhas(self,returnkeyin9defget(self,returndefset(self,key,self.cache[key]=classBOWInvertedIndexEngineWithCache(BOWInvertedIndexEngine,

init(self):super(BOWInvertedIndexEngineWithCache,self).init()LRUCache.init(self)defsearch(self,ifprint('cachereturnresult=super(BOWInvertedIndexEngineWithCache,self.set(query, returnsearch_engine=輸出found2cachefound2它的代碼很簡(jiǎn)單，LRUCache定義了一個(gè)緩存類，你可以通過(guò)繼承這個(gè)類來(lái)調(diào)用其方法。LRU緩存是一種很經(jīng)典的緩存（同時(shí)，LRU的實(shí)現(xiàn)也是硅谷大廠?？嫉乃惴嬖囶}，這里為了簡(jiǎn)單，我直接使用pylru這個(gè)包），它符合自然界的局部性原理，可以保留最近使用因此，這里的緩存使用起來(lái)也很簡(jiǎn)單，調(diào)用has()函數(shù)get函數(shù)直接返回結(jié)果；如果不在，送入計(jì)算結(jié)果，然后再塞入緩存我們可以看到，BOWInvertedIndexEngineWithCache類，多重繼承了兩個(gè)類。首先需要第一種，super(BOWInvertedIndexEngineWithCache,self).init()直第二種，對(duì)于多重繼承，如果有多個(gè)構(gòu)造函數(shù)需要調(diào)用，我們就必須用傳統(tǒng)的LRUCache.init(self)第二個(gè)需要注意，query(數(shù)被子類BOWInvertedIndexEngineWithCache次重載，但是我還需要調(diào)用BOWInvertedIndexEngine的search()函數(shù)，這時(shí)該怎么辦呢？請(qǐng)看下面這行代碼代碼super(BOWInvertedIndexEngineWithCache,我們可以強(qiáng)行調(diào)用被覆蓋的父類的函數(shù)這樣一來(lái)，我們就簡(jiǎn)潔地實(shí)現(xiàn)了緩存，而且還是在不影響B(tài)OWIvrte的情況下。這部分內(nèi)容希望你多讀幾遍，自己揣摩清楚，通過(guò)這個(gè)例子多多體會(huì)繼承的優(yōu)今天這節(jié)課是面向?qū)ο蟮膶?shí)戰(zhàn)應(yīng)用，相比起前面的理論知識(shí)，內(nèi)容其實(shí)不那么友好。不過(guò)，若你能靜下心來(lái)，仔細(xì)學(xué)習(xí)，理清楚整個(gè)過(guò)程的要點(diǎn)，對(duì)你理解面向?qū)ο蟊?/p>