【文章內(nèi)容簡(jiǎn)介】 3。 45 1 全文搜索引擎技術(shù)的研究和實(shí)現(xiàn) 摘要： 隨著互聯(lián)網(wǎng)（ Inter）的出現(xiàn)和普及，人們的信息來(lái)源得到極大的豐富，獲取信息的方式也隨之改變。換句話說(shuō)，互聯(lián)網(wǎng)成為人們獲取信息的主要來(lái)源之一。在 Web信息以幾何級(jí)數(shù)增長(zhǎng)的情況下，如何快速獲取所需信息成為研究熱點(diǎn)之一。 本文介紹了一個(gè)基于 Linux平臺(tái)下 C++的 可索引百萬(wàn)級(jí)網(wǎng)頁(yè)原文 的全文搜索引擎的設(shè)計(jì)及其實(shí)現(xiàn)， 并對(duì)該搜索引擎的基 本框架設(shè)計(jì)和主要功能模塊的實(shí)現(xiàn)作了詳細(xì)介紹， 其中包括 通過(guò)信號(hào)量和互斥鎖達(dá)到同步的 多線程并行網(wǎng)頁(yè)爬蟲， 采用 正向窗口最大匹配分詞 算法 ，網(wǎng)頁(yè)原文采用天網(wǎng)格式的數(shù)據(jù)存儲(chǔ)，核心數(shù)據(jù)結(jié)構(gòu)包括 ISAM順序索引文件， 正向索引文件， 倒排索引文件等， 最后給出了相應(yīng)的測(cè)試 結(jié)果。 關(guān)鍵詞 ： 多線程 網(wǎng)頁(yè) 爬蟲；線程同步；順序、倒排索引； 全文搜索引擎 Full Text Search Engine Abstract： With the inventation and popularization of the Inter， it has been kinds of source of news and the way access to information also has been a great other words， Inter has bee one of the main means which people obtain the Web information grows in a geometric progression， how to obtain the required information fast bees one of hot spot of researches. This paper introduces a Linux platform based on C++ of one million web pages indexed the full text of the original search engine design and its implementation, and the search engine design and the basic framework for the realization of the main functional modules described in detail, including through the signal Mutex and achieve synchronization in parallel multithreaded page reptiles, the use of the window are the largest subword matching algorithms, the original web page format using Tianwang data storage, data structures, including the core sequence ISAM index file, index files, inverted index file。 Finally， it educes the corresponding test results. Keywords： Multithreaded page crawler； Thread Synchronization； Order、 inverted index； Full text search engine 2 第一章 緒論 早在工業(yè)時(shí)代以前 ， 許多專家 、 學(xué)者就開始致力于信息整序的研究，并積累了豐富的經(jīng)驗(yàn)。進(jìn)入信息時(shí)代以后，人們加深了對(duì)信息資源的認(rèn)識(shí)，把信息資源的重要性提升到前所未有的高度，將之與物質(zhì)和能源相 提并論，稱之為現(xiàn)代社會(huì)的三大支柱之一。國(guó)際互聯(lián)網(wǎng)的誕生和發(fā)展，給信息資源的建設(shè)提供了一個(gè)無(wú)限的空間。網(wǎng)上信息資源的迅速增長(zhǎng)，為信息的開發(fā)與利用提供了便利條件。然而，網(wǎng)絡(luò)信息微觀上的有序性和宏觀上的分散性、無(wú)序性、動(dòng)態(tài)變化性給人們?cè)谒鸭c利用信息時(shí)帶來(lái)了種種障礙。為了能從網(wǎng)絡(luò)上找到用戶所需要的特定信息，為了更加有效的開發(fā)利用互聯(lián)網(wǎng)上的數(shù)字金礦，搜索引擎應(yīng)運(yùn)而生了 。 論文的研究背景 伴隨著萬(wàn)維網(wǎng)的普及和發(fā)展 ， 因特網(wǎng)上的信息資源正在呈幾何級(jí)數(shù)增長(zhǎng) ， 據(jù)統(tǒng)計(jì) 09年 4月 服務(wù)器主機(jī)數(shù) 已經(jīng) 超過(guò) 2億 個(gè) [1]， 如圖 11所示 。 圖 11 世界 Web 服務(wù)器總量 [1] Total Sites Across All Domains August 1995 April 2020 [1] 根據(jù) 2020 年的一個(gè)研究， 在互聯(lián)網(wǎng)上已 超過(guò) 5500 億個(gè) 網(wǎng)頁(yè) 文檔 [2]。 2020 年 7月25日谷歌軟件工程師 Jesse Alpert和 Nissan Hajaj宣布谷歌搜索引擎已經(jīng)索引了萬(wàn)億 3 級(jí)的不同 URL 地址 [2]。 中國(guó)網(wǎng)頁(yè)規(guī)模如圖 12所示 。 圖 12 20202020年中國(guó)網(wǎng)頁(yè) 規(guī)模變化 [3] 20202020 Chinese web page size changes[3] 截至 2020 年底，中國(guó)網(wǎng)頁(yè)總數(shù)超過(guò) 160 億個(gè)，較 2020 年增長(zhǎng) 90%[3]。網(wǎng)頁(yè)的增長(zhǎng)速度與網(wǎng)站的增速基本一致。 如上所述 萬(wàn)維網(wǎng) 給人們帶來(lái)極其豐富的信息 ， 同時(shí)也向人們提出了新的問(wèn)題 ，即如何從浩如煙海的信息資源中迅速有效地檢索出人們所需要的信息。 Web 搜索引擎就是為滿足人們 的這種需要而誕生的 。 搜索引擎是一種在互聯(lián)網(wǎng)上采取一定的策略搜集 、 發(fā)現(xiàn)信息 ， 并對(duì)信息進(jìn)行分析 、 提取 、 組織和處理 ， 為用戶提供 檢索服務(wù)的搜索工具。 本論文針對(duì) Web全文搜索引擎 技術(shù) 進(jìn)行研究和實(shí)現(xiàn) 。 論文研究目的和意義 全球最大的網(wǎng)絡(luò)調(diào)查公司 CyberAtlas 最近的一項(xiàng)調(diào)查表明 ， 網(wǎng)站 75%的訪問(wèn)量都來(lái)自于搜索引擎。另一家美國(guó)權(quán)威顧問(wèn)公司 IMT Strategies 調(diào)查發(fā)現(xiàn)，新網(wǎng)站的有效途徑中：搜索引擎占 85%；自由沖浪占 6%；口碑宣傳占 4%； BANNER 廣告 2%； 偶然發(fā)現(xiàn)、報(bào)紙、電視各占 1%。 由此可見，搜索引擎 不僅僅作為用戶快速檢索互聯(lián)網(wǎng)上的浩瀚資源的工具，同時(shí) 作為網(wǎng)站推廣的首選媒介， 對(duì) 互聯(lián)網(wǎng) 有著不可忽視 的 作用。 本論 文在 相關(guān) 商業(yè) 全文 搜索引擎 公開的 技術(shù)原理 和開源全文搜索引擎技術(shù)原理 的 4 基礎(chǔ)上，對(duì) 全文搜索引擎 技術(shù) 研究并實(shí)現(xiàn) 。 整個(gè)過(guò)程 會(huì)設(shè)計(jì) 并實(shí)現(xiàn) 一個(gè) 百萬(wàn)級(jí)網(wǎng)頁(yè)規(guī)模的全文搜索引擎 ，來(lái)滿足 普通 用戶對(duì) 浩瀚 信息資源的檢索需要。 研究現(xiàn)狀 1990 年以前，沒(méi)有任何人能搜索互聯(lián)網(wǎng)。 1990 年誕生的 Archie 是一個(gè)可以用文件名自動(dòng)索引互聯(lián)網(wǎng)上匿名 FTP網(wǎng)站文件的程序，它實(shí)現(xiàn)了搜索，但還不是真正的搜索引擎 。 現(xiàn)代意義上的搜索引擎出現(xiàn)于 1994 年 7 月 ， 當(dāng)時(shí) Michael Mauldin 將 JohnLeavitt的蜘蛛程序接入到其索引 程序中 ， 創(chuàng)建了大家現(xiàn)在熟知的 Lycosa。 1995 年末 ， Altavista 永遠(yuǎn)改變了搜索引擎的定義 ， AItavista 是第一個(gè)支持自然語(yǔ)言搜索的搜索引擎，也是第一個(gè)實(shí)現(xiàn)高級(jí)搜索語(yǔ)法的搜索引擎。 1998 年 ， Google 在 Pagerank、動(dòng)態(tài)摘要、網(wǎng)頁(yè)快照、 DailyRefresh、多文檔格式支持、地圖 、 股票 、 詞典 、 尋人等集成搜索、多語(yǔ)言支持、用戶界面等功能上的革新，象 Altavista 一樣，再一次永遠(yuǎn)改變了搜索引擎的定義?，F(xiàn)階段，出現(xiàn) Ask Jeeves， ， ， MySimon， Dito 等內(nèi)容類別不同的搜索引擎。從出現(xiàn)第一個(gè)搜索引擎至今 ， 搜索引擎技術(shù)已獲得了飛速的發(fā)展，現(xiàn)在的搜索引擎功能越來(lái)越強(qiáng)大，提供的服務(wù)也越來(lái)越全面，它們的目標(biāo)不僅僅是提供單純的查詢功能，而是把自己發(fā)展成為用戶首選的 Inter 入口站點(diǎn)。目前的搜索引擎主要有以下幾個(gè)主要特點(diǎn) ： 多樣化和個(gè)性化的服務(wù)。現(xiàn)在絕大多數(shù)搜索引擎都提供多樣化的服務(wù)，以吸引更多的用戶，商業(yè)搜索引擎尤其注重這一點(diǎn) ； 強(qiáng)大的查詢功能與最早的搜索引擎相比，現(xiàn)在的搜索引擎在查詢功能方面已有了很大的改進(jìn)。除了簡(jiǎn)單的 AND、 OR和 NOT 邏輯外，不少搜 索引擎還支持相似查詢 ； 目錄和基于 Robot 的搜索引擎相互結(jié)合目錄和基于 Robot 的搜索引擎都具有自己的特點(diǎn)，在當(dāng)前的技術(shù)條件下，最好的選擇是將兩種技術(shù)進(jìn)行結(jié)合，同時(shí)為用戶提供這兩種類型的服務(wù)。 這些 搜索引擎基本工作原理是 ： 數(shù)據(jù)采集機(jī)制按照一定規(guī)律和方式對(duì)網(wǎng)絡(luò)上的各種信息資源進(jìn)行搜索，并將搜索到的頁(yè)面信息存入到一個(gè)臨時(shí)數(shù)據(jù)庫(kù)中；數(shù)據(jù)分類索引機(jī)制對(duì)臨時(shí)數(shù)據(jù)庫(kù)中的頁(yè)面信息進(jìn)行索引 ， 經(jīng)過(guò)整理形成各種倒排文檔 ， 相應(yīng)地建立起索引數(shù)據(jù)庫(kù)；用戶查詢接口則提供友好的查詢界面，接受用戶提交的查詢?nèi)蝿?wù) ， 并根據(jù)要求訪問(wèn)相應(yīng)的索引數(shù) 據(jù)庫(kù)，將符合要求的結(jié)果按一定規(guī)則排序輸出。 5 論文的研究?jī)?nèi)容 本文的研究?jī)?nèi)容主要包括以下 三 點(diǎn)： 互聯(lián)網(wǎng)上 全文搜索引擎技術(shù) 面臨的 挑戰(zhàn) ， 整體結(jié)構(gòu) 的分析 以及相關(guān)技術(shù)的 研究 ，其中分為分布式處理，中文分詞，網(wǎng)頁(yè)排序，海量存儲(chǔ)，壓縮 等技術(shù) 的 介紹 ； 本論文 設(shè)計(jì)出 的 全文搜索引擎整體系統(tǒng)架構(gòu)， 各 模塊 的 交互 和 設(shè)計(jì) ； 實(shí)現(xiàn)，最終完成一個(gè)可以對(duì)校內(nèi)網(wǎng)站進(jìn)行全文檢索的搜索引擎，該全文搜索引擎主要分為以下三部分： 網(wǎng)頁(yè)爬蟲。存儲(chǔ)與索引 表 ，天網(wǎng)格式的網(wǎng)頁(yè)數(shù)據(jù)原文存儲(chǔ)格式，順序索引表，倒排索引表 ， 相關(guān)性分析 ， 查詢服務(wù)系統(tǒng)。 論文的組織結(jié)構(gòu) 本論文共分 五 章，具體結(jié)構(gòu)如下： 第一章 概述本文的研究背景和 研究意義以及國(guó)內(nèi)外的研究現(xiàn)狀，在此基礎(chǔ)上提出本文研究的主要內(nèi)容 。 第二章 對(duì) 互聯(lián)網(wǎng)上 的 全文搜索引擎 技術(shù)的 分析 和研究 。 第三章 對(duì)本論文設(shè)計(jì)出的全文 搜索引擎 系統(tǒng) 的架構(gòu)分析 ，結(jié)構(gòu)分析 和 交互 設(shè)計(jì) 等 。 第四章 對(duì) 整個(gè) 系統(tǒng) 各個(gè)部分模塊的具體編碼 實(shí)現(xiàn)與 關(guān)鍵技術(shù) 研究 。 第五章 全文總結(jié)， 以及 對(duì) 本論文設(shè)計(jì)出的 全文搜索引擎的 創(chuàng)新 點(diǎn) 與展望 的說(shuō)明 。 6 圖 13 論文結(jié)構(gòu) Thesis structure 小結(jié) 通過(guò)對(duì)互聯(lián)網(wǎng)上網(wǎng)頁(yè)數(shù)的調(diào)查，以及出現(xiàn)全文搜索引擎的背景和其研究的現(xiàn)狀，最終提出了本論文研究的內(nèi)容和論文的布局結(jié)構(gòu)。 第一章 緒論 第二章 全文搜索引擎技術(shù)分析 第三章 本論文所設(shè)計(jì)的全文搜索引擎技術(shù)分析 第四章 本論文所設(shè)計(jì)的全文搜索引擎編碼實(shí)現(xiàn)與關(guān)鍵技術(shù)研究 第五章 總結(jié)與展望 7 第二章 搜索引擎 相關(guān) 技術(shù) 分析 著名的搜索引擎 搜索引擎自 1993 年出現(xiàn)發(fā)展至今 ， 已取得了長(zhǎng)足的進(jìn)步 ， 信息檢索工具搜索引擎也是層出不窮 ， 以下是與搜索引擎發(fā)展歷史息息相關(guān)的幾個(gè)搜索引擎 ： (1)Fast(All the web)公司創(chuàng)立于 1997 年 ， 是挪威科技大學(xué) (NTNU)學(xué)術(shù)研究的副產(chǎn)品。 1999 年 5 月 ， 它發(fā)布了自己的搜索引擎 All The Web。 Fast 創(chuàng)立的目標(biāo)是做世界上最大和最快的搜索引擎 ， 幾年來(lái)庶幾近之 。 Fast(All the web)的網(wǎng)頁(yè)搜索可利用 ODP 自動(dòng)分類 ， 支持 Flash 和 Pdf 搜索 ， 支持多語(yǔ)言搜索 ，還提供新聞搜索、 圖像搜索、視頻、 MP3和 FTP 搜索 ， 擁有極其強(qiáng)大的高級(jí)搜索功能。 (2)Teoma 起源于 1998 年 Rutgers 大學(xué)的一個(gè)項(xiàng)目。 Apostolos Gerasoulis教授帶領(lǐng)華裔 Tao Yang 教授等人創(chuàng)立 Teoma 于新澤西 Piscataway， 2020 年春初次登場(chǎng) ， 2020 年 9 月被提問(wèn)式搜索引擎 Ask Jeeves 收購(gòu) ， 2020 年 4月再次發(fā)布 。Teoma 的數(shù)據(jù)庫(kù)目前仍偏小 ， 但有兩個(gè)出彩的功能 ： 支持類似自動(dòng)分類的 Refine； 同時(shí)提供專業(yè)鏈接目錄的 Resources。 (3)Wisenut 由韓裔 Yeogirl Yun 創(chuàng)立 。 2020 年春季發(fā)布 Beta 版 ， 2020 年 9月 5 日發(fā)布正式版 ， 2020 年 4月被分類目錄提供商 looksmart 收購(gòu) 。 Wisenut 也有兩個(gè)出彩的功能 ： 包含類似自動(dòng)分類和相關(guān)檢索詞的 WiseGuide； 預(yù)覽搜索結(jié)果的 SneakaPeek。 (4)Gigablast 由前 Infoseek 工程師 Matt Wells 創(chuàng)立 ， 2020 年 3 月展示 prebeta 版 ， 2020 年 7月 21 日發(fā)布 Beta 版。 Gigablast 的數(shù)據(jù)庫(kù)目前仍偏小 ，但也提供網(wǎng)頁(yè)快照 ， 一個(gè)特色功能是即時(shí)索引網(wǎng)頁(yè) ， 你的網(wǎng)頁(yè)剛提交它就能搜索(注 ： 這個(gè) spammers 的肉包子功能暫已關(guān)閉 )。 (5)Openfind 創(chuàng)立于 1998 年 1月 ， 其技術(shù)源自臺(tái)灣中正大學(xué)吳升教授所領(lǐng)導(dǎo)的 GAIS 實(shí)驗(yàn)室。 Openfind 起先只做中文搜索引擎 ， 曾經(jīng)是最好的中文搜索引擎 ， 鼎盛時(shí)期同時(shí)為三大著名門戶新浪 、 奇摩 、 雅虎提供中文搜索引擎 ， 但 2000 年后市場(chǎng)逐 漸被 Baidu 和 Google 瓜分。 2020 年 6月 ， Openfind 重新發(fā)布基 8 于 GAIS30 Project的 Open2find搜索引擎 Beta版 ， 推出多元排序 (PolyRankTM)，宣布累計(jì)抓取網(wǎng)頁(yè) 35億 ， 開始進(jìn)入英文搜索領(lǐng)域 ， 此后技術(shù)升級(jí)明顯加快。 (6)北大天網(wǎng)是國(guó)家“九五”重點(diǎn)科技攻關(guān)項(xiàng)目“中文編碼和分布式中英文信息發(fā)現(xiàn)”的研究成果 ， 由北大計(jì)算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)研究室開發(fā) ， 于 1997年 10 月 29 日正式在 CERNET 上提供服務(wù)。 2020 年初成立天網(wǎng)搜索引擎新課題組 ， 由國(guó)家 973 重點(diǎn)基礎(chǔ)研究發(fā)展規(guī)劃項(xiàng) 目基金資助開發(fā) ， 收錄網(wǎng)頁(yè)約 6000 萬(wàn) ，利用教育網(wǎng)優(yōu)勢(shì) ， 有強(qiáng)大的 FTP 搜索功能。 (7)2020 年 1 月 ， 兩位北大校友 、 超鏈分析專利發(fā)明人 、 前 Infoseek 資深工程師李彥宏與好友徐勇 (加州伯克利分校博士 )在北京中關(guān)村創(chuàng)立了百度 (Baidu)公司。 2020 年 8 月發(fā)布 搜索引擎 Beta 版 (此前 Baidu 只為其它門戶網(wǎng)站搜狐新浪 Tom 等提供搜索引擎 )， 2020 年 10 月 22 日正式發(fā)布 Baidu 搜索引擎 ， 專注于中文搜索。 Baidu 搜索引擎的其它特色包括 ： 網(wǎng)頁(yè)快照 、 網(wǎng)頁(yè)預(yù)覽/預(yù)覽全部網(wǎng)頁(yè) 、 相關(guān)搜索詞 、 錯(cuò)別 字糾正提示 、 新聞搜索 、 Flash 搜索 、 信息快遞搜索。 2020 年 3月閃電計(jì)劃 (BlitzenProject)開始后 ， 技術(shù)升級(jí)明顯加快。 (8)Northernlight 公司于 1995 年 9 月成立于馬薩諸塞州劍橋 ， 1997 年 8月Northernlight 搜索引擎正式現(xiàn)身。它曾是擁有最大數(shù)據(jù)庫(kù)的搜索引擎之一 ， 它沒(méi)有 StopWords， 它有出色的 CurrentNews、 7100 多出版物組成的 Special Collection、 良好的高級(jí)搜索語(yǔ)法 ， 第一個(gè)支持對(duì)搜索結(jié)果進(jìn)行簡(jiǎn)單的自動(dòng)分類 (注 ：2020 年 1 月 16 日 ， Northernlight 公共搜索引擎關(guān)閉 ， 隨后被 divine 收購(gòu) ， 但在 Nlresearch， 選中“ World Wide Web only” ， 仍可使用 Northernlight 搜索引擎 )。 (9)1995 年 9 月 26 日 ， 加州伯克利分校 CS 助教 EricBrewer、 博士生 PaulGauthier 創(chuàng)立了 Inktomi(UCBerkeleyAnnouncesInktomi)， 1996 年 5月 20 日 ， Inktomi 公司成立 ， 強(qiáng)大的 HotBot 出現(xiàn)在世人面前。聲稱每天能抓取索引 1千萬(wàn)頁(yè)以上 ， 所以有遠(yuǎn)超過(guò)其它搜索引擎的新內(nèi)容。 HotBot 也大量運(yùn)用 cookie 儲(chǔ)存用戶的個(gè)人搜索喜好設(shè)置 (注 ： Hotbot 曾是隨后幾年最受歡迎的搜索引擎之一 ，后被 Lycos 收購(gòu) )。 (10)Google 在 1998 年 10月之前 ， 只是 Stanford 大學(xué)的一個(gè)小項(xiàng)目 BackRub。 1995 年博士生 Larry Page 開始學(xué)習(xí)搜索引擎設(shè)計(jì) ， 于 1997 年 9 月 15 日注 9 冊(cè)了 的域名 ， 1997 年底 ， 在 Sergey Brin 和 Scott Hassan， Alan Steremberg 的共同參與下 ， BachRub 開始提供 Demo。 1999 年 2月 ， Google 完成了從 Alpha 版到 Beta 版的蛻變。 Google 公司則把 1998 年 9 月 27 日認(rèn)作自己的生日。 Google 在 Pagerank、 動(dòng)態(tài)摘要 、 網(wǎng)頁(yè)快照 、 DailyRe2fresh、 多文檔格式支持 、 地圖股票詞典尋人等集成搜索 、 多語(yǔ)言支持 、 用戶界面等功能上的革新 ，象 Altavista 一樣 ， 再一次永遠(yuǎn)改變了搜索引擎的定義。在 2020 年中以前 ， Google 雖然以搜索準(zhǔn)確性備受贊譽(yù) ， 但因?yàn)閿?shù)據(jù)庫(kù)不如其它搜索引擎大 ， 缺乏高級(jí)搜索語(yǔ)法 ， 所以推廣并不快。直到 2020 年中數(shù)據(jù)庫(kù)升級(jí)后 ， 又借被 Yahoo 選作搜索引擎的東風(fēng) ， 才一飛沖天。 搜索引擎存在的問(wèn)題以及挑戰(zhàn) 搜索引擎在飛速發(fā)展的同時(shí)也存在著很多缺陷 ， 需要進(jìn)一步改進(jìn)和完善 ， 筆者對(duì)這些問(wèn)題進(jìn)行了歸納 ， 如下 ： (1)網(wǎng)絡(luò)信息質(zhì)量控制欠缺。任何人只要具備相應(yīng)的條件就可以把任何信息送到網(wǎng)上 ， 800C 這些信息不經(jīng)任何質(zhì)量控制就被搜索引擎標(biāo)引 ， 未經(jīng)質(zhì)量控制的信息必然會(huì)影響搜索結(jié)果的質(zhì)量。 (2)大量占用昂貴的網(wǎng)絡(luò)帶寬和 CPU資源。由于搜索引擎必須將大量資源站點(diǎn)的內(nèi)容傳送至搜索站點(diǎn)本地 ， 然后進(jìn)行分析索引 ， 這樣大規(guī)模的資源文件的傳送和出路無(wú)疑會(huì)