搜索引擎技术介绍
引言
早些時候分享過一份關于搜索引擎技術的PPT,這篇文章基本上是基于原來框架,在內容上做了一些改進和擴充。
主要是對搜索引擎技術的各方面做一些簡單的介紹和入門的指引。
索引
1. 需求與歷史
2. 搜索產品簡單介紹
3. 搜索技術
3.1 系統
3.2 數據
3.3 算法
4. 開源方案
5. 現狀與未來
需求與歷史
搜索引擎的誕生源自互聯網最根本的用途之中的一個:信息獲取。在搜索引擎出現之前,互聯網缺少入口,用戶往往須要自己記住實用的站點和網頁。
為了滿足這樣的需求,最早的“搜索引擎”,即分類文件夾瀏覽式的引擎便出現了,Yahoo就是當中的代表。
當時僅僅是把一些實用的站點通過分類的方式手工組織起來,便于用戶找到實用的信息。
可以手工組織也是基于早年整個互聯網的站點數量也很少,可以通過人工方式實現組織。
但隨著互聯網的壯大,網頁站點數量越來越多,手工組織的方式變為不可行,于是由機器實現的全文檢索引擎便出現了。
用戶能夠通過keyword查詢來獲取相關的網頁。
但隨著網頁數量進一步增多,不論什么keyword查詢都會返回大量的相關網頁,假設對網頁進行評分和排序,返回給用戶真正有價值的網頁便成為重點。
基于網頁之間的鏈接關系為網頁進行評分,成為非常多搜索引擎的網頁排序算法基礎,Google的PageRank算法便是當中的代表者和姣姣者。
Google也以此為基礎成為搜索引擎產品中的率先者,為用戶提供了更好的搜索結果相關性。
現代搜索引擎基本上也由此基本成型,盡管后來的技術創新和改進非常多,但基本的思路基本上沒有變。
搜索引擎發展到今天,基礎架構和算法在技術上都已經基本成型和成熟?,F在的一些改進和變化基于在多元化的信息整合,以及產品形態的改進上。
未來會往什么方向發展,或者有什么革命的變化,都不能確定。
搜索產品
搜索引擎產品事實上包含非常多種類,并不限于我們最熟悉的全網搜索引擎。
簡單分類羅列一下:
* 全網搜索:包含市場份額最高的幾大搜索引擎巨頭,Google, Yahoo, Bing。
* 中文搜索:在中文搜索市場中,百度一家獨大,其他幾家如搜狗、搜搜、有道,市場份額相對還比較小。
* 垂直搜索:在各自的垂直領域成為搜索入口的,購物的淘寶,美食的大眾點評,旅游的去哪兒,等等。
* 問答搜索:專注于為問句式提供有效的答案,比方Ask.com;其他的如問答社區像Quora和國內的知乎,應該也會往這方面發展。
* 知識搜索:典型代表就是WolframAlpha,差別于提供搜索結果列表,它會針對查詢提供更具體的整合信息。
* 云搜索平臺:為其他產品和應用提供搜索服務托管平臺(SaaS或是PaaS),Amazon剛剛推出它的CloudSearch, IndexTank在被Linkedin收購之前也是做這項服務。
* 其他:比始DuckDuckGo,主打隱私保護,也有部分用戶買帳。
各種搜索產品在各自領域都須要解決特定的技術和業務問題,所以也能夠建立相對通用搜索的優勢,來得到自己的市場和用戶。
搜索技術
搜索引擎所涉及和涵蓋的技術范圍很廣,涉及到了系統架構和算法設計等很多方面。
能夠說因為搜索引擎的出現,把互聯網產品的技術水平提高到了一個新的高度;搜索引擎不管是在數據和系統規模,還是算法技術的研究應用深度上,都遠超之前的簡單互聯網產品。
列舉一些搜索引擎所涉及到的技術點:
* 爬蟲 (Crawling)
* 索引結構 (Inverted Index)
* 檢索模型 (VSM & TF-IDF)
* 搜索排序 (Relevance Ranking & Evaluation)
* 鏈接分析 (Link Analysis)
* 分類 (Document & Query Classification)
* 自然語言處理 (NLP: Tokenization, Lemmatization, POS Tagging, NER, etc.)
* 分布式系統 (Distributed Processing & Storage)
* 等等
盡管搜索引擎涉及的技術方方面面,但歸結起來最關鍵的幾點在于:
* 系統:大規模分布式系統,支撐大規模的數據處理容量和在線查詢負載
* 數據:數據處理和挖掘能力
* 算法:搜索相關性排序,查詢分析,分類,等等
系統
搜索引擎系統是一個由很多模塊組成的復雜系統。
核心模塊通常包含:爬蟲,索引,檢索,排序。
除了必需的核心模塊之外,通常還須要一些支持輔助模塊,常見的有鏈接分析,去重,反垃圾,查詢分析,等等。
[附圖:搜索系統架構概念模型]
簡介一下搜索系統的概念模型中的各模塊:
* 爬蟲
從互聯網爬取原始網頁數據,存儲于文檔server。
* 文檔server
存儲原始網頁數據,通宵是分布式Key-Value數據庫,能依據URL/UID高速獲取網頁內容。
* 索引
讀取原始網頁數據,解析網頁,抽取有效字段,生成索引數據。
索引數據的生成方式一般是增量的,分塊/分片的,并會進行索引合并、優化和刪除。
生成的索引數據通常包含:字典數據,倒排表,正排表,文檔屬性等。
生成的索引存儲于索引server。
* 索引server
存儲索引數據,主要是倒排表。
一般是分塊、分片存儲,并支持增量更新和刪除。
數據內容量很大時,還依據類別、主題、時間、網頁質量劃分數據分區和分布,更好地服務在線查詢。
* 檢索
讀取倒排表索引,響應前端查詢請求,返回相關文檔列表數據。
* 排序
對檢索器返回的文檔列表進行排序,基于文檔和查詢的相關性、文檔的鏈接權重等屬性。
* 鏈接分析
收集各網頁的鏈接數據和錨文本(Anchor Text),以此計算各網頁鏈接評分,終于會作為網頁屬性參與返回結果排序。
* 去重
提取各網頁的相關特征屬性,計算相似網頁組,提供離線索引和在線查詢的去重服務。
* 反垃圾
收集各網頁和站點歷史信息,提取垃圾網頁特征,從而對在線索引中的網頁進行判定,去除垃圾網頁。
* 查詢分析
分析用戶查詢,生成結構化查詢請求,指派到對應的類別、主題數據server進行查詢。
* 頁面描寫敘述/摘要
為檢索和排序完畢的網頁列表提供對應的描寫敘述和摘要。
* 前端
接受用戶請求,分發至對應server,返回查詢結果。
[附圖:爬蟲系統架構]
爬蟲系統也是由多個模塊構成:
* URL Scheduler
存儲和高度待爬取的網頁地址。
* Downloader
依據指定的網頁列表爬取網頁內容,存儲至文檔server。
* Processer
對網頁內容進行簡單處理,提取一些原始屬性,為爬取的興許操作服務。
* Traffic Controller
爬取流量控制,防止對目標站點在短時間內造成過大負載。
[附圖:搜索系統架構實例:Google]
這是Google早期的一張系統架構圖,能夠看出Google系統的各模塊基本和前面概念模型一致。
所以一個完整的全網搜索系統的大致系統架構是類似的,差別和競爭力體如今細節實現和優化上。
數據
除了搜索引擎系統提供了系統支撐外,搜索結果質量非常大程度上依賴于源數據的數量和質量,以及數據處理的能力。
全網數據的主要來源一般是從互聯網上進行自己主動爬取,從一些高質量的種子網站開始,并沿網頁鏈接不斷展開,收集巨量的網頁數據;這通常能達到數據在數量的要求,但也不可避免混入了大量的低質量網頁。
除了自己主動爬取來的數據外,搜索引擎的數據來源還能夠來自人工收集、合作伙伴提供、第三方數據源和API、以及購買;這些來源一般會有更好的質量保證,但在數量規模和覆蓋率上會相對少一些,能夠和爬取的數據形成有效的互補。
收集到足量的原始數據后,須要進行各種數據處理操作,把原始數據轉換成在線檢索須要的數據。
這個過程通常包含:網頁分析,數據抽取,文本處理和分詞,索引及合并;終于生成的數據會包含:詞典,倒排表,正排表,文檔權重和各種屬性。
終于生成的數據要布署上對應的在線檢索server上,一般會進行數據分區和分片布署,數據內容更豐富時還可能依據內容分類和主題進行分別布署,比方新聞時效類的網頁可能就會獨立布署,針對性地響應時效類的查詢。
[附圖:索引數據:字典、倒排表、正排表]
這張圖來源于Google早期的索引數據結構,包含詞典、倒排表、正排表。
算法
有了相當數量的高質量數據之后,搜索結果的質量改進就取決于搜索算法的準確性上。
如今的搜索引擎通常通過向量空間模型(VSM = Vector Space Model)來計算查詢和各文檔之間的文本相似性;即把查詢或文檔抽象成一個詞向量,然后再計算向量在向量空間中的夾角,能夠用余弦公式得出,作為文本相似度的度量值。
在 主要的向量空間模型基礎上一般會進一步增加詞的權重值進行改進,通過經典的TF-IDF公式得出,即詞頻(TF)乘上逆文檔頻率(IDF);當中TF = Term Frequency,即該詞在所在文檔中的出現次數;IDF = Invert Document Frequency,即包括該詞的文檔數除以總文檔數,再取反,通常還會取對數來降維,這個值值越大表示這個詞越能代表文檔特征。
除了通過向量空間模型得出的文本匹配評分外,每一個文檔還會有自己本身的質量評分,通常由網頁鏈接數據計算得出,代表了該網頁本身的流行度權重。
終于的評分會以文本匹配的查詢時動態評分和文檔靜態評分為基礎計算得出;搜索引擎的評分計算都會考慮非常多因素,但這兩項一般是評分計算的基礎。
有了確定的排序算法后,還有一個重要的任務就是評估搜索結果的質量。
因為搜索結果的好與壞是一個比較主觀的過程,所以進行定量的評估并不easy。
常見的做法是通過事先選定一批查詢,通過人工評估或是預先設定標準值的方式,逐個評估每一個設定查詢搜索結果,終于得到一個統計結果,作為搜索算法的評估度量。
還有一類做法是直接通過線上的用戶PV數據來統計評估搜索結果質量,或是通過A/B測試來比較兩種排序算法的點擊效果來衡量。
合理而有效的評估方法,是搜索算法能夠不斷改進和比較的前提。
查詢分析是還有一個對搜索結果影響非常大的方面,主要任務是把用戶的查詢文本轉換成內部的結構化的搜索請求。
涉及的處理可能包含主要的分詞處理,專有名詞的識別和提取,或是查詢模式的識別,或是查詢分類的識別。
這些處理的準確性將能極大地改進搜索請求的方式,進一步影響搜索結果的相關性和質量。
開源方案
近年來在搜索公司內部搜索系統和技術的改進和發展的同一時候,一批開源的搜索系統和解決方式也逐漸發展和成熟起來。
當然開源系統在功能全面性、復雜性和規模上都不能與專業的搜索引擎系統相比,但對于中小企業的搜索應用來說應該已經能非常好地滿足需求,并且也成功應用到了一些大規模的產品系統中(比方Twitter的搜索就使用和改進了Lucene)。
如今比較常見的開源搜索解決方式有:
* Lucene
Lucene自然是如今最流行,使用度最高的搜索開源方案。它用Java開發,以索引和檢索庫的方式提供,能夠非常easy地嵌入須要的應用中。
* Solr & SolrCloud
Solr是Lucene的子項目,同屬Apache軟件基金會項目;它是基于Lucene之上實的一個完整的搜索服務應用,提供了大量的搜索定制功能,能夠滿足大部分的搜索產品需求。
SolrCloud是Solr為了加強其分布式服務能力而開發的功能,眼下還在開發階段,將在Solr 4.0公布。
* Zoie & Sensei (Linkedin)
Zoie是Linkedin公司在Lucene基礎上實現的準實時索引庫,通過增加額外的內存索引,來達到準實時索引的效果。
Sensei是Linkedin公司在Zoie基礎上實現的分布式搜索服務,通過索引分區來實現分布式搜索服務。
* ElasticSearch
ElasticSearch 也是剛推出不久的一個基于Lucene實現的分布式搜索服務,據說在分布式支持和易用性上都有不錯的表現。由于還比較年輕,真實的應用應該還不多,須要觀 察。由于也是基于Lucene的分布式開源搜索框架,基本上會與SolrCloud和Sensei形成正面競爭關系。
* 其他開源產品
除了Lucene家族以外,另一些其他的開源產品,比方Sphinx和Xapian,也有不少的應用;但近年來的更新頻率和社區活躍度都不太能和Lucene系的產品相比。
* 托管平臺
除 了開源產品外,如今還出現了一些基于云計算和云服務的搜索服務,比方Amazon新近推了的CloudSearch,還有更早一些的 IndexTank(已被Linkedin收購)。這類服務無需自己布置搜索系統,直接使用在線服務,按需付費,所以也將是開源產品的替代方案和競爭對 手。
附幾張上面提到的開源系統的概念模型和架構圖:
[附圖:Lucene概念模型]
[附圖:Lucene工作流程]
[附圖:Sensei系統架構]
[附圖:SolrCloud系統架構]
現狀與未來
傳統的搜索引擎經過了十幾年的發展,眼下在技術和產品上都已走向逐漸穩定和成熟,通用搜索的市場也基本進入飽和,不像早些年一直呈現高增長率。
同一時候,在各個垂直領域,也出現了非常多和產品結合的非常好的垂直搜索產品,比方淘寶的購物搜索,大眾點評的美食搜索,去哪兒和酷訊的旅游搜索等,也都在各自領域占領了相當大的市場,成為除了通用搜索引擎之外的重要的用戶入口。
在開源領域,各種開源產品和解決方式也逐漸發展成熟,通用搜索技術不再為大公司所專有,中小企業可以以較低的成本實現自己的搜索應用。
如今搜索引擎產品之間的競爭很多其它的在數據、應用方式和產品形態上,在系統架構和基本算法上區分并不大。
搜索引擎在未來發展上,一是搜索將不只以獨立產品的形式出現,很多其它的會作為搜索功能整合到很多其它的產品和應用中。
在產品形態上,基于傳統的搜索引擎,會演化出像推薦引擎,知識引擎,決策引擎等形式的產品,更好地滿足和服務用戶需求。
而搜索引擎所涉及和發展起來的各種技術,會更廣泛地應用到各種基它產品上,比方自然語言處理,推薦和廣告,數據挖掘,等等。
總之,搜索引擎對互聯網技術和產品帶來的影響是巨大的,未來也仍將有非常大的發展和應用空間。
轉自:網易杭研后臺技術中心的博客http://backend.blog.163.com/blog/static/202294126201252872124208/
總結
- 上一篇: 避孕方法有哪些(你知道的避孕方法有几种)
- 下一篇: 走遍欧洲 —— 东欧、南斯拉夫