全文搜索引擎技術的研究和實現(編輯修改稿)

　

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