計(jì)與實(shí)現(xiàn)：從爬蟲到倒排索引的完整實(shí)戰(zhàn))
做畢設(shè)的時(shí)候我選了“基于Python的搜索引擎設(shè)計(jì)與實(shí)現(xiàn)”這個(gè)題目。說實(shí)話剛開始心里挺沒底的因?yàn)樗阉饕孢@東西聽起來就像是個(gè)巨頭才能搞的項(xiàng)目百度谷歌那是多大的工程。但真正把一個(gè)能用的搜索引擎從零寫出來之后我才發(fā)現(xiàn)畢設(shè)級(jí)別的搜索引擎核心并不在于海量數(shù)據(jù)和高并發(fā)而是在于你是否真正吃透了“檢索”這件事本身。這個(gè)項(xiàng)目做完我對(duì)Python的理解、對(duì)數(shù)據(jù)結(jié)構(gòu)的理解、對(duì)整個(gè)軟件工程流程的理解都上了一個(gè)臺(tái)階。這篇文章我就把整個(gè)項(xiàng)目的設(shè)計(jì)思路、核心模塊實(shí)現(xiàn)、踩過的坑和排查技巧全部整理出來。不管你是正在為畢設(shè)選題發(fā)愁還是想深入了解搜索引擎內(nèi)部原理這篇文章都應(yīng)該能給你一個(gè)完整、可落地的參考而且代碼方案都可以直接抄作業(yè)。1. 搜索引擎整體設(shè)計(jì)與架構(gòu)拆解1.1 搜索引擎的本質(zhì)把無序變有序你平時(shí)用百度搜東西背后是數(shù)以千億計(jì)的網(wǎng)頁(yè)但你的畢設(shè)搜索引擎不需要去爬整個(gè)互聯(lián)網(wǎng)。畢設(shè)搜索引擎的本質(zhì)是讓你理解從“抓取數(shù)據(jù)”到“建立索引”再到“查詢返回”的完整鏈路。簡(jiǎn)單說搜索引擎干的事情就是三塊數(shù)據(jù)從哪來、數(shù)據(jù)怎么存、用戶搜的時(shí)候怎么把最相關(guān)的結(jié)果算出來。很多人把搜索引擎和數(shù)據(jù)庫(kù)混淆。數(shù)據(jù)庫(kù)是存什么取什么你查“id 1”它就返回id為1的記錄。搜索引擎不一樣你得處理“模糊的、自然語(yǔ)言的、帶有相關(guān)性語(yǔ)義”的請(qǐng)求。比如用戶搜“Python爬蟲教程”他不是要一個(gè)精確值他想要的是一個(gè)排好序的列表而且最前面的一定是最相關(guān)的。這個(gè)“排序”的能力才是搜索引擎的靈魂。畢設(shè)級(jí)別的搜索引擎我用的是經(jīng)典的“爬蟲 分詞 倒排索引 TF-IDF排序”架構(gòu)。這套架構(gòu)非常成熟業(yè)界主流搜索引擎包括Lucene、Elasticsearch的底層核心思想都離不開它。你只要把這條鏈路走通面試的時(shí)候聊搜索相關(guān)的崗位你都能接得住。1.2 技術(shù)選型為什么全棧用Python選型階段我最糾結(jié)的是核心模塊用Python但是不是有些部分要用C寫后來我想明白一件事畢設(shè)的目的是驗(yàn)證思路、展示能力不是生產(chǎn)環(huán)境做性能比拼。全棧Python的好處有幾點(diǎn)開發(fā)效率極高。爬蟲用requestsBeautifulSoup分詞用jiebaWeb框架用Flask全是Python生態(tài)里最成熟的輪子一天的開發(fā)量頂C一周。代碼可讀性好。答辯的時(shí)候老師翻開你的代碼Python的語(yǔ)法接近偽代碼解釋起來非常輕松。無縫對(duì)接數(shù)據(jù)分析。后期你想做搜索日志分析、點(diǎn)擊率模型Pandas和Scikit-learn直接就能用起來。當(dāng)然Python不是沒有坑。GIL全局鎖讓多線程爬蟲在CPU密集場(chǎng)景下乏力所以我在爬蟲部分用的是多進(jìn)程 異步IO的組合后面會(huì)細(xì)說。另外純Python的處理速度確實(shí)比C慢但畢設(shè)的數(shù)據(jù)量級(jí)幾千到幾萬網(wǎng)頁(yè)P(yáng)ython的處理能力完全夠用而且邏輯清晰遠(yuǎn)比速度重要。1.3 適合畢設(shè)的模塊化架構(gòu)我的項(xiàng)目分成了四個(gè)獨(dú)立的模塊每個(gè)模塊都可以單獨(dú)運(yùn)行和測(cè)試這也是我后來答辯時(shí)的一個(gè)加分項(xiàng)。四個(gè)模塊分別是數(shù)據(jù)采集模塊爬蟲負(fù)責(zé)從種子URL開始抓取網(wǎng)頁(yè)內(nèi)容。內(nèi)容解析與預(yù)處理模塊清洗HTML、提取正文、中文分詞、去除停用詞。索引模塊構(gòu)建倒排索引計(jì)算TF-IDF權(quán)重。檢索與排序模塊接收查詢?cè)~返回排序后的搜索結(jié)果。這四個(gè)模塊間的數(shù)據(jù)流是單向的非常清晰。爬蟲產(chǎn)出原始網(wǎng)頁(yè)文件預(yù)處理產(chǎn)出分詞后的文檔索引模塊產(chǎn)出索引文件檢索模塊讀索引并提供服務(wù)。單向下游的好處是任何一個(gè)模塊壞了之前的產(chǎn)出還在你可以斷點(diǎn)調(diào)試不用每次從頭跑。2. 網(wǎng)頁(yè)數(shù)據(jù)采集爬蟲模塊的設(shè)計(jì)與實(shí)現(xiàn)2.1 從零構(gòu)建一個(gè)小型爬蟲框架爬蟲是整個(gè)搜索引擎的“上游”。你的數(shù)據(jù)源質(zhì)量直接決定了搜索效果。如果爬回來的都是亂碼、廣告、噪聲內(nèi)容后面分詞和索引做得再好也白搭。我這里的爬蟲目標(biāo)站點(diǎn)選的是幾個(gè)知名技術(shù)博客和新聞網(wǎng)站注意要選允許爬取或者有公開API的站點(diǎn)遵守robots協(xié)議是基本素養(yǎng)。核心代碼其實(shí)很短我用的是requests.Session()保持會(huì)話狀態(tài)避免頻繁握手。解析用lxml而不是BeautifulSoup因?yàn)閤path在復(fù)雜HTML結(jié)構(gòu)下定位更精準(zhǔn)速度也快不少。import requests from lxml import etree from urllib.parse import urljoin class Crawler: def __init__(self): self.session requests.Session() self.session.headers.update({ User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 }) def fetch(self, url): try: resp self.session.get(url, timeout5) resp.encoding resp.apparent_encoding return resp.text except Exception as e: print(f抓取失敗 {url}: {e}) return None def parse_links(self, html, base_url): tree etree.HTML(html) hrefs tree.xpath(//a/href) links set() for href in hrefs: full_url urljoin(base_url, href) if full_url.startswith(http): links.add(full_url) return links這里有個(gè)細(xì)節(jié)resp.encoding resp.apparent_encoding非常重要。很多網(wǎng)站用的是utf-8但有些老站是gbk或者gb2312如果你不動(dòng)態(tài)識(shí)別編碼中文部分全是亂碼后面分詞直接崩。實(shí)測(cè)下來加上這行代碼能解決90%的編碼問題。2.2 布隆過濾器去重的核心原理爬蟲最怕的是什么重復(fù)抓取。你抓了一個(gè)頁(yè)面的鏈接AA里面又指向BB里面又指向A如果不做去重爬蟲就會(huì)在兩個(gè)頁(yè)面之間死循環(huán)。我在這里采用的是**布隆過濾器Bloom Filter**做URL去重。布隆過濾器的核心原理是用多個(gè)哈希函數(shù)把URL映射到一個(gè)位圖數(shù)組的多個(gè)位置上全部置為1表示該URL可能存在過。它的好處是空間占用極小、查詢速度極快代價(jià)是有一定的誤判率把沒訪問過的URL誤判為已訪問但不會(huì)漏判已訪問的一定能識(shí)別出來。對(duì)于爬蟲去重來說少量誤判意味著偶爾少爬一個(gè)URL完全不影響整體效果。import hashlib import bitarray class BloomFilter: def __init__(self, size1000000, hash_count7): self.size size self.hash_count hash_count self.bits bitarray.bitarray(size) self.bits.setall(0) def _hashes(self, url): result [] for i in range(self.hash_count): digest hashlib.md5(f{i}:{url}.encode()).hexdigest() result.append(int(digest, 16) % self.size) return result def add(self, url): for pos in self._hashes(url): self.bits[pos] 1 def contains(self, url): for pos in self._hashes(url): if self.bits[pos] 0: return False return True布隆過濾器的兩個(gè)參數(shù)需要注意。位圖大小size和預(yù)估的URL數(shù)量有關(guān)公式是m -n * ln(p) / (ln2)^2其中n是預(yù)計(jì)元素?cái)?shù)量p是可接受的誤判率。如果預(yù)計(jì)爬5萬個(gè)URL誤判率控制在1%的話位圖大小大概需要-50000 * ln(0.01) / 0.48 ≈ 479,000位也就是約58KB哈希函數(shù)個(gè)數(shù)k (m/n) * ln2 ≈ 7。這就是代碼里size1000000, hash_count7的來歷拍腦袋是拍不出這個(gè)參數(shù)的。2.3 爬蟲調(diào)度策略與反爬應(yīng)對(duì)爬蟲的調(diào)度策略我用了廣度優(yōu)先BFS。用一個(gè)隊(duì)列管理待抓取URL每次從隊(duì)列頭部取出一個(gè)URL抓取后把頁(yè)面里的新鏈接加入隊(duì)列尾部。這樣能保證搜索結(jié)果的覆蓋面廣一些不至于沿著一條鏈接一路走到黑。至于反爬我的經(jīng)驗(yàn)是不要硬剛。畢設(shè)爬蟲的目標(biāo)是“拿到足夠的合法數(shù)據(jù)”不是和網(wǎng)站管理員斗智斗勇。我的策略是設(shè)置隨機(jī)延時(shí)time.sleep(random.uniform(1, 3))避免請(qǐng)求頻率過高使用輪換的User-Agent池模擬不同瀏覽器訪問對(duì)頁(yè)面體積做限制超過2MB的頁(yè)面直接丟棄防止內(nèi)存被撐爆如果觸發(fā)驗(yàn)證碼或返回403立刻停止對(duì)該域名的爬取切換到其他源站。很多同學(xué)一開始寫爬蟲很興奮把目標(biāo)站點(diǎn)爬得風(fēng)生水起結(jié)果對(duì)方服務(wù)器直接給你IP封了整個(gè)項(xiàng)目停擺。爬蟲模塊的正確思路是“穩(wěn)”而不是“快”。3. 中文分詞與倒排索引搜索引擎的核心3.1 中文分詞為什么是難點(diǎn)搜索引擎處理英文和中文有一個(gè)巨大的區(qū)別英文單詞之間有空格天然分隔而中文句子里的詞之間沒有明顯的邊界。比如“武漢市長(zhǎng)江大橋”分詞可以是“武漢/市長(zhǎng)/江大橋”也可以是“武漢市/長(zhǎng)江大橋”這個(gè)歧義是中文分詞的核心難點(diǎn)。我用的是jieba分詞庫(kù)它是目前Python中文分詞的事實(shí)標(biāo)準(zhǔn)。jieba支持三種模式精確模式、全模式和搜索引擎模式。精確模式適合文本分析搜索引擎模式適合構(gòu)建索引。注意我構(gòu)建索引時(shí)用的是搜索引擎模式它會(huì)在精確模式的基礎(chǔ)上對(duì)長(zhǎng)詞再次切分提高召回率。import jieba def tokenize(text): # 搜索引擎模式提高召回率 tokens jieba.lcut_for_search(text) # 過濾停用詞和單字 stopwords load_stopwords() return [t for t in tokens if t not in stopwords and len(t.strip()) 1]停用詞表是必須的。中文里的“的、了、是、在、和”這些詞在幾乎每個(gè)文檔里都出現(xiàn)它們對(duì)相關(guān)性排序沒有幫助還占用大量索引空間。停用詞表網(wǎng)上有很多開源版本也可以在實(shí)驗(yàn)過程中自己積累把高頻且無實(shí)義的詞不斷加進(jìn)去。3.2 倒排索引的數(shù)據(jù)結(jié)構(gòu)與構(gòu)建流程倒排索引是搜索引擎的“命根子”。它的設(shè)計(jì)思路直接決定了檢索速度能快到什么程度。正排索引是“文檔ID - 包含的詞”倒排索引反過來了是“詞 - 包含這個(gè)詞的文檔ID列表”。這就是“倒排”兩個(gè)字的由來。為什么要倒排用戶搜“Python爬蟲”系統(tǒng)查倒排索引表直接定位到python這個(gè)詞對(duì)應(yīng)的文檔列表再定位到爬蟲這個(gè)詞對(duì)應(yīng)的文檔列表然后取交集就能知道哪些文檔同時(shí)包含這兩個(gè)詞。如果用了正排索引你得遍歷每一篇文檔看看它是否包含“Python”和“爬蟲”那效率就是災(zāi)難級(jí)的。我用的索引結(jié)構(gòu)是Python的字典 列表# 倒排索引結(jié)構(gòu) # { 詞項(xiàng): [(文檔ID, 詞頻TF), (文檔ID, 詞頻TF), ...] } inverted_index {} def build_index(doc_id, token_list): token_count {} for token in token_list: token_count[token] token_count.get(token, 0) 1 for token, count in token_count.items(): if token not in inverted_index: inverted_index[token] [] inverted_index[token].append((doc_id, count))這里每個(gè)詞項(xiàng)后面存的不是單純的文檔ID而是**文檔ID 詞頻TF**的元組。詞頻是后面計(jì)算相關(guān)性權(quán)重的重要輸入。你在一篇5000字的文章里提了50次“Python”和在一篇500字的短文里提了5次“Python”顯然前者的相關(guān)度更高當(dāng)然歸一化后是后者更高所以詞頻必須記錄。索引構(gòu)建完成后我把它用JSON序列化保存到本地文件。Python的字典序列化非常方便但注意數(shù)據(jù)量大時(shí)JSON的讀寫效率不高你可以改用picklePython原生二進(jìn)制格式或者sqlite3輕量級(jí)數(shù)據(jù)庫(kù)。我做畢設(shè)時(shí)數(shù)據(jù)量不大JSON完全夠用而且答辯時(shí)直接打開文件向老師展示數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)格式非常直觀。3.3 TF-IDF權(quán)重計(jì)算與實(shí)現(xiàn)建立好倒排索引之后面臨的關(guān)鍵問題是**怎么判斷哪個(gè)文檔更相關(guān)**這里我用的是經(jīng)典算法 TF-IDF全稱Term Frequency-Inverse Document Frequency翻譯過來就是“詞頻-逆文檔頻率”。TF-IDF的直覺很簡(jiǎn)單它由兩部分構(gòu)成TF詞頻詞在文檔中出現(xiàn)次數(shù)越多越相關(guān)。但純看次數(shù)不公平長(zhǎng)文檔天然比短文檔容易積累更多詞頻所以一般做歸一化處理比如除以該文檔的總詞數(shù)。IDF逆文檔頻率詞在整個(gè)文檔集合中越罕見攜帶的信息量越大。比如“優(yōu)化”這個(gè)詞在技術(shù)文章中到處都是而“布隆過濾器”這個(gè)詞只出現(xiàn)在少數(shù)幾篇深入文章中那后者對(duì)區(qū)分文檔的貢獻(xiàn)更大。數(shù)學(xué)公式是TF-IDF(t, d) TF(t, d) * IDF(t)其中IDF(t) log(N / df_t)N是文檔總數(shù)df_t是包含詞t的文檔數(shù)。為什么取log因?yàn)槲臋n總數(shù)和包含該詞的文檔數(shù)的比值可能非常懸殊取log可以壓縮數(shù)值范圍避免某個(gè)詞因?yàn)檫^于稀缺而權(quán)重爆炸。import math class Indexer: def __init__(self, inverted_index, doc_count): self.inverted_index inverted_index self.doc_count doc_count def compute_tfidf(self, token, doc_id, doc_token_count): # TF詞在文檔中出現(xiàn)的次數(shù) / 文檔總詞數(shù) doc_posting dict(self.inverted_index[token]) tf doc_posting.get(doc_id, 0) / doc_token_count # IDFlog(總文檔數(shù) / 包含該詞的文檔數(shù)) df len(self.inverted_index[token]) idf math.log((self.doc_count 1) / (df 1)) 1 return tf * idf這里有個(gè)小細(xì)節(jié)是(self.doc_count 1) / (df 1)) 1為什么都加1因?yàn)槿绻粋€(gè)詞在所有文檔中都出現(xiàn)了比如某些高頻詞沒被停用詞表完全清洗掉idf log(N/N) 0這個(gè)詞的權(quán)重就清零了。加1是為了做平滑處理防止除數(shù)為零或權(quán)重歸零的情況。4. 檢索排序與查詢處理從輸入到結(jié)果的完整鏈路4.1 查詢解析與檢索流程用戶輸入查詢?cè)~“Python爬蟲怎么入門”這個(gè)查詢?cè)~不能直接拿去檢索。檢索模塊需要經(jīng)過和索引時(shí)完全相同的預(yù)處理流程分詞 - 過濾停用詞 - 得到查詢的Token列表。這個(gè)一致性非常重要如果你索引時(shí)用的是“python爬蟲”這種處理方式查詢時(shí)卻用了另一種方式兩邊就對(duì)不上了召回率會(huì)慘不忍睹。匹配階段我采用的是“包含所有查詢?cè)~AND”策略。也就是說搜“Python爬蟲”返回的文檔必須同時(shí)包含“Python”和“爬蟲”兩個(gè)詞經(jīng)過分詞后查詢Token可能包含多個(gè)。這個(gè)策略的好處是結(jié)果集非常精確壞處是如果用戶輸入了三個(gè)以上的關(guān)鍵詞可能一個(gè)文檔都匹配不上。實(shí)際使用中AND策略對(duì)畢設(shè)項(xiàng)目更合適因?yàn)槟銈兊奈臋n集本身就小寧可少結(jié)果也要保證權(quán)威相關(guān)。業(yè)界搜索引擎用的是“包含任一查詢?cè)~OR)”召回再用排序模型把最相關(guān)的頂上去那是工程上的選擇畢設(shè)階段掌握AND其實(shí)夠了。在Python中實(shí)現(xiàn)AND檢索已經(jīng)簡(jiǎn)化為先從倒排索引里拿到每個(gè)查詢?cè)~對(duì)應(yīng)的文檔ID列表然后做交集操作。寫完這一瞬你就能體會(huì)到倒排索引的效率優(yōu)勢(shì)了。def search(self, query_tokens): if not query_tokens: return [] # 得到每個(gè)詞的文檔ID集合 doc_sets [] for token in query_tokens: posting self.inverted_index.get(token, []) doc_set set([doc_id for doc_id, _ in posting]) if not doc_set: return [] # 有一個(gè)詞沒匹配到直接返回空 doc_sets.append(doc_set) # 取交集所有查詢?cè)~都出現(xiàn)的文檔 result_docs set.intersection(*doc_sets) return list(result_docs)4.2 排序算法的設(shè)計(jì)與優(yōu)化拿到候選文檔集合后下一步就是排序。最開始我直接用“匹配詞數(shù)量”排序也就是誰(shuí)的文檔里包含的關(guān)鍵詞種類更多誰(shuí)排前面。這個(gè)策略在只有一個(gè)查詢?cè)~時(shí)完全失效因?yàn)樗腥说钠ヅ湓~數(shù)量都一樣。后來我引入了經(jīng)典方案把每個(gè)查詢?cè)~的TF-IDF分值相加作為文檔的最終相關(guān)度。def rank_docs(self, candidate_docs, query_tokens, doc_token_count_map): scores {} for doc_id in candidate_docs: total_score 0.0 for token in query_tokens: total_score self.compute_tfidf(token, doc_id, doc_token_count_map[doc_id]) scores[doc_id] total_score # 按得分降序排列 ranked_docs sorted(scores.items(), keylambda x: x[1], reverseTrue) return ranked_docs這個(gè)算法的效果怎么樣直觀地說如果一篇文章在開頭、正文、結(jié)尾等多個(gè)位置多次出現(xiàn)“Python”和“爬蟲”且這些詞在你的整個(gè)文檔集中不算特別爛大街那它的得分就會(huì)很高排名自然靠前。這個(gè)排序算法雖然樸素但已經(jīng)是“基于內(nèi)容的檢索排序”的標(biāo)準(zhǔn)范式了。優(yōu)化的方向我調(diào)研過很多比如給標(biāo)題的匹配詞加更高的權(quán)重標(biāo)題權(quán)重系數(shù)2.0因?yàn)槲恼聵?biāo)題往往是內(nèi)容的濃縮比如引入文檔長(zhǎng)度歸一化防止長(zhǎng)文刷分比如引入PageRank需要鏈接關(guān)系數(shù)據(jù)爬蟲模塊里可以順手抽取外鏈。我實(shí)際做了標(biāo)題加權(quán)和長(zhǎng)度歸一化效果提升非常明顯推薦大家至少做到這一步。4.3 檢索接口與前端展示后端我用的是Flask一個(gè)輕量級(jí)的Web框架。接口設(shè)計(jì)遵循RESTful風(fēng)格前端用一個(gè)簡(jiǎn)單的HTML頁(yè)面 fetchAPI完成異步搜索。搜索框、結(jié)果列表、耗時(shí)統(tǒng)計(jì)、結(jié)果數(shù)量四要素一個(gè)不能少。app.route(/api/search, methods[GET]) def api_search(): query request.args.get(q, ) start time.time() results search_engine.search(query) elapsed time.time() - start return jsonify({ query: query, elapsed_ms: round(elapsed * 1000, 2), total_results: len(results), results: results[:50] })前端展示里有一個(gè)容易被忽略的點(diǎn)關(guān)鍵詞高亮。把搜索詞在結(jié)果標(biāo)題和摘要中高亮顯示會(huì)極大地提升用戶體驗(yàn)。實(shí)現(xiàn)方式很簡(jiǎn)單拿到查詢?cè)~列表后把結(jié)果文本中的這些詞用HTML標(biāo)簽包裹加上突出顏色。注意高亮?xí)r的分詞粒度要和查詢一致否則會(huì)高亮不上。還有一個(gè)經(jīng)驗(yàn)是結(jié)果頁(yè)里一定要顯示搜索耗時(shí)。這不僅是為了好看更是為了向答辯老師直觀展示倒排索引的查詢性能。我做的畢設(shè)項(xiàng)目中在5000篇文檔的索引下一次搜索在10毫秒以內(nèi)完成這種“肉眼可見的快”比任何PPT上的性能對(duì)比圖都有說服力。5. 常見問題與排查技巧實(shí)錄5.1 爬蟲模塊的典型問題問題1抓回來的網(wǎng)頁(yè)全是二進(jìn)制亂碼。原因通常是響應(yīng)內(nèi)容被gzip壓縮了而你沒有解壓。requests庫(kù)其實(shí)自帶解壓功能但如果你用Session且手動(dòng)處理了響應(yīng)流就可能繞過這層。排查方法是打印resp.headers.get(Content-Encoding)看到gzip就說明需要解壓。request庫(kù)正常情況下會(huì)自動(dòng)處理這個(gè)問題多數(shù)出現(xiàn)在你把streamTrue打開之后又手動(dòng)讀取了原始流。問題2XPath定位不準(zhǔn)確匹配不到鏈接。很多同學(xué)直接復(fù)制瀏覽器F12里看到的XPath結(jié)果在代碼里跑不通。原因是瀏覽器里復(fù)制出來的XPath往往包含了很多div[2]/div[3]這樣的層級(jí)索引頁(yè)面結(jié)構(gòu)稍微一變化就失效。我的建議優(yōu)先用相對(duì)路徑和屬性定位比如//a[contains(href, article)]這種寫法魯棒性好得多。另外記得用urljoin拼接相對(duì)鏈接HTML里的href/foo是相對(duì)路徑不拼接的話你抓回來的URL全是殘廢的。問題3爬蟲越跑越慢。大概率是請(qǐng)求超時(shí)設(shè)置太長(zhǎng)或者沒有限制單個(gè)域名的并發(fā)請(qǐng)求。我后來加了每域名延時(shí)隊(duì)列每個(gè)域名最多每2秒處理一個(gè)請(qǐng)求速度確實(shí)慢了但穩(wěn)定性極大地提升了。5.2 索引與檢索的排查思路問題1搜索一個(gè)肯定存在的內(nèi)容卻返回空結(jié)果。最常見的坑是查詢預(yù)處理和索引預(yù)處理的流程不一致。比如你索引時(shí)把小寫和大寫歸并了Python轉(zhuǎn)成python但查詢時(shí)沒有做同樣的轉(zhuǎn)換。很多同學(xué)喜歡“先跑通再優(yōu)化”結(jié)果優(yōu)化了一邊忘了另一邊。排查時(shí)用同樣的輸入分別在索引代碼和查詢代碼里跑一遍對(duì)比輸出Token列表是否一致。問題2檢索結(jié)果的排序不符合直覺。比如搜“Python”時(shí)一篇只提到一次“Python”的文章比一篇深入講“Python”的文章排得還靠前。這時(shí)候要檢查IDF的計(jì)算。如果包含“Python”的文檔只有2篇而你要搜的文檔集合總共只有3篇那idf log(3/2) 0.405幾乎沒起到區(qū)分作用。這就是文檔集太小導(dǎo)致的IDF失效。解決方法是擴(kuò)充文檔集或者把IDF分母里包含該詞的文檔數(shù)做平滑處理。問題3檢索速度越來越慢。如果索引數(shù)據(jù)量上來了但檢索還是幾十毫秒甚至幾百毫秒八成是你在檢索時(shí)做了重復(fù)計(jì)算。比如每次查詢都把整個(gè)索引重新load一遍或者把TF-IDF計(jì)算放在查詢鏈路里而不是構(gòu)建時(shí)預(yù)先算好。正確的做法是索引構(gòu)建時(shí)就把每個(gè)詞在每個(gè)文檔中的TF-IDF預(yù)計(jì)算好存下來查詢時(shí)只做查表求和不做任何乘法和開方運(yùn)算。5.3 性能優(yōu)化與擴(kuò)展方向畢設(shè)答辯時(shí)老師最喜歡問的問題是“如果讓你繼續(xù)做你會(huì)怎么優(yōu)化”這里給你三個(gè)方向既能展示你的思考深度又不會(huì)給自己挖坑方向一引入向量空間模型VSM和余弦相似度。把每個(gè)文檔表示成一個(gè)詞向量查詢也變成一個(gè)詞向量?jī)烧邐A角越接近說明越相關(guān)。這個(gè)思路是TF-IDF的自然延伸代碼實(shí)現(xiàn)也就幾十行但寫進(jìn)論文里能顯著提升理論高度。方向二構(gòu)建多級(jí)索引加速查詢。對(duì)倒排索引按照文檔ID排序存儲(chǔ)可以方便做跳表加速skip pointer。用戶在查詢時(shí)先在熱詞索引里撈結(jié)果冷門詞再走全量索引降低耗時(shí)。這個(gè)方向涉及算法和數(shù)據(jù)結(jié)構(gòu)的知識(shí)深度。方向三搜索結(jié)果緩存。用戶搜索的詞頻分布高度傾斜一小部分熱門查詢占據(jù)了絕大多數(shù)流量。把熱門查詢的結(jié)果緩存到內(nèi)存里能大幅減少重復(fù)計(jì)算。這個(gè)方向明顯有工程實(shí)踐的價(jià)值而且容易和Redis等知識(shí)點(diǎn)聯(lián)動(dòng)起來。在我實(shí)際做項(xiàng)目的過程里把爬蟲數(shù)據(jù)量從2000篇擴(kuò)展到1萬篇時(shí)明顯感受到存儲(chǔ)和速度的數(shù)據(jù)壓力。當(dāng)時(shí)我也想過用數(shù)據(jù)庫(kù)比如MySQL或SQLite來存倒排索引后來發(fā)現(xiàn)Python的json存儲(chǔ)和加載在1萬篇文檔下仍在毫秒級(jí)就沒多折騰。如果你想要一個(gè)更加“正式”的版本來應(yīng)對(duì)答辯也可以用SQLite存詞項(xiàng)和倒排列表順便展示一下你的數(shù)據(jù)庫(kù)設(shè)計(jì)能力也是加分項(xiàng)。結(jié)語(yǔ) | 關(guān)于這個(gè)項(xiàng)目的一些個(gè)人體會(huì)最后說點(diǎn)實(shí)在的。做這個(gè)畢設(shè)項(xiàng)目技術(shù)上我能總結(jié)的東西很多但最大的收獲反而不是技術(shù)本身。搜索引擎這個(gè)題目它像是一個(gè)“算法放大器”你在數(shù)據(jù)結(jié)構(gòu)課上學(xué)的每一種抽象哈希、樹、圖在搜索引擎里都有真實(shí)的、迫切的用武之地。以前我學(xué)布隆過濾器覺得是為了考試當(dāng)我看到爬蟲死循環(huán)的那一刻我才明白它解決的到底是什么問題。當(dāng)時(shí)踩過的坑和調(diào)整后的經(jīng)驗(yàn)現(xiàn)在復(fù)盤后整理成下面這幾個(gè)建議給正在做類似項(xiàng)目的同學(xué)作為參考不要一開始就追求“大而全”。先抓100個(gè)網(wǎng)頁(yè)跑通整個(gè)搜索流程然后再逐步擴(kuò)展數(shù)據(jù)量。你要知道整個(gè)系統(tǒng)能夠“轉(zhuǎn)起來”帶給你的信心遠(yuǎn)比你悶頭優(yōu)化某個(gè)模塊要大得多。寫代碼時(shí)養(yǎng)成“模塊可單獨(dú)驗(yàn)證”的習(xí)慣。爬蟲抓下來的數(shù)據(jù)是否完整、分詞結(jié)果是否正確、索引是否可加載——每一步都要能獨(dú)立驗(yàn)證。項(xiàng)目后期的調(diào)試時(shí)間幾乎都花在“回溯定位是哪一層出了問題”上模塊驗(yàn)證能幫你節(jié)省至少一半時(shí)間。項(xiàng)目進(jìn)度要及時(shí)備份。第一次我寫完索引構(gòu)建代碼后清理了爬蟲緩存發(fā)現(xiàn)索引文件被誤刪了整個(gè)索引要重新構(gòu)建。從那以后我都是把關(guān)鍵模塊的產(chǎn)出物備份到不同目錄這個(gè)習(xí)慣幫我在答辯前避免了很多麻煩。搜索這個(gè)領(lǐng)域表面上是技術(shù)工程實(shí)際上還牽扯到對(duì)“用戶意圖”的理解對(duì)信息的組織方式等等挑戰(zhàn)。你的Python畢設(shè)搜索項(xiàng)目做完之后如果對(duì)這個(gè)領(lǐng)域還保持著興趣往Elasticsearch的方向了解就是一個(gè)很好的延伸選擇。畢竟從自己寫一個(gè)“五臟俱全”的搜索引擎開始你會(huì)對(duì)檢索這件事形成更深層的肌肉記憶這個(gè)東西的價(jià)值是長(zhǎng)遠(yuǎn)的。 基于Python的搜索引擎設(shè)計(jì)與實(shí)現(xiàn)：從爬蟲到倒排索引的完整實(shí)戰(zhàn)
做畢設(shè)的時(shí)候我選了“基于Python的搜索引擎設(shè)計(jì)與實(shí)現(xiàn)”這個(gè)題目。說實(shí)話剛開始心里挺沒底的因?yàn)樗阉饕孢@東西聽起來就像是個(gè)巨頭才能搞的項(xiàng)目百度谷歌那是多大的工程。但真正把一個(gè)能用的搜索引擎從零寫出來之后我才發(fā)現(xiàn)畢設(shè)級(jí)別的搜索引擎核心并不在于海量數(shù)據(jù)和高并發(fā)而是在于你是否真正吃透了“檢索”這件事本身。這個(gè)項(xiàng)目做完我對(duì)Python的理解、對(duì)數(shù)據(jù)結(jié)構(gòu)的理解、對(duì)整個(gè)軟件工程流程的理解都上了一個(gè)臺(tái)階。這篇文章我就把整個(gè)項(xiàng)目的設(shè)計(jì)思路、核心模塊實(shí)現(xiàn)、踩過的坑和排查技巧全部整理出來。不管你是正在為畢設(shè)選題發(fā)愁還是想深入了解搜索引擎內(nèi)部原理這篇文章都應(yīng)該能給你一個(gè)完整、可落地的參考而且代碼方案都可以直接抄作業(yè)。1. 搜索引擎整體設(shè)計(jì)與架構(gòu)拆解1.1 搜索引擎的本質(zhì)把無序變有序你平時(shí)用百度搜東西背后是數(shù)以千億計(jì)的網(wǎng)頁(yè)但你的畢設(shè)搜索引擎不需要去爬整個(gè)互聯(lián)網(wǎng)。畢設(shè)搜索引擎的本質(zhì)是讓你理解從“抓取數(shù)據(jù)”到“建立索引”再到“查詢返回”的完整鏈路。簡(jiǎn)單說搜索引擎干的事情就是三塊數(shù)據(jù)從哪來、數(shù)據(jù)怎么存、用戶搜的時(shí)候怎么把最相關(guān)的結(jié)果算出來。很多人把搜索引擎和數(shù)據(jù)庫(kù)混淆。數(shù)據(jù)庫(kù)是存什么取什么你查“id 1”它就返回id為1的記錄。搜索引擎不一樣你得處理“模糊的、自然語(yǔ)言的、帶有相關(guān)性語(yǔ)義”的請(qǐng)求。比如用戶搜“Python爬蟲教程”他不是要一個(gè)精確值他想要的是一個(gè)排好序的列表而且最前面的一定是最相關(guān)的。這個(gè)“排序”的能力才是搜索引擎的靈魂。畢設(shè)級(jí)別的搜索引擎我用的是經(jīng)典的“爬蟲 分詞 倒排索引 TF-IDF排序”架構(gòu)。這套架構(gòu)非常成熟業(yè)界主流搜索引擎包括Lucene、Elasticsearch的底層核心思想都離不開它。你只要把這條鏈路走通面試的時(shí)候聊搜索相關(guān)的崗位你都能接得住。1.2 技術(shù)選型為什么全棧用Python選型階段我最糾結(jié)的是核心模塊用Python但是不是有些部分要用C寫后來我想明白一件事畢設(shè)的目的是驗(yàn)證思路、展示能力不是生產(chǎn)環(huán)境做性能比拼。全棧Python的好處有幾點(diǎn)開發(fā)效率極高。爬蟲用requestsBeautifulSoup分詞用jiebaWeb框架用Flask全是Python生態(tài)里最成熟的輪子一天的開發(fā)量頂C一周。代碼可讀性好。答辯的時(shí)候老師翻開你的代碼Python的語(yǔ)法接近偽代碼解釋起來非常輕松。無縫對(duì)接數(shù)據(jù)分析。后期你想做搜索日志分析、點(diǎn)擊率模型Pandas和Scikit-learn直接就能用起來。當(dāng)然Python不是沒有坑。GIL全局鎖讓多線程爬蟲在CPU密集場(chǎng)景下乏力所以我在爬蟲部分用的是多進(jìn)程 異步IO的組合后面會(huì)細(xì)說。另外純Python的處理速度確實(shí)比C慢但畢設(shè)的數(shù)據(jù)量級(jí)幾千到幾萬網(wǎng)頁(yè)P(yáng)ython的處理能力完全夠用而且邏輯清晰遠(yuǎn)比速度重要。1.3 適合畢設(shè)的模塊化架構(gòu)我的項(xiàng)目分成了四個(gè)獨(dú)立的模塊每個(gè)模塊都可以單獨(dú)運(yùn)行和測(cè)試這也是我后來答辯時(shí)的一個(gè)加分項(xiàng)。四個(gè)模塊分別是數(shù)據(jù)采集模塊爬蟲負(fù)責(zé)從種子URL開始抓取網(wǎng)頁(yè)內(nèi)容。內(nèi)容解析與預(yù)處理模塊清洗HTML、提取正文、中文分詞、去除停用詞。索引模塊構(gòu)建倒排索引計(jì)算TF-IDF權(quán)重。檢索與排序模塊接收查詢?cè)~返回排序后的搜索結(jié)果。這四個(gè)模塊間的數(shù)據(jù)流是單向的非常清晰。爬蟲產(chǎn)出原始網(wǎng)頁(yè)文件預(yù)處理產(chǎn)出分詞后的文檔索引模塊產(chǎn)出索引文件檢索模塊讀索引并提供服務(wù)。單向下游的好處是任何一個(gè)模塊壞了之前的產(chǎn)出還在你可以斷點(diǎn)調(diào)試不用每次從頭跑。2. 網(wǎng)頁(yè)數(shù)據(jù)采集爬蟲模塊的設(shè)計(jì)與實(shí)現(xiàn)2.1 從零構(gòu)建一個(gè)小型爬蟲框架爬蟲是整個(gè)搜索引擎的“上游”。你的數(shù)據(jù)源質(zhì)量直接決定了搜索效果。如果爬回來的都是亂碼、廣告、噪聲內(nèi)容后面分詞和索引做得再好也白搭。我這里的爬蟲目標(biāo)站點(diǎn)選的是幾個(gè)知名技術(shù)博客和新聞網(wǎng)站注意要選允許爬取或者有公開API的站點(diǎn)遵守robots協(xié)議是基本素養(yǎng)。核心代碼其實(shí)很短我用的是requests.Session()保持會(huì)話狀態(tài)避免頻繁握手。解析用lxml而不是BeautifulSoup因?yàn)閤path在復(fù)雜HTML結(jié)構(gòu)下定位更精準(zhǔn)速度也快不少。import requests from lxml import etree from urllib.parse import urljoin class Crawler: def __init__(self): self.session requests.Session() self.session.headers.update({ User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 }) def fetch(self, url): try: resp self.session.get(url, timeout5) resp.encoding resp.apparent_encoding return resp.text except Exception as e: print(f抓取失敗 {url}: {e}) return None def parse_links(self, html, base_url): tree etree.HTML(html) hrefs tree.xpath(//a/href) links set() for href in hrefs: full_url urljoin(base_url, href) if full_url.startswith(http): links.add(full_url) return links這里有個(gè)細(xì)節(jié)resp.encoding resp.apparent_encoding非常重要。很多網(wǎng)站用的是utf-8但有些老站是gbk或者gb2312如果你不動(dòng)態(tài)識(shí)別編碼中文部分全是亂碼后面分詞直接崩。實(shí)測(cè)下來加上這行代碼能解決90%的編碼問題。2.2 布隆過濾器去重的核心原理爬蟲最怕的是什么重復(fù)抓取。你抓了一個(gè)頁(yè)面的鏈接AA里面又指向BB里面又指向A如果不做去重爬蟲就會(huì)在兩個(gè)頁(yè)面之間死循環(huán)。我在這里采用的是**布隆過濾器Bloom Filter**做URL去重。布隆過濾器的核心原理是用多個(gè)哈希函數(shù)把URL映射到一個(gè)位圖數(shù)組的多個(gè)位置上全部置為1表示該URL可能存在過。它的好處是空間占用極小、查詢速度極快代價(jià)是有一定的誤判率把沒訪問過的URL誤判為已訪問但不會(huì)漏判已訪問的一定能識(shí)別出來。對(duì)于爬蟲去重來說少量誤判意味著偶爾少爬一個(gè)URL完全不影響整體效果。import hashlib import bitarray class BloomFilter: def __init__(self, size1000000, hash_count7): self.size size self.hash_count hash_count self.bits bitarray.bitarray(size) self.bits.setall(0) def _hashes(self, url): result [] for i in range(self.hash_count): digest hashlib.md5(f{i}:{url}.encode()).hexdigest() result.append(int(digest, 16) % self.size) return result def add(self, url): for pos in self._hashes(url): self.bits[pos] 1 def contains(self, url): for pos in self._hashes(url): if self.bits[pos] 0: return False return True布隆過濾器的兩個(gè)參數(shù)需要注意。位圖大小size和預(yù)估的URL數(shù)量有關(guān)公式是m -n * ln(p) / (ln2)^2其中n是預(yù)計(jì)元素?cái)?shù)量p是可接受的誤判率。如果預(yù)計(jì)爬5萬個(gè)URL誤判率控制在1%的話位圖大小大概需要-50000 * ln(0.01) / 0.48 ≈ 479,000位也就是約58KB哈希函數(shù)個(gè)數(shù)k (m/n) * ln2 ≈ 7。這就是代碼里size1000000, hash_count7的來歷拍腦袋是拍不出這個(gè)參數(shù)的。2.3 爬蟲調(diào)度策略與反爬應(yīng)對(duì)爬蟲的調(diào)度策略我用了廣度優(yōu)先BFS。用一個(gè)隊(duì)列管理待抓取URL每次從隊(duì)列頭部取出一個(gè)URL抓取后把頁(yè)面里的新鏈接加入隊(duì)列尾部。這樣能保證搜索結(jié)果的覆蓋面廣一些不至于沿著一條鏈接一路走到黑。至于反爬我的經(jīng)驗(yàn)是不要硬剛。畢設(shè)爬蟲的目標(biāo)是“拿到足夠的合法數(shù)據(jù)”不是和網(wǎng)站管理員斗智斗勇。我的策略是設(shè)置隨機(jī)延時(shí)time.sleep(random.uniform(1, 3))避免請(qǐng)求頻率過高使用輪換的User-Agent池模擬不同瀏覽器訪問對(duì)頁(yè)面體積做限制超過2MB的頁(yè)面直接丟棄防止內(nèi)存被撐爆如果觸發(fā)驗(yàn)證碼或返回403立刻停止對(duì)該域名的爬取切換到其他源站。很多同學(xué)一開始寫爬蟲很興奮把目標(biāo)站點(diǎn)爬得風(fēng)生水起結(jié)果對(duì)方服務(wù)器直接給你IP封了整個(gè)項(xiàng)目停擺。爬蟲模塊的正確思路是“穩(wěn)”而不是“快”。3. 中文分詞與倒排索引搜索引擎的核心3.1 中文分詞為什么是難點(diǎn)搜索引擎處理英文和中文有一個(gè)巨大的區(qū)別英文單詞之間有空格天然分隔而中文句子里的詞之間沒有明顯的邊界。比如“武漢市長(zhǎng)江大橋”分詞可以是“武漢/市長(zhǎng)/江大橋”也可以是“武漢市/長(zhǎng)江大橋”這個(gè)歧義是中文分詞的核心難點(diǎn)。我用的是jieba分詞庫(kù)它是目前Python中文分詞的事實(shí)標(biāo)準(zhǔn)。jieba支持三種模式精確模式、全模式和搜索引擎模式。精確模式適合文本分析搜索引擎模式適合構(gòu)建索引。注意我構(gòu)建索引時(shí)用的是搜索引擎模式它會(huì)在精確模式的基礎(chǔ)上對(duì)長(zhǎng)詞再次切分提高召回率。import jieba def tokenize(text): # 搜索引擎模式提高召回率 tokens jieba.lcut_for_search(text) # 過濾停用詞和單字 stopwords load_stopwords() return [t for t in tokens if t not in stopwords and len(t.strip()) 1]停用詞表是必須的。中文里的“的、了、是、在、和”這些詞在幾乎每個(gè)文檔里都出現(xiàn)它們對(duì)相關(guān)性排序沒有幫助還占用大量索引空間。停用詞表網(wǎng)上有很多開源版本也可以在實(shí)驗(yàn)過程中自己積累把高頻且無實(shí)義的詞不斷加進(jìn)去。3.2 倒排索引的數(shù)據(jù)結(jié)構(gòu)與構(gòu)建流程倒排索引是搜索引擎的“命根子”。它的設(shè)計(jì)思路直接決定了檢索速度能快到什么程度。正排索引是“文檔ID - 包含的詞”倒排索引反過來了是“詞 - 包含這個(gè)詞的文檔ID列表”。這就是“倒排”兩個(gè)字的由來。為什么要倒排用戶搜“Python爬蟲”系統(tǒng)查倒排索引表直接定位到python這個(gè)詞對(duì)應(yīng)的文檔列表再定位到爬蟲這個(gè)詞對(duì)應(yīng)的文檔列表然后取交集就能知道哪些文檔同時(shí)包含這兩個(gè)詞。如果用了正排索引你得遍歷每一篇文檔看看它是否包含“Python”和“爬蟲”那效率就是災(zāi)難級(jí)的。我用的索引結(jié)構(gòu)是Python的字典 列表# 倒排索引結(jié)構(gòu) # { 詞項(xiàng): [(文檔ID, 詞頻TF), (文檔ID, 詞頻TF), ...] } inverted_index {} def build_index(doc_id, token_list): token_count {} for token in token_list: token_count[token] token_count.get(token, 0) 1 for token, count in token_count.items(): if token not in inverted_index: inverted_index[token] [] inverted_index[token].append((doc_id, count))這里每個(gè)詞項(xiàng)后面存的不是單純的文檔ID而是**文檔ID 詞頻TF**的元組。詞頻是后面計(jì)算相關(guān)性權(quán)重的重要輸入。你在一篇5000字的文章里提了50次“Python”和在一篇500字的短文里提了5次“Python”顯然前者的相關(guān)度更高當(dāng)然歸一化后是后者更高所以詞頻必須記錄。索引構(gòu)建完成后我把它用JSON序列化保存到本地文件。Python的字典序列化非常方便但注意數(shù)據(jù)量大時(shí)JSON的讀寫效率不高你可以改用picklePython原生二進(jìn)制格式或者sqlite3輕量級(jí)數(shù)據(jù)庫(kù)。我做畢設(shè)時(shí)數(shù)據(jù)量不大JSON完全夠用而且答辯時(shí)直接打開文件向老師展示數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)格式非常直觀。3.3 TF-IDF權(quán)重計(jì)算與實(shí)現(xiàn)建立好倒排索引之后面臨的關(guān)鍵問題是**怎么判斷哪個(gè)文檔更相關(guān)**這里我用的是經(jīng)典算法 TF-IDF全稱Term Frequency-Inverse Document Frequency翻譯過來就是“詞頻-逆文檔頻率”。TF-IDF的直覺很簡(jiǎn)單它由兩部分構(gòu)成TF詞頻詞在文檔中出現(xiàn)次數(shù)越多越相關(guān)。但純看次數(shù)不公平長(zhǎng)文檔天然比短文檔容易積累更多詞頻所以一般做歸一化處理比如除以該文檔的總詞數(shù)。IDF逆文檔頻率詞在整個(gè)文檔集合中越罕見攜帶的信息量越大。比如“優(yōu)化”這個(gè)詞在技術(shù)文章中到處都是而“布隆過濾器”這個(gè)詞只出現(xiàn)在少數(shù)幾篇深入文章中那后者對(duì)區(qū)分文檔的貢獻(xiàn)更大。數(shù)學(xué)公式是TF-IDF(t, d) TF(t, d) * IDF(t)其中IDF(t) log(N / df_t)N是文檔總數(shù)df_t是包含詞t的文檔數(shù)。為什么取log因?yàn)槲臋n總數(shù)和包含該詞的文檔數(shù)的比值可能非常懸殊取log可以壓縮數(shù)值范圍避免某個(gè)詞因?yàn)檫^于稀缺而權(quán)重爆炸。import math class Indexer: def __init__(self, inverted_index, doc_count): self.inverted_index inverted_index self.doc_count doc_count def compute_tfidf(self, token, doc_id, doc_token_count): # TF詞在文檔中出現(xiàn)的次數(shù) / 文檔總詞數(shù) doc_posting dict(self.inverted_index[token]) tf doc_posting.get(doc_id, 0) / doc_token_count # IDFlog(總文檔數(shù) / 包含該詞的文檔數(shù)) df len(self.inverted_index[token]) idf math.log((self.doc_count 1) / (df 1)) 1 return tf * idf這里有個(gè)小細(xì)節(jié)是(self.doc_count 1) / (df 1)) 1為什么都加1因?yàn)槿绻粋€(gè)詞在所有文檔中都出現(xiàn)了比如某些高頻詞沒被停用詞表完全清洗掉idf log(N/N) 0這個(gè)詞的權(quán)重就清零了。加1是為了做平滑處理防止除數(shù)為零或權(quán)重歸零的情況。4. 檢索排序與查詢處理從輸入到結(jié)果的完整鏈路4.1 查詢解析與檢索流程用戶輸入查詢?cè)~“Python爬蟲怎么入門”這個(gè)查詢?cè)~不能直接拿去檢索。檢索模塊需要經(jīng)過和索引時(shí)完全相同的預(yù)處理流程分詞 - 過濾停用詞 - 得到查詢的Token列表。這個(gè)一致性非常重要如果你索引時(shí)用的是“python爬蟲”這種處理方式查詢時(shí)卻用了另一種方式兩邊就對(duì)不上了召回率會(huì)慘不忍睹。匹配階段我采用的是“包含所有查詢?cè)~AND”策略。也就是說搜“Python爬蟲”返回的文檔必須同時(shí)包含“Python”和“爬蟲”兩個(gè)詞經(jīng)過分詞后查詢Token可能包含多個(gè)。這個(gè)策略的好處是結(jié)果集非常精確壞處是如果用戶輸入了三個(gè)以上的關(guān)鍵詞可能一個(gè)文檔都匹配不上。實(shí)際使用中AND策略對(duì)畢設(shè)項(xiàng)目更合適因?yàn)槟銈兊奈臋n集本身就小寧可少結(jié)果也要保證權(quán)威相關(guān)。業(yè)界搜索引擎用的是“包含任一查詢?cè)~OR)”召回再用排序模型把最相關(guān)的頂上去那是工程上的選擇畢設(shè)階段掌握AND其實(shí)夠了。在Python中實(shí)現(xiàn)AND檢索已經(jīng)簡(jiǎn)化為先從倒排索引里拿到每個(gè)查詢?cè)~對(duì)應(yīng)的文檔ID列表然后做交集操作。寫完這一瞬你就能體會(huì)到倒排索引的效率優(yōu)勢(shì)了。def search(self, query_tokens): if not query_tokens: return [] # 得到每個(gè)詞的文檔ID集合 doc_sets [] for token in query_tokens: posting self.inverted_index.get(token, []) doc_set set([doc_id for doc_id, _ in posting]) if not doc_set: return [] # 有一個(gè)詞沒匹配到直接返回空 doc_sets.append(doc_set) # 取交集所有查詢?cè)~都出現(xiàn)的文檔 result_docs set.intersection(*doc_sets) return list(result_docs)4.2 排序算法的設(shè)計(jì)與優(yōu)化拿到候選文檔集合后下一步就是排序。最開始我直接用“匹配詞數(shù)量”排序也就是誰(shuí)的文檔里包含的關(guān)鍵詞種類更多誰(shuí)排前面。這個(gè)策略在只有一個(gè)查詢?cè)~時(shí)完全失效因?yàn)樗腥说钠ヅ湓~數(shù)量都一樣。后來我引入了經(jīng)典方案把每個(gè)查詢?cè)~的TF-IDF分值相加作為文檔的最終相關(guān)度。def rank_docs(self, candidate_docs, query_tokens, doc_token_count_map): scores {} for doc_id in candidate_docs: total_score 0.0 for token in query_tokens: total_score self.compute_tfidf(token, doc_id, doc_token_count_map[doc_id]) scores[doc_id] total_score # 按得分降序排列 ranked_docs sorted(scores.items(), keylambda x: x[1], reverseTrue) return ranked_docs這個(gè)算法的效果怎么樣直觀地說如果一篇文章在開頭、正文、結(jié)尾等多個(gè)位置多次出現(xiàn)“Python”和“爬蟲”且這些詞在你的整個(gè)文檔集中不算特別爛大街那它的得分就會(huì)很高排名自然靠前。這個(gè)排序算法雖然樸素但已經(jīng)是“基于內(nèi)容的檢索排序”的標(biāo)準(zhǔn)范式了。優(yōu)化的方向我調(diào)研過很多比如給標(biāo)題的匹配詞加更高的權(quán)重標(biāo)題權(quán)重系數(shù)2.0因?yàn)槲恼聵?biāo)題往往是內(nèi)容的濃縮比如引入文檔長(zhǎng)度歸一化防止長(zhǎng)文刷分比如引入PageRank需要鏈接關(guān)系數(shù)據(jù)爬蟲模塊里可以順手抽取外鏈。我實(shí)際做了標(biāo)題加權(quán)和長(zhǎng)度歸一化效果提升非常明顯推薦大家至少做到這一步。4.3 檢索接口與前端展示后端我用的是Flask一個(gè)輕量級(jí)的Web框架。接口設(shè)計(jì)遵循RESTful風(fēng)格前端用一個(gè)簡(jiǎn)單的HTML頁(yè)面 fetchAPI完成異步搜索。搜索框、結(jié)果列表、耗時(shí)統(tǒng)計(jì)、結(jié)果數(shù)量四要素一個(gè)不能少。app.route(/api/search, methods[GET]) def api_search(): query request.args.get(q, ) start time.time() results search_engine.search(query) elapsed time.time() - start return jsonify({ query: query, elapsed_ms: round(elapsed * 1000, 2), total_results: len(results), results: results[:50] })前端展示里有一個(gè)容易被忽略的點(diǎn)關(guān)鍵詞高亮。把搜索詞在結(jié)果標(biāo)題和摘要中高亮顯示會(huì)極大地提升用戶體驗(yàn)。實(shí)現(xiàn)方式很簡(jiǎn)單拿到查詢?cè)~列表后把結(jié)果文本中的這些詞用HTML標(biāo)簽包裹加上突出顏色。注意高亮?xí)r的分詞粒度要和查詢一致否則會(huì)高亮不上。還有一個(gè)經(jīng)驗(yàn)是結(jié)果頁(yè)里一定要顯示搜索耗時(shí)。這不僅是為了好看更是為了向答辯老師直觀展示倒排索引的查詢性能。我做的畢設(shè)項(xiàng)目中在5000篇文檔的索引下一次搜索在10毫秒以內(nèi)完成這種“肉眼可見的快”比任何PPT上的性能對(duì)比圖都有說服力。5. 常見問題與排查技巧實(shí)錄5.1 爬蟲模塊的典型問題問題1抓回來的網(wǎng)頁(yè)全是二進(jìn)制亂碼。原因通常是響應(yīng)內(nèi)容被gzip壓縮了而你沒有解壓。requests庫(kù)其實(shí)自帶解壓功能但如果你用Session且手動(dòng)處理了響應(yīng)流就可能繞過這層。排查方法是打印resp.headers.get(Content-Encoding)看到gzip就說明需要解壓。request庫(kù)正常情況下會(huì)自動(dòng)處理這個(gè)問題多數(shù)出現(xiàn)在你把streamTrue打開之后又手動(dòng)讀取了原始流。問題2XPath定位不準(zhǔn)確匹配不到鏈接。很多同學(xué)直接復(fù)制瀏覽器F12里看到的XPath結(jié)果在代碼里跑不通。原因是瀏覽器里復(fù)制出來的XPath往往包含了很多div[2]/div[3]這樣的層級(jí)索引頁(yè)面結(jié)構(gòu)稍微一變化就失效。我的建議優(yōu)先用相對(duì)路徑和屬性定位比如//a[contains(href, article)]這種寫法魯棒性好得多。另外記得用urljoin拼接相對(duì)鏈接HTML里的href/foo是相對(duì)路徑不拼接的話你抓回來的URL全是殘廢的。問題3爬蟲越跑越慢。大概率是請(qǐng)求超時(shí)設(shè)置太長(zhǎng)或者沒有限制單個(gè)域名的并發(fā)請(qǐng)求。我后來加了每域名延時(shí)隊(duì)列每個(gè)域名最多每2秒處理一個(gè)請(qǐng)求速度確實(shí)慢了但穩(wěn)定性極大地提升了。5.2 索引與檢索的排查思路問題1搜索一個(gè)肯定存在的內(nèi)容卻返回空結(jié)果。最常見的坑是查詢預(yù)處理和索引預(yù)處理的流程不一致。比如你索引時(shí)把小寫和大寫歸并了Python轉(zhuǎn)成python但查詢時(shí)沒有做同樣的轉(zhuǎn)換。很多同學(xué)喜歡“先跑通再優(yōu)化”結(jié)果優(yōu)化了一邊忘了另一邊。排查時(shí)用同樣的輸入分別在索引代碼和查詢代碼里跑一遍對(duì)比輸出Token列表是否一致。問題2檢索結(jié)果的排序不符合直覺。比如搜“Python”時(shí)一篇只提到一次“Python”的文章比一篇深入講“Python”的文章排得還靠前。這時(shí)候要檢查IDF的計(jì)算。如果包含“Python”的文檔只有2篇而你要搜的文檔集合總共只有3篇那idf log(3/2) 0.405幾乎沒起到區(qū)分作用。這就是文檔集太小導(dǎo)致的IDF失效。解決方法是擴(kuò)充文檔集或者把IDF分母里包含該詞的文檔數(shù)做平滑處理。問題3檢索速度越來越慢。如果索引數(shù)據(jù)量上來了但檢索還是幾十毫秒甚至幾百毫秒八成是你在檢索時(shí)做了重復(fù)計(jì)算。比如每次查詢都把整個(gè)索引重新load一遍或者把TF-IDF計(jì)算放在查詢鏈路里而不是構(gòu)建時(shí)預(yù)先算好。正確的做法是索引構(gòu)建時(shí)就把每個(gè)詞在每個(gè)文檔中的TF-IDF預(yù)計(jì)算好存下來查詢時(shí)只做查表求和不做任何乘法和開方運(yùn)算。5.3 性能優(yōu)化與擴(kuò)展方向畢設(shè)答辯時(shí)老師最喜歡問的問題是“如果讓你繼續(xù)做你會(huì)怎么優(yōu)化”這里給你三個(gè)方向既能展示你的思考深度又不會(huì)給自己挖坑方向一引入向量空間模型VSM和余弦相似度。把每個(gè)文檔表示成一個(gè)詞向量查詢也變成一個(gè)詞向量?jī)烧邐A角越接近說明越相關(guān)。這個(gè)思路是TF-IDF的自然延伸代碼實(shí)現(xiàn)也就幾十行但寫進(jìn)論文里能顯著提升理論高度。方向二構(gòu)建多級(jí)索引加速查詢。對(duì)倒排索引按照文檔ID排序存儲(chǔ)可以方便做跳表加速skip pointer。用戶在查詢時(shí)先在熱詞索引里撈結(jié)果冷門詞再走全量索引降低耗時(shí)。這個(gè)方向涉及算法和數(shù)據(jù)結(jié)構(gòu)的知識(shí)深度。方向三搜索結(jié)果緩存。用戶搜索的詞頻分布高度傾斜一小部分熱門查詢占據(jù)了絕大多數(shù)流量。把熱門查詢的結(jié)果緩存到內(nèi)存里能大幅減少重復(fù)計(jì)算。這個(gè)方向明顯有工程實(shí)踐的價(jià)值而且容易和Redis等知識(shí)點(diǎn)聯(lián)動(dòng)起來。在我實(shí)際做項(xiàng)目的過程里把爬蟲數(shù)據(jù)量從2000篇擴(kuò)展到1萬篇時(shí)明顯感受到存儲(chǔ)和速度的數(shù)據(jù)壓力。當(dāng)時(shí)我也想過用數(shù)據(jù)庫(kù)比如MySQL或SQLite來存倒排索引后來發(fā)現(xiàn)Python的json存儲(chǔ)和加載在1萬篇文檔下仍在毫秒級(jí)就沒多折騰。如果你想要一個(gè)更加“正式”的版本來應(yīng)對(duì)答辯也可以用SQLite存詞項(xiàng)和倒排列表順便展示一下你的數(shù)據(jù)庫(kù)設(shè)計(jì)能力也是加分項(xiàng)。結(jié)語(yǔ) | 關(guān)于這個(gè)項(xiàng)目的一些個(gè)人體會(huì)最后說點(diǎn)實(shí)在的。做這個(gè)畢設(shè)項(xiàng)目技術(shù)上我能總結(jié)的東西很多但最大的收獲反而不是技術(shù)本身。搜索引擎這個(gè)題目它像是一個(gè)“算法放大器”你在數(shù)據(jù)結(jié)構(gòu)課上學(xué)的每一種抽象哈希、樹、圖在搜索引擎里都有真實(shí)的、迫切的用武之地。以前我學(xué)布隆過濾器覺得是為了考試當(dāng)我看到爬蟲死循環(huán)的那一刻我才明白它解決的到底是什么問題。當(dāng)時(shí)踩過的坑和調(diào)整后的經(jīng)驗(yàn)現(xiàn)在復(fù)盤后整理成下面這幾個(gè)建議給正在做類似項(xiàng)目的同學(xué)作為參考不要一開始就追求“大而全”。先抓100個(gè)網(wǎng)頁(yè)跑通整個(gè)搜索流程然后再逐步擴(kuò)展數(shù)據(jù)量。你要知道整個(gè)系統(tǒng)能夠“轉(zhuǎn)起來”帶給你的信心遠(yuǎn)比你悶頭優(yōu)化某個(gè)模塊要大得多。寫代碼時(shí)養(yǎng)成“模塊可單獨(dú)驗(yàn)證”的習(xí)慣。爬蟲抓下來的數(shù)據(jù)是否完整、分詞結(jié)果是否正確、索引是否可加載——每一步都要能獨(dú)立驗(yàn)證。項(xiàng)目后期的調(diào)試時(shí)間幾乎都花在“回溯定位是哪一層出了問題”上模塊驗(yàn)證能幫你節(jié)省至少一半時(shí)間。項(xiàng)目進(jìn)度要及時(shí)備份。第一次我寫完索引構(gòu)建代碼后清理了爬蟲緩存發(fā)現(xiàn)索引文件被誤刪了整個(gè)索引要重新構(gòu)建。從那以后我都是把關(guān)鍵模塊的產(chǎn)出物備份到不同目錄這個(gè)習(xí)慣幫我在答辯前避免了很多麻煩。搜索這個(gè)領(lǐng)域表面上是技術(shù)工程實(shí)際上還牽扯到對(duì)“用戶意圖”的理解對(duì)信息的組織方式等等挑戰(zhàn)。你的Python畢設(shè)搜索項(xiàng)目做完之后如果對(duì)這個(gè)領(lǐng)域還保持著興趣往Elasticsearch的方向了解就是一個(gè)很好的延伸選擇。畢竟從自己寫一個(gè)“五臟俱全”的搜索引擎開始你會(huì)對(duì)檢索這件事形成更深層的肌肉記憶這個(gè)東西的價(jià)值是長(zhǎng)遠(yuǎn)的。